循环冗余校验码原理

CRC校验采用多项式编码方法，如一个8位二进制数(B7B6B5B4B3B2B1B0)可以用7阶二进制码多项式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。
　　例如11000001可表示为
　　1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0
　　一般说，n位二进制数可用(n-1)阶多项式表示。它把要发送的数据位串看成是系数只能为“1”或“0”的多项式。一个n位的数据块可以看成是从Xn-1到X0的n项多项式的系数序列，位于数据块左边的最高位是Xn-1项的系数，次高位是Xn-2项的系数，依此类推，位于数据块右边的最低位是X0项的系数，这个多项式的阶数为n-1。
　　多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进、错位，如同逻辑异或运算。
　　采用CRC校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。设m位数据块的多项式为M(X)，生成多项式G(X)的阶数必需比M(X)的阶数低。CRC校验码的检错原理是：发送方先为数据块生成CRC校验码，使这个CRC校验码的多项式能被G(X)除尽，实际发送此CRC校验码；接收方用收到的CRC校验码除以G(X)，如果能除尽，表明传输正确，否则，表示有传输错误，请求重发。
　　生成数据块的CRC校验码的方法是：
　　(1)   设G(X)为r阶，在数据块末尾添加r个0，使数据块为m+r位，则相应的多项式为XrM(X)；
　　(2)   以2为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串；
　　(3)   以2为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC校验码位串。
　　例如，设要发送的数据为1101011011，G(X)=X4+X+1，则首先在发送数据块的末尾加4个0，得到11010110110000，然后用G(X)的位串10011去除，再用11010110110000减去余数位串1110，得到的即为CRC位串11010110111110，将对应多项式称为T(X)，显然，T(X)能被G(X)除尽。这样，一旦接收到的CRC位串不能被同样的G(X)的位串除尽，那么一定有传输错误。
　　当使用CRC校验码进行差错控制时，除了为G(X)的整数倍的差错多项式不能被检测外，其它差错均能被查出。CRC校验码的差错控制效果取决于G(X)的阶数，阶数越高，效果越好。目前，常用的有两种生成多项式G(X)的方法，分别是：
　　CRC-16　　X16+X15+X2+1
　　CCITT　　X16+X12+X5+1
　　CRC校验码实际上是一种线性码，将任意CRC校验码循环移位后仍然是一个CRC校验码。由于它有良好的结构，检错能力强，易于实现硬件编、译码，因此在数据通信系统中得到广泛的应用。