3.3 差错控制

概括地说，传输中的差错都是由于噪声引起的。噪声有两大类：一类是信道中所固定的、持续存在的随机热噪声；另一类是由于外界特定个的短暂原因所造成的冲击噪声。前者可以通过提高信噪比来减少或避免干扰，而后者不可能靠提高信号幅度来避免干扰造成的差错，是产生差错的重要原因。

通常利用编码技术进行差错控制，主要由两类：自动重传请求（Automatic Retransmission Request，ARQ）和前向纠错（Forward Error Correction，FEC）。在ARQ方式中，接收端差错时，就设法通知发送端重发，直到接收到正确的码字为止。在FEC方式中，接受端不但能发现差错，而且能确定二进制数码的错误位置，从而加以纠正。因此，差错控制又可以分为检错编码（Error-Detecting Code）和纠错编码（Error-Correcting Code）。

3.3.1 检错编码

检错编码都是采用冗余编码技术，其核心思想是在有效数据（信息位）被发送前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使得码字遵从不变的规则。接受端根据收到码字是否符合原规则，从而判断是否出错。常见的检错编码有奇偶检验码和循环冗余码。

1.奇偶检验码

奇偶检验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它是由n-1位信息元和1位检验元组成，如果是奇检验码，在附加上一个检验元后，码元为n的码字中“1”的个数为奇数；如果是偶检验码，在附加上一个检验元以后，码长为n的码字中“1”的个数为偶数，它又分为奇偶校验、水平奇偶校验和水平垂直奇偶校验。

2.循环冗余码

循环冗余码（Cyclic Redundancy Code，CRC）又称为多项式码，任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应关系。一个k位帧可以看成是X^(k-1)到X^(0)的k次多项式的系数序列，这个多项式的阶数为k-1，高位是X^(k-1)项的系数，下一位是X^(k-2)的系数，依次类推。例如1110011有7位，表示多项式X^6+X^5+X^4+X+1，而多项式X^5+X^4+X^2+X的对应位串是110110。

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

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

1）加0。假设G(x)的阶为r，在帧的低位端加上r个0。

2）模2除。利用模2除法，用G(x)对应的数据串去除1）中计算出的数据串，得到的余数即为冗余码（ 共r位，前面的0不可省略）。

多项式以2为模运算，按照模2运算规则，加法不进位，减法不错位，它刚好是异或操作，乘除法类似于二进制的运算，只是在加减法时按模2规则进行。

冗余码的计算举例：设G(x)=1101(即r=3),待传送数据M=101001（即m=6），经模2除法运算后的结果是：商Q=110101(这个商没什么用)，余数R=001.所以发送出去的数据为101001001（即2^rM+FCS）,共有m+r位。

3.3.2 纠错编码

在数据通信的过程中，解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息，使接受方能够推导出发送方实际送出的应该是什么样的比特串。最常见的纠错编码是海明码，它能发现双比特错，但只能纠正单比特错。

海明码将码字内的位从左至右依次编号，第1位是1号，第2位是2号……第n位是n号，编号为2的幂的位（1号位，2号位，4号位，8号位等）是校验位，其余的位填入m位数据。每个校验位的取值应使得包括自己在内的一些位的集合服从规定的奇偶性（例如偶性要求这些位的集合中1的个数是偶数）。为了知道编号为k的数据为对哪些校验位有影响，将编号k改写成2的幂的和，例如11=1+2+8,29=1+4+8+16。一个位只由扩展式中所示编号的位检验，例如编号为11的位只由编号为1,2和8的校验位检测。

m个信息位中插入r个校验位组成m+r位码字，它们必须满足的关系是2^r>=m+r+1，以典型的4位数据编码为例，海明码将加入3个校验位，从而实际传输7为码字;

数据位：1 2 3 4 5 6 7

代码：P1 P2  D1 P3 D2 D3 D4

说明：Px为校验码，Dx为数据码。

现以数据码1101为例讲述海明码的编码原理。此时D1=1，D2=1，D3=0，D4=1，对于数据位的编号，有1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4。

于是P1对应数据位1、3、5、7，令P1异或D1异或D2异或D4=0得P1=1;

P2对应的数据位为2、3、6、7，令P2异或D1异或D3异或D4=0得P2=0;

P3对应的数据位为4、5、6、7，令p3异或D2异或D3异或D4=0得P3=0;

那么海明编码的结果就是1010101.

接下来讨论如何纠错。接受方收到的正确码字应该是1010101，如果D3在传输过程中因干扰而变成了1，接受方就收到1010111.检测时，P1异或D1异或D2异或D4=0，第一位纠错代码为0，正确。

P2异或D1异或D3异或D4=1，第二位纠错代码为1，有错误。

p3异或D2异或D3异或D4=1，第三位纠错代码为1，有错误。

将三个纠错代码从高到低排列为二进制编码110，换算成十进制就是6，也就是说第6位数据错了，而数据D3在海明编码后的位置正好是第六位，取反即可。