08980b11ec484f6ee68d7c470fdaafb6
CRC 循环冗余校验

1 引言

  CRC循环冗余校验方式是通信领域中最为常用的校验方式。正好最近手上有个项目需要对传输数据进行循环冗余的校验,就借着这个机会,系统的整理一下循环冗余校验的知识。

2 数据校验

  当数据在通信信道传输时,并不能保证终端接收的数据与发送端数据完全一致。常见的数据通信问题有:
  (1)数据丢失:数据长度发送改变,丢失一位或者多位数据。
  (2)数据位改变:受传输过程外界因素干扰,导致数据位值发生改变。
  那么当接收端接收到数据后就需要对收到的数据进行校验,以保证数据的完整性和正确性。

3 奇偶校验

3.1 原理

  为了解决数据传输过程中可能存在数据错误的问题,有人提出了一种比较简单的方式——奇偶校验法。奇偶校验主要原理如下:
  在原始数据流的头部或者末尾添加一位bit,此bit用于校验此数据包的正确与否。例如:

原始码 奇校验(奇数个1) 偶校验(偶数个1)
1011000 10110000 10110001
1010000 10100001 10100000

3.2 优缺点

奇偶校验法优点:
  (1)原理简单,实现方便。
奇偶校验法缺点:
  (1)奇偶校验的检错率只有50%,因为只有奇数个数据位发生变化能检测到,如果偶数个数据位发生变化,奇偶校验方式不能检测出错误。
  (2)奇偶校验每传输一个字节都需要加一位校验位,对传输效率影响很大。
  (3)奇偶校验只能发现错误,但不能纠正错误,也就是说它只能告诉你出错了,但不能告诉你怎么出错了,一旦发现错误,只好重发。

4 循环冗余校验

4.1 生成多项式

  生成多项式将一个任意的二进制数转换为多项式形式得到的一个特征多项式:
  例如:二进制数 101011 ,对应的生成多项式为 :
  X6 + X4+X2 + X + 1。
  二进制数101111,对应的生成多项式为:
  X5+X3+X2+X+1。

4.2 模2运算

  模2运算是一种二进制算法。与四则运算相同,模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。而且,模2运算也使用与四则运算相同的运算符,即“+”表示模2加,“-”表示模2减,“×”或“·”表示模2乘,“÷”或“/”表示模2除。
  模2加减法运算其实就是异或运算,运算规则如下:

0 ± 0 = 0
1 ± 1 = 0
0 ± 1 = 1
1 ± 0 = 1
例如:1101 ± 1001 = 0100
计算过程如下:
          1 1 0 1 
        ± 1 0 0 1 
        -----------
          0 1 0 0

模2除法运算过程:
规则 : 设被除数为X,除数为P,余数为R。
  (1)被除数X除以P(对X和P做模2加减法),被除数首位为1时,商为1。当被除数首位为0时,商为0。
  (2)所得余数去除首位(左移一位)。
  R第一位为0,将其作为新的被除数,除以P,此时其首位为0,商即为0。
  R第一位为1,将其作为新的被除数,除以P,此时其首位为1,商即为1。
  (3)重复第2步直到R位数少于P位数。
例如:被除数为X = 1111000,除数P = 1101。运算过程如下:

1 0 1 1     //商
---------------
1 1 1 1 0 0 0     //被除数,注意首位为1
1 1 0 1           //被除数首位为1,除以除数
---------------
  0 1 0 0 0 0     //余数去除首位,作为新的被除数
  0 0 0 0         //被除数首位为0,除以0
---------------
    1 0 0 0 0     //余数去除首位,作为新的被除数
    1 1 0 1       //被除数首位为1,除以除数  
---------------
      1 0 1 0     //余数去除首位,作为新的被除数
      1 1 0 1     //被除数首位为1,除以除数
---------------
      0 1 1 1     //余数,此时余数位数少于除数,不能继续除了(忽略首位0)
--------------------- 

详细过程
第1步:

      1         //商
-------------
1 1 1 1 0 0 0   //被除数,注意首位为1
1 1 0 1         //除数
-------------
0 0 1 0 0 0 0   //余数,模2运算后结果

第2步:余数去除首位(左移一位),当第一位为0时,除以0;为1时,除以除数。

1 0        //商
---------------
  0 1 0 0 0 0    //余数去除首位,作为新的被除数
  0 0 0 0        //被除数首位为0,除以0
---------------
  0 1 0 0 0 0    //余数,模2运算后结果
--------------------- 

第3步:
```
1 0 1 //商

top Created with Sketch.