1.概述

　　CRC即Cyclic Redundancy Check，循環(huán)冗余校驗(yàn)，是一種數(shù)字通信中的常用信道編碼技術(shù)。其特征是信息段和校驗(yàn)字段的長度可以任意選定。

2.CRC校驗(yàn)的基本原理：

　　CRC碼是由兩部分組成的，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是校驗(yàn)碼，如果CRC碼長共n bit，信息碼長k bit，就稱為(n,k)碼，剩余的r bit即為校驗(yàn)位。如：(7,3)碼：110?1001，前三位110為信息碼，1001為校驗(yàn)碼。

3.校驗(yàn)碼的生成規(guī)則：

　　1)將原信息碼左移r bit，右側(cè)補(bǔ)零，如 110--> 110 0000；

　　2)用110 0000除以g(x)? (注意，使用的是模2除法,見下文)，得到的余數(shù)即為CRC校驗(yàn)碼；

　　3)將校驗(yàn)碼續(xù)接到信息碼的尾部，形成CRC碼。

4.關(guān)于生成多項(xiàng)式g(x)

　　在產(chǎn)生CRC校驗(yàn)碼時(shí)，要用到除法運(yùn)算，一般來說，這是比較麻煩的，因此，把二進(jìn)制信息預(yù)先轉(zhuǎn)換成一定的格式，這就是CRC的多項(xiàng)式表示。二進(jìn)制數(shù)表示為生成多項(xiàng)式的系數(shù)，如下：

　　所有二進(jìn)制數(shù)均被表示為一個(gè)多項(xiàng)式，x僅是碼元位置的標(biāo)記，因此我們并不關(guān)心x的取值，稱之為碼多項(xiàng)式。(我沒研究過CRC代數(shù)推理過程，沒體會(huì)到用多項(xiàng)式計(jì)算的方便之處，這里要學(xué)會(huì)的就是給出生成多項(xiàng)式g(x)，能寫出對(duì)應(yīng)的二進(jìn)制即可)

　　常見的生成多項(xiàng)式如下：

?　　

5.關(guān)于模2除法

　　模2運(yùn)算就是加法不考慮進(jìn)位，減法不考慮借位，

　　1）加法運(yùn)算：

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

　　　　例如0101＋0011＝0110，列豎式計(jì)算：

???????　　　　0 1 0 1

? 　　　　?＋ 0 0 1 1

　　　　　　──────

????? 　　　　?0 1 1 0

　　2）減法運(yùn)算：

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

　　　　例如0110－0011＝0101，列豎式計(jì)算：

? ???　　　　?0 1 1 0

　　　　?－? 0 0 1 1

　　　　 ?　──────

? ???　　　　?0 1 0 1

　　3）乘法運(yùn)算

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

　　　　多位二進(jìn)制模2乘法類似于普通意義上的多位二進(jìn)制乘法，不同之處在于后者累加中間結(jié)果時(shí)采用帶進(jìn)位的加法，而模2乘法對(duì)中間結(jié)果的處理方式采用的是模2加法。例如1011×101＝100111，列豎式計(jì)算：

　　4）除法運(yùn)算：

　　　　0÷1＝0??????? 1÷1＝1

　　　　多位二進(jìn)制模2除法也類似于普通意義上的多位二進(jìn)制除法，但是在如何確定商的問題上兩者采用不同的規(guī)則。后者按帶借位的二進(jìn)制減法，根 據(jù)余數(shù)減除數(shù)夠減與否確定商1還是商0，若夠減則商1，否則商0。多位模2除法采用模2減法，不帶借位的二進(jìn)制減法，因此考慮余數(shù)夠減除數(shù)與否是沒有意義 的。

? ? ? ? ? ? ?實(shí)際上，在CRC運(yùn)算中，總能保證除數(shù)的首位為1，則模2除法運(yùn)算的商是由余數(shù)首位與除數(shù)首位的模2除法運(yùn)算結(jié)果確定。因?yàn)槌龜?shù)首位總是1，按照模2 除法運(yùn)算法則，那么余數(shù)首位是1就商1，是0就商0。例如1100100÷1011＝1110……110，列豎式計(jì)算：

掌握了上面的運(yùn)算規(guī)則，您可以嘗試計(jì)算一個(gè)復(fù)雜一點(diǎn)的，如下：

　　如果您得到的余數(shù)結(jié)果正確，您掌握的東西就夠用了。

6.CRC-CCITT的硬件實(shí)現(xiàn)

CRC-CCITT的生成多項(xiàng)式為：

　　對(duì)應(yīng)的二進(jìn)制數(shù)就是上面復(fù)雜運(yùn)算中那個(gè)除數(shù)。由剛才的計(jì)算可知，對(duì)于8 bit的數(shù)據(jù) 0xaa，它的CRC校驗(yàn)碼為0001 0100 1010 0000，下面用verilog來實(shí)現(xiàn)，看能否得到這個(gè)結(jié)果：

　　要實(shí)現(xiàn)這一過程，仍然需要LFSR電路，參看《FPGA產(chǎn)生基于LFSR的偽隨機(jī)數(shù)》中關(guān)于該電路特性的介紹，如果您不需要了解原理，直接略過即可;有所改進(jìn)的地方就是，可以將偽隨機(jī)數(shù)發(fā)生器看作一個(gè)Moore型狀態(tài)機(jī)，它的輸出只與當(dāng)前的狀態(tài)有關(guān)；而此時(shí)利用LFSR電路，需要引入數(shù)據(jù)輸入端，輸出不僅取決于當(dāng)前的狀態(tài)，還取決于輸入信號(hào)，相當(dāng)于Mealy型狀態(tài)機(jī)，如下圖：

注意對(duì)比與偽隨機(jī)數(shù)產(chǎn)生器中該反饋支路的區(qū)別！

　　反饋項(xiàng)gr+1gr……g0為生成多項(xiàng)式的系數(shù)，依然是1代表存在反饋，0代表不存在反饋；此電路可以完成上述的模2除法操作，若我們要求0xaa的CRC校驗(yàn)碼，則從高位到低位順序輸入0xaa共8 bit后，D15……D0中的數(shù)據(jù)即為所要求的余數(shù)，即CRC校驗(yàn)位。

7.verilog描述

　　如果用時(shí)序電路串行實(shí)現(xiàn)，則8 bit數(shù)據(jù)要移位8次，就需要8個(gè)clk，效率低下，為了能在一個(gè)時(shí)鐘周期輸出結(jié)果，必須采用組合電路，當(dāng)然，這是以空間換時(shí)間的方法，由于使用了for循環(huán)8次，直觀的講電路規(guī)模將擴(kuò)大8倍。。。

?

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;          /*觸發(fā)器中的初始值十分重要 */
    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

?

?仿真結(jié)果如下：得到的是數(shù)據(jù)0xaa和0xf0的CRC校驗(yàn)碼，為驗(yàn)證結(jié)果的正確性，您可以按照模2法則手工計(jì)算一下^.^

8.同樣給出一個(gè)4 bit信息位，5 bitCRC碼的(9，4)碼的程序和仿真結(jié)果，程序的流程與上述流程完全一樣：

?

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

?

審核編輯：劉清