CRC校驗采用多項式編碼方法。

被處理的數(shù)據(jù)塊可以看作是一個二進制多項式，例如，10110101可以看作是2^7+2^5+2^4+2^2+2^0,多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進，錯位，和邏輯異或運算一致。

采用CRC校驗時，發(fā)送方和接收方用同一個生成多項式g(x),并且g(x)的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以g(x)去除t(x)，得到余數(shù)作為CRC校驗碼。校驗時，以計算的校正結果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯。

CRC校驗可以100％地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k(k為g(x)的階數(shù))的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。

CCITT建議：2048 kbit/s的PCM基群設備采用CRC-4方案，使用的CRC校驗采用16位CRC校驗。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16。g(x)的位數(shù)越高，檢錯能力就越強。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機等領域運用十分廣泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)內(nèi)，都采用了CRC校驗碼進行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進行差錯控制。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

CRC校驗碼的基本思想是利用線性編碼理論， 在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的監(jiān)督碼(既CRC碼)r位，并附在信息后邊，構成一個新的二進制碼序列數(shù)共(k+r)位，最后發(fā)送出去。在接收端，則根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。

在數(shù)據(jù)存儲和數(shù)據(jù)通訊領域，CRC無處不在:著名的通訊協(xié)議X.25的FCS(幀檢錯序列)采用的是CRC. CCITT，ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤驅(qū)動器的讀寫采用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。

CRC的本質(zhì)是模-2除法的余數(shù)，采用的除數(shù)不同，CRC的類型也就不一樣。通常，CRC的除數(shù)用生成多項式來表示。最常用的CRC碼的生成多項式有CRC16,CRC32.

以CRC16為例,16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進制序列數(shù)左移16位(既乘以2^16)后，再除以一個多項式，最后所得到的余數(shù)既是CRC碼，如下式所示，其中K(X)表示n位的二進制序列數(shù)，G(X)為多項式，Q(X)為整數(shù)，R(X)是余數(shù)(既CRC碼)。

K(X)>>16=G(x)Q(x)+R(x)

求CRC碼所采用模2加減運算法則，既是不帶進位和借位的按位加減，這種加減運算實際上就是邏輯上的異或運算，加法和減法等價，乘法和除法運算與普通代數(shù)式的乘除法運算是一樣，符合同樣的規(guī)律。生成CRC碼的多項式如下，其中CRC-16和CRC-CCITT產(chǎn)生16位的CRC碼，而CRC-32則產(chǎn)生的是32位的CRC碼

接收方將接收到的二進制序列數(shù)(包括信息碼和CRC碼)除以多項式，如果余數(shù)為0，則說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤，關于其原理這里不再多述。用軟件計算CRC碼時，接收方可以將接收到的信息碼求CRC碼，比較結果和接收到的CRC碼是否相同。

CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗序列FCS中，使用CCITT-16即CRC16,其生成多項式為G(x)=x16+x12+x5+1,?CRC-32的生成多項式為G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

CRC校驗碼的算法分析

CRC校驗碼的編碼方法是用待發(fā)送的二進制數(shù)據(jù)t(x)除以生成多項式g(x)，將最后的余數(shù)作為CRC校驗碼。其實現(xiàn)步驟如下：

設待發(fā)送的數(shù)據(jù)塊是m位的二進制多項式t(x)，生成多項式為r階的g(x)。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應的二進制多項式為 。

用生成多項式g(x)去除 ，求得余數(shù)為階數(shù)為r-1的二進制多項式y(tǒng)(x)。此二進制多項式y(tǒng)(x)就是t(x)經(jīng)過生成多項式g(x)編碼的CRC校驗碼。

用 以模2的方式減去y(x)，得到二進制多項式 。 就是包含了CRC校驗碼的待發(fā)送字符串。

從CRC的編碼規(guī)則可以看出，CRC編碼實際上是將代發(fā)送的m位二進制多項式t(x)轉(zhuǎn)換成了可以被g(x)除盡的m+r位二進制多項式，所以解碼時可以用接受到的數(shù)據(jù)去除g(x)，如果余數(shù)位零，則表示傳輸過程沒有錯誤；如果余數(shù)不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時可以看做是由t(x)和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。

為了更清楚的了解CRC校驗碼的編碼過程，下面用一個簡單的例子來說明CRC校驗碼的編碼過程。由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致，只有位數(shù)和生成多項式不一樣。為了敘述簡單，用一個CRC-4編碼的例子來說明CRC的編碼過程。

設待發(fā)送的數(shù)據(jù)t(x)為12位的二進制數(shù)據(jù)100100011100；CRC-4的生成多項式為g(x)= ，階數(shù)r為4，即10011。首先在t(x)的末尾添加4個0構成 ，數(shù)據(jù)塊就成了1001000111000000。然后用g(x)去除，不用管商是多少，只需要求得余數(shù)y(x)。下表為給出了除法過程。

除數(shù)次數(shù) 被除數(shù)/ g(x)/結果 余數(shù)

0 1 001000111000000 100111000000

1 0011

0 000100111000000

1 1 00111000000 1000000

1 0011

0 00001000000

2 1 000000 1100

1 0011

0 001100

從上面表中可以看出，CRC編碼實際上是一個循環(huán)移位的模2運算。對CRC-4，我們假設有一個5 bits的寄存器，通過反復的移位和進行CRC的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述：

//reg是一個5 bits的寄存器

把reg中的值置0.

把原始的數(shù)據(jù)后添加r個0.

While (數(shù)據(jù)未處理完)

Begin

If (reg首位是1)

reg = reg XOR 0011.

把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。

End

reg的后四位就是我們所要求的余數(shù)。

這種算法簡單，容易實現(xiàn)，對任意長度生成多項式的G(x)都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長的話，這種方法就不太適合了。它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率，可以一次處理4位、8位、16位、32位。由于處理器的結構基本上都支持8位數(shù)據(jù)的處理，所以一次處理8位比較合適。

為了對優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程：

由于最后只需要余數(shù)，所以我們只看后四位。構造一個四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0(reg的0位)，同時reg3的數(shù)據(jù)移出 reg。有上面的算法可以知道，只有當移出的數(shù)據(jù)為1時，reg才和g(x)進行XOR運算；移出的數(shù)據(jù)為0時，reg不與g(x)進行XOR運算，相當與和0000進行XOR運算。就是說，reg和什么樣的數(shù)據(jù)進行XOR移出的數(shù)據(jù)決定。由于只有一個bit，所以有 種選擇。上述算法可以描述如下，

//reg是一個4 bits的寄存器

初始化t[]={0011,0000}

把reg中的值置0.

把原始的數(shù)據(jù)后添加r個0.

While (數(shù)據(jù)未處理完)

Begin

把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。

reg = reg XOR t[移出的位]

End

上面算法是以bit為單位進行處理的，可以將上述算法擴展到8位，即以Byte為單位進行處理，即CRC-32。構造一個四個Byte的寄存器reg，初值為0x00000000，數(shù)據(jù)依次移入reg0(reg的0字節(jié)，以下類似)，同時reg3的數(shù)據(jù)移出reg。用上面的算法類推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進行XOR。由于有8個bit，所以有 種選擇。上述算法可以描述如下：

//reg是一個4 Byte的寄存器

初始化t[]＝{…}//共有 ＝256項

把reg中的值置0.

把原始的數(shù)據(jù)后添加r/8個0字節(jié).

While (數(shù)據(jù)未處理完)

Begin

把reg中的值左移一個字節(jié)，讀入一個新的字節(jié)并置于reg的第0個byte的位置。

reg = reg XOR t[移出的字節(jié)]

End

算法的依據(jù)和多項式除法性質(zhì)有關。如果一個m位的多項式t(x)除以一個r階的生成多項式g(x)， ，將每一位(0=

參考資料：

http://www.52rd.com/Blog/Detail_RD.Blog_zx_zx_13124.html

http://www.equn.com/forum/viewthread.php?tid=5470&sid=3rrqVomR

http://blog.csdn.net/yeyumin89/article/details/7932650

轉(zhuǎn)載聲明：本站文章若無特別說明，皆為原創(chuàng)，轉(zhuǎn)載請注明來源：破曉(http://www.code2048.net)，謝謝！^^

總結

以上是生活随笔為你收集整理的tcp中的crc检验算法原理_CRC校验算法原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。