3.差错控制

一、检错编码

奇偶校验码

• 如果是奇校验码,那么在附加一个校验元后,码长为n 的码字中“1” 的个数为奇数
• 如果是偶校验码,那么在附加一个校验元以后,码长为n的码字中“1” 的个数为偶数。

提示

它只能检测奇数位的出错情况,但并不知道哪些位错了,也不能发现偶数位的出错情况。

循环冗余码

背景知识

任何一个由二进制数位串组成的代码都可与一个只含有0和 1 两个系数的多项式建立一一对应关系。例如1110011有 7 位，对应的多项式为$X^6+X^5+X^4+X+1$,(中间几个 0 没有对应的项)

计算方法

给定一个$m$ bit 的帧或报文，发送器生成一个$r$ bit 的序列，称为帧检验序列(FCS)。这样所形成的帧将由$m+r$比特组成。发送方和接收方事先商定一个多项式$G(x)$（最高位和最低位必须为 1)，使这个带检验码的帧刚好能被预先确定的多项式$G(x)$整除。接收方用相同的多项式去除收到的帧,如果无余数,那么认为无差错。

假定一个帧有$m$位，其对应的多项式为$M(x)$,计算冗余码步骤如下:

1. 加 0。假设$G(x)$的阶为$r$，在帧的低位端加上$r$个$0$。
2. 模$2$除。利用模$2$除法^[1]，用$G(x)$对应的数据串去除上一步得到的数据串，得到的余数即为冗余码(共$r$位，前面的$0$不可省略)。

image.png

图示中得到对应的冗余码为001，发送出去的数据为101001 001，接收方接受后，可以将该数据除事先约定的1101，肯定是可以整除的，否则说明出现了差错，则丢弃该帧

计算原则

1. 除数与被除数最高几位（与除数位数相同）做异或，商1。（除数首位必须为1）
2. 余数先去掉首位，若此时余数最高位为1，商1，并对以它为除数继续模2除。  若最高位为0，则商0，重复步骤2。
3. 直到余数位数小于除数位数时，运算结束。

注意

循环冗余码(CRC)是具有纠错功能的,只是数据链路层仅使用了它的检错功能,检测到帧出错则直接丟弃,是为了方便协议的实现。

二、纠错编码

在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。
在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错位,而且能指出错位的位置,为自动纠错提供依据。

海明码

以数据码 1010 为例讲述海明码的编码原理和过程。

1.确定海明码的位数

设$n$为有效信息的位数，$k$为校验位的位数，则信息位$n$和校验位$k$应满足

$$n+k\le 2^k-1$$

若需要检测两位错，则需要再增加 1 位校验位，即$k+1$位
海明码位数为$n+k=7\le 2^3-1$成立，则$n\text{、}k$有效。设信息位为$D_{4}D_{3}D_{2}D_{1}(1010)$,共 4 位，校验位为$P_{3}P_{2}P_{1}$，共 3 位，对应的海明码为$H_{7}H_{6}H_{5}H_{4}H_{3}H_{2}H_{1}$。

2.确定校验位的分布

规定校验位$P_{i}$在海明位号为$2^{i-1}$的位置上，其余各位为信息位，因此有

• $P_{1}$的海明位号为$2^{i-1}=2^0=1$，即$H_{1}$为$P_{1}$
• $H_{2}$为$P_{2}$
• $H_{4}$为$P_{3}$
  将信息位按原来的顺序插入，则海明码各位的分布如下:

$$\begin{matrix} 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} \end{matrix}$$

3.分组以形成校验关系

每个数据位用多个校验位进行校验，但要满足条件：被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。另外，校验位不需要再被校验。分组形成的校验关系如下:

4.校验位取值

校验位$P_{i}$的值为第$i$组(由该校验位校验的数据位)所有位求异或。
根据3.分组以形成校验关系中的分组有

$$\begin{align*} P_{1}&=D_{1}\oplus D_{2}\oplus D_{4}=0\oplus 1\oplus 1=0\\ P_{2}&=D_{1}\oplus D_{3}\oplus D_{4}=0\oplus 0 \oplus 1=1\\ P_{3}&=D_{2}\oplus D_{3} \oplus D_{4} =1 \oplus 0 \oplus 1 = 0 \end{align*}$$

故1010对应的海明码为$101\underline{0}0\underline{10}$(下划线为校验位，其他为信息位)。

5.海明码的校验原理

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成$k$个校验方程:

$$\begin{align*} S_{1}&=P_{1}\oplus D_{1}\oplus D_{2} \oplus D_{4}\\ S_{2}&=P_{2}\oplus D_{1}\oplus D_{3}\oplus D_{4}\\ S_{3}&=P_{3}\oplus D_{2}\oplus D_{3}\oplus D_{4} \end{align*}$$

若$S_{3}S_{2}S_{1}$的值为000，则说明无错；否则说明出错，且这个数就是错误位的位号，如$S_{3}S_{2}S_{1}=001$，说明$H_{1}$出错，直接将该位取反就达到纠错的目的^[2]。

---

1. 用模 2 运算进行加法时不进位,例如,1111 + 1010 = 0101。减法和加法一样,按加法规则计算。 ↩︎

2. 二进制只有两种状态，该状态出错，取反则为正确状态 ↩︎