crc校驗碼詳細介紹看懂了就會了

1、v1.0可編輯可修改詳細介紹循環(huán)冗余校驗碼(CRC的基本原理是：在 K位信息碼后再拼接R位的校驗 碼，整個編碼長度為 N位，因此，這種編碼又叫(N, K)碼。對于一個給定的 (N, K)碼，可以證明存在一個最高次幕為N-K=R的多項式G(x)。根據(jù)G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRM的生成多項式。校驗碼的具體生成過程為：假設發(fā)送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2的R次方，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。 通過C(x)*2的R次方除以生成多項式 G(x)得到的余數(shù)就是校驗碼。 編輯本段 幾個基本概念1、多項式與二進制

2、數(shù)碼多項式和二進制數(shù)有直接對應關系：x的最高幕次對應二進制數(shù)的最高位， 以下各位對應多項式的各幕次，有此事次項對應1,無此幕次項對應00可以看出：x的最高幕次為R,轉換成對應白二進制數(shù)有 R+1位。多項式包括生成多項式G(x)和信息多項式C(x)。如生成多項式為G(x)=xA4+xA3+x+1 ,可轉換為二進制數(shù)碼11011。而發(fā)送信息位1111 ,可轉換為數(shù)據(jù)多項式為 C(x)=xA3+xA2+x+1。2、生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進制數(shù)，在整個傳輸過程中， 這個數(shù)始終保持不變。在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼

3、多項式做模 2除檢測和確定錯誤位置。應滿足以下條件：a、生成多項式的最高位和最低位必須為 1。b、當被傳送信息(CRC碼)任何一位發(fā)生錯誤時，被生成多項式做除后應 該使余數(shù)不為00c、不同位發(fā)生錯誤時，應該使余數(shù)不同。d、對余數(shù)繼續(xù)做除，應使余數(shù)循環(huán)。3 CRC碼的生成步驟1、將x的最高次幕為R的生成多項式G(x)轉換成對應的R+1位二進制數(shù)。2、將信息碼左移R位，相當與對應的信息多項式 C(x)*2的R次方。3、用生成多項式(二進制數(shù))對信息碼做除，得到R位的余數(shù)。4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRCK?！纠考僭O使用的生成多項式是G(x)=x"+x+1。4位的原

4、始報文為1010,求編碼后的報文。解：1、將生成多項式G(x)=xA3+x+1轉換成對應的二進制除數(shù)1011。2、此題生成多項式有4位(R+1),要把原始報文C(x)左移3 (R)位變成 10100003、用生成多項式對應的二進制數(shù)對左移 3位后的原始報文進行模2除，相 當于按位異或：1010000101110001011011得到的余位011,所以最終編碼為：1010011 編輯本段生成CRCK的基本原理任意一個由二進制位用組成的代碼都可以和一個系數(shù)僅為0和'1'取值的多項式對應。例如：代碼 1010111對應的多項式為x6+x4+x2+x+1,而 多項式為x5+x3+x2+

5、x+1對應的代碼101111。 編輯本段 CRCB集選擇的原則若設碼字長度為N,信息字段為K位，校驗字段為R位(N=K+R),則對于CRC 碼集中的任一碼字，存在且僅存在一個R次多項式g(x),使得V(x)=A(x)g(x)=xRm(x)+r(x);其中：m(x)為K次原始的信息多項式，r(x)為R-1次校驗多項式(即CRC 校驗和)，g(x)稱為生成多項式：g(x)=g0+g1x1+ g2x2+.+g(R-1)x(R-1)+gRxR發(fā)送方通過指定的g(x)產生CRCK字，接收方則通過該g(x)來驗證收到的 CRCB 字。編輯本段CRO驗碼軟件生成方法：借助于多項式除法，其余數(shù)為校驗字段。例如

6、：信息字段代碼為:1011001 ;對應m(x)=x6+x4+x3+1假設生成多項式為：g(x)=x4+x3+1 ;則對應g(x)的代碼為:11001x4m(x)=x10+x8+x7+x4對應的代碼記為：;采用多項式除法：得余數(shù)為：1010 (即校驗字段為：1010)發(fā)送方：發(fā)出的傳輸字段為：1 0 1 1 0 0 1 1010信息字段校驗字段接收方：使用相同的生成碼進行校驗：接收到的字段/生成碼(二進制除法)如果能夠除盡，則正確，給出余數(shù)(1010)的計算步驟：除法沒有數(shù)學上的含義，而是采用計算機的模二除法，即，除數(shù)和被除數(shù) 做異或運算。進行異或運算時除數(shù)和被除數(shù)最高位對齊，按位異或。A11

7、00100000A1100100A1100100111000111000a 11001001010則四位CRCS督碼就為：1010。利用CRG!行檢錯的過程可簡單描述為：在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以一定的規(guī)則產生一個校驗用的r位監(jiān)督碼(CRC碼)，附在原始信息 后邊，構成一個新的二進制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗，以確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”編輯本段代數(shù)學的一般性算法在代數(shù)編碼理論中，將一個碼組表示為一個多項式，碼組中各碼元當作多 項式的系數(shù)。例如 1100101 表示為 1 x6+1

8、 x5+0 x4+0 x3+1 x2+0 x+1, 即 x6+x5+x2+1。設編碼前的原始信息多項式為 P(x) , P(x)的最高幕次加1等于k;生成多 項式為G(x), G(x)的最高幕次等于r; CRCg；項式為R(x);編碼后的帶CRC勺 信息多項式為T(x)。發(fā)送方編碼方法：將P(x)乘以xr(即對應的二進制碼序列左移r位)，再除 以G(x),所得余式即為R(x)。用公式表示為T(x)=xrP(x)+R(x)接收方解碼方法：將T(x)除以G(x),得到一個數(shù)，如果這個余數(shù)為 0,則 說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤。舉例來說，設信息編碼為1100,生成多項式為1011,即P(

9、x)=x3+x2 ,G(x)=x3+x+1 ,計算CRC勺過程為xrP(x) =x3(x3+x2) = x6+x5 G(x)= x3+x+1 即 R(x)=x 。注意至U G(x)最高 幕次r=3,得出CRE 010。如果用豎式除法(計算機的模二，計算過程為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) = x3+x2+x, G(x)=

10、 x3+x+1 無余式?；仡^看一下上面的豎式除法，如果被除數(shù)是 1100010,顯然在商第三個1時，就能除盡。上述推算過程，有助于我們理解CRC的概念。但直接編程來實現(xiàn)上面的算法，不僅繁瑣，效率也不高。實際上在工程中不會直接這樣去計算和驗證CRC下表中列出了一些見于標準的 CRCK料：名稱 生成多項式簡記式*應用舉例CRC-4 x4+x+1 3 ITUCRC-12 x12+x11+x3+x+1CRC-16 x16+x15+x2+1 8005 IBM SDLCCRC-ITU* x16+x12+x5+1 1021 ISO HDLC, ITU , , PPP-FCSCRC-32 x32+x26+x2

11、3+x2+x+104C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32cx32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP*生成多項式的最高幕次項系數(shù)是固定的 1,故在簡記式中，將最高的1統(tǒng)一去 掉了，如04C11DB成際上是104C11DB7 * 前稱CRC-CCITT ITU的前身是 CCITTo備注：(1)生成多項式是標準規(guī)定的(2) CRCK驗碼是基于將位用看作是系數(shù)為0或1的多項式，一個k位的數(shù)據(jù)流可以看作是關于x的從k-1階 到0階的k-1次多項式的系數(shù)序列。采用此編碼，發(fā)送方和接收方必須事先商 定一個生成多項式G(x),其高位和低位必須是1。要計算m位的幀M(x)的校驗 和，基本思想是將校驗和加在幀的末尾，使這個帶校驗和的幀的多項式能被 G(x) 除盡。當接收方收到加有校驗和的幀時，用 G(x)去除它，如果有余數(shù)，則 CRC 校驗錯誤，只有沒有余數(shù)的校驗才是正確的。(3)名稱生成多項式簡記式*標準引用 CRC-4 x4+x+1 3 ITU CRC-8 x8+x5+x4+1 0x31 CRC-8x8+x2+x1+1 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x5E CRC-12 x12+x11+x3+x+1 80F CRC-16 x16+x15+x2+1 80