2.3 差错检测

数据传输过程中会由于噪声或者其他因素而出现差错。差错分为位错与帧错两大类。

位错：二进制数字出错，如00000000变成00000001

帧错：包括丢失、重复、失序三种。如发送编号顺序为1、2、3的三个帧，如果接收方收到的是13，就是发生了丢失，2号帧丢失；如果接收方收到的是1223，就是发生了重复，2号帧重复；如果接收方收到的是132，就是发生了失序，2 、3号帧失序。

为了保证数据传输的可靠性，必须采取一些措施来检测差错。差错控制既可以检测差错然后重传，也可以检测差错后直接纠错。前者使用检测编码，后者使用纠错编码。

注：这里的编码是数据链层的编码，针对的是一组比特。而物理层的编码是针对单个比特，如归零编码、曼彻斯特编码。

2.3.1 检测编码

检测编码有奇偶校验码和CRC循环冗余码两种。

2.3.1.1 奇偶校验码

奇偶校验码分为奇校验和偶校验。n位的奇偶校验码中有n-1位信息元和1位校验元。在编码时，先看信息元中的“1”的个数是奇数还是偶数，对于奇校验，如果信息元中“1”的个数为奇数，则校验位设置为0，如果为偶数，则校验元设置为1，总之奇校验就是通过设置校验元时校验码中“1”的个数为奇数。而偶校验就是通过设置校验元时校验码中“1”的个数为偶数。

接收方收到数据后会检查“1”的个数，对于奇校验，如果“1”的个数为奇数，则认为没有出错，如果为偶数，则判定出错，要求发送方重传。偶校验同理。从工作过程中我们可以发现，如果判定出错，则肯定发生了错误；但是如果判定未出错，却不一定传输正确。

比如传送奇校验码为000000001 ，如果接收方收到的是000000111，此时会判定正确，但实际出现了错误。奇偶校验码只能检测出奇数个比特的错误。

2.3.1.2 CRC循环冗余码

CRC循环冗余码比较复杂，用一个例子来说明。比如要发送数据1101 0110 11，首先发送方与接收方会商定一个生成多项式，如10011，生成多项式可以换一种形式G（x）=x4 x 1。事实上G（x）=1*x4 0*x3 0*x2 1*x1 1*x0,，取各项系数就得到了10011，然后确定生成多项式的阶，生成多项式的阶为x的最高次数，此生成多项式x的最高次数为4，故阶为4。接下来在要发送的数据后面加上4（阶数）个0，得到1101 0100 11 0000，然后进行模2除法（相同取0，不同取1，见下图）。

最后得到的余数1110即为冗余码，故最终发送的数据为1101 0110 111110。

接收方收到数据后除以生成多项式10011，如果得到的余数为0，则判定没有错误并接收；否则判定未出错并丢弃。

值得注意的是，使用CRC循环冗余校验也不一定保证接收就没有出错，只是出错概率低，一般生成多项式越高阶，出错概率越低。

2.3.2 检错编码

检错编码这里介绍海明码。海明码工作流程：

确定校验码位数r→确定校验码和数据的位置→求出校验码的值→检错并纠错

①确定校验码位数：如果数据有m位，设校验码为r位，则校验码一共有2r种取值，减去1种全对的情况，则2r-1种取值方式表示有1位出错，而编码后一共有m r位，故r应满足：

2r-1≥m r（海明不等式）

例如发送数据1100，m=4，代入不等式可得最小的r=3，海明码有m r=7位。

②确定校验码和数据的位置：校验码放在序号为2n（1,2,4,8…）的位置上，按序填上。

③求出校验码的值：

4号校验码，4对应的二进制为100，则其负责1**的校验，即100、101、110、111，再转换为十进制，也就是4,5,6,7。1、2号校验码同理。

偶校验说明：4对于x4,5对应0,6、7均对应1，则x4取0，这样有偶数（也就是2）个“1”。

④检错并纠错：

假设接收方收到的数据：

我们很容易发现5号位出错了，但是接收方并不能直接识别，需要采用一定的方法进行判断。

x4负责的4、5、6、7：0、1、1、1，由于是偶校验，而这里是奇数个1，故判定出错。

x2负责的2、3、6、7：0、0、1、1，偶数个1，判定正确

x1负责的1、3、5、7：1、0、1、1，奇数个1，判定错误

据此可得出数据传输出错。接下来判定出错的位数：

法一：

合起来就得到了101，转换为十进制就是5，也就是5号位出错。

法二：

先作图，如图所示。最外面三个部分是1、2、4，然后交叉的部分写其和，3=1 2,5=1 4,6=2 4,7=1 2 4。根据前面的判断4、5、6、7和1、3、5、7中有错，取4、5、6、7的圆与1、3、5、7相交的部分，可得到错误在5、7中，又根据2、3、6、7正确，可以排除7，这样就可以确定5号位出错。

,