一、CRC循环校验码
1、理论解释：
(1) 预先确定的多项式G(X)：
Gx：生成码，这个是可以人为设定的，它就是CRC里面所谓的生成多项式对应的系数。
其中，Gx 的首位和最后一位的系数必须为1
(2) 信息码，待发送的原始数据序列：Kx
Kx：信息码，就是指要发送的信息，是一组1、0组合的字符串（当然可以看作是整数，或者浮点数等，在程序里是把它看作字符串的，长度可以自定）。
(3) CRC码/循环冗余校验码（CRC），简称循环码
Rx：指冗余码。
(4) 信息码+冗余码/（最终接收到的数据也就是经过冗余码处理后的信息码）
Tx：指真正发送出去的码字
- 举例：
以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC码）。
K(X)>>16=G(x)Q(x)+R(x)
求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码
接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。
- 示例计算：
下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X） = X^4 + X^3 + 1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：
（1）首先把生成多项式转换成二进制数，由G（X） = X^4 + X^3 + 1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。
（2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即CRC校验码为0100，如下图所示。注意参考前面介绍的“模2除法”运算法则。
（3）把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。
（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。
通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。
- 百度百科中的流程解释：
实际的CRC校验码生成是采用二进制的模2算法（即减法不借位、加法不进位）计算出来的，这是一种异或操作。下面通过一些例子来进一步解释CRC的基本工作原理。假设：
(1) 设约定的生成多项式为G(x)=x4+x+1，其二进制表示为10011，共5位，其中k=4。
(2) 假设要发送数据序列的二进制为101011(即f(x))，共6位。
(3) 在要发送的数据后面加4个0(生成f(x)*xk)/左移4位，二进制表示为1010110000，共10位。
(4) 用生成多项式的二进制表示10011去除乘积1010110000，按模2算法求得余数比特序列为0100（注意余数一定是k位的）。
(5) 将余数添加到要发送的数据后面，得到真正要发送的数据的比特流：1010110100，其中前6位为原始数据，后4位为CRC校验码。
(6) 接收端在接收到带CRC校验码的数据后，如果数据在传输过程中没有出错，将一定能够被相同的生成多项式G(x)除尽，如果数据在传输中出现错误，生成多项式G(x)去除后得到的结果肯定不为0。
2、编码实现：
如在IBM的SDLC(同步数据链路控制)规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式为g(x)= _x_^16 + _x^_15 + _x^_2 +1（对应二进制比特串为：11000000000000101）
即：crc16 = 0x00018005; //生成码CRC-16:
对应的二进制位：11000000000000101 生成码为17位，冗余码16位
其中，生成码和信息码之间位异或(^)运算；
参考：
1、循环冗余校验码
3、CRC校验算法学习(这个算法看了很多遍了,都是囫囵吞枣,这次将资料拷贝到这里,好好学习一下)
5、CRC校验
7、 CRC循环校验C语言版本
评论（0）
您还未登录，请登录后发表或查看评论