1. 简介

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

2. 汉明码

2.1 二元汉明码

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

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

2.2 多元汉明码

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

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

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

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

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

3. 性质

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

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

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

4. 译码方法

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

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

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

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

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

   $$\boldsymbol{\alpha}_{i}=\overbrace{\underbrace{0 \cdots 0}_{i-1} b 0 \cdots 0}^{n}$$

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

5. 对偶码

5.1 二元汉明码的对偶码

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

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

附录

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