循环冗余校验

循环冗余码校验（Cyclic Redundancy Check， CRC）是目前在磁表面存储器中应用最广泛的一种校验方法，也是多机网络通信中常用的校验方法。它所约定的校验规则是：让校验码处以某个约定代码，如果余数为0，则表明代码正确，否则利用余数指明出错位。

任意一串数码，很可能除不尽，将产生一个余数。如果让被除数减去余数，势必能为约定除数所除尽。但减法操作需要借位运算，难以用简单的拼装方法实现编码。因此我们采用一种模2运算，即通过模2减来实现模2除，以模2加将所得余数拼接在被除数后面，形成一个能除尽的校验码。当然，在采用模2除后，对除数的选择是有条件的。

这里所讲的模2运算是一种以按位加减为基础的四则运算，不考虑进位和借位。注意，它与以2为摸得定点小数运算时两个不同的概念。因此，模2加减即按位加减，逻辑上等价于“异或”运算，因此可用异或门实现。

待编码的信息是一串代码，可能是表示数值大小的数字，也可能是字符编码，或其他性质的代码。在模2除中，暂将它视为数字，可用多项式来描述。我们定义待编信息（被除数）为$M(x)$；约定的除数为$G(x)$，因为它是用来产生余数的，所以$G(x)$又被成为生成多项式，所产生的余数$R(x)$相当于所配的冗余校验位。

编码方法

1、将待编码的$k$位有效信息$M(x)$左移$r$位，得$M(x) \cdot x^{r}$。这样做的目的是空出$r$位，以便拼装将来求得的$r$位余数。

2、选取一个$r+1$位的生成多项式$G(x)$。对$M(x) \cdot x ^ r$作模2除。

$\frac{M(x)x^r}{G(x)}=Q(x)+\frac{R(x)}{G(x)}$ 模2除

要产生$r$位余数，所以除数应为$r+1$位。

3、将左移$r$位的待编码有效信息，与余数$R(x)$模2加，即拼接得到循环校验码。

$M(x) \cdot x^{r}+R(x)=Q(x) \cdot G(x)$ 模2加

在按位运算中，“模2加”等价于“异或”运算。$M(x) \cdot x^{r}$的末尾$r$位是0，所以再与余数$R(x)$做“模2加”实际上是将$M(x)$与$R(x)$拼接。拼接成的校验码必定能被约定的$G(x)$除尽。在本节中，将$M(x) \cdot x^{r}+R(x)$称为循环校验码，即CRC码。但在许多磁表面存储器的记录格式中，有时候只将$R(x)$对应的这部分代码称为校验码。

$\tiny{本段内容选自由中国工信出版集团和电子工业出版社联合出版的《计算机组成原理（第5版）》，侵删}$