算法及Verilog实现

1、CRC算法原理及其Verilog实现1 CRC简介 CRC校验是一种在数据通信系统和其它串行传输系统中广泛使用的错误检测手段。通用的CRC标准有CRC-8、CRC-16、CRC-32、CRC-CCIT，其中在网络通信系统中应用最广泛的是CRC-32标准。本文将以CRC-32为例，说明CRC编码的实现方式以及如何用verilog语言对CRC编码进行描述。 2 二模2运算 在说明CRC编码方式之前，首先介绍一下模2运算法则，在CRC运算过程中会使用到模2除法运算。模2运算是一种二进制运算法则，与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种运算。模2运算用“+”表示加法运算，用“-

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

3、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/

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

5、即为监督码。在求解一个k位二进制信息码的CRC之前，首先需要将二进制信息码转换成多项式。一个二进制数序列的各个位是它对应多项式的系数，例如，二进制序列1101011101对应的多项式为： M(x)= 1×X9+1×X8+0×X7+1×X6+0×X5+1×X4+1×X3+1×X2+0×X1+1×X0 M(x)= X9+X8+X6+X4+X3+X2+1 通过这种转换方式获得的多项式称为信息多项式。在进行CRC计算时，除了信息多项式之外，还需要有一个生成多项式G(x)。生成多项式G(x)要求次数大于0

6、，并且要求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+11.1 CRC的值等于信息多项式M(x)乘以2n ，再除以生成多项式G(x)所得的余数，除法采用模2除法。其中，n表示的是生成多项式G（x）的最高次幂，CRC16中n为16，CRC32中n为32。 4 四CRC-32串行计算公式推导 根据二进制信息码

7、转换成多项式的方法，对于任意一个长度为（m+1）的二进制信息码，可以转换成一个最高次幂为m的多项式： M(x)= Mm×Xm+ Mm-1×Xm-1+ + M1×X1+ M0×X0 将以上公式中的X置换成2，表示是一个二进制的多项式，那么该多项式的系数只能是1和0。 M(x)= Mm×2m+ Mm-1×2m-1+ + M1×21+ M0×20 为求此二进制序列的CRC值，首先将M(x）乘以232，然后再除以生成多项式G（x），所得余数即为CRC32的值。G（x）亦为一个二进制多项式。设除法运算获得的商为Q(x),余数

8、为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是一个只有0次

9、幂的多项式，Mm的值为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

10、15;232/ G(x) = Qm(x)×2mRm(x)×2/G(x)×2m-1Mm-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&#

11、215;232)/ G(x)= Qm-1(x) + Rm-1(x)/ G(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 + Q

12、m-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<m+1)时，首先将第n+1位运算后的结果乘以2，再将第n的值(0或1)乘以232，两者相加后除以生成多项式G(x)。因此，每一位的CRC32运算就转化成了一个最高次幂为32的多项式除以一个最高次幂为32的多项式（生成多项式）

13、，结果（余数）为一个最高次幂不超过31的多项式。 5 五CRC32串行计算的LFSR实现 上一节已经推导出了CRC的串行实现方法，但如何将公式六用Verilog语言表示出来呢？用Verilog描述CRC32的串行计算方法时，使用到了一种叫做LFSR（Linear feedback shift register）的结构。下图为该LFSR的结构图，其中寄存器3到寄存器25没有在图中画出。 图1.CRC32的串行移位寄存器实现 如图所示，各个寄存器储存着上一次CRC32运算的结果，寄存器的输出即为CRC32的值。让我们回顾一下CRC32的生成多项式： G(x)= 232+226+223+ 222+2

14、16+212+211+210+28+ 27+25+ 24+ 22+21+1 当输入新的位参与运算时，信息多项式为： M(x)= Mn×232 上一次CRC计算的结果为： Rn+1(x) = A31×231+ A30×230+ A29×229+ + A2×22+ A1×21+ A0×1 根据上一节推导出的公式，新的CRC32值Rn(x)为Rn+1(x)×2 + M(x)/ G(x)的余数。设 Q(x) = Rn+1(x)×2 + M(x),则： Q(x) = （A31+ Mn）×232+ A30&

15、#215;231+ A29×230+ +A1×22+ A0×21在计算Q(x)/ G(x)的结果时，根据模2运算法则，如果A31+ Mn的结果为1，则商为1，余数为Q(x)- G(x)；如果A31+ Mn的结果为0，则商为0，余数为Q(x)本身。其中，A31+ Mn是模2加法，不进位；Q(x)- G(x) 模2减法，不借位。根据以上分析，上图中的结构刚好能够完成一位串行输入的CRC32计算。当上一个CRC32结果的最高位A31和输入的数值Mn模2加法结果为1时，上一次CRC结果右移一位，完成乘2的过程，再与G(x)多项式的系数进行异或运算，完成减法。由于任何数与0

16、异或保持不变，所以LFSR中只有在G(x)多项式为1的系数处才放置异或门。运算完毕以后把结果存入寄存器即为新的CRC32值。当上一个CRC32结果的最高位A31和输入的数值Mn模2加法结果为0时，Q(x)不够除，Q(x)本身作为余数存入寄存器，获得新的CRC32值。由于A31+ Mn的结果为0，异或门不起作用，Q(x) = A30×231+ A29×230+ +A1×22+ A0×21，由Rn+1(x) 右移一位获得, Q(x)的0次幂为0，刚好把A31+ Mn的结果作为输入。因此，以上LFSR结构能够实现串行CRC32运算，且这种结构很容易在Veril

17、og语言中描述。6 六CRC32串行计算的Verilog实现 根据第五节中的描述，一位数据的CRC32值为：_ crc32_new = crc32_old30:0,1'b0 (32(crc32_old31 datain) & POLYNOMIAL) ;_ 其中，crc32_old为之前存储在LFSR中的值，可以是上一次计算的结果，也可以中第一次计算时的初始值。datain表示的是新参与运算的一位数值。POLYNOMIAL是生成多项式的系数对应的二进制序列，POLYNOMIAL=32'h04C11DB7,是个常数。上述Verilog语句中，如果crc32_old31dat

18、ain为0，则crc32_new由crc32_old左移一位（即乘以2）后获得；如果crc32_old31datain为1，在POLYNOMIAL为1的位上，crc32_old30:0,1'b0与1相异或获得新的CRC32值crc32_new。此语句实现的逻辑，刚好满足CRC32的定义，是对第五节中提及的LFSR行为的描述。 求一个二进制序列的CRC32值时，可以让二进制序列的各个位依次计算CRC32，最终的结果即为二进制序列的CRC32值。例如一个长度为8的二进制序列，它的CRC32值为： _ always( * ) begin for(i = 0 ,i<= 7,i = i +

19、1) crc32_new = crc32_old30:0,1'b0 (32(crc32_old31 dataini) & POLYNOMIAL) ; end_ 以上代码中，datain位宽为8，表示的是一个宽度为8的二进制序列。在以上代码中，实现一个输入数据位宽为8的crc32计算逻辑。在输入位宽为1的CRC32计算逻辑的基础上，很容易实现更大输入位宽的CRC32计算逻辑。 _博主导读： 本博文的第二小节有借鉴网友关于模2运算的文章，原文链接：模2运算原理，本文关于模2运算的说明比较简洁，有需要详细了解模2运算的朋友可点击链接阅读原文。另外，本博文的第四节公式推导过程颇为艰涩，大家可以直接阅读第四节末尾结论部分，无须阅读推导过程。7