信息论-汉明码

[TOC]

这一节在讲什么

汉明码（Hamming Code）是一种典型的单比特错误纠正码。它的目标不是只判断“数据有没有错”，而是进一步定位“哪一位错了”，然后把那一位翻转回来。

普通奇偶校验只能发现错误，不能定位错误；汉明码通过插入多个校验位，让不同校验位负责不同位置，从而把校验结果组合成一个二进制编号。这个编号就是出错位的位置。

可以把汉明码的核心逻辑压缩成一句话：

校验位负责不同的位置集合，接收端得到的综合征就是错误位置的二进制编号。

一、校验位数量

设原始数据有 $m$ 个信息位，需要加入 $p$ 个校验位。发送的总位数为

$$n=m+p$$

为了能够区分：

1. 完全没有错误；
2. 第 $1$ 位出错；
3. 第 $2$ 位出错；
4. $\cdots$
5. 第 $n$ 位出错；

校验结果至少要能表示 $n+1$ 种情况。因此校验位数量必须满足：

$$2^p \ge m+p+1$$

其中：

• $m$：数据位数量；
• $p$：校验位数量；
• $1$：表示“无错误”这一种额外情况。

例如，当 $m=4$ 时：

$$2^3=8,\qquad m+p+1=4+3+1=8$$

所以需要 $p=3$ 个校验位。这就是常见的 Hamming(7,4)：总共 7 位，其中 4 位是数据位，3 位是校验位。

二、Hamming(7,4) 的位排列

汉明码的校验位放在 $2$ 的幂次位置：

• 第 $1$ 位：$2^0$，放 $p_1$；
• 第 $2$ 位：$2^1$，放 $p_2$；
• 第 $4$ 位：$2^2$，放 $p_3$；
• 第 $8$ 位：$2^3$，放 $p_4$，更长的汉明码才会用到。

对于 Hamming(7,4)，位置安排如下：

位置	1	2	3	4	5	6	7
类型	$p_1$	$p_2$	$m_1$	$p_3$	$m_2$	$m_3$	$m_4$

也就是：

$$p_1,\ p_2,\ m_1,\ p_3,\ m_2,\ m_3,\ m_4$$

校验位之所以放在 $1,2,4$ 这些位置，是因为这些位置的二进制表示只有一个 $1$，方便后面用综合征直接定位错误。

三、校验位负责哪些位置

汉明码的编号从 1 开始。把每一个位置写成二进制：

十进制位置	二进制位置
1	$001$
2	$010$
3	$011$
4	$100$
5	$101$
6	$110$
7	$111$

每个校验位负责那些“对应二进制位为 1”的位置。

1. $p_1$ 的覆盖范围

$p_1$ 在第 1 位，对应二进制的最低位。因此它负责所有二进制编号最低位为 1 的位置：

$$1,\ 3,\ 5,\ 7$$

也就是：

$$p_1,\ m_1,\ m_2,\ m_4$$

2. $p_2$ 的覆盖范围

$p_2$ 在第 2 位，对应二进制的中间位。因此它负责：

$$2,\ 3,\ 6,\ 7$$

也就是：

$$p_2,\ m_1,\ m_3,\ m_4$$

3. $p_3$ 的覆盖范围

$p_3$ 在第 4 位，对应二进制的最高位。因此它负责：

$$4,\ 5,\ 6,\ 7$$

也就是：

$$p_3,\ m_2,\ m_3,\ m_4$$

用表格汇总：

校验位	负责的位置	位置规律
$p_1$	1, 3, 5, 7	二进制最低位为 1
$p_2$	2, 3, 6, 7	二进制中间位为 1
$p_3$	4, 5, 6, 7	二进制最高位为 1

四、偶校验下如何生成汉明码

下面默认使用偶校验：每个校验组中，$1$ 的个数必须为偶数。

设 4 个数据位为：

$$m_1m_2m_3m_4=1011$$

先把数据位放入 Hamming(7,4) 的数据位置：

位置	1	2	3	4	5	6	7
类型	$p_1$	$p_2$	$m_1$	$p_3$	$m_2$	$m_3$	$m_4$
数值	?	?	1	?	0	1	1

1. 求 $p_1$

$p_1$ 负责第 1, 3, 5, 7 位：

$$p_1,\ 1,\ 0,\ 1$$

已知的 $1$ 有 2 个，已经是偶数，所以

$$p_1=0$$

2. 求 $p_2$

$p_2$ 负责第 2, 3, 6, 7 位：

$$p_2,\ 1,\ 1,\ 1$$

已知的 $1$ 有 3 个，为了变成偶数，所以

$$p_2=1$$

3. 求 $p_3$

$p_3$ 负责第 4, 5, 6, 7 位：

$$p_3,\ 0,\ 1,\ 1$$

已知的 $1$ 有 2 个，已经是偶数，所以

$$p_3=0$$

最终编码为：

位置	1	2	3	4	5	6	7
数值	0	1	1	0	0	1	1

所以发送的汉明码是：

$$0110011$$

五、综合征：如何定位错误

接收端重新检查每一组校验，得到三个检查结果：

• $S_1$：检查 $p_1$ 负责的组；
• $S_2$：检查 $p_2$ 负责的组；
• $S_3$：检查 $p_3$ 负责的组。

这里统一把综合征写成：

$$S_3S_2S_1$$

也就是高位在左，低位在右。这样它可以直接当成二进制数读取：

$$(S_3S_2S_1)_2=\text{出错位置}$$

如果综合征为 $000$，表示没有检测到单比特错误。

综合征 $S_3S_2S_1$	十进制位置	含义
$000$	0	无错误
$001$	1	第 1 位出错，即 $p_1$
$010$	2	第 2 位出错，即 $p_2$
$011$	3	第 3 位出错，即 $m_1$
$100$	4	第 4 位出错，即 $p_3$
$101$	5	第 5 位出错，即 $m_2$
$110$	6	第 6 位出错，即 $m_3$
$111$	7	第 7 位出错，即 $m_4$

注意：如果你把综合征写成 $S_1S_2S_3$，就不能直接按这个表读位置。考试或做题时必须先确认综合征的书写顺序。

六、纠错例题

继续使用上面生成的码字：

$$0110011$$

假设传输后第 5 位发生翻转，接收端收到：

$$0110111$$

按位置写出：

位置	1	2	3	4	5	6	7
接收值	0	1	1	0	1	1	1

1. 计算 $S_1$

$S_1$ 检查第 1, 3, 5, 7 位：

$$0,\ 1,\ 1,\ 1$$

其中 $1$ 的个数为 3，是奇数，所以

$$S_1=1$$

2. 计算 $S_2$

$S_2$ 检查第 2, 3, 6, 7 位：

$$1,\ 1,\ 1,\ 1$$

其中 $1$ 的个数为 4，是偶数，所以

$$S_2=0$$

3. 计算 $S_3$

$S_3$ 检查第 4, 5, 6, 7 位：

$$0,\ 1,\ 1,\ 1$$

其中 $1$ 的个数为 3，是奇数，所以

$$S_3=1$$

因此综合征为：

$$S_3S_2S_1=101$$

而

$$101_2=5_{10}$$

所以第 5 位出错。把第 5 位从 $1$ 翻转回 $0$，得到正确码字：

$$0110011$$

再去掉校验位 $1,2,4$，保留第 $3,5,6,7$ 位，恢复数据：

$$1011$$

七、为什么这种设计能定位错误

关键在于每个位置都有唯一的二进制编号。例如第 5 位的编号是：

$$5=101_2$$

这表示：

• 最高位为 1，所以 $S_3$ 会报错；
• 中间位为 0，所以 $S_2$ 不报错；
• 最低位为 1，所以 $S_1$ 会报错。

因此综合征就是：

$$S_3S_2S_1=101$$

它直接指向第 5 位。

换句话说，每个数据位都被一组独特的校验位覆盖。一旦某一位发生翻转，受影响的校验位组合也唯一，于是可以定位错误。

八、做题步骤

1. 编码步骤

1. 根据 $2^p\ge m+p+1$ 求校验位数量 $p$；
2. 把校验位放在 $1,2,4,8,\dots$ 这些位置；
3. 把数据位填入剩余位置；
4. 根据偶校验或奇校验求出每个校验位；
5. 写出完整码字。

2. 解码与纠错步骤

1. 按校验位分组重新检查；
2. 得到 $S_1,S_2,S_3,\dots$；
3. 按高位到低位写成综合征，例如 $S_3S_2S_1$；
4. 把综合征转成十进制，得到错误位置；
5. 若综合征为 0，则认为无单比特错误；
6. 若综合征不为 0，则翻转对应位置；
7. 去掉校验位，读出原始数据。

九、常见易错点

• 位编号从 1 开始，不是从 0 开始。
• 校验位放在 $1,2,4,8,\dots$，不是随便插入。
• 必须先确认使用的是偶校验还是奇校验。
• 综合征顺序要统一。本文使用 $S_3S_2S_1$，可以直接读成二进制位置。
• Hamming(7,4) 可以纠正单比特错误，但不能可靠纠正多比特错误。
• 表中 $111$ 对应第 7 位，也就是 $m_4$，不是 $m_3$。

十、复习清单

• 我能解释为什么校验位数量满足 $2^p\ge m+p+1$。
• 我能写出 Hamming(7,4) 的位置结构：$p_1,p_2,m_1,p_3,m_2,m_3,m_4$。
• 我能判断 $p_1,p_2,p_3$ 分别覆盖哪些位置。
• 我能用偶校验生成一个 Hamming(7,4) 码字。
• 我能从接收码字计算综合征。
• 我能把综合征转换成出错位置，并翻转对应比特。
• 我能去掉校验位，恢复原始数据。
• 我能说明汉明码只能纠正单比特错误的原因。

视频参考