1. 简介

汉明码是一种完备的线性码，具有很多很好的性质，而且其译码方法也非常简洁高效。

2. 汉明码

2.1 二元汉明码

  • 定义一：设 rr 是一个正整数，设 H\boldsymbol{H} 是一个 r×(2r−1)r \times (2^r - 1) 阶矩阵，其列向量由 V(r,2)V(r, 2) 中的所有不同的非零向量组成。以 H\boldsymbol{H} 为校验矩阵的线性码称为二元汉明码，记为 Ham(r,2)\mathrm{Ham}(r, 2)。

    显然，二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的码长为 n=2r−1n = 2^r - 1，维数为 k=n−r=2r−1−rk = n - r = 2^r - 1 - r，rr 为校验位的数目。在等价意义下，Ham(r,2)\mathrm{Ham}(r, 2) 是惟一的。

2.2 多元汉明码

  • 定义二：设 rr 是一个正整数，对任意 α∈V(r,q)\boldsymbol{\alpha} \in V(r, q)，令 Vα={λα∣0≠λ∈GF(q)}V_{\boldsymbol{\alpha}} = \{\lambda \boldsymbol{\alpha} | 0 \neq \lambda \in GF(q)\}。不难发现，对任意 α,β∈V(r,q)\boldsymbol{\alpha}, \boldsymbol{\beta} \in V(r, q)，VαV_{\boldsymbol{\alpha}} 与 VβV_{\boldsymbol{\beta}} 或者相同或者不相交。显然，当 α=0\boldsymbol{\alpha} = 0 时，∣Vα∣=1|V_{\boldsymbol{\alpha}}| = 1；当 α≠0\boldsymbol{\alpha} \neq 0 时，∣Vα∣=q−1|V_{\boldsymbol{\alpha}}| = q - 1。因此，存在非零的 α1,α2,⋯ ,αn∈V(r,q)\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2 , \cdots, \boldsymbol{\alpha}_n \in V(r, q)，其中 n=qr−1q−1n = \frac{q^r - 1}{q - 1}，使得 Vα1,Vα2,⋯ ,VαnV_{\boldsymbol{\alpha}_1}, V_{\boldsymbol{\alpha}_2}, \cdots, V_{\boldsymbol{\alpha}_n} 互不相交，并且

    ⋃i=1nVαi=V(r,q)−{0}\bigcup_{i=1}^n V_{\boldsymbol{\alpha}_i} = V(r, q) - \{\boldsymbol{0}\}

    分别从 Vα1,Vα2,⋯ ,VαnV_{\boldsymbol{\alpha}_1}, V_{\boldsymbol{\alpha}_2}, \cdots, V_{\boldsymbol{\alpha}_n} 中任取一个向量作为列向量构成一个 r×nr \times n 阶的矩阵 H\boldsymbol{H}。以 H\boldsymbol{H} 为校验矩阵的线性码称为 qq 元汉明码，记为 Ham(r,q)\mathrm{Ham}(r, q)。

    qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 的码长为 n=qr−1q−1n = \frac{q^r - 1}{q-1}，维数为 k=n−r=qr−1q−1−rk = n - r = \frac{q^r - 1}{q - 1} - r，rr 为校验位的数目。对于给定的 rr 和 qq，由于 H\boldsymbol{H} 中的列向量可以任意排列，并且 VαiV_{\boldsymbol{\alpha}_i} 中的向量可以任意选取，1≤i≤n1 \leq i \leq n，所以 qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 指的是一类等价的码中的任意一个。在等价意义下，Ham(r,q)\mathrm{Ham}(r, q) 是惟一的。

不难看出，对任意 0≠α∈V(r,q)0 \neq \boldsymbol{\alpha} \in V(r, q)，VαV_{\boldsymbol{\alpha}} 中恰好有一个向量，其第一个非零分量为 11。因此，一种写出 Ham(r,q)\mathrm{Ham}(r, q) 的校验矩阵的简单方法就是：按字典排序写出 V(r,q)V(r, q) 中所有第一个非零分量为 11 的非零向量。

3. 性质

  • 定理一：qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 是一个完备的 qq 元 [n,n−r,3][n, n-r, 3] 线性码，其中 n=qr−1q−1n = \frac{q^r - 1}{q - 1}。

  • 定理二：设 r≥2r \geq 2 是一个整数，qq 是一个素数的幂次方。如果 n=qr−1q−1n = \frac{q^r - 1}{q - 1}，则 Aq(n,3)=qn−rA_q(n, 3) = q^{n-r}。

    Aq(n,d)A_q(n, d) 表示在所有 qq 元 (n,M,d)(n, M, d) 码中，MM 的最大值。

4. 译码方法

由于 Ham(r,q)\mathrm{Ham}(r, q) 是一个完备的 qq 元 [n,n−r,3][n, n-r, 3] 线性码，其中 n=qr−1q−1n = \frac{q^r - 1}{q-1}，Ham(r,q)\mathrm{Ham}(r, q) 至多可以纠正一个错误，所以 V(n,q)V(n, q) 中所有重量不大于 11 的向量恰好就是 Ham(r,q)\mathrm{Ham}(r, q) 的标准阵中的所有陪集代表元。

qq 元汉明码 Ham(r,q)\mathrm{Ham}(r, q) 的译码过程描述如下：

  1. 对于在信道接收端接收到的向量 y\boldsymbol{y}，计算其伴随 S(y)=yH⊤S(\boldsymbol{y}) = \boldsymbol{y} \boldsymbol{H}^\top；

  2. 如果 S(y)=0S(\boldsymbol{y}) = \boldsymbol{0}，则认为没有错误发生，y\boldsymbol{y} 就是发送的码字；

  3. 如果 S(y)≠0S(\boldsymbol{y}) \neq \boldsymbol{0}，则 S(y)=bHi⊤≠0S(\boldsymbol{y}) = b\boldsymbol{H}_i^\top \neq \boldsymbol{0}，其中 0≠b∈GF(q),1≤i≤n0 \neq b \in GF(q), 1 \leq i \leq n。此时，y\boldsymbol{y} 中第 ii 个分量发生错误，y\boldsymbol{y} 被译为码字 y−αi\boldsymbol{y} - \boldsymbol{\alpha}_i，其中

    αi=0⋯0⏟i−1b0⋯0⏞n\boldsymbol{\alpha}_{i}=\overbrace{\underbrace{0 \cdots 0}_{i-1} b 0 \cdots 0}^{n}

    也就是说，将 y\boldsymbol{y} 的第 ii 个分量减去 bb 所得到的向量就是 y\boldsymbol{y} 译成的码字。

5. 对偶码

5.1 二元汉明码的对偶码

二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的对偶码有时也称为极长码或单纯码，记为 Σr\Sigma_r。Σr\Sigma_r 的生成矩阵（也即 Ham(r,2)\mathrm{Ham}(r, 2) 的校验矩阵）记为 Gr\boldsymbol{G}_r。Σr\Sigma_r 是一个二元 [2r−1,r][2^r-1, r] 线性码。

  • 定理三：在二元汉明码 Ham(r,2)\mathrm{Ham}(r, 2) 的对偶码 Σr\Sigma_r 中，任意一个非零码字的重量都是 2r−12^{r-1}，并且任意两个不同码字之间的距离都等于 2r−12^{r-1}。

附录

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