《计算机组成与体系结构（原书第4版）》 —2.7　错误检测与纠错

2.7　错误检测与纠错

没有通信信道或存储介质可以完全无错误。这在物理上是不可能的。随着传输速率的增加，位传输变得更紧密，随着每平方毫米存储空间可以保存更多位，磁通量密度也增加了。错误率与每秒传输的位数或每平方毫米磁存储器的位数成正比。

在2.6.3节中，我们提到可以将一个奇偶校验位添加到ASCII字节中以帮助检测传输过程中是否有已损坏的位。这种错误检测方法的有效性具有局限性：简单的奇偶校验只能检测到每个字节中的奇数个错误。如果发生两个错误，我们无法检测出。不正确的数据被误认为是正确的数据。如果这种错误发生在发送财务信息或程序代码中，结果可能是灾难性的。

当你阅读下面的部分时，你应该记住创建无差错介质是不可能的，100％的检测或者纠正在介质中出现的错误也是不可能。错误检测和纠错是在设计计算机系统时必须进行的另一项研究。因此，构建良好的错误控制系统是在合理的经济范围内检测或纠正“合理”数量“合理”预期错误的系统。（注：单词“合理”是由实现决定的。）

2.7.1　循环冗余校验

校验和用于各种各样的编码系统，从条形码到国际标准图书编号。这些都是自检码，它们可以很快地显示前一个数字是否被误读了。循环冗余校验(CRC）是一种校验和，它主要用于确定在数据通信中在大的数据块或信息字节流内是否发生了错误。要检查的数据块越大，提供足够保护的校验和也就越大。校验和和循环冗余校验是两种类型的系统错误检测方案，这意味着错误检查位被附加到原始信息字节上了。该组错误检查位称为特征位。添加错误校验位，原始信息字节不会改变。

在循环冗余校验中，“循环”这个词是指这种错误控制系统背后的抽象的数学理论。虽然这个理论的讨论超出了本文的范围，但是我们可以演示该方法是如何工作的，以帮助理解它经济地检测传输错误的能力。

模2运算

你可能会熟悉超过一个模数的整数运算。每天告诉你时间的十二小时的钟表是一个模数为12的系统。当我们给11:00加上2小时，我们得到1:00。模2运算使用两个不借位或不进位的二进制操作数，结果同样是二进制数，也是模2系统的一个成员。由于加法中闭包和恒等元素的存在，数学家说这个模2系统形成了一个代数场。

加法规则如下：

0+0＝0

0+1＝1

1+0＝1

1+1＝0

例2.38计算10112和1102的模2和。

这个总和仅在模2运算中有意义。

模2除法是通过使用模2加法规则进行一系列部分和的运算。例2.39说明了该过程。

例2.39计算10010112除以10112的商和余数。

商为10102。

模2域上的算术运算有等价的多项式，它们类似于整数域上的多项式。我们已经看到位置数字系统如何表示增加的基数指数。例如：

通过让X=2，二进制数10112可成为多项式的缩写：

这样，在例2.39中的除法就变为多项式运算：

计算和使用CRC

在进行了如上冗长的介绍后，我们下面将通过一个具体的例子来展示如何构造CRC：

1.假设信息字节I=10010112。（可以使用任意数量的字节形成消息块。）

2.发送方和接收方同意任意二进制模式，如P=10112。（以1开始和结束的模式工作得最好。）

3.I向左移动一个小于P中的位数，给出一个新的I=10010110002。

4.使用I作为被除数和P作为除数，执行模2除法（如例2.39所示）。我们忽略商，并注意余数是1002。这个余数就是实际的CRC校验和。

5.将余数与I相加，给出消息M：

6.消息接收方使用相反的过程对M进行解码和检查。直到M被P整除：

注意：相反的过程将包括附加的余数。

非零的余数表示在M的传输中发生了错误。当使用大的多项式时，该方法效果最好。为此广泛使用4种标准多项式：

●lCRC-CCITT（ITU-T）:X16+X12+X5+1

●lCRC-12:X12+X11+X3+X2+X+1

●lCRC-16（ANSI）:X16+X15+X2+1

●lCRC-32:X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X+1

CRC-CCITT、CRC-12和CRC-16在一对字节上操作；CRC-32使用4字节，它适用于32位字的系统操作。已经证明了使用这些多项式的CRC可以检测超过99.8％单个位的错误。

可以使用查找表有效地实现CRC，而不是用每个字节计算余数。每个可能的输入位模式生成的余数可以直接“烧”到通信和存储电子器件中。与16或32个周期的除法操作相比，用一个周期查找表就可以找到余数。显然，这需要在速度和更复杂的控制电路的成本之间进行权衡。