编码理论基础

1. 码的定义

  • 定义一:设 AA 是一个有限集合,称之为字母表AA 中元素构成的有限序列称为。一个字中的元素的个数称为字长。

  • 定义二:设 AA 是一个字母表。AA 上所有字的集合记为 AA^*AA^* 中包含一个长度的零的特殊字,称之为空字,记为 ε\varepsilon。对 AA^* 中的任意两个字 xxyy,将 yy 排在 xx 后面得到 xyxyxyxy 显然还是 AA^* 中的一个字,即运算即为字的拼接运算。显然,AA^* 对拼接运算为带幺半群,单位元为空字 ε\varepsilon

  • 定义三:设 CCAA^* 的一个子集。如果对任意 c1,c2,,cm,c1,,cnCc_1, c_2, \cdots, c_m, c_1^{'}, \cdots, c_n^{'} \in C,当

    c1c2cm=c1c2cnc_1 c_2 \cdots c_m = c_1^{'} c_2^{'} \cdots c_n^{'}

    时,一定有 m=nm = n,并且 ci=ci,1inc_i = c_i^{'}, 1 \leq i \leq n,则称 CC 为字母表 AA 上的一个。码 CC 中的字称为码字。如果码 CC 中的码字长度都相同,则称 CC定长码;否则称其为变长码。如果 A=n|A| = n,则称 CCnn 元码。

在编码理论中,字母表 AA 一般取为有限域 GF(q)GF(q)。设 V(n,q)=GF(q)nV(n, q) = GF(q)^n 表示 GF(q)GF(q) 上的 nn 维向量空间。V(n,q)V(n, q) 中的向量 (x1,x2,,xn)(x_1, x_2, \cdots, x_n) 通常记为 x1,x2,,xnx_1, x_2, \cdots, x_n

  • 定义四V(n,q)V(n, q) 中的任意一个非空子集 CC 称为一个 qq分组码CC 中的每一个向量称为一个码字。如果 C=M|C| = M,则称 CC 是一个 qq(n,M)(n, M) 码,其中 nn 表示码长,MM 表示码字个数。

分组码是定长码,一个 qq(n,M)(n, M) 码的所有码字长度都是 nn。编码理论中主要讨论的就是分组码。

2. 码率的定义

  • 定义五:一个 qq(n,M)(n, M) 码的码率定义为

    R(C)=logqMnR(C) = \frac{\log_q M}{n}

一个 qq(n,M)(n, M) 码有 MM 个码字,可以用于传送 MM 个不同信息中的任意一个。然而,要传送 MM 个信息中的任意一个,码长只需要 logqM\log_q M 就足够了。因此,在一个 qq(n,M)(n, M) 码中,每个码字中的信息位个数为 logqM\log_q M,其余的 nlogqMn - \log_q M 位是冗余位,用于在信道接收端纠正信息在信道传输过程中发生的错误。一个 qq(n,M)(n, M) 码使用 nn 个字符来传送 logqM\log_q M 个信息字符,显然一个好码应该具有较大的码率。

3. 汉明距离

  • 定义六:设 x,yV(n,q)\boldsymbol{x}, \boldsymbol{y} \in V(n, q)x\boldsymbol{x}y\boldsymbol{y}汉明距离 d(x,y)d(\boldsymbol{x}, \boldsymbol{y}) 定义为 x\boldsymbol{x}y\boldsymbol{y} 中不同分量的个数。设 x=x1x2xn\boldsymbol{x} = x_1 x_2 \cdots x_ny=y1y2yn\boldsymbol{y} = y_1 y_2 \cdots y_n。对于 i=1,2,,ni = 1, 2, \cdots, n,定义

    d(xi,yi)={0, if xi=yi1, if xiyid(x_i, y_i) = \begin{cases} 0, \text{ if } x_i = y_i \\ 1, \text{ if } x_i \neq y_i \\ \end{cases}

    显然

    d(x,y)=i=1nd(xi,yi)d(\boldsymbol{x}, \boldsymbol{y}) = \sum_{i=1}^n d(x_i, y_i)

    性质

    显然,汉明距离作为一个距离度量,满足距离度量的三大性质:非负性、对称性以及三角不等式。

    1. 非负性:d(x,y)0d(\boldsymbol{x}, \boldsymbol{y}) \geq 0,且 d(x,y)=0d(\boldsymbol{x}, \boldsymbol{y}) = 0 当且仅当 x=y\boldsymbol{x} = \boldsymbol{y}
    2. 对称性:d(x,y)=d(y,x)d(\boldsymbol{x}, \boldsymbol{y}) = d(\boldsymbol{y}, \boldsymbol{x})
    3. 三角不等式:d(x,y)d(x,z)+d(y,z)d(\boldsymbol{x}, \boldsymbol{y}) \leq d(\boldsymbol{x}, \boldsymbol{z}) + d(\boldsymbol{y}, \boldsymbol{z})
  • 定义七:设 CC 是一个 (n,M)(n, M) 码。码 CC最小距离定义为 CC 中的任意两个不同的码字的汉明距离的最小值,记为 d(C)d(C),即

    d(C)=min{d(x,y)x,yC,xy}d(C) = \min\{d(\boldsymbol{x}, \boldsymbol{y}) | \boldsymbol{x}, \boldsymbol{y} \in C, \boldsymbol{x} \neq \boldsymbol{y}\}

  • 定义八:设 xV(n,q)\boldsymbol{x} \in V(n, q)x\boldsymbol{x} 中非零分量的个数称为汉明重量,记为 W(x)W(\boldsymbol{x})。设 x=x1x2xn\boldsymbol{x} = x_1 x_2 \cdots x _n,对于 i=1,2,,ni = 1, 2, \cdots, n,定义

    W(xi)={0, if xi=01, if xi0W(x_i) = \begin{cases} 0, \text{ if } x_i = 0 \\ 1, \text{ if } x_i \neq 0 \\ \end{cases}

    显然

    W(x)=i=1nW(xi)W(\boldsymbol{x}) = \sum_{i=1}^n W(x_i)

    性质

    1. 对任意 x,yV(n,q)\boldsymbol{x}, \boldsymbol{y} \in V(n, q)d(x,y)=W(xy)d(\boldsymbol{x}, \boldsymbol{y}) = W(\boldsymbol{x} - \boldsymbol{y})。特别地,对任意 u,vV(n,2)\boldsymbol{u}, \boldsymbol{v} \in V(n, 2)d(u,v)=W(u+v)d(\boldsymbol{u}, \boldsymbol{v}) = W(\boldsymbol{u} + \boldsymbol{v})
    2. 对任意 xV(n,q)\boldsymbol{x} \in V(n, q)W(x)0W(\boldsymbol{x}) \geq 0W(x)=0W(\boldsymbol{x}) = 0 的充分必要条件为 x=0\boldsymbol{x} = \boldsymbol{0}
    3. 对任意 x,yV(n,q)\boldsymbol{x}, \boldsymbol{y} \in V(n, q)W(x+y)W(x)+W(y)W(\boldsymbol{x} + \boldsymbol{y}) \leq W(\boldsymbol{x}) + W(\boldsymbol{y})
  • 定义九:码 CV(n,q)C \subseteq V(n, q)最小重量定义为 CC 中所有非零码字的最小重量,记为 W(C)W(C),即

    W(C)=min{W(x)xC,x0}W(C) = \min\{W(\boldsymbol{x}) | \boldsymbol{x} \in C, \boldsymbol{x} \neq \boldsymbol{0}\}

4. 最近邻译码

  • 定义十:设 x\boldsymbol{x} 是一个码字,经过信道传输后,在接收端我们收到的向量为 y\boldsymbol{y}。由于噪声的干扰,可能 yx\boldsymbol{y} \neq \boldsymbol{x},并且 y\boldsymbol{y} 可能不是一个码字。将 y\boldsymbol{y} 译为与 y\boldsymbol{y} 汉明距离最小的码字 x\boldsymbol{x}^{'} 是合理的。这种译码策略称为最近邻译码
  • 定义十一:满足下述两个条件的信道称为 qq 元对称信道:
    1. 每个字符在传输过程中发生错误的概率相同,都为 pp
    2. 如果一个字符在传输过程中发生了错误,则它错为其它 q1q-1 个字符中的任意一个的概率都是相同的。

一般地,对于 qq 元对称信道而言,最近邻译码就是最大似然译码。

5. 检错和纠错

码的最小距离是刻画码的检错和纠错性能的一个重要参数。一般用 (n,M,d)(n, M, d) 表示码长为 nn,码字个数为 MM,最小距离为 dd 的一个码。

  • 定理一:码 CC 至多可以检查 tt 个错误的充分必要条件为 d(C)=t+1d(C) = t+1
  • 定理二:码 CC 至多可以纠正 tt 个错误的充分必要条件为 d(C)=2t+1d(C) = 2t + 12t+22t + 2

因此,设 CC 是一个码,其最小距离为 dd,则码 CC 至多可以检查 d1d - 1 个错误,至多纠正 d12\lfloor \frac{d-1}{2} \rfloor 个错误。

6. 编码理论的基本问题

一个好的 qq(n,M,d)(n, M, d) 码应具有如下性质:

  1. 为了更快的发送信息,码长 nn 应该小;
  2. 为了更多的发送信息,码字个数 MM 应该大;
  3. 为了能纠正更多的错误,最小距离 dd 应该大。

7. 完备码

  • 定义十二:对任意 xV(n,q)\boldsymbol{x} \in V(n, q) 以及整数 r0r \geq 0,以 x\boldsymbol{x} 为中心 rr 为半径的球记为 Sq(x,r)S_q(\boldsymbol{x}, r) 定义为

    Sq(x,r)={yV(n,q)d(x,y)r}S_q(\boldsymbol{x}, r) = \{\boldsymbol{y} \in V(n, q) | d(\boldsymbol{x}, \boldsymbol{y}) \leq r\}

  • 定理三:对任意 xV(n,q)\boldsymbol{x} \in V(n, q),球 Sq(x,r)S_q(\boldsymbol{x}, r) 中包含的向量个数为

    (n0)+(n1)(q1)++(nr)(q1)r\binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{r} (q - 1)^r

  • 定理四(汉明界):对任意一个 qq(n,M,2t+1)(n, M, 2t+1)CC,都满足

    M{(n0)+(n1)(q1)++(nt)(q1)t}qnM\left\{ \binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{t} (q - 1)^t \right\} \leq q^n

    Mqni=0t(ni)(q1)iM \leq \frac{q^n}{\sum_{i=0}^t \binom{n}{i} (q-1)^i}

  • 定义十三:设 CC 是一个 qq(n,M,2t+1)(n, M, 2t+1) 码,如果汉明界等号成立,即

    M{(n0)+(n1)(q1)++(nt)(q1)t}=qnM\left\{ \binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{t} (q - 1)^t \right\} = q^n

    则称 CC完备码

8. 系统码

在代数编码理论中,通常取 M=qkM = q^k。一个 qq(n,qk)(n, q^k) 码可以对 V(k,q)V(k, q) 中的全体向量进行编码。

  • 定义十四:设 CC 是一个 qq(n,qk)(n, q^k) 码。如果存在 kk 个分量位置 i1,i2,,iki_1, i_2, \cdots, i_k,使得去掉码 CC 中所有码字的其它 nkn - k 个分量后,所得到的向量全体为 V(k,q)V(k, q),则称码 CC 为具有 kk 个信息位的 qq系统码。分量位置 i1,i2,,iki_1, i_2, \cdots, i_k 称为信息位,其余 nkn - k 个分量位置称为校验位

    在系统码中,信息位和校验位是截然分开的。但在非系统码中,信息位和校验位无法截然分开。校验位就是冗余位,用于在信道的接收端纠正码字在信道传输过程中发生的错误。

9. 新码的构造

我们可以利用一个已知的码来构造新码:

9.1 延长码

将一个码中每个码字都增加一个或多个分量,称为码的延长。最常用的码的延长方法是对每个码字都增加一个奇偶校验位。

  • 定义十五:设 CV(n,q)C \subseteq V(n, q) 是一个 qq(n,M,d)(n, M, d) 码,定义

    C^={x1x2xnxn+1V(n+1,q)x1x2xnC,i=1n+1xi=0}\hat{C} = \{x_1 x_2 \cdots x_n x_{n+1} \in V(n+1, q) | x_1 x_2 \cdots x_n \in C, \sum_{i=1}^{n+1} x_i = 0\}

    C^\hat{C} 为码 CC延长码。码字中的第 n+1n+1 个分量 xn+1x_{n+1} 称为奇偶校验位。显然 C^\hat{C} 是一个 qq(n+1,M,d)(n+1, M, d^{'}) 码,其中 d=dd^{'} = dd+1d+1

9.2 截短码

码的截短是码的延长的逆过程。将一个码中的每个码字都删去一个或多个分量,称为码的截短

  • 定义十六:设 CV(n,q)C \subseteq V(n, q) 是一个 qq(n,M,d)(n, M, d) 码,其中 d2d \geq 2,则将码 CC 中的每个码字都删去第 ii 个分量后,就得到一个 qq(n1,M,d)(n-1, M, d^{'}) 码,其中 d=dd^{'} = dd1d-1

9.3 扩张码

对一个码增加一个或多个码字后所得到的码称为扩张码

9.4 删除码

从一个码中去掉一个或多个码字后所得到的码称为删除码

9.5 加长码

  • 定义十七:设 CV(n,q)C \subseteq V(n, q) 是一个 qq(n,M,d)(n, M, d) 码。对 s=0,1,2,,q1s = 0, 1, 2, \cdots, q-1,令

    Cs={x1x2xnxn+1V(n+1,q)x1x2xnC,xn+1=s}C_s = \{x_1 x_2 \cdots x_n x_{n+1} \in V(n+1, q) | x_1 x_2 \cdots x_n \in C, x_{n+1} = s\}

    C0C1Cq1C_0 \cup C_1 \cup \cdots \cup C_{q-1} 为码 CC 的加长码。

9.6 缩小码

  • 定义十八:设 CV(n,q)C \subseteq V(n, q) 是一个 qq(n,M,d)(n, M, d) 码。由 CC 中第 ii 个分量都是 ss 的所有码字组成的码记为 Ci,sC_{i, s},其中 1in,sGF(q)1 \leq i \leq n, s \in GF(q)。将 Ci,sC_{i, s} 中每个码字的第 ii 个分量去掉后得到的码称为码 CC 的缩小码。

10. 码的等价变换

  • 定义十九:关于 qq(n,M)(n, M) 码有两种置换。一种是关于码字分量位置集合的置换,称为换位型置换,记为 σ1\sigma_1

    σ1=(12nσ1(1)σ1(2)σ1(n))\sigma_1 = \left( \begin{matrix} 1 & 2 & \cdots & n \\ \downarrow & \downarrow & \cdots & \downarrow \\ \sigma_1(1) & \sigma_1(2) & \cdots & \sigma_1(n) \end{matrix} \right)

    另一种是关于字母表 A=GF(q)={0,1,,q1}A = GF(q) = \{0, 1, \cdots, q-1\} 的置换,称为换元型置换,记为 σ2\sigma_2

    σ2=(12nσ2(1)σ2(2)σ2(n))\sigma_2 = \left( \begin{matrix} 1 & 2 & \cdots & n \\ \downarrow & \downarrow & \cdots & \downarrow \\ \sigma_2(1) & \sigma_2(2) & \cdots & \sigma_2(n) \end{matrix} \right)

  • 定义二十:两个 qq(n,M)(n, M) 码是等价的,如果能够通过一系列下述两种变换将其中一个码变为另一个码:

    1. 换位型置换:将码的坐标位置进行置换;
    2. 换元型置换:将出现在某一个固定坐标位置上的字符进行置换。

附录

  • 《编码理论基础》by 陈鲁生

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!