生成方法
借助于模2除法則,其馀數為校驗字段。
例如:信息字段代碼為:1011001;對應m(x)=x6+x4+x3+1
假設生成多項式為:g(x)=x4+x3+1;則對應g(x)的代碼為:11001
x4m(x)=x10+x8+x7+x4對應的代碼記為:10110010000;
采用模2除法則:得馀數為:1010(即校驗字段為:1010)
發送方:發出的傳輸字段為:10110011010
信息字段校驗字段
接收方:使用相同的生成碼進行校驗:接收到的字段/生成碼(二進制除法)
如果能夠除盡,則正确,
給出馀數(1010)的計算步驟:
除法沒有數學上的含義,而是采用計算機的模二除法,即除數和被除數做異或運算。進行異或運算時除數和被除數最高位對齊,按位異或。
10110010000
^11001
--------------------------
01111010000
1111010000
^11001
-------------------------
0011110000
11110000
^11001
--------------------------
00111000
111000
^11001
-------------------
001010
則四位CRC校驗碼就為:1010。
利用CRC進行檢錯的過程可簡單描述為:在發送端根據要傳送的k位二進制碼序列,以一定的規則産生一個校驗用的r位監督碼(CRC碼),附在原始信息後邊,構成一個新的二進制碼序列數共k+r位,然後發送出去。在接收端,根據信息碼和CRC碼之間所遵循的規則進行檢驗,以确定傳送中是否出錯。這個規則,在差錯控制理論中稱為“生成多項式”。
算法
在代數編碼理論中,将一個碼組表示為一個多項式,碼組中各碼元當作多項式的系數。例如1100101表示為1·x+1·x+0·x+0·x+1·x+0·x+1,即x+x+x+1。
設編碼前的原始信息多項式為P(x),P(x)的最高幂次加1等于k;生成多項式為G(x),G(x)的最高幂次等于r;CRC多項式為R(x);編碼後的帶CRC的信息多項式為T(x)。
發送方編碼方法:将P(x)乘以xr(即對應的二進制碼序列左移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+x5G(x)=x3+x+1即R(x)=x。注意到G(x)最高幂次r=3,得出CRC為010。
如果用豎式除法(計算機的模二,計算過程為
1110——1011/1100000(1100左移3位)1011——11101011——10101011——00100000——010因此,T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010
如果傳輸無誤,T(x)=x6+x5+x)/G(x)=,G(x)=無馀式。回頭看一下上面的豎式除法,如果被除數是1100010,顯然在商第三個1時,就能除盡。
上述推算過程,有助于我們理解CRC的概念。但直接編程來實現上面的算法,不僅繁瑣,效率也不高。實際上在工程中不會直接這樣去計算和驗證CRC。
生成多項式的最高幂次項系數是固定的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校驗錯誤,隻有沒有馀數的校驗才是正确的。
(3)名稱生成多項式簡記式*标準引用
CRC-4x4+x+13ITUG.704
CRC-8x8+x5+x4+10x31
CRC-8x8+x2+x1+10x07
CRC-8x8+x6+x4+x3+x2+x10x5E
CRC-12x12+x11+x3+x+180F
CRC-16x16+x15+x2+18005IBMSDLC
CRC16-CCITTx16+x12+x5+11021ISOHDLC,ITUX.25,V.34/V.41/V.42,PPP-FCS
CRC-32x32+x26+x23+...+x2+x+104C11DB7ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCS
CRC-32cx32+x28+x27+...+x8+x6+11EDC6F41SCTP。
電路實現
以下以CRC8x8+x5+x4+1為例說明,其它可以以此類推
生成算法
一個簡單的RTL解釋,是上文“生成方法”的Verilog描述
moduleCRC8(EN,data,crc);
parameterWIDTH=12;
inputEN;
output[7:0]crc;
input[WIDTH-1:0]data;
reg[7:0]crc;
wire[7:0]poly=8'h31;
//x8+x5+x4+1-->0x131,ignoreMSB
reg[WIDTH-1+8:0]crc_reg;
integerlen;
always@(EN)
begin
if(!EN)
begin
crc=8'h00;
crc_reg={data,8'h00};
end
else
begin
for(len=WIDTH;len>0;len=len-1'b1)
begin
if(crc_reg[WIDTH-1+8])
begin
crc_reg=crc_reg<<1'b1;
crc_reg[WIDTH-1+8:WIDTH]=crc_reg[WIDTH-1+8:WIDTH]^poly;
end
else
crc_reg=crc_reg<<1'b1;
end
crc=crc_reg[WIDTH-1+8:WIDTH];
$display("Convertiondone!CRCis:0x%2x",crc);
end
end
endmodule
檢測電路
modulecrc(dataout,datain,clk,rst);
inputclk,rst,datain;
outputdataout;
DFFa1(clk,dataout,Q7,rst),
a2(clk,Q7,Q6,rst),
a3(clk,Q6,Q5,rst),
a4(clk,Q5,Q4,rst);
xora5(temp5,Q4,dataout);
DFFa6(clk,temp5,Q3,rst);
xora7(temp4,Q3,dataout);
DFFa8(clk,temp4,Q2,rst),
a9(clk,Q2,Q1,rst),
a10(clk,Q1,Q0,rst);
xora11(dataout,Q0,datain);
endmodule
////////////////////////////////////////
moduleDFF(clk,D,Q,rst);
inputclk,D,rst;
outputQ;
regQ;
always@(posedgeclkorposedgerst)
begin
if(rst)
Q<=0;
else
Q<=D;
end
endmodule