计算机网络循环冗余检查（网络数据通信的差错控制）

计算机网络数据通信过程中，差错的产生是无法避免的。信号在物理信道中传输时，线路本身电器特性造成的随机噪声、信号幅度的衰减、频率和相位的畸变、电器信号在线路上产生反射造成的回音效应、相邻线路间的串扰以及各种外界因素（如大气中的闪电、开关的跳火、外界强电流磁场的变化、电源的波动等）都会造成信号的失真。所以如何有效地检测收到的数据中是否存在传输差错？万一出现了差错，又如何能够从中恢复出正确的数据？

差错控制的基本原理

如果出现了通信接收端接收到的数据与发送方发出的数据不一致，我们就可以认定为传输差错。比如从物理层的角度来看，发送端发了0110，4个比特。接收端根据收到的信号电平值判断出收到的是0100，那么就是出现了一个比特的差错；对应的对于数据链路层来说会出现收到的帧和发送的帧不一致，也就是出现了错帧；同样对于网络层来说可能会出现分组差错。

在通信过程中出现差错的原因很多，单纯从传输的层面来看，可能是由于信道本身的传输特性不理想或者外部的干扰所导致。比如不同的传输媒介对应的频谱特性，如果信号的带宽超出了信道的频带宽度，或者对于数字信号的速率超出了信道的传输能力，那我们从图上就可以看到，明明发送的是矩形的信号，但接收到的信号却出现了变形失真，有可能造成码元的错误判决，从而引起传输差错。

特别是对于无线信道的传输更加复杂，不仅容易受到外界电磁信号的干扰，还会由于电磁波信号在传播过程中可能会遇到散射、反射等现象会出现信号波形失真，从而引起传输差错。

那么我们如何来控制差错？我们先通过一个简单的例子来引出所采用的差错控制的思想。

假设在一个公司内部领导下发一个会议通知，内容是14点到16点开会。这里我们将从会议通知被发出后到员工收到通知前，这个过程看作是经过了一个传输信道，信道噪声导致通知传达到员工内，彼时变成了10点到16点开会，那显然会议的时间出现了错误，但对于所有的员工而言无法检测出差错，即使他们觉得这个会议的持续时间让人难以忍受。这种传输方式没有包含任何的差错控制措施，即使发生差错也检测不到，更不要提纠正差错了。那如果说领导下发通知的时候多写两个字，加一些在我们看来多余的信息变为下午14点到16点开会，情况会有什么改变？同样经过噪声信道出现了差错，变为下午10点到16点开会，那员工收到通知以后一眼就能识别出通知有问题，明显的有矛盾，可以肯定通知是有差错的。那至于说正确的通知到底是什么，确切的开会时间是下午哪个时间段，从这个出错的通知上显然无法辨别，也无法进行纠正。当然员工们可以通过向领导进一步核实来纠正差错，所以通过多加了看似冗余的下午两个字就可以达到差错检测的目的，但是并没有纠错的能力，那怎么才能既能检错又能够纠正错误，我们还需要多加一些冗余信息进去，比如将通知改为下午14点到16点开会两小时，明确指明会议时长，这样即使经过有噪声信道的传输，会议时间出错为10点到16点，那这时员工们不仅能够发现错误，还能根据会议时间两小时这样的一个冗余信息，将出错的通知纠正为14点到16点。

显然通过加入更多的冗余信息，不仅能够检测出错误，还能纠正错误。通过例子是要告诉大家，在通信系统中要想达到差错控制的目的，仅仅传送原始数据本身是远远不够的，因为我们要传输的数据码元之间是独立随机的，没有任何关联，单纯从接收到的数据序列中无法判断是否存在差错，就跟我们刚刚原始的会议通知14点到16点开会一样，起始时间、结束时间和开会这事情三者之间没有任何的联系，任何一个信息出错都无法从其他的信息中发现。

所以为了能够进行差错控制，还必须加入一些冗余信息，那在发送的数据码元序列中加入监督，并且进行某种变换，使它们和原来的相互独立的数据码元之间具有某种约束关系，这种约束关系是能够检测甚至纠正差错的。我们前面例子里面的加入“下午”这个冗余信息就能够检测到差错，那在加入“两小时后”就能够进行纠错。

其实“下午”和“两小时”就是所谓的监督，为它们和原始的通知之间构成了一定的约束关系，设计合理有效的约束关系正是操作控制技术的关键，当然也要注意，由于通过引入冗余信息来实现差错控制，这在一定程度上会降低信道的传输效率。引入监督以后，接收端只需要检测接收到的数据码元和监督码元的约束关系，如果发现这种约束关系被破坏了，就说明接收端接收到的是出错的数据。如果冗余信息足够多的情况下，接收端还可以利用约束关系来进行差错的纠正，如果约束关系依旧存在，没有被破坏，就可以认为是没有差错。但是也请大家注意，任何一种差错控制方法，它的检错或纠错的能力都是有限的，往往会存在着差错未被检测出来的可能性。

差错控制编码

根据纠错检错能力差错控制编码可以分为检错码和纠错码。检错码仅仅具备检测差错的能力，实际应用的检测码有很多，包括奇偶校验码、循环冗余码等等。其中奇偶校验码编码比较简单，检测能力有限，但是它的应用却很广泛，比如冗余串行通信、硬盘校验等；循环冗余码检错能力比较强，主要应用于数据链路层传输中，比如在广泛使用的以太网中，数据帧内所采用就是循环容易码来进行差错检测。纠错码具备纠错能力，典型的代表是海明码，编码规则并不复杂，采用的约束关系是异或运算。

奇偶校验码

奇偶校验码的编码规则很简单，只需要在所传数据后面附加一位监督，使得数据位和监督位中，总共包含奇数个1或者偶数个1。如果使编码中1的个数成为奇数则称为奇校验；反之，则称为偶校验。

例如，假设在串行通信中要传送的比特序列是1011001，一共是七位，包含了4个1。如果说选择奇校验方式为了保证加入校验位以后总共包含奇数个1，所以说校验位也必须为1。这样构造完整的奇偶校验编码的就是10110011。如果选择偶校验方式，为了确保偶数个1，校验位必须为0，从而形成偶检验编码是10110010。

奇偶校验码编码规则简单也决定了这种编码的检测能力很有限，如果奇校验10110011，传送时其中一位出错传成了10010011，奇校验能检查出错误。但是若传送有两位出错比如10000011，奇校验就不能检查出错误了。在实际传输过程中，偶然一位出错的机会最多，故这种简单的校验方法还是很有用处的。但这种方法只能检测错误，不能纠正错误，不能检测出错在哪一位，故一般只能用于通信要求较低的环境。

海明码

海明编码的实现原理是：在数据编码中加入几个校验位，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验组的值发生变化，这样不但可以发现出错，还能指出是哪一位出错。

海明码是奇偶校验码的另一种扩充。和奇偶检验码的不同之处在于海明码采用多位校验的方式，在这些多个校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个检验位对原始数据进行的校验的组合，可以达到发现错误、纠正错误的目的。海明码能够纠正一位比特的错误。

一个长度为m的数据中增加k位冗余位，构成一个 n=m k 位的码字，然后用 k 个监督关系式产生的 k 个校正因子来检测和纠正错误。为了能够纠正一个比特的错误，数据长度和冗余位的数目必须满足公式：

2^k-1≥m k

例：已知原始数据为1001011,采用Hamming Code编码后，求实际发送的数据？

求解过程如下：

1.计算需要的校验位数目。从题目中可知数据为的长度为7，即 m=7 ，带入公式 2^k-1≥m k

2.得到 k>=4 ，为了减少冗余k取最小值4。最后实际发送的数据长度为 7 4=11 位。

3.重新排列数据。定义4个校验位分别是 a1,a2,a3,a4 。根据海明码原则组合排列7位数据和4位校验码。校验码的位置分别是 1=2^0,2=2^1,4=2^2,8=2^3 。排列后的顺序如下所示。

4. 计算每个校验位的值。根据下图，位置1，2，4，8存放校验数据。最后一列列名称是1，数字3，5，7，9，11的二进制数在该列的数据为1，因此位置1对这些位置进行监督，同理，列名为2，4，8的位置对二进制数在该列为1的位置进行校验。

在采用偶校验时，各检验位的值等于含有该检验位的数据位的异或运算结果，异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）。把数据带入公式可以得到各校验位的值：

5. 带入校验数据得到发送数据。得到一个新的数据序列 10110010011，这个新序列就是发送端发送出去的数据，也是线路上传输的数据。如果数据没有发生冲突，这也将是接收方收到的数据。

海明码纠错

接收端在接收到海明码后，将校验位与其对应的数据位进行异或运算，公式如下：

因为在新的数据串中a1和X1是同一个数据位，a2和 X2 是同一个数据位，a3和 X4 是同一个数据位，a4和 X8 是同一个数据位，因此公式也可以表示为：

计算结果按照 h4h3h2h1 的顺序进行排列，如果结果等于0说明数据没有出错；如果结果不等于0，说明数据出错。把该数据转化为10进制数，就是出错数据的位置。因为二进制数中每一位置只有2种状态，0或者1。因此知道错误的位置后，改正错误就非常简单，把对应的数据取反即可。

假如接收端收到的数据为10110110011，代入公式得到：

新的数据 h4h3h2h1=0110 ，转换为十进制数值为6，因此说明接收到的数据中第6位出错，将第六位数据取反就可以得到正确的原始数据，原始数据为 10110010011 。

循环冗余码

循环冗余码（Cyclic Redundancy Code，CRC）是使用最广泛并且检错能力很强的一种检验码。循环冗余校验的基本思想是：把要传送的信息码看成是一个多项式M（X）的系数，在发送前，将多项式用生成多项式G（X）来除，将相除结果的余数作为校验码跟在原信息码之后一同发送出去。在接收端，把接收到的含校验码的信息码再用同一个生成多项式来除，如果在传送过程中无差错，则应该除尽，即余数应为0；若除不尽，则说明传输过程中有差错，应要求对方重新发送一次。

我们来做一个实例，就很容易地可以理解CRC循环冗余检验码，当发送方要发送的帧为1101011011，生成多项式 为G（x）= x^4 x 1，则 r = 4，r为何是4，其实就是生成多项式最大的x^4 ，此时 r = 4 ，所以则在帧后附加4个0。

生成多项式 G（x）= x^4 x 1 = 10011 （对应x位写1，没有对应的位填0，就成为相应的生成多项式G（x））。

发送端计算的过程是：要发送的数据帧 r 位的校检序列，得到要发送的数据帧然后与生成多项式进行模2除法运算，取余数，这个余数就是需要增加的FCS帧检验序列。

通过计算，可以得到余数为1110，那么实际发送的帧为11010110111110。

接收端计算的过程是：当接收端收到帧11010110111110 与 生成多项式进行模2除法运算，然后检查得到的余数，如果余数为0，则表示传输过程是正常的则接收数据，否则是存在错误的则丢弃数据。

,