循环冗余校验码

具有检错、纠错能力的校验码

循环冗余校验码（CRC），简称循环码，是一种常用的、具有检错、纠错能力的校验码，在早期的通信中运用广泛。循环冗余校验码常用于外存储器和计算机同步通信的数据校验。奇偶校验码和海明校验码都是采用奇偶检测为手段检错和纠错的(奇偶校验码不具有纠错能力)，而循环冗余校验则是通过某种数学运算来建立数据位和校验位的约定关系的。

简介

循环冗余校验码(cyclic redundancy check)简称CRC（循环码），是一种能力相当强的检错、纠错码，并且实现编码和检码的电路比较简单，常用于串行传送（二进制位串沿一条信号线逐位传送）的辅助存储器与主机的数据通信和计算机网络中。

循环码是指通过某种数学运算实现有效信息与校验位之间的循环校验（而海明码是一种多重校验）。

这种编码基本思想是将要传送的信息M(X)表示为一个多项式L，用L除以一个预先确定的多项式G(X)，得到的余式就是所需的循环冗余校验码。

这种校验又称多项式校验。

理论上可以证明循环冗余校验码的检错能力有以下特点：①可检测出所有奇数位错；②可检测出所有双比特的错；③可检测出所有小于、等于校验位长度的突发错。

校验位的生成

循环冗余校验码由信息码n位和校验码k位构成。k位校验位拼接在n位数据位后面，n+k为循环冗余校验码的字长，又称这个校验码（n+k,n）码。

n位信息位可以表示成为一个报文多项式M(x)，最高幂次是xn-1。约定的生成多项式G(x)是一个k+1位的二进制数，最高幂次是xk。将M(x)乘以xk，即左移k位后，除以G(x)，得到的k位余数就是校验位。这里的除法运算是模2除法，即当部分余数首位是1时商取1，反之商取0。然后每一位的减法运算是按位减，不产生借位。

CRC检错和纠错

CRC码存储或传送后，在接收方进行校验过程，以判断数据是否有错，若有错则进行纠错。一个CRC码一定能被生成多项式整除，所以在接收方对码字用同样的生成多项式相除，如果余数为0，则码字没有错误；若余数不为0，则说明某位出错，不同的出错位置余数不同。对（n，k）码制，在生成多项式确定时，出错位置和余数的对应关系是确定的。

检错计算举例

实际的CRC校验码生成是采用二进制的模2算法（即减法不借位、加法不进位）计算出来的，这是一种异或操作。下面通过一些例子来进一步解释CRC的基本工作原理。假设：

(1)设约定的生成多项式为G(x)=x4+x+1，其二进制表示为10011，共5位，其中k=4。

(2)假设要发送数据序列的二进制为101011(即f(x))，共6位。

(3)在要发送的数据后面加4个0(生成f(x)*xk)，二进制表示为1010110000，共10位。

(4)用生成多项式的二进制表示10011去除乘积1010110000，按模2算法求得余数比特序列为0100（注意余数一定是k位的）。

(5)将余数添加到要发送的数据后面，得到真正要发送的数据的比特流：1010110100，其中前6位为原始数据，后4位为CRC校验码。

(6)接收端在接收到带CRC校验码的数据后，如果数据在传输过程中没有出错，将一定能够被相同的生成多项式G(x)除尽，如果数据在传输中出现错误，生成多项式G(x)去除后得到的结果肯定不为0。

全国各地天气预报查询

上海市

市辖区

云南省