下载掌阅APP，畅读海量书库
立即打开
前面讨论过，信号在经过物理线路传输时会发生差错。例如，对于电缆来说，由于工作环境的电磁干扰，就有可能发生差错。尽管随着通信技术的提高，传输介质的质量越来越高，出现差错的概率也越来越小（特别是光纤介质），但我们还是需要某种机制来检测差错，以便进行差错纠正。
物理线路传输信号时所发生的差错常常是突发性的。突发性差错与孤立的单个的差错相比，既有优点，也有缺点。假设数据块大小为1000比特，每一比特出错的概率是0.001。如果差错是孤立的，则大多数数据块在传输过程中都会发生一比特的差错。然而，如果差错是突发的，则发生一次差错就是连续的100比特，平均而言，在100个数据块中可能只有1个或2个数据块受到影响。突发性差错的缺点是，它比单个差错更加难以纠正。
用来处理计算机系统中比特差错的技术已有很长历史，可追溯到汉明码（Hamming code）和里德-所罗门码（Reed-Solomon code），它们被用于检测存储在磁盘上或早期磁芯存储器中数据的正确性。本节主要介绍普遍用于数据通信和计算机网络中的差错检测方法。
检错编码的一项最普遍的技术叫作循环冗余校验（Cyclic Redundancy Check，CRC），它广泛用于物理介质传输中。本节还介绍广泛用于TCP/IP协议栈进行差错检测的校验和（checksum）差错检测方法。
循环冗余校验编码 的基本思想是，将比特串看成是系数为0或1的多项式。一个 k 比特的帧被看作一个 k -1次多项式的系数列表，该多项式共有 k 项，分别是从 x k -1 到 x 0 。这样的多项式为 k -1阶多项式。高次（最左边）位是 x k -1 项的系数，接下去是 x k -2 项的系数，依次类推。例如，110001有6位，因此可以表示为多项式 x 5 + x 4 +1，其各个项的系数分别为1、1、0、0、0和1。
多项式的算术运算采用代数域理论的规则，以2为模来完成。加法没有进位，减法没有借位，加法和减法都等同于异或。例如：
长除法与二进制中的长除运算一样，只不过减法按模2进行。
当使用多项式编码时，发送端和接收端必须预先商定一个生成多项式（generator polynomial） G （ x ）。生成多项式的最高位和最低位必须是1。假设一帧有 m 位，它对应于多项式 M （ x ），为了计算它的循环冗余校验编码，该帧必须比生成多项式长。基本思想是，在该帧的尾部加上校验和，使加上校验和后的帧所对应的多项式能够被 G （ x ）除尽。当接收端收到带校验和的帧之后，试着用 G （ x ）去除它，如果有余数，则表明传输过程中有差错。
计算对应于多项式 M （ x ）的帧的循环冗余校验编码的算法如下。
1）假设生成多项式 G （ x ）的阶为 r 。在帧的低位端加上 r 个0，所以该帧包含 m + r 位，对应于多项式为 x r M （ x ）。
2）利用模2除法，用对应于 G （ x ）的位串去除对应于 x r M （ x ）的位串。
3）利用模2减法，从对应于 x r M （ x ）的位串中减去余数（总是小于等于 r 位）。结果就是将被传输的带校验和的帧，它所对应的多项式不妨设为 T （ x ）。图3-3显示了当帧为1101011011时，生成多项式为 x 4 + x +1时计算校验和的情形。
显然， T （ x ）可以被 G （ x ）除尽（模2）。在任何一种除法中，如果将被除数减掉余数，则剩下的差值一定可以被除数除尽。例如，在十进制中，如果用210278除以10941，则余数为2399。从210278中减去2399，得到207879，它可以被10941除尽。
现在分析循环冗余校验能检测什么样的差错。想象一下，如果发送的帧在传输过程中发生了差错，因此接收端收到的不是 T （ x ），而是 T （ x ）+ E （ x ）， E （ x ）中的每一项[ E （ x ）多项式所表示的二进制位串中该位为1]都对应地有一位反了（从0变为1或者是从1变为0）。如果 E （ x ）中有 k 项[ E （ x ）多项式所表示的二进制位串中有 k 个1]，则表明发生了 k 个差错。一个突发性差错从 E （ x ）的角度可以这样来描述： E （ x ）多项式所表示的二进制位串中第1个为1的位到最后一个为1的位，而中间的位既可以为1，也可以为0，所有的其他的位都是0（突发性差错并不意味着所有的位都是有差错的，它只意味着至少第一位和最后一位是有差错的）。
图3-3 CRC的计算过程
接收端在收到带校验和的帧之后，用 G （ x ）来除它，也就是说，接收端计算（ T （ x ）+ E （ x ））/ G （ x ）。 T （ x ）/ G （ x ）是0，所以接收端计算的结果是 E （ x ）/ G （ x ）。如果差错多项式 E （ x ）恰好包含 G （ x ）这样的因子，则这样的差错将无法检测出来，除此之外的所有其他差错都能够检测出来。
假设帧在传输过程中只发生一位错，即 E （ x ）= x i ，这里的 i 决定了差错出现在哪一位。如果 G （ x ）包含两项或更多项，则 G （ x ）永远也不会被 E （ x ）除尽，也就是说，任何一位差错都能够被检测出来。
同样的道理，假设帧在传输过程中出现了两位差错，而且这两位差错是相互独立的，即 E （ x ）= x i + x j = x j （ x i-j +1），这里 i ＞ j 。如果假定 G （ x ）不能被 E （ x ）除尽，则所有的两位差错能够被检测到的充分条件是：对于任何小于等于 i-j 最大值（即小于等于最大帧长度）的 k 值， G （ x ）都不能被 x k +1除尽。简单的结论是：低阶的多项式可以保护很长的帧。例如，对于任何15＜ k ＜32768， x 15 + x 14 +1都不能除尽 x k +1。
如果有奇数个二进制位出现差错，则 E （ x ）包含奇数项（比如 x 5 + x 2 +1，而不是 x 2 +1）。有意思的是，在模2代数计算中，没有一个奇数项多项式包含 x +1因子。因此，只要生成多项式 G （ x ）中包含（ x +1）因子，我们就可以检测出所有奇数个位出错的情形。
最后，也是最重要的，带 r 个校验位的循环冗余校验可以检测到所有长度小于等于 r 的突发性差错。长度为 k 的突发性差错可以用 x i （ x k-i +…+1）来表示，这里 i 决定了突发性差错的位置离帧的最右端有多远。如果 G （ x ）包含一个 x 0 项，则它不可能有 x 1 项作为因子，所以，如果多项式 x k-i +…+1的阶小于 G （ x ）的阶，则余数永远不可能为0。
如果突发性差错的长度为 r +1，则当且仅当差错多项式 E （ x ）等于生成多项式 G （ x ）时，差错多项式 E （ x ）除以生成多项式 G （ x ）的余数才为0。根据突发性差错的定义，第一位和最后一位必须为1，所以差错多项式 E （ x ）是否与生成多项式 G （ x ）匹配取决于其他 r -1个中间位。如果所有的组合被认为是等概率的，则这样一个不正确的帧被当作正确帧接收的概率是（1/2） r -1 。
同样可以证明，当一个长度大于 r +1位的突发性差错发生时，或者几个短一点的突发性差错（加起来总的差错位数大于 r +1位）发生时，一个出错帧被当作正确帧接收的概率是（1/2） r 。这里假设所有位出错的概率是相同的。因此，可以得到下面的结论，即对于阶数为 r 的生成多项式 G （ x ），它能够检测的差错具有如下特性：
· 只要 G （ x ）中的 x r 和 x 0 项的系数不为0，就可以检测出所有1比特出差错的情况；
· 只要 G （ x ）中含有一个至少三项的因式，就可以检测出所有2比特出差错的情况；
· 只要 G （ x ）包含因式（ x +1），就可以检测出所有出现奇数比特出差错的情况；
· 可以检测到所有长度小于等于 r 的突发性差错。也能检测到大部分大于 r 比特的突发性差错。
目前已经有一些特殊的多项式成为循环冗余校验编码生成多项式的国际标准，如表3-1所示。
表3-1 常用的CRC生成多项式
其中，以太网使用CRC-32，HDLC使用CRC-CCITT，而ATM使用CRC-8、CRC-10和CRC-32。
最后，我们注意到，循环冗余校验算法看起来复杂，但在硬件上使用 r 比特移位寄存器和异或门（XOR）是比较容易实现的。移位寄存器的位数就等于生成多项式的阶（ r ）。图3-4显示了生成多项式 x 3 + x 2 +1的硬件实现。先在帧的后面附加 r 个0，然后从最高位开始输入到移位寄存器，正如上面例子中的长除法一样。当所有的比特都移入并进行了相应的异或操作后，移位寄存器就包含了余数，即CRC码（最高位在右边）。异或门的位置按照如下方式确定：如果移位寄存器中的各位从左到右标记了0到 r -1，那么，如果生成多项式中有 x i 项，就在 i 位之前放置一个异或门。因而，对于生成多项式 x 3 + x 2 +1，就在位置0和2之前放置一个异或门。
图3-4 用移位寄存器实现CRC
在TCP/IP协议栈中，IP、ICMP、UDP和TCP报文头都有检验和字段，大小都是16比特，算法基本上是一样的。
在发送端，为了计算校验和，把报文以16位二进制为单位进行反码相加（求和时遇到的任何溢出都被回卷相加），然后将累加的结果取反，得到二进制反码求和的结果就是校验和。
在接收端，将包括校验和在内所有字段以16位二进制为单位依次进行反码求和。由于接收端在计算校验和的过程中包含了校验和，如果报文在传输过程中没有发生任何差错，那么接收端计算的结果应该为全1。如果结果不是全1，那么表示报头在传输过程中出错。下面是RFC 1071中提供的C语言程序。
该程序使用反码求和。值得注意的是，if语句在while循环之内。如果sum有进位，那么把进位加到sum上（即首先把sum的最高位去掉，然后将sum加1），这称为回卷。图3-5给出了如何求校验和的一个实例。
图3-5 求校验和实例
在TCP/IP校验和中使用反码求和的优点是：不依赖系统是大端还是小端，计算和验证校验和比较简单、快速。
校验和算法比较简单，但校验和的差错检测能力较差。例如，假设报文中有2比特出错，而且这2比特刚刚好处在某2个16比特字的相同位置上，其中一个由“0”变为“1”，而另外一个由“1”变为“0”，但最终的校验和反映不出差错。另外，校验和算法对于将报文中的16位字重新排列也不能提供保护。尽管校验和算法在检错能力上相对较弱（主要是相比于前面介绍的CRC），但它在互联网中被大量使用，原因是该算法简单且易于用软件实现，它很好地兼顾了计算的简单性和差错检测的有效性，因此在互联网的许多协议（如IP、ICMP、UDP、TCP和OSPF）中得到了广泛应用。