1.CRC简介

CRC循环冗余校验码是数据通信中的一种查错校验码。

2.CRC原理

CRC 算法的基本思想是将传输的数据[M(X)] 当做一个位数很长的数。将这个数除以另一个数[G(X)] ,得到的余数[R(X)] 作为校验数据附加到原数据后面,组成循环校验码。

M(X)代表待编码的有效信息
G(X)代表约定好的多项式
R(X)代表代表检验位

由于，CRC的结构 = 信息位(N位) + 校验位(K位)

所以，CRC编码 = M(X) + R(X)

3.CRC编码方法

• 把待编码的N位有效信息位表示为多项式M(X)

• 把M(X)左移K位，得到M(X)*X^K，这样就空出了K位，以便拼接K位余数，这里的K位是由多项式G(X)的最高位决定的

• 选取一个生成多项式G(x)，对M(X)*X^K做模二除 (多项式G(X)一般会直接给你，模二除看下面例子，实质是异或运算)，以下是运算公式

  ( M(X) * X^K ) / G(X) = Q(X) + R(X) / G(X)

  这里的Q(X)是商，它本身不重要，这里最重要的是求出余数R(X)

• 将信息位M(X)与余数R(X)拼接起来，构成CRC循环冗余校验码

  CRC编码 = M(X) + R(X)

4.举个栗子

题目：选择产生多项式位1011，把4位有效信息1100编成CRC码

• M(X) = X^3 + X^2 = 1100

• M(X) * X^3 = X^6 + X^5 = 1100000 （这里多项式最高位位3，左移3位）

• G(X) = X^3 +X +1 = 1011

• ( M(X) * X^K ) / G(X) = 1100000 / 1011 = 1110 + 010 / 1011 (关键，这里进行模二运算，实质上是异或运算，求R(X))
  经运算，此时确定R(X)为 010

• 此时得出CRC编码 = M(X) + R(X) = 1100010

5.CRC编码的校验

校验原理：将得到的CRC码用约定的G(X)去除，余数为0，结果正确 ，某一位出错，则余数不为0

纠错的话，与G(X)的选择有关系，这方面比较深，考研大纲不考察纠错这块的知识点

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

CRC校验原理虽然看起来比较复杂，其实也不难理解，其根本思想就是先在要发送的帧后面附加一个数，生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除。这里不是直接采用二进制除法，而是采用一种称之为“模2除法”。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理，所以结果应该是没有余数，结果能够被除数整除。如果有余数，则表明该帧在传输过程中出现了差错。

        这里，为了能够对CRC校验有深入了解，我们来介绍一下模2除法。与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2减法运算实际上是按位异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如下图所示，二进制的数101000110100000除以110101，结果得到商为1101010110，余数为01110
 

 CRC校验算法，说白了，就是把需要校验的数据与多项式进行循环异或（XOR）。下面举个例子说明一下计算的过程： 
使用多项式：x8+x5+x4+1（二进制为：100110001） 
计算一个字节：0x11（二进制为：00010001） 
计算步骤

A、 将需要计算的数据左移8位， 
移位后数据为：0001 0001 0000 000 
B、 先进行高9bit异或（多项式为9bit），0001 0001 0000 0000，因为高9bit的 
最高bit为0，不需要进行异或，同理，接下来的两bit也是0，也不需要进行进行异或。 
这样处理后数据为：1 0001 0000 0000； 
C、 接下来最高位为1，需要进行异或操作了

 从上面的计算过程可以看到，多项式最高位为1，遇到需要异或数据最高位为1时， 
才进行异或计算，并且异或后，最高位就为0了，最高位为0，下次也不需要异或了， 
这样需要采用代码计算的方式，就可以把最高位去掉，不需要异或，最后结果也是一样的。 
对于上面的计算过程，采用代码实现的方式如下：

unsigned char cal_table_high_first(unsigned char value)
{
    unsigned char i, crc;
 
    crc = value;
    /* 数据往左移了8位，需要计算8次 */
    for (i=8; i>0; --i)
    { 
        if (crc & 0x80)  /* 判断最高位是否为1 */
        {
        /* 最高位为1，不需要异或，往左移一位，然后与0x31异或 */
        /* 0x31(多项式：x8+x5+x4+1，100110001)，最高位不需要异或，直接去掉 */
            crc = (crc << 1) ^ 0x31;        }
        else
        {
            /* 最高位为0时，不需要异或，整体数据往左移一位 */
            crc = (crc << 1);
        }
    }
 
    return crc;
}

上面的代码是计算一个字节数据的crc结果，如果是计算多个字节的crc结果，也是比较简单的，先计算第一个字节的crc结果，然后把第一个字节的crc结果与第二个字节进行异或， 
异或后的值再进行一次crc计算就可以了，多个字节也是反复这过程就好，如下为多个字节 
的crc校验代码：

unsigned char crc_high_first(unsigned char *ptr, unsigned char len)
{
    unsigned char i; 
    unsigned char crc=0x00； /* 计算的初始crc值 */ 
 
    while(len--)
    {
        crc ^= *ptr++;  /* 每次先与需要计算的数据异或,计算完指向下一数据 */  
        for (i=8; i>0; --i)   /* 下面这段计算过程与计算一个字节crc一样 */  
        { 
            if (crc & 0x80)
                crc = (crc << 1) ^ 0x31;
            else
                crc = (crc << 1);
        }
    }
 
    return (crc); 
}

上面的crc计算是纯采用逻辑运行的方式，可以看到，需要的运行量也是不少的，每一个字节都需要进行8次判断、移位、或异或操作。可以采用查表法，大大减少计算量，先计算出 
0x00~0xFF每一个字节的crc校验结果，后面就可以通过表来查出每个字节的crc结果，大大 
减少计算量。 
下面是一个表生成程序： 
（生成表对应多项式：0x31(多项式：x8+x5+x4+1，100110001)）

    void  create_crc_table(void)
    {
        unsigned short i;
        unsigned char j;
 
        for (i=0; i<=0xFF; i++)
        {
            if (0 == (i%16))
                printf("\n");
 
            j = i&0xFF;
            printf("0x%.2x, ", cal_table_high_first (j));  /*依次计算每个字节的crc校验值*/
        }
    }
得到的表整理后如下：

static const unsigned char crc_table[] =
{
    0x00,0x31,0x62,0x53,0xc4,0xf5,0xa6,0x97,0xb9,0x88,0xdb,0xea,0x7d,0x4c,0x1f,0x2e,
    0x43,0x72,0x21,0x10,0x87,0xb6,0xe5,0xd4,0xfa,0xcb,0x98,0xa9,0x3e,0x0f,0x5c,0x6d,
    0x86,0xb7,0xe4,0xd5,0x42,0x73,0x20,0x11,0x3f,0x0e,0x5d,0x6c,0xfb,0xca,0x99,0xa8,
    0xc5,0xf4,0xa7,0x96,0x01,0x30,0x63,0x52,0x7c,0x4d,0x1e,0x2f,0xb8,0x89,0xda,0xeb,
    0x3d,0x0c,0x5f,0x6e,0xf9,0xc8,0x9b,0xaa,0x84,0xb5,0xe6,0xd7,0x40,0x71,0x22,0x13,
    0x7e,0x4f,0x1c,0x2d,0xba,0x8b,0xd8,0xe9,0xc7,0xf6,0xa5,0x94,0x03,0x32,0x61,0x50,
    0xbb,0x8a,0xd9,0xe8,0x7f,0x4e,0x1d,0x2c,0x02,0x33,0x60,0x51,0xc6,0xf7,0xa4,0x95,
    0xf8,0xc9,0x9a,0xab,0x3c,0x0d,0x5e,0x6f,0x41,0x70,0x23,0x12,0x85,0xb4,0xe7,0xd6,
    0x7a,0x4b,0x18,0x29,0xbe,0x8f,0xdc,0xed,0xc3,0xf2,0xa1,0x90,0x07,0x36,0x65,0x54,
    0x39,0x08,0x5b,0x6a,0xfd,0xcc,0x9f,0xae,0x80,0xb1,0xe2,0xd3,0x44,0x75,0x26,0x17,
    0xfc,0xcd,0x9e,0xaf,0x38,0x09,0x5a,0x6b,0x45,0x74,0x27,0x16,0x81,0xb0,0xe3,0xd2,
    0xbf,0x8e,0xdd,0xec,0x7b,0x4a,0x19,0x28,0x06,0x37,0x64,0x55,0xc2,0xf3,0xa0,0x91,
    0x47,0x76,0x25,0x14,0x83,0xb2,0xe1,0xd0,0xfe,0xcf,0x9c,0xad,0x3a,0x0b,0x58,0x69,
    0x04,0x35,0x66,0x57,0xc0,0xf1,0xa2,0x93,0xbd,0x8c,0xdf,0xee,0x79,0x48,0x1b,0x2a,
    0xc1,0xf0,0xa3,0x92,0x05,0x34,0x67,0x56,0x78,0x49,0x1a,0x2b,0xbc,0x8d,0xde,0xef,
    0x82,0xb3,0xe0,0xd1,0x46,0x77,0x24,0x15,0x3b,0x0a,0x59,0x68,0xff,0xce,0x9d,0xac
}；
采用查表法计算crc代码如下：

unsigned char cal_crc_table(unsigned char *ptr, unsigned char len) 
{
    unsigned char  crc = 0x00;
 
    while (len--)
    {
        crc = crc_table[crc ^ *ptr++];
    }
    return (crc);
}
 

1 产生原理

循环冗余校验码Cyclic Redundancy Check（CRC）

简介：在发送端根据要传送的K位二进制码序列，以一定的规则产生一个校验用的r位监督码（CRC码），附在信息后面组成n=k+r位的码发出去。这种编码也叫（n,k）码。对于一个给定的（n,k）码，存在一个高次幂为r的多项式G(x)，根据多项式G(x)可以生成k位信息的校验码，G(x)叫做这个CRC码的生成多项式, 生成多项式的最高位和最低位必是1。

1.1 CRC可检测的错误？

• 突发长度小于n-k+1的突发错误；
• 大部分突发长度等于n-k+1的突发错误，其中不可检出的占2-(n-k-1)；
• 大部分突发长度大于n-k+1的突发错误，其中不可检出的占2-(n-k)；
• 所有与许用码组 码距 小于dmin-1的错误及所有奇数个错误。

1.2 CRC生成过程？

生成过程：发送信息C(x)左移r位，表示为C(x)×2^{r，C(x)右边空出的r位就是校验码的位置。通过C(x)×2}r模2除以生成多项式G(x)得到的余数就是校验码。

1.3 接收过程？

接收过程：

1. 计算CRC比较。
2. 收到的二进制序列（信息码+循环码）除以多项式，如果余数为0，则说明传输过程无错误发生。

2 CRC 的计算

以输入数据0x5a，G(x)=x^8+x^2+x+1计算为例。

2.1 手算

首先了解模2运算：
模2加：0+0=0，0+1=1，1+1=0 -> a(模2加)b = a⊕b
模2减：0-0=0，0-1=1，1-0=1，1-1=0 -> a(模2减)b = a⊕b
模2乘：0×0=0，0×1=0，1×1=1
模2除：0/1=0，1/1=1

根据生成过程：C(x)×2^r模2除以生成多项式G(x)得到的余数就是校验码。
G(x)对应：0x107

运算过程减法为模2减，即异或运算。
设余数为R[8:0]，注意的是，当 R[7] 为1，下一商位为1，当 R[7] 为0，下一商位为0。
其他规则与正常二进制除法一致。

可以看到每次运算的结果：

最终的到的余数为：0x81，即我们需要的CRC码，0x5a编码之后为 0x5a|0x81。

2.1 在线计算器

CRC（循环冗余校验）在线计算

网页就有各参数的介绍。
需要注意的是

• POLY：生成项的简写，以16进制表示。忽略了最高位的"1"。
• INIT：这是算法开始时寄存器（crc）的初始化预置值，十六进制表示。手动计算过程初始值是0x00。

3 Verilog 实现

3.1 线性反馈移位寄存器（LFSR）循环码编码

以上的计算过程很多文章都有介绍，但是都没有介绍为什么是题目中的结构？
比如为什么 Verilog实现串行CRC-8，G(D)=D8+D2+D+1，电路结构如下？

其实这是线性反馈移位寄存器（LFSR）循环码编码。

引用《数字通信（第四版）John G.Proakis著.张力军译》8.1.3 循环码的内容：

对于CRC-8进行信源0x5a的校验，移位运算过程为：
信源数据的逐个输入等效于把0x5a（8’b01011010）移位后的 16’b0101_1010_0000_0000 拆分为：

1. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 = 商0…余 R1:0000_0000

                                0
                 ________________________
   8’b1_0000_0111|16'b0000_0000_0000_0000
                 /-   0000_0000_0 
                     ____________
                 =R1: 0000_0000_0     
   

   

   这一步比较直观。所以在这我们就知道为什么在线计算器需要设置初始值？嘿嘿

2. 16’b0100_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R1 = 商1…余 R2: 0000_0111

                                01
                 ________________________
   8’b1_0000_0111|16'b0100_0000_0000_0000
                 /-    100_0001_11   
                  +R1: 0000_0000_0
                      ____________ 
                  =R2: 0000_0011_1
                       
   

   

   这一步值得注意的是生成多项式为0的位可以想象有一个C_(i-1) ⊕ 0，只不过与结果为C_(i-1)省略了，因为加减都是等效于异或，以此实现加上上一步的余数减去因式。

3. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R2 = 商0…余 R3:0000_1110:

4. 16’b0001_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R3 = 商1…余 R4:0001_1011:

5. 16’b0000_1000_0000_0000 模2除 9’b1_0000_0111 ⊕ R4 = 商1…余 R5:1000_1100:

6. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R5 = 商0…余 R6:0110_0010:

7. 16’b0000_0010_0000_0000 模2除 9’b1_0000_0111 ⊕ R6 = 商1…余 R7:1100_0001:

8. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R7 = 商1…余 R8:1000_0001:

可以看到，这其实就是对应我们模2除运算的过程。

3.2 Verilog代码

OutputLogic可以在线生成CRC代码，我们在生成的基础上改就好了。