基于FPGA的CRC校验码生成器

客官°小女子只卖身不卖艺 2022-07-17 04:28 171阅读 0赞

## reference: http://www.cnblogs.com/BitArt/archive/2012/12/26/2833100.html    ##

**1.概述**

CRC即Cyclic Redundancy Check，循环冗余校验，是一种数字通信中的常用信道编码技术。其特征是信息段和校验字段的长度可以任意选定。

**2.CRC校验的基本原理：**

CRC码是由两部分组成的，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码长共n bit，信息码长k bit，就称为(n,k)码，剩余的r bit即为校验位。如：(7,3)码：110 1001，前三位110为信息码，1001为校验码。

详细点说：

**循环冗余校验码（CRC）的基本原理是：**在 K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明 存在一个[最高次幂][Link 1]为N-K=R的多项式G(x)。根据G(x)可以生成（N-K）位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)\*2 R），这样C(x)的右边就会空出R位，这就是校验码的位置。 用 C(x)\*2R 除以生成多项式G(x)得到的余数就是校验码。 （ 难点是如何进行除法运算）

任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的 [多项式][Link 2]为x 6\+x 4\+x 2\+x+1，而多项式为x 5\+x 3\+x 2\+x+1对应的代码101111。

**3.校验码的生成规则：**

1)将原信息码左移r bit，右侧补零，如 110--> 110 0000；

2)用110 0000除以g(x) (注意，使用的是模2除法,见下文)，得到的余数即为CRC校验码；

3)将校验码续接到信息码的尾部，形成CRC码。

**4.关于生成多项式g(x)**

在产生CRC校验码时，要用到除法运算，一般来说，这是比较麻烦的，因此，把二进制信息预先转换成一定的格式，这就是CRC的多项式表示。二进制数表示为生成多项式的系数，如下：

![25212539-4253a90466474b45a2e64820b4b14830.jpg][]  (例如 1100101 表示为1·x6\+1·x5\+0·x4\+0·x3\+1·x2\+0·x+1，即 x6\+x5\+x2\+1) （X的最高幂次为R，转换成对应的二进制数有R+1位。）

所有二进制数均被表示为一个多项式，x仅是码元位置的标记，因此我们并不关心x的取值，称之为码多项式。(我没研究过CRC代数推理过程，没体会到用多项式计算的方便之处，这里要学会的就是给出生成多项式g(x)，能写出对应的二进制即可)

常见的生成多项式如下：

![25212625-50c1b3b1ada8484db223421575bacf4a.jpg][]

\* 多项式是如何得到的？

### 生成多项式 ###

是接受方和发送方的 一个约定，也就是一个 [二进制数][Link 3]，在整个传输过程中，这个数始终保持不变。

在发送方，利用生成多项式对 **信息多项式**做 **模2除**生成校验码。 在接收方利用生成多项式对 **收到的编码多项式**做模2除检测和确定错误位置。

应满足以下条件：

A、 **生成多项式的最高位和最低位必须为1。**

B、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。

C、不同位发生错误时，应该使余数不同。

D、对 [余数][Link 4]继续做除，应使余数循环。

**5.关于模2除法**

模2运算就是加法不考虑进位，减法不考虑借位，

1）加法运算：

0＋0＝0 0＋1＝1 1＋0＝1 1＋1＝0

例如0101＋0011＝0110，列竖式计算：

0 1 0 1

＋ 0 0 1 1

──────

0 1 1 0

2）减法运算：

0－0＝0 0－1＝1 1－0＝1 1－1＝0

例如0110－0011＝0101，列竖式计算：

0 1 1 0

－ 0 0 1 1

──────

0 1 0 1

3）乘法运算

0×0＝0 0×1＝0 1×0＝0 1×1＝1

多位二进制模2乘法类似于普通意义上的多位二进制乘法，不同之处在于后者累加中间结果时采用带进位的加法，而模2乘法对中间结果的处理方式采用的是模2加法。例如1011×101＝100111，列竖式计算：

![25212909-6adb6fc2ffba4c10825a8c1ffa903b84.jpg][]

4）除法运算：

0÷1＝0 1÷1＝1

多位二进制模2除法也类似于普通意义上的多位二进制除法，但是在如何确定商的问题上两者采用不同的规则。后者按带借位的二进制减法，根 据余数减除数够减与否确定商1还是商0，若够减则商1，否则商0。多位模2除法采用模2减法，不带借位的二进制减法，因此考虑余数够减除数与否是没有意义 的。实际上，**在CRC运算中，总能保证除数的首位为1，则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定**。因为除数首位总是1，按照模2 除法运算法则，那么余数首位是1就商1，是0就商0。例如1100100÷1011＝1110……110，列竖式计算：

![25212957-5b819a4f7da64b71ac98028b9641ce78.jpg][]

掌握了上面的运算规则，您可以尝试计算一个复杂一点的，如下：

![25213034-0cb1b24c88134086875aa738ef92d253.jpg][]

如果您得到的余数结果正确，您掌握的东西就够用了。

**详细来说：**

此除法没有数学上的含义，而是采用计算机的**模二除法**，即除数和被除数做**[异或][Link 5]运算**。进行异或运算时**除数和被除数最高位对齐**，按位异或。

例如： 信息字段代码为: 1011001；对应g(x)的代码为: 11001；计算CRC

10110010000

^11001

\--------------------------

01111010000

1111010000

^11001

\-------------------------

11110000

^11001

\--------------------------

00111000

111000

^11001

\-------------------

1010

**6.CRC-CCITT的硬件实现**

CRC-CCITT的生成多项式为：

![25213138-ebed32cf481b47349fd52d382a47700a.jpg][]

对应的二进制数就是上面复杂运算中那个除数。由刚才的计算可知，对于8 bit的数据 0xaa，它的CRC校验码为0001 0100 1010 0000，下面用verilog来实现，看能否得到这个结果：

要实现这一过程，仍然需要LFSR电路，参看《[FPGA产生基于LFSR的伪随机数][FPGA_LFSR]》中关于该电路特性的介绍，如果您不需要了解原理，直接略过即可;有所改进的地方就是，可以将伪随机数发生器看作一个Moore型状态机，它的输出只与当前的状态有关；而此时利用LFSR电路，需要引入数据输入端，输出不仅取决于当前的状态，还取决于输入信号，相当于Mealy型状态机，如下图：

![25213335-91947f4532c549f987aed0a16a7a0c65.jpg][]

注意对比与伪随机数产生器中该反馈支路的区别！

反馈项gr+1gr……g0为生成多项式的系数，依然是1代表存在反馈，0代表不存在反馈；此电路可以完成上述的模2除法操作，若我们要求0xaa的CRC校验码，则从高位到低位顺序输入0xaa共8 bit后，D15……D0中的数据即为所要求的余数，即CRC校验位。

**7.verilog描述**

如果用时序电路串行实现，则8 bit数据要移位8次，就需要8个clk，效率低下，为了能在一个时钟周期输出结果，必须采用组合电路，当然，这是以空间换时间的方法，由于使用了for循环8次，直观的讲电路规模将扩大8倍。。。

![复制代码][copycode.gif]

module CRC_GEN(
        input            rst,     /*async reset,active low*/
        input            clk,     /*clock input*/
        input     [7:0]  data_in, /*parallel data input pins */
        input            d_valid, /* data valid,start to generate CRC, active high*/
        output reg[15:0] crc
    );
    
    integer i;
    reg feedback;
    reg [15:0] crc_tmp;
    /*
    *　　sequential process
    */
    always @(posedge clk or negedge rst)
    begin
        if(!rst) 
            crc <= 16'b0;          /*触发器中的初始值十分重要 */
        else if(d_valid==1'b0)
            crc <= 16'b0;
        else
            crc <= crc_tmp;
    end
    
    /*
    *   combination process
    */
    always@( data_in or crc)
    begin
        crc_tmp = crc;
        for(i=7; i>=0; i=i-1)
        begin
            feedback    = crc_tmp[15] ^ data_in[i];
            crc_tmp[15]  = crc_tmp[14];
            crc_tmp[14]  = crc_tmp[13];
            crc_tmp[13]  = crc_tmp[12];
            crc_tmp[12]  = crc_tmp[11] ^ feedback;
            crc_tmp[11]  = crc_tmp[10] ;
            crc_tmp[10]  = crc_tmp[9];
            crc_tmp[9]   = crc_tmp[8];
            crc_tmp[8]   = crc_tmp[7];
            crc_tmp[7]   = crc_tmp[6];
            crc_tmp[6]   = crc_tmp[5];
            crc_tmp[5]   = crc_tmp[4] ^ feedback;
            crc_tmp[4]   = crc_tmp[3];
            crc_tmp[3]   = crc_tmp[2];
            crc_tmp[2]   = crc_tmp[1];
            crc_tmp[1]   = crc_tmp[0];
            crc_tmp[0]   = feedback;
         end
    end
    
    endmodule

![复制代码][copycode.gif]

仿真结果如下：得到的是数据0xaa和0xf0的CRC校验码，为验证结果的正确性，您可以按照模2法则手工计算一下^.^

![25213828-261d45d95151408f9bfa51cfb4033b88.jpg][]

8.同样给出一个4 bit信息位，5 bitCRC码的(9，4)码的程序和仿真结果，程序的流程与上述流程完全一样：

![26100220-94dac4b67d3f4f088f08220aff016eff.jpg][]

![复制代码][copycode.gif]

module CRC5_GEN(
        input           rst,
        input           clk,
        input     [3:0] data_in,
        input           d_valid, 
        output reg[4:0] crc
    );
    
    integer i;
    reg feedback;
    reg [4:0] crc_tmp;
    always @(posedge clk or negedge rst)
    begin
        if(!rst) 
            crc <= 5'b0;         
        else if(d_valid==1'b0)
            crc <= 5'b0;
        else
            crc <= crc_tmp;
    end
    
    
    always@( data_in or crc)
    begin
        crc_tmp = crc;
        for(i=3; i>=0; i=i-1)
        begin
            feedback    = crc_tmp[4] ^ data_in[i];
            crc_tmp[4]  = crc_tmp[3];
            crc_tmp[3]  = crc_tmp[2];
            crc_tmp[2]  = crc_tmp[1] ^ feedback;
            crc_tmp[1]  = crc_tmp[0];
            crc_tmp[0]  = feedback;
        end
        
    end
    
    endmodule

![复制代码][copycode.gif]

![26095823-6b24c5083d3245d79a87edd0711256df.jpg][]

后记：细心的读者可能发现，博主对LFSR电路能完成模2求余操作的原因避而不谈，不是因为不告诉您，是因为博主也不是很清楚，工科背景对数学推理实在是有点不知所云，尤其是看到国内教材那好几页的公式的时候…………如果您有深入浅出的讲解LFSR电路由来与应用的文章，注意是深入浅出的，请您为博主推荐，在此感谢！

扩展：

reference : http://baike.baidu.com/link?url=ejm7-lzVBMDPx\_xgnoaJFHa0iZPPOUWWABo4rpaCrxTyy2fv2zbghpvuJIHeE8by4Q\_epL7UjAdxvx-7\_udus\_

CRC算法： 设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k； **生成多项式为G(x)**， **G(x)的最高幂次等于r**；  **CRC多项式为R(x)**；  **编码后的带CRC的信息多项式为T(x)**。

**发送方编码方法**：将P(x)乘以 **x^r**(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为 R(x)。用公式表示为T(x)=xrP(x)+R(x)

**接收方解码方法**：将T(x)除以G(x)，得到一个数，如果这个余数为0，则说明传输中无错误发生，否则说明传输有误。

举例来说，设信息编码为1100，生成多项式为1011，即P(x)=x3+x2，G(x)=x3+x+1，计算CRC的过程为

xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 即 R(x)=x。注意到G(x)最高幂次r=3，得出CRC为010。 ( **CRC的位数 是G（x）的最高次冪**）

如果用 [竖式][Link 6]除法(计算机的模二，计算过程为

1110 ------- 1011 /1100000 (1100左移3位) 1011 ---- 1110 1011 ----- 1010 1011 ----- 0010 0000 ---- 010 因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010

如果传输无误，

T(x)= （x6+x5+x）/G(x) =

![dc54564e9258d10941962c76d258ccbf6d814df9.jpg][]

, G(x)=

![4b90f603738da9776a9202efb351f8198718e3b1.jpg][]

无余式。回头看一下上面的 [竖式][Link 6]除法，如果被除数是1100010，显然在商第三个1时，就能除尽。

上述推算过程，有助于我们理解CRC的概念。但直接编程来实现上面的算法，不仅繁琐，效率也不高。实际上在工程中不会直接这样去计算和验证CRC。

下表中列出了一些见于标准的CRC资料： \[2\]

名称 生成多项式 简记式\* 应用举例

CRC-4 x4+x+1 3 ITU G.704

**CRC-8 x8+x5+x4+1** 31 DS18B20

CRC-12 x12+x11+x3+x2+x+1 80F

CRC-16 x16+x15+x2+1 8005 IBM SDLC

CRC-ITU\*\* x16+x12+x5+1 1021 ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS,ZigBee

CRC-32 x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI,IEEE 1394,PPP-FCS

CRC-32c x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP

\* 生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。 \*\* 前称CRC-CCITT。ITU的前身是CCITT。

备注：

（1） **生成多项式是标准规定的**

（2）CRC校验码是基于将位串看作是系数为0或1的多项式， **一个k位的数据流可以看作是关于x的从k-1阶到0阶的k-1次多项式的系数序列**。采用此编码，发送方和接收方必须 **事先商定一个生成多项式G(x)，其高位和低位必须是1**。要计算m位的帧M(x)的校验和，基本思想是将校验和加在帧的末尾，使这个带校验和的帧的多项式能被G(x)除尽。当接收方收到加有校验和的帧时，用G(x)去除它，如果有余数，则CRC校验错误，只有没有余数的校验才是正确的。

## 校验电路实现 ##

以下以CRC8： **x8+x5+x4+1**为例说明，其它可以以此类推

一个简单的RTL解释，是上文“生成方法”的Verilog描述

module CRC8(EN,data,crc);

parameter WIDTH=**12**;

input EN;

output \[7:0\] **crc**;

input \[WIDTH-1:0\]  **data**;

reg \[7:0\] crc;

wire \[7:0\] poly = 8'h31; //x8+x5+x4+1-->0x131,ignore MSB

reg \[**WIDTH-1+8**:**0**\] crc\_reg;

integer len;

always@(EN)

begin

if(!EN)

begin

crc=8'h00;

crc\_reg=\{data,8'h00\};

end

else

begin

for(len=WIDTH+8;len>0;len=len-1'b1)

begin

if(crc\_reg\[WIDTH-1+8\])

begin

crc\_reg\[WIDTH-1+8:WIDTH\] = crc\_reg\[WIDTH-1+8:WIDTH\]^poly;

crc\_reg = crc\_reg<<1'b1;

end

else

crc\_reg = crc\_reg<<1'b1;

end

crc=**crc\_reg**\[WIDTH-1+8:WIDTH\];

// $display("Convertion done! CRC is: 0x%2x",crc);

end

endmodule

![Center][]  
**CRC-8的电路框图**

module  **crc** (dataout, datain, clk, rst);

input clk,rst,**datain;**

output **dataout**;

DFF a1(clk,**dataout**,Q7,rst),

a2(clk,Q7,Q6,rst),

a3(clk,Q6,Q5,rst),

a4(clk,Q5,Q4,rst);

xor a5(temp5,Q4,dataout);

DFF a6(clk,temp5,Q3,rst);

xor a7(temp4,Q3,dataout);

DFF a8(clk,temp4,Q2,rst),

a9(clk,Q2,Q1,rst),

a10(clk,Q1,Q0,rst);

xor a11(**dataout**,Q0,**datain**);

endmodule

module DFF(clk,D,Q,rst);

input clk,D,rst;

output Q;

reg Q;

always@(posedge clk or posedge rst)

begin

if(rst)

Q<=0;

else

Q<=D;

end

endmodule

![Center 1][]

[Link 1]: http://baike.baidu.com/view/2171688.htm
[Link 2]: http://baike.baidu.com/view/613580.htm
[25212539-4253a90466474b45a2e64820b4b14830.jpg]: /images/20220717/38acac7e1024415688c79855f0507a7a.png
[25212625-50c1b3b1ada8484db223421575bacf4a.jpg]: /images/20220717/f531dfae38314c8186f7da6b2ddff38b.png
[Link 3]: http://baike.baidu.com/view/1349.htm
[Link 4]: http://baike.baidu.com/view/1068391.htm
[25212909-6adb6fc2ffba4c10825a8c1ffa903b84.jpg]: /images/20220717/5755b2c902f94b05b7e9174462e43f44.png
[25212957-5b819a4f7da64b71ac98028b9641ce78.jpg]: /images/20220717/d921804859974c849ffe608d11793ece.png
[25213034-0cb1b24c88134086875aa738ef92d253.jpg]: /images/20220717/52d62d245b0c4f69ba4d4bfb756620ee.png
[Link 5]: http://baike.baidu.com/view/674171.htm
[25213138-ebed32cf481b47349fd52d382a47700a.jpg]: /images/20220717/0014696de0344dcb94d662f8f6c20b1e.png
[FPGA_LFSR]: http://www.cnblogs.com/BitArt/archive/2012/12/22/2827005.html
[25213335-91947f4532c549f987aed0a16a7a0c65.jpg]: /images/20220717/d7b7e0fd53a4401db14bcdfc4c517fd5.png
[copycode.gif]: /images/20220717/492e46bc0dff4e3fac6891dae1d9db83.png
[25213828-261d45d95151408f9bfa51cfb4033b88.jpg]: /images/20220717/8f6b70a490d54ae9a2fd0d8d3fa75640.png
[26100220-94dac4b67d3f4f088f08220aff016eff.jpg]: /images/20220717/ab2d9989d65a40d8b4edd4e23ec3de16.png
[26095823-6b24c5083d3245d79a87edd0711256df.jpg]: /images/20220717/d43ccdfd71d94413ba2fa822345724f6.png
[Link 6]: http://baike.baidu.com/view/2838331.htm
[dc54564e9258d10941962c76d258ccbf6d814df9.jpg]: /images/20220717/aeec7cd82cb147d79b045ef526be8e03.png
[4b90f603738da9776a9202efb351f8198718e3b1.jpg]: /images/20220717/c6f08c7eb3a44c22a39a9f690a795934.png
[Center]: /images/20220717/05fa1597258749ed85a2146085b9753a.png
[Center 1]: /images/20220717/60f4fd5297e44dfda17afa619af612de.png