线性码

1. 简介

线性码是一类非常重要的分组码，是讨论各种码的基础。线性码的编码方案和译码方案都非常简单。许多特殊的线性码都具有非常好的性质，绝大多数的已知好码都是线性码。

2. 线性码

  • 定义一：如果 C⊆V(n,q)C \subseteq V(n, q) 是 V(n,q)V(n, q) 的一个子空间，则称 CC 为一个 qq 元线性码。如果 CC 是 V(n,q)V(n, q) 的一个 kk 维子空间，则称 CC 为一个 qq 元 [n,k][n, k] 线性码。进一步，如果 CC 的最小距离是 dd，则称 CC 为一个 qq 元 [n,k,d][n, k, d] 线性码。

性质

显然，C⊆V(n,q)C \subseteq V(n, q) 是一个线性码当且仅当

  1. 对任意 x,y∈C\boldsymbol{x}, \boldsymbol{y} \in C，都有 x+y∈C\boldsymbol{x} + \boldsymbol{y} \in C；
  2. 对任意 x∈C\boldsymbol{x} \in C 和任意 a∈GF(q)a \in GF(q)，都有 ax∈Ca \boldsymbol{x} \in C。

特别地，一个二元码 C∈V(n,2)C \in V(n, 2) 是线性码当且仅当对任意 x,y∈C\boldsymbol{x}, \boldsymbol{y} \in C，都有 x+y∈C\boldsymbol{x} + \boldsymbol{y} \in C。

3. 生成矩阵

  • 定义二：设 CC 是一个 qq 元 [n,k][n, k] 线性码，将 CC 的一组基作为行向量构成一个 k×nk \times n 阶矩阵 G\boldsymbol{G}。G\boldsymbol{G} 称为线性码 CC 的生成矩阵。

  • 定理一：设 G1\boldsymbol{G}_1 和 G2\boldsymbol{G_2} 是 GF(q)GF(q) 上的两个 k×nk \times n 阶矩阵，并且 Rank(G1)=Rank(G2)=k\mathrm{Rank}(\boldsymbol{G}_1) = \mathrm{Rank}(\boldsymbol{G}_2) = k。如果可以通过一系列下述变换将 G1\boldsymbol{G}_1 化成 G2\boldsymbol{G}_2，则 G1\boldsymbol{G}_1 和 G2\boldsymbol{G}_2 生成的 qq 元 [n,k][n, k] 线性码一定是等价的。

    （R1）重新排列行向量；

    （R2）将某一行乘以一个非零元素；

    （R3）将某一行乘以一个非零元素，然后加到另一行；

    （C1）重新排列列向量；

    （C2）将某一列乘以一个非零元素。

    行变换（R1）、（R2）和（R3）保持了生成矩阵中行向量的线性无关性，这三种行变换只不过是将同一个对性码的一组基换成了另外一组基。

    列变换（C1）、（C2）是将一个线性码的生成矩阵变换成了与其等价的线性码的生成矩阵。

4. 编码方法

设 CC 是一个 qq 元线性码，GG 为其生成矩阵。CC 中的每个码字是 GG 的行向量的线性组合，即

C={uG∣u∈V(r,q)}C = \{\boldsymbol{u} \boldsymbol{G} | \boldsymbol{u} \in V(r, q)\}

由于 CC 中有 qkq^k 个码字，故线性码可以用来传输 qkq^k 个不同信源中的任意一个。因此，线性码的编码方法为：假设信源信息由 V(k,q)V(k, q) 中的向量来表示，则对任意信源信息向量 u∈V(k,q)\boldsymbol{u} \in V(k, q)，u\boldsymbol{u} 编码为 CC 中的码字 uG\boldsymbol{u}\boldsymbol{G}。

5. 标准阵译码方法

  • 定义三：设 CC 是一个 qq 元 [n,k][n, k] 线性码，a∈V(n,q)\boldsymbol{a} \in V(n, q)。定义

    a+C≜{a+x∣x∈C}\boldsymbol{a} + C \triangleq \{\boldsymbol{a} + \boldsymbol{x} | \boldsymbol{x} \in C\}

    称为 CC 的一个陪集。

  • 定义四：设 CC 是一个 qq 元 [n,k][n, k] 线性码。在 CC 的一个陪集中，重量最小的向量称为陪集代表元。

    陪集代表元可能不是唯一的。

  • 定理二：设 CC 是一个 qq 元 [n,k][n, k] 线性码，则

    1. V(n,q)V(n, q) 中的每个向量都在 CC 的某个陪集中；
    2. CC 的每个陪集中都恰好含有 qkq^k 个向量；
    3. CC 的任意两个陪集或者相等或者不相交。

    因此，nn 维向量空间 V(n,q)V(n, q) 被划分成了 CC 的 qn−kq^{n-k} 个不相交的陪集，即

    V(n,q)=(0+C)∪(a1+C)∪⋯∪(as+C)V(n, q) = (\boldsymbol{0} + C) \cup (\boldsymbol{a}_1 + C) \cup \cdots \cup (\boldsymbol{a}_s + C)

    其中 s=qn−k−1s = q^{n-k} - 1，0,a1,⋯ ,as\boldsymbol{0}, \boldsymbol{a}_1, \cdots, \boldsymbol{a}_s 可以选为陪集代表元。

对于线性码的译码，可以使用标准阵译码方法。一个 qq 元 [n,k][n, k] 线性码 CC 的标准阵是由 V(n,q)V(n, q) 中的向量组成的一个 qn−k×qkq^{n-k} \times q^k 阶阵列，其每一行都是 CC 的一个陪集。第一行由 CC 中的码字构成，0\boldsymbol{0} 码字在最左端，其它各行由陪集 ai+C\boldsymbol{a}_i + C 构成，陪集代表元在最左端，其它元素的排列次序与第一行中码字的排列次序相对应。即标准阵中的 (i,j)(i, j) 位置上的向量是第 jj 列最顶端的码字与第 ii 行最左端的陪集代表元的加和。

标准阵构造方法

一个 qq 元 [n,k][n, k] 线性码 CC 的标准阵可以按下述方法来构造：

  1. 首先列出 CC 中的所有码字，0\boldsymbol{0} 码字在最左端；
  2. 在 V(n,q)V(n, q) 中选取一个不在第一行出现并且具有最小重量的向量 a1\boldsymbol{a}_1，将 a1\boldsymbol{a}_1 与第一行中的每个码字相加得到第二行，它们构成陪集 a1+C\boldsymbol{a}_1 + C；
  3. 一般地，在 V(n,q)V(n, q) 中选取一个不在前 ii 行中出现并且具有最小重量的向量 ai\boldsymbol{a}_i，将 ai\boldsymbol{a}_i 与第一行中的每个码字相加得到第 i+1i+1 行，它们构成陪集 ai+C\boldsymbol{a}_i + C。
  4. 继续上述过程，直到将 V(n,q)V(n, q) 中所有向量都列出为止。

标准阵译码方法

设 CC 是一个 qq 元 [n,k,d][n, k, d] 线性码，x∈C\boldsymbol{x} \in C 是在信道发送端发送的码字，y∈V(n,q)\boldsymbol{y} \in V(n, q) 是在信道接收端接收到的向量。称 e=y−x\boldsymbol{e} = \boldsymbol{y} - \boldsymbol{x} 为差错向量。译码器的作用就是确定差错向量，然后纠正码字在信道传输过程中发生的错误。线性码的标准阵译码方法描述如下：

设 y\boldsymbol{y} 是在信道接收端接收到的向量。在标准阵中找到 y\boldsymbol{y} 所在的行和列，将 y\boldsymbol{y} 译为 y\boldsymbol{y} 所在的列中最顶端的码字，y\boldsymbol{y} 所在行的最左端的向量为差错向量。

对于一个 [n,k,2t+1][n, k, 2t+1] 或 [n,k,2t+2][n, k, 2t+2] 线性码 CC，如果按照陪集代表元的重量从小到大的顺序对 CC 的标准阵中的陪集进行排序，则可以将 CC 标准阵分为上下两部分。上半部分的陪集代表元的重量都不大于 tt，下半部分的陪集代表元的重量都大于 tt。当在信道接收端接收到的向量 y\boldsymbol{y} 位于标准阵的上半部分时，则可以认为发生的错误不大于 tt（当然实际也有可能大于 tt），此时按照正常的标准阵译码方法进行译码；当信道接收端收到的向量 y\boldsymbol{y} 位于标准阵的下半部分时，则发生的错误一定大于 tt，此时可以考虑请求信道发送端重新发送码字。

这种只有当接收到的向量 y\boldsymbol{y} 位于标准阵上半部分时才进行译码的做法称为不完全译码，完全译码则是不管接收到的向量 y\boldsymbol{y} 位于标准阵的上半部分还是下半部分，都进行译码。

完备码的标准阵中，所有陪集代表元重量都不大于 tt。

6. 译码分析

为简单起见，以二元线性码为例，假设信道为二元对称信道，一个字符在信道传输过程中发生错误的概率为 pp。

6.1 译码错误概率

令 Pcorr(C)P_{\mathrm{corr}}(C) 表示利用标准阵译码方法将一个接收到的向量正确译码的概率。设 αi\alpha_i 为线性码 CC 的标准阵中重量为 ii 的陪集代表元的数目，0≤i≤n0 \leq i \leq n。当发送的一个码字在信道传输过程中发生的差错向量恰好为一个陪集代表元时，利用标准阵译码方法一定可以正确译码，故显然有

Pcorr(C)=∑i=0nαipi(1−p)n−iP_{\mathrm{corr}}(C) = \sum_{i=0}^n \alpha_i p^i (1-p)^{n-i}

所谓译码错误，即利用标准阵译码方法将一个接收向量译成的码字不是在信道发送端发送的码字。用 Perr(C)P_{\mathrm{err}}(C) 表示译码错误概率，则显然有

Perr(C)=1−Pcorr(C)=1−∑i=0nαipi(1−p)n−iP_{\mathrm{err}}(C) = 1 - P_{\mathrm{corr}}(C) = 1 - \sum_{i=0}^n \alpha_i p^i (1-p)^{n-i}

6.2 不可检错误概率

所谓不可检错误，即一个码字在信道传输过程中发生了错误，而在信道接收端的译码器却检查不出来。用 Pundetec(C)P_{\mathrm{undetec}}(C) 表示不可检错误概率。显然，译码器检查不出一个码字 x\boldsymbol{x} 在信道传输过程中所发生的错误当且仅当接收到的向量 y\boldsymbol{y} 是一个与 x\boldsymbol{x} 不同的码字，即当且仅当差错向量 e=y−x\boldsymbol{e} = \boldsymbol{y} - \boldsymbol{x} 是一个非零码字。

  • 定理三：设 CC 是一个二元 [n,k][n, k] 线性码，AiA_i 是 CC 中重量为 ii 的码字的数目，0≤i≤n0 \leq i \leq n。如果码 CC 用于检错，则发生不可检错误的概率为

    Pundetec(C)=∑i=1nAipi(1−p)n−iP_{\mathrm{undetec}}(C) = \sum_{i=1}^n A_i p^i (1-p)^{n-i}

7. 对偶码

  • 定义五：设 CC 是一个 qq 元 [n,k][n, k] 线性码，定义

    C⊥≜={x∈V(n,q)∣∀a∈C,x⋅a=0}C^\bot \triangleq = \{ \boldsymbol{x} \in V(n, q) | \forall \boldsymbol{a} \in C, \boldsymbol{x} \cdot \boldsymbol{a} = 0 \}

    称为 CC 的对偶码，其中，⋅\cdot 表示向量的内积。换句话，CC 的对偶码 C⊥C^\bot 定义为 V(n,q)V(n, q) 中与 CC 的所有码字都正交的向量集合。

  • 定理四：设 CC 是一个 qq 元 [n,k][n, k] 线性码：

    1. 如果 G\boldsymbol{G} 是线性码 CC 的生成矩阵，则

      C⊥={x∈V(n,q)∣xG⊤=0}C^\bot = \{\boldsymbol{x} \in V(n, q) | \boldsymbol{x} \boldsymbol{G}^\top = \boldsymbol{0} \}

      这里 G⊤\boldsymbol{G}^\top 表示生成矩阵 G\boldsymbol{G} 转置；

    2. CC 的对偶码 C⊥C^\bot 是一个 qq 元 [n,n−k][n, n-k] 线性码；

    3. (C⊥)⊥=C(C^\bot)^\bot = C。

8. 校验矩阵

  • 定义六：设 CC 是一个 qq 元 [n,k][n, k] 线性码，对偶码 C⊥C^\bot 的生成矩阵 H\boldsymbol{H} 称为线性码 CC 的校验矩阵。

一个 qq 元 [n,k][n, k] 线性码 CC 的对偶码 C⊥C^\bot 的基不惟一，所以 CC 的校验矩阵也不惟一。但校验矩阵的秩是惟一的，等于 n−kn - k。校验矩阵是一个 (n−k)×n(n - k) \times n 阶矩阵。此外，根据定理四，可以得到 x∈C\boldsymbol{x} \in C 的充分必要条件是 xH⊤=0\boldsymbol{x} \boldsymbol{H}^\top = \boldsymbol{0}，即

C={x∈V(n,q)∣xH⊤=0}C = \{ \boldsymbol{x} \in V(n, q) | \boldsymbol{x} \boldsymbol{H}^\top = \boldsymbol{0} \}

  • 定理五：对于一个 qq 元 [n,k][n, k] 线性码 CC，如果其生成矩阵为标准型

    G=(Ik∣A)\boldsymbol{G} = (\boldsymbol{I}_k | \boldsymbol{A})

    则其校验矩阵为

    H=(−A⊤∣In−k)\boldsymbol{H} = (-\boldsymbol{A}^\top | \boldsymbol{I}_{n-k})

  • 定理六：设 CC 是一个 qq 元 [n,k][n, k] 线性码，其校验矩阵为 H\boldsymbol{H}，则 d(C)=dd(C) = d 的充分必要条件是 H\boldsymbol{H} 的任意 d−1d-1 列线性无关，并且存在 dd 列线性相关。

9. MDS 码

  • 定理七：设 CC 是一个 qq 元 [n,k,d][n, k, d] 线性码，则 d≤n−k+1d \leq n - k + 1。

  • 定义七：对于一个 qq 元 [n,k,d][n, k, d] 线性码，如果 d=n−k+1d = n - k + 1，则称 CC 为最大距离可分码，简称 MDS 码。

    对于一个 qq 元 [n,k,d][n, k, d] 线性码 CC ，n−kn - k 称为其冗余度。

10. 伴随式译码方法

  • 定义八：设 CC 是一个 qq 元 [n,k][n, k] 线性码，其校验矩阵为 H\boldsymbol{H}。对任意 y∈V(n,q)\boldsymbol{y} \in V(n, q)，称 yH⊤\boldsymbol{y}\boldsymbol{H}^\top 为 y\boldsymbol{y} 的伴随，记为 S(y)S(\boldsymbol{y})。
  • 定理八：设 CC 是一个 qq 元 [n,k][n, k] 线性码，其校验矩阵为 H\boldsymbol{H}。对任意 x,y∈V(n,q)\boldsymbol{x}, \boldsymbol{y} \in V(n, q)，x\boldsymbol{x} 和 y\boldsymbol{y} 属于 CC 的同一个陪集的充分必要条件是它们的伴随式相同。

伴随式译码方法

由定理八可以看出，一个 qq 元 [n,k][n, k] 线性码 CC 的所有不同陪集与 V(n,q)V(n, q) 中向量的所有不同伴随之间存在着一个一一对应关系。列出线性码 CC 的所有陪集代表元，并计算相应的伴随，将每个陪集代表元和相应的伴随排成一行，即得到一个伴随式列表。一个 qq 元 [n,k][n, k] 线性码 CC 的伴随式译码方法描述如下：

  1. 设 y\boldsymbol{y} 是在信道接收端接收到的向量，计算 y\boldsymbol{y} 的伴随 S(y)S(\boldsymbol{y})；
  2. 在伴随式列表中找到 S(y)S(\boldsymbol{y}) 所对应的陪集代表元 a\boldsymbol{a}；
  3. 将 y\boldsymbol{y} 译为码字 y−a\boldsymbol{y} - \boldsymbol{a}。

伴随式译码方案是标准阵译码方案的改进，它不需要存储标准阵，只需要存储陪集代表元和相应的伴随即可，既节省了大量存储空间，又提高了译码效率。

11. 构造新线性码

除了在编码理论基础中提到的几种由已知码构造新码的简单方法外，对于线性码还有几种方法。

11.1 直和

设 C1C_1 是一个 qq 元 [n,k1,d1][n, k_1, d_1] 线性码，其生成矩阵为 G1\boldsymbol{G}_1；C2C_2 是一个 qq 元 [n,k2,d2][n, k_2, d_2] 线性码，其生成矩阵为 G2\boldsymbol{G}_2。假设 C1∩C2={0}C_1 \cap C_2 = \{\boldsymbol{0}\}，定义

C1⊕C2={x+y∣x∈C1,y∈C2}C_1 \oplus C_2 = \{ \boldsymbol{x} + \boldsymbol{y} | \boldsymbol{x} \in C_1, \boldsymbol{y} \in C_2 \}

称 C1⊕C2C_1 \oplus C_2 为 C1C_1 与 C2C_2 的直和。不难看出，C1⊕C2C_1 \oplus C_2 是一个 qq 元 [n,k1+k2,d][n, k_1 + k_2, d] 的线性码，其中 d≤min⁡{d1,d2}d \leq \min\{d_1, d_2\}。C1⊕C2C_1 \oplus C_2 的生成矩阵为

G=(G1G2)\boldsymbol{G} = \left( \begin{matrix} \boldsymbol{G}_1 \\ \boldsymbol{G}_2 \\ \end{matrix} \right)

11. 2 Cartesian 积

设 C1C_1 是一个 qq 元 [n1,k1,d1][n_1, k_1, d_1] 线性码，其生成矩阵为 G1\boldsymbol{G}_1；C2C_2 是一个 qq 元 [n2,k2,d2][n_2, k_2, d_2] 线性码，其生成矩阵为 G2\boldsymbol{G}_2。定义

C1×C2={(x,y)∣x∈C1,y∈C2}C_1 \times C_2 = \{ (\boldsymbol{x}, \boldsymbol{y}) | \boldsymbol{x} \in C_1, \boldsymbol{y} \in C_2 \}

称 C1×C2C_1 \times C_2 为 C1C_1 与 C2C_2 的 Cartesian 积。不难看出，C1×C2C_1 \times C_2 是一个 qq 元 [n1+n2,k1+k2,d][n_1 + n_2, k_1 + k_2, d] 的线性码，其中 d=min⁡{d1,d2}d = \min\{d_1, d_2\}。C1×C2C_1 \times C_2 的生成矩阵为

G=(G10102G2)\boldsymbol{G} = \left( \begin{matrix} \boldsymbol{G}_1 & \boldsymbol{0}_1 \\ \boldsymbol{0}_2 & \boldsymbol{G}_2 \\ \end{matrix} \right)

11.3 Kronecker 积

设 C1C_1 是一个 qq 元 [n1,k1,d1][n_1, k_1, d_1] 线性码，其生成矩阵为 G1=(gij(1))k1×n1\boldsymbol{G}_1 = (g_{ij}^{(1)})_{k_1 \times n_1}；C2C_2 是一个 qq 元 [n2,k2,d2][n_2, k_2, d_2] 线性码，其生成矩阵为 G2=(gij(2))k2×n2\boldsymbol{G}_2 = (g_{ij}^{(2)})_{k_2 \times n_2}。由生成矩阵

G=G1⊗G2=(g11(1)G2⋯g1n1(1)G2⋮⋱⋮gk11(1)G2⋯gk1n1(1)G2)\boldsymbol{G} = \boldsymbol{G}_1 \otimes \boldsymbol{G}_2 = \left( \begin{matrix} g_{11}^{(1)} \boldsymbol{G}_2 & \cdots & g_{1n_1}^{(1)} \boldsymbol{G}_2 \\ \vdots & \ddots & \vdots \\ g_{k_1 1}^{(1)} \boldsymbol{G}_2 & \cdots & g_{k_1 n_1}^{(1)} \boldsymbol{G}_2 \end{matrix} \right)

生成的线性码称为 C1C_1 与 C2C_2 的 Kronecher 积，记为 C1⊗C2C_1 \otimes C_2。不难证明，C1⊗C2C_1 \otimes C_2 是一个 qq 元 [n1n2,k1k2,d1d2][n_1n_2, k_1k_2, d_1d_2] 线性码。

附录

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