CRC校驗(yàn)（查錯(cuò)校驗(yàn)碼）

CRC校驗(yàn)（查錯(cuò)校驗(yàn)碼）

CRC校驗(yàn) （查錯(cuò)校驗(yàn)碼） 次瀏覽 | 2022.10.31 10:18:18 更新 來(lái)源 ：互聯(lián)網(wǎng) 精選百科 本文由作者推薦 CRC校驗(yàn)查錯(cuò)校驗(yàn)碼

CRC即循環(huán)冗余校驗(yàn)碼（Cyclic?Redundancy?Check[1]）：是數(shù)據(jù)通信領(lǐng)域中最常用的一種查錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長(zhǎng)度可以任意選定。循環(huán)冗余檢查（CRC）是一種數(shù)據(jù)傳輸檢錯(cuò)功能，對(duì)數(shù)據(jù)進(jìn)行多項(xiàng)式計(jì)算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也執(zhí)行類(lèi)似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。

中文名

循環(huán)冗余校驗(yàn)碼

外文名

Cyclic Redundancy Check

別名

CRC校驗(yàn)

發(fā)布屬性

編碼

使用類(lèi)型

數(shù)據(jù)、通訊

開(kāi)發(fā)者

W. Wesley Peterson

編程語(yǔ)言

英語(yǔ)

開(kāi)發(fā)時(shí)間

1961年

生成方法

借助于模2除法則，其馀數(shù)為校驗(yàn)字段。

例如：信息字段代碼為:1011001；對(duì)應(yīng)m(x)=x6+x4+x3+1

假設(shè)生成多項(xiàng)式為：g(x)=x4+x3+1；則對(duì)應(yīng)g(x)的代碼為:11001

x4m(x)=x10+x8+x7+x4對(duì)應(yīng)的代碼記為：10110010000；

采用模2除法則:得馀數(shù)為:1010(即校驗(yàn)字段為：1010）

發(fā)送方：發(fā)出的傳輸字段為:10110011010

信息字段校驗(yàn)字段

接收方：使用相同的生成碼進(jìn)行校驗(yàn):接收到的字段/生成碼（二進(jìn)制除法）

如果能夠除盡，則正確，

給出馀數(shù)（1010）的計(jì)算步驟：

除法沒(méi)有數(shù)學(xué)上的含義，而是采用計(jì)算機(jī)的模二除法，即除數(shù)和被除數(shù)做異或運(yùn)算。進(jìn)行異或運(yùn)算時(shí)除數(shù)和被除數(shù)最高位對(duì)齊，按位異或。

10110010000

^11001

--------------------------

01111010000

1111010000

^11001

-------------------------

0011110000

11110000

^11001

--------------------------

00111000

111000

^11001

-------------------

001010

則四位CRC校驗(yàn)碼就為：1010。

利用CRC進(jìn)行檢錯(cuò)的過(guò)程可簡(jiǎn)單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。這個(gè)規(guī)則，在差錯(cuò)控制理論中稱(chēng)為“生成多項(xiàng)式”。

算法

在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如1100101表示為1·x+1·x+0·x+0·x+1·x+0·x+1，即x+x+x+1。

設(shè)編碼前的原始信息多項(xiàng)式為P(x)，P(x)的最高冪次加1等于k；生成多項(xiàng)式為G(x)，G(x)的最高冪次等于r；CRC多項(xiàng)式為R(x)；編碼后的帶CRC的信息多項(xiàng)式為T(mén)(x)。

發(fā)送方編碼方法：將P(x)乘以xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移r位)，再除以G(x)，所得馀式即為R(x)。用公式表示為T(mén)(x)=xrP(x)+R(x)

接收方解碼方法：將T(x)除以G(x)，得到一個(gè)數(shù)，如果這個(gè)馀數(shù)為0，則說(shuō)明傳輸中無(wú)錯(cuò)誤發(fā)生，否則說(shuō)明傳輸有誤。

舉例來(lái)說(shuō)，設(shè)信息編碼為1100，生成多項(xiàng)式為1011，即P(x)=x3+x2，G(x)=x3+x+1，計(jì)算CRC的過(guò)程為

xrP(x)=x3(x3+x2)=x6+x5G(x)=x3+x+1即R(x)=x。注意到G(x)最高冪次r=3，得出CRC為010。

如果用豎式除法(計(jì)算機(jī)的模二，計(jì)算過(guò)程為

1110——1011/1100000(1100左移3位)1011——11101011——10101011——00100000——010因此，T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010

如果傳輸無(wú)誤，T(x)=x6+x5+x）/G(x)=,G(x)=無(wú)馀式。回頭看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個(gè)1時(shí)，就能除盡。

上述推算過(guò)程，有助于我們理解CRC的概念。但直接編程來(lái)實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會(huì)直接這樣去計(jì)算和驗(yàn)證CRC。

生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如04C11DB7實(shí)際上是104C11DB7。前稱(chēng)CRC-CCITT。ITU的前身是CCITT。

備注：

（1）生成多項(xiàng)式是標(biāo)準(zhǔn)規(guī)定的。

（2）CRC校驗(yàn)碼是基于將位串看作是系數(shù)為0或1的多項(xiàng)式，一個(gè)k位的數(shù)據(jù)流可以看作是關(guān)于x的從k-1階到0階的k-1次多項(xiàng)式的系數(shù)序列。采用此編碼，發(fā)送方和接收方必須事先商定一個(gè)生成多項(xiàng)式G(x)，其高位和低位必須是1。要計(jì)算m位的幀M(x)的校驗(yàn)和，基本思想是將校驗(yàn)和加在幀的末尾，使這個(gè)帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)除盡。當(dāng)接收方收到加有校驗(yàn)和的幀時(shí)，用G(x)去除它，如果有馀數(shù)，則CRC校驗(yàn)錯(cuò)誤，只有沒(méi)有馀數(shù)的校驗(yàn)才是正確的。

(3)名稱(chēng)生成多項(xiàng)式簡(jiǎn)記式*標(biāo)準(zhǔn)引用

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。

電路實(shí)現(xiàn)

以下以CRC8x8+x5+x4+1為例說(shuō)明，其它可以以此類(lèi)推

生成算法

一個(gè)簡(jiǎn)單的RTL解釋?zhuān)巧衔摹吧煞椒ā钡腣erilog描述

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

el

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

el

crc_reg=crc_reg<<1'b1;

end

crc=crc_reg[WIDTH-1+8:WIDTH];

$display("Convertiondone!CRCis:0x%2x",crc);

end

end

endmodule

檢測(cè)電路

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@(podgeclkorpodgerst)

begin

if(rst)

Q<=0;

el

Q<=D;

end

endmodule

參考資料