纠错编码

差错控制

在数据链路层中，差错控制的主要目标是发现并解决一个帧内部的“位错”，有两种解决方法：

• 解决方法一：接收方发现比特错误后丢弃帧，并通知发送方重传帧；即检错编码，主要有：奇偶校验码、CRC 校验码

• 解决方法二：由接收方发现并纠正比特错误；即纠错编码，主要有：海明校验码

奇偶校验码

采用奇偶校验的帧含有两个部分：信息位（有效数据）和校验位（冗余数据）。

校验原理：

• 在帧的首部或尾部添加一个校验位，使整个帧中“1”的个数为奇数或偶数。

• 奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

• 偶校验码：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

举例

以二进制数 10110100 为例，

校验方法	校验位	校验码
奇校验码	0	010110100
偶校验码	1	110110100

在实际使用中，通常采用偶校验码，因为对各信息进行异或（模2加法）^[1]运算，得到的结果即为偶校验位

还是以二进制数 10110100 为例，

求偶校验码的步骤如下：

1. 计算校验码：

$$1\oplus0\oplus1\oplus1\oplus0\oplus1\oplus0\oplus0 = 1$$

2. 校验码为 1 ，因此偶校验码为 11010100。

对于接收方来说，校验数据只需要对整个数据进行异或运算，得到的结果为 0 ，则说明数据没有错误。

奇偶校验的缺点：

• 无法检测出偶数个的错误；

• 只能检测出错误，不能纠正错误。

循环冗余校验码

循环冗余校验码（Cyclic Redundancy Check，CRC）是一种常用的检错编码，它通过在数据后面附加冗余位来检测数据中的错误。

CRC的基本思想：数据发送，接收方约定一个“除数”，k 个信息位 + r 个校验位作为“被除数”，添加校验位后需保证除法的余数为 0。

接收方收到数据后，对数据进行“除法”，如果余数为 0，则说明数据没有错误。

举例

以二进制数 101101 为例，

设生成多项式为 $G(x) = x^3 + x + 1$，

1. 确定 k 和 r 以及生成多项式对应的二进制码：

   k = 信息位的长度 = 6，r = 生成多项式最高次幂 = 3，校验码位数 n = k + r = 9，

   生成多项式对应的二进制码为生成多项式幂次从高到低的每一项系数即 $G(x) = 1 \times x^3 + 0 \times + x^2 + 1 \times x + 1 \times x^0 = 1010$。

信息位	校验位	生成多项式二进制码
6	3	1010

2. 移位

信息码左移 r 位，低位补 0

补齐后为： 101101000

3. 模 2 除法

基本规则：

• 当被除数的最高位为 1 时，用被除数“除以”除数，商最高位补 1

• 当被除数的最高位为 0 时，用被除数“除以”除数，商最高位补 0

• 剩余位数进行异或减运算

将补齐后的信息码除以生成多项式，得到余数，余数即为校验码

$$\begin{array}{lr} & 100100 \\ 1010 \!\!\!\!\!\! & \overline{)101101000} \\ & \underline{1010\ \ \ \ \ \ \ \ \ \ } \\ & 0010 \ \ \ \ \ \ \ \ \\ & \underline{0000\ \ \ \ \ \ \ \ } \\ & 0101 \ \ \ \ \ \ \\ & \underline{0000\ \ \ \ \ \ } \\ & 1010 \ \ \ \ \\ & \underline{1010\ \ \ \ } \\ & 0000 \ \ \\ & \underline{0000\ \ } \\ & 0000 \\ & \underline{0000} \\ & 000 \\ \end{array}$$

余数为 000，因此校验位为 000，

因此 CRC 码为 101101000。

4. 检错和纠错

当校验位为 000 时，说明数据没有错误；

当校验位不为 000 时，说明数据有错误，需要纠错。

对于能够进行纠错的情况，只能是：当含有 k 个信息位， r 个校验位，若生成多项式选择得当

且 $2^r \geq k + r + 1$ ，则可纠正 1 位错误；但是该算法一般不会用来纠错，一般只会用来检错

循环冗余校验码理论上的检错能力包括以下几点：

• 可检测出所有奇数个错误

• 可检测出所有双比特的错误

• 可检测出所有小于等于校验位长度的连续错误

总的来说，循环冗余校验码，具有检错能力和一定纠错能力

海明校验码

基本思想（设计思路）

将信息位分组进行偶校验 —— 多个校验位 —— 多个校验位标注出错位置

信息位 + 校验位 共 $n + k$ 位，

$k$ 位校验位共能表示 $2^k$ 个状态，上面的 $n + k$ 位都有可能出错，同时需要 1 位来表示正确状态，因此可以得到：

$$2^k \geq n + k + 1$$

求解步骤

确定校验位数量 —— 确定校验位的分布 —— 求校验位的值 —— 检错纠错

例如：信息位为 1010

• 确定海明码位数：

$2^k \geq n + k + 1$，

可以解得 $k = 3$，因此海明码位数为 $n + k = 7$ 位。

信息位为：$D_4$、$D_3$、$D_2$、$D_1$

校验位为：$P_3$、$P_2$、$P_1$

共 3 位，对应的海明码为：$H_7$、$H_6$、$H_5$、$H_4$、$H_3$、$H_2$、$H_1$

• 确定校验位的分布：

校验位 $P_i$ 应放在 $H_{2^i}$ 的位置上，其余信息位按顺序放置到空余位置

对于本例的海明码分布为：

$H_7$	$H_6$	$H_5$	$H_4$	$H_3$	$H_2$	$H_1$
$D_4$	$D_3$	$D_2$	$P_3$	$D_1$	$P_2$	$P_1$
1	0	1	?	0	?	?

• 求校验位的值：

首先对每位信息位的海明码位下标值进行求二进制值

对下标二进制为 1 的位，将对应的信息位异或起来，得到校验位的值、从末尾开始计算

对于本例：

海明码位	$H_7$	$H_6$	$H_5$	$H_3$
信息码位	$D_4$	$D_3$	$D_2$	$D_1$
信息位	1	0	1	0
码位下标	7	6	5	3
下标二进制	111	110	101	011

计算校验位：

$$\begin{array}{lr} P_1 = H_3 \oplus H_5 \oplus H_7 = D_1 \oplus D_2 \oplus D_4 = 0 \oplus 1 \oplus 1 = 0 \\ P_2 = H_3 \oplus H_6 \oplus H_7 = D_1 \oplus D_3 \oplus D_4 = 0 \oplus 0 \oplus 1 = 1 \\ P_3 = H_5 \oplus H_6 \oplus H_7 = D_2 \oplus D_3 \oplus D_4 = 1 \oplus 0 \oplus 1 = 0 \end{array}$$

最后可以确定整个海明码为：

海明码位	$H_7$	$H_6$	$H_5$	$H_4$	$H_3$	$H_2$	$H_1$
信息码位	$D_4$	$D_3$	$D_2$	$P_3$	$D_1$	$P_2$	$P_1$
二进制码	1	0	1	0	0	1	0

• 检错纠错

使用校验码和对应分组的信息位进行异或运算，或者说进行偶校验

$$\begin{array}{lr} S_1 = P_1 \oplus D_1 \oplus D_2 \oplus D_4 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \\ S_2 = P_2 \oplus D_1 \oplus D_3 \oplus D_4 = 1 \oplus 0 \oplus 0 \oplus 1 = 1 \\ S_3 = P_3 \oplus D_2 \oplus D_3 \oplus D_4 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \end{array}$$

对于没有出现误差的情况，校验结果 $S_1$、$S_2$、$S_3$ 均为 0

对于有误差的情况：假设接收到 1010000

则计算得到的校验结果为：$S_1 = 0$、$S_2 = 1$、$S_3 = 0$

$S_3$	$S_2$	$S_1$
0	1	0

则是第 010 位出错，即第 2 位出错，也就是 $H_2$ 位出错

注意

对于有些题目的排序顺序是从小到大，计算方法也一样只是顺序需要调整

• 海明码的检错、纠错能力

纠错能力：1 位

检错能力：2 位 （并且无法区分到底是 1 位出错或者 2 位出错）

解决方法是在整个海明码前面加上一个全校验位（对整体进行偶校验）

对于本例

$H_8$	$H_7$	$H_6$	$H_5$	$H_4$	$H_3$	$H_2$	$H_1$
1	1	0	1	0	0	1	0

如果全校验位偶校验成功并且$S_1$、$S_2$、$S_3$ 均为 0，则说明没有出错

如果全校验位偶校验失败，则说明有出错，说明有一位出错，进行纠错即可

如果全校验位偶校验成功但是$S_1$、$S_2$、$S_3$ 不全为 0，则说明有 2 位出错并且无法确定两位出错的位置，需要重传

---

1. 模2加法：$\begin{cases} 0\oplus0=0 \\ 0\oplus1=1 \\ 1\oplus0=1 \\ 1\oplus1=0 \end{cases}$，即异或运算 ↩︎