CRC校验

CRC循环冗余校验码(Cyclic Redundancy Check):是数据通讯领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选择。

    循环冗余校验码(CRC)的基本原理是：长为K位的信息码，后拼接R位的校验码，整个编码长度为N位，这种编码又叫(N, K)码。对于一个给定的(N, K)，可以证明存在一个最高次幂为(N - K) = R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。校验码的具体生成过程：假设发送信息用信息多项式C(x)表示，首先将C(x)左移R位，相当于C(x)乘以2的R次方，这样C(x)的右边就会空出R位，即为校验码的位置，用C(x)乘以2的R次方得到的数据，除以生成多项式G(x)得到余数就是校验码。

2 相关概念及应满足的条件：

k位信息码，比如要传送的信息为：1111，k即为4(bit)

G(x)生成多项式，相对应的R+1位的二进制数码，比如G(x)=x^4+x^3+x+1， 二进制数据为11011

应满足的条件：

a、生成多项式的最高位和最低位必须为1。

b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。

c、不同位发生错误时，应该使余数不同。

d、对余数继续做除，应使余数循环。

3 CRC码的生成步骤

1、将x的最高次幂为R的生成多项式G(x)转换成对应的R+1位二进制数。

2、将信息码左移R位，相当于对应的信息多项式C(x)*x。

3、用生成多项式（二进制数）对信息码做除，得到R位的余数。

4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。

【例】假设使用的生成多项式是G(x)=x^3+x+1。4位的原始报文为1010，求编码后的报文。

解：

1、将生成多项式G(x)=x^3+x+1转换成对应的二进制除数1011。

2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000

3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除，相当于按位异或：

1010000

1011

------------------

1000

1011

------------------

011

得到的余位011，所以最终编码为：1010011