循环冗余检验

来自EEWiki.

在数字数据通信中，由发送器发送的数据信号祯(Frame)在经由网络传到接收器后，由于多种原因可能导致错误位(bit errors)的出现，因此必须由接收器采取一定的措施探测出所有的错误位，并进而采取一定的措施予以修正。 CRC循环冗余校验就是一种有效的方法。

发送器和接收器约定选择同一个由n+1个位组成的二进制位列P作为校验列，发送器在数据祯的K个位信号后添加n个位(n < K)组成的FCS祯检验列(Frame Check Sequence)，以保证新组成的全部信号列值可以被预定的校验二进制位列P的值对二取模整除；接收器检验所接收到数据信号列值(含有数据信号祯和FCS祯检验列)是否能被校验列P对二取模整除，如果不能，则存在传输错误位。P被称为CRC循环冗余校验列，正确选择P可以提高CRC冗余校验的能力。可以证明，只要数据祯信号列M和校验列P是确定的，则可以唯一确定FCS祯检验列(也称为CRC冗余检验值)的各个位。FCS帧检验列可由下列方法求得：在M后添加n个零后对二取模整除以P所得的余数。

例如：如要传输的M=7位列为1011101，选定的P校验二进制位列为10101(共有n+1=5位)，对应的FCS帧校验列即为用1011101 0000(共有M+n=7+4=11位)对二取模整除以10101后的余数0111(共有n=4位)。因此，发送方应发送的全部数据列为10111010111。接收方将收到的11位数据对二取模整除以P校验二进制位列10101，如余数非0，则认为有传输错误位。

为了表示方便，实用时发送器和接收器共同约定选择的校验二进制位列P常被表示为具有二进制系数(1或0)的CRC标准校验多项式P(X)。CRC循环冗余校验常用的标准多项式P(X)

　　CRC(16位) = X^16+X^15+X^2+1

　　CRC(CCITT) = X^16+X^12+X^5+1

　　CRC(32位) =X^32+X^26+X^23+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1

以CRC(16位)多项式为例，其对应校验二进制位列为1 1000 0000 0000 0101。

CRC循环冗余校验具有比奇偶校验强得多的检错能力。可以证明：它可以检测出所有的单个位错、几乎所有的双个位错、低于P(X)对应二进制校验列位数的所有连续位错、大于或等于P(X)对应二进制校验列位数的绝大多数连续位错。但是，当传输中发生的错误多项式E(X)能被校验多项式P(X)对二取模整除时，它就不可能被P(X)探测出来，例如当E(X)=P(X)时。