CRC算法原理及其Verilog实现

一．CRC简介

CRC校验是一种在数据通信系统和其它串行传输系统中广泛使用的错误检测手段。通用的CRC标准有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在网络通信系统中应用最广泛的是CRC-32标准。本文将以CRC-32为例，说明CRC编码的实现方式以及如何用verilog语言对CRC编码进行描述。

二．模2运算

   在说明CRC编码方式之前，首先介绍一下模2运算法则，在CRC运算过程中会使用到模2除法运算。模2运算是一种二进制运算法则，与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种运算。模2运算用“+”表示加法运算，用“-”、“×”或“.”、“/”分别表示减法、乘法和除法运算。与普通四则运算法则不同的是，模2加法是不带进位的二进制加法运算，模2减法是不带借位的二进制减法运算。同时，模2乘法在累加中间结果时采用的是模2加法运算；模2除法求商过程中余数减除数采用的是模2减法运算。因此，两个二进制数进行模2加减法运算时，相当于两个二进制数进行按位异或运算，每一位的结果只与两个数的当前位有关。模2除法在确定商时，与普通二进制除法也略有区别。普通二进制除法中，当余数小于除数时，当前位的商为0，当余数大于等于除数时，当前位的商为1。模2除法在确定当前位的商时，只关心余数的首位，首位为1则商为1，首位为0则商为0。

1.模2加法的定义：

     0+0=0，0+1=1，1+0=1，1+1=0。

  举例如下：

     1010+0110=1100。

2.模2减法的定义：

     0-0=0，0-1=1，1-0=1，1-1=0。

  举例如下：

     1010-0110=1100。

3.模2乘法的定义：

     0×0=0，0×1=0，1×0=0，1×1=1。

  举例如下：

     1011×101=100111

  列竖式计算：

       1011

     × 101

   ——————

       1011

      0000

       1011

   ——————

     100111

  其中横线之间的累加过程，采用的是2进制加法，不进位。

4.模2除法：

     0/1=0，1/1=1。

  举例如下：

     1011/101=10，余数为100。

  列竖式计算： 

             10  

        ————

      101  ）1011

            101

        ————

              100

三.CRC实现原理

    CRC校验的基本思想是：利用线性编码理论，在发送端根据要发送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码（即CRC码），并附在信息码后面，构成一个新的共k+r位的二进制码序列，最后发送出去。在接受端，则根据信息码和CRC码之间所遵行的规则进行校验，以确定传输过程中是否出错，并纠错。一般而言，监督码的位宽r越大，纠错能力就越能，例如，CRC32的纠错能力比CRC16要强。CRC校验获得监督码的方式是，将k位信息码转换成多项式，然后除以一个生成多项式，获得余数即为监督码。

在求解一个k位二进制信息码的CRC之前，首先需要将二进制信息码转换成多项式。一个二进制数序列的各个位是它对应多项式的系数，例如，二进制序列1101对应的多项式为：

      M(x)= X3×X2+X0

通过这种转换方式获得的多项式称为信息多项式。在进行CRC计算时，除了信息多项式之外，还需要有一个生成多项式G(x)。生成多项式G(x)要求次数大于0，并且要求0次幂的系数为1。根据以上约束，以及对纠错能力的要求，人们提出了一些通用的CRC生成多项式，例如：CRC16和CRC32等。

CRC16的生成多项式为：G(x)= X15+X10+X2+1

CRC32的生成多项式为：G(x)= X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

CRC的值等于信息多项式M(x)乘以2n，再除以生成多项式G(x)所得的余数，除法采用模2除法。其中，n表示的是生成多项式G（x）的最高次幂，CRC16中n为16，CRC32中n为32。

四．CRC-32串行计算公式推导

根据二进制信息码转换成多项式的方法，对于任意一个长度为（m+1）的二进制信息码，可以转换成一个最高次幂为m的多项式：

                             M(x)= Mm×2m+ Mm-1×2m-1+ … + M1×21+ M0×20

为求此二进制序列的CRC值，首先将M(x）乘以232，然后再除以生成多项式G（x），所得余数即为CRC32的值。G（x）亦为一个二进制多项式。设除法运算获得的商为Q(x),余数为R（x），那么：

   M(x)×232/ G(x) = Mm×2m×232/ G(x) + Mm-1×2m-1×232/ G(x) + … + M1×21×232/ G(x)+ M0×20×232/ G(x)  --------（公式一）

 M(x)×232/ G(x) = Q(x) + R(x)/ G(x)                                             --------（公式二）  

我们从最高位开始解，将M(x)中最高次项的系数Mm作为一个特殊的M(x)即带入公式二：

 Mm×232/ G(x) = Qm(x) + Rm(x)/ G(x)                                           --------（公式三）

其中，Mm的值为1，因为最高次项必须为1。Rm(x)是余数，是一个最高次幂为31的多项式。再将公式三代入公式一:

  M(x)×232/ G(x) = Mm×2m×232/ G(x) + Mm-1×2m-1×232/ G(x) + … + M1×21×232/ G(x)+M0×20×232/ G(x)

          ={Qm(x)×2m + Rm(x)/ G(x)×2m} + Mm-1×2m-1×232/G(x)+ … + M1×21×232/ G(x) + M0×20×232/ G(x)

          = Qm(x)×2m + {Rm(x)×2/G(x)×2m-1+Mm-1×2m-1×232/G(x)} + … + M1×21×232/ G(x) + M0×20×232/ G(x)

= Qm(x)×2m + {(Rm(x)×2 + Mm-1×232)/ G(x)}×2m-1+ … + M1×21×232/ G(x)+ M0×20×232/ G(x)

--------（公式四）

公式四中，设

        {(Rm(x)×2 + Mm-1×232)/ G(x)}= Qm-1(x) + Rm-1(x)/ G(x)           --------（公式五）

再代入到公式四中，那么公式四转化为,相当于只留下可以整除的Q(x)，而将余数R(x)一层一层拆解：

 M(x)×232/ G(x)= Qm(x)×2m+Qm-1(x)×2m-1+{(Rm-1(x)×2 + Mm-2×232)/G(x)}×2m-2+ …+M1×21×232/G(x)+M0×20×232/G(x)

以此类推，最终获得公式：

 M(x)×232/G(x)=Qm(x)×2m+Qm-1(x)×2m-1+Qm-2(x)×2m-2+…+Q1(x)×21+Q0(x)+R0(x)/G(x)      --------(公式六)

根据CRC的定义，多项式R0(x)对应的系数即为我们的CRC32的值。

以上推导过程表明：一个m+1位的二进制序列，可以按位求取CRC32的值。运算时，首先从最高位(第m+1位，设最右边的为第1位)开始计算，然后依次计算较低位。当输入第n个位(n