循环冗余校验（CRC）优化技巧

奇偶检验码虽然简单，但漏检率太高。目前应用广泛的差错检测技术是循环冗余码校验（CRC，Cyclic Redundancy Check）。循环冗余校验方法是数据通信中错码检查与纠正方法中非常重要的一种。其优点是对随机错码和突发错码均能以较低的冗余度进行严格检查。其方法是在发送端产生一个循环冗余校验码，附加在信息位后而一起发到接收端，接收端将收到的信息按发送端形成循环冗余校验码同样的算法进行校验，若有错，需要重发。

CRC码采用的是一种多项式的编码方式。把要发送的数据位串看成系数只能是“1”成“0”的多项式。一个k位的数据块可以看成从Xk-1到X0的k项多项式的系数序列。左边的最高位是Xk-1的系数；下一位是Xk-2的系数，以此类推。这个多项式的阶数为k-1。例如，110001有6位，表示成多项式是X5+X4+X0，因多项式系数分别是1、1、0、0、0和1。多项式的运算以2为模，加减法时不进借位，即逻辑异或运算。除法中的减法也是异或运算。

例如，代码1011011对应的多项式为x6+x4+x3+x+1，而多项式x5+x4+x2+x对应的代码为110110。

首先，发送方和接收方必须事先约定一个生成多项式G（x），该生成多项式的最高位和最低位必须为1。设要发送的信息为K（x），加在信息位后面的校验位为R（x），因此循环码的编码过程就是由K（x）和G（x）求R（x）的过程。

接收方收到带有校验码的数据T（x）时用G（x）去除T（x），若为0，表示没有出错。因此发送方生成R（x）的方法是用G（x）去除xrK（x）得到的余数就是R（x）（r为余数的位数）。(www.xing528.com)

例如，信息位1010001：K（x）=x6+x4+1；生成多项式G（x）=x4+x2+x+1（10111），取r=4，则用10111去除x4 K（x）（10100010000），余数为1101，即为冗余校验码。T（x）=10100011101。

采用CRC码时，发方与收方必须事先约定一个生成多项式G（x），并且G（x）的最高位和最低位系数必须是1。要计算m位数据块的M（x）的校验和，生成多项式必须比该多项式短。基本思想是：将校验和附加在数据块的末尾，使这个带校验和的多项式能被G（x）除尽。当接收方收到带校验和的数据块时，用G（x）去除它，如果有余数，则传输有错误，再请求重传。

循环码具有良好的结构，易于实现编码、译码，检错能力强，所以在计算机系统和计算机通信网络中得到了广泛的应用。