crc校驗(yàn)碼詳細(xì)介紹看懂了就會(huì)了

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

2、念1、多項(xiàng)式與二進(jìn)制數(shù)碼多項(xiàng)式和二進(jìn)制數(shù)有直接對(duì)應(yīng)關(guān)系： x 的最高幕次對(duì)應(yīng)二進(jìn)制數(shù)的最高位， 以下各位對(duì)應(yīng)多項(xiàng)式的各幕次，有此事次項(xiàng)對(duì)應(yīng) 1,無此幕次項(xiàng)對(duì)應(yīng) 00可以看出：x 的最高幕次為 R,轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)有 R+1 位。多項(xiàng)式包括生成多項(xiàng)式 G(x)ffi 信息多項(xiàng)式 C(x)如生成多項(xiàng)式為 G(x)=xA4+xA3+x+h1 可轉(zhuǎn)換為二進(jìn)制數(shù)碼 11011。而發(fā)送信息位 1111,可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為 C(x)=xA3+xA2+x+.12、生成多項(xiàng)式是接受方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過程中，這個(gè)數(shù)始終保持不變。在發(fā)送方，利用生成多項(xiàng)式對(duì)信息多項(xiàng)式做模 2

3、除生成校驗(yàn)碼。在接受方利用生成多項(xiàng)式對(duì)收到的編碼多項(xiàng)式做模 2 除檢測(cè)和確定錯(cuò)誤位置。應(yīng)滿足以下條件：a、生成多項(xiàng)式的最高位和最低位必須為 1。b、當(dāng)被傳送信息(CRCS)任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做除后應(yīng)該使余數(shù)不為 00c、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。d、對(duì)余數(shù)繼續(xù)做除，應(yīng)使余數(shù)循環(huán)。3CRCK 的生成步驟1、將 x 的最高次幕為 R 的生成多項(xiàng)式 G(x#專換成又 t 應(yīng)的 R+1 位二進(jìn)制數(shù)。2、將信息碼左移 R 位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式 C(x)*2 的 R 次方。3、用生成多項(xiàng)式(二進(jìn)制數(shù))對(duì)信息碼做除，得到 R 位的余數(shù)。4、將余數(shù)拼到信息碼左移后空出的位置，得到完

4、整的 CRC 馬?！纠考僭O(shè)使用的生成多項(xiàng)式是 G(x)=xA3+x+14 位的原始報(bào)文為 1010,求編碼后的報(bào)文。解：1、將生成多項(xiàng)式 G(x)=xA3+x+1 專換成對(duì)應(yīng)的二進(jìn)制除數(shù) 1011。2、此題生成多項(xiàng)式有 4 位( (R+1),要把原始報(bào)文 C(x 左移 3(R)位變成 10100003、用生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)對(duì)左移 3 位后的原始報(bào)文進(jìn)行模 2 除，相當(dāng)于按位異或：1010000101110001011011得到的余位 011,所以最終編碼為：1010011編輯本段生成 CRCK 的基本原理任意一個(gè)由二進(jìn)制位用組成的代碼都可以和一個(gè)系數(shù)僅為0和1取值的多項(xiàng)式對(duì)應(yīng)。例如：代

5、碼 1010111 對(duì)應(yīng)的多項(xiàng)式為 x6+x4+x2+x+1 而多項(xiàng)式為 x5+x3+x2+x+1 寸應(yīng)的代碼 101111。編輯本段 CRCK 集選擇的原則若設(shè)碼字長(zhǎng)度為 N,信息字段為 K 位，校驗(yàn)字段為 R 位(N=K+R)則對(duì)于 CRC 碼集中的任一碼字，存在且僅存在一個(gè) R 次多項(xiàng)式 g(x),使得V(x)=A(x)g(x)=xRm(x)+r(x);其中：m(x)為 K 次原始的信息多項(xiàng)式，r(x)為 R-1 次校驗(yàn)多項(xiàng)式(即 CRCK 驗(yàn)和)，g(x 豚為生成多項(xiàng)式：g(x)=g0+g1x1+g2x2+.+g(R-1)x(R-1)+gRxR發(fā)送方通過指定的 g(x)產(chǎn)生 CRC 碼

6、字，接收方則通過該 g(x 怵驗(yàn)證收到的 CRCk編輯本段CRCK 驗(yàn)碼軟件生成方法：借助于多項(xiàng)式除法，其余數(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(xW 代碼為：11001x4m(x)=x10+x8+x7+x4 寸應(yīng)的代碼記為：10110010000;采用多項(xiàng)式除法：得余數(shù)為：1010(即校驗(yàn)字段為：1010)發(fā)送方：發(fā)出的傳輸字段為：10110011010信息字段校驗(yàn)字段接收方：使用相同的生成碼進(jìn)行校驗(yàn)：接收到的字段/生成碼(二進(jìn)制除法)如果能夠除盡，則正確，給出余數(shù)( (1010)的計(jì)算

7、步驟：除法沒有數(shù)學(xué)上的含義，而是采用計(jì)算機(jī)的模二除法，即，除數(shù)和被除數(shù)做異或運(yùn)算。進(jìn)行異或運(yùn)算時(shí)除數(shù)和被除數(shù)最高位對(duì)齊，按位異或。1011001000071001011110100001111010000710010011110000111100007100100111000111000A11001001010則四位 CRC 監(jiān)督碼就為：1010。利用 CRC!行檢錯(cuò)的過程可簡(jiǎn)單描述為：在發(fā)送端根據(jù)要傳送的 k 位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的 r 位監(jiān)督碼( (CRM),附在原始信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共 k+r 位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC 碼之間

8、所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。這個(gè)規(guī)則，在差錯(cuò)控制理論中稱為“生成多項(xiàng)式”。編輯本段代數(shù)學(xué)的一般性算法在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如 1100101 表示為 1x6+1x5+0 x4+0 x3+1x2+0 x+1,即 x6+x5+x2+1設(shè)編碼前的原始信息多項(xiàng)式為 P(x),P(xW 最高幕次加 1 等于 k；生成多項(xiàng)式為G(x),G(x)勺最高幕次等于 r；CRC 多項(xiàng)式為 R(x);編碼后的帶 CRC 的信息多項(xiàng)式為 T(x)0發(fā)送方編碼方法：將 P(x 銖以 xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移 r 位)，再除以G(x),所得余式

9、即為 R(x用公式表示為 T(x)=xrP(x)+R(x)接收方解碼方法：將 T(x 除以 G(x),得到一個(gè)數(shù)，如果這個(gè)余數(shù)為 0,則說明傳輸中無錯(cuò)誤發(fā)生，否則說明傳輸有誤。舉例來說，設(shè)信息編碼為 1100,生成多項(xiàng)式為 1011,即 P(x)=x3+x2G(x)=x3+x+1 計(jì)算 CRC 的過程為xrP(x)=x3(x3+x2)=x6+x5G(x)=x3+x+1R(x)=x注意至UG(x)!i高幕次r=3,得出CRC為 010o如果用豎式除法(計(jì)算機(jī)的模二，計(jì)算過程為11101011/1100000(1100 左移 3 位)1011-11101011-10101011-00100000-

10、010 因止匕，T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010如果傳輸無誤，T(x)=(x6+x5+x/G(x)=x3+x2+x,G(x)=x3+x+1余式?；仡^看下上面的豎式除法，如果被除數(shù)是 1100010,顯然在商第三個(gè) 1 時(shí)，就能除盡。上述推算過程，有助于我們理解 CRC 的概念。但直接編程來實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會(huì)直接這樣去計(jì)算和驗(yàn)證 CRC卜表中列出了一些見于標(biāo)準(zhǔn)的 CR 匾料:名稱生成多項(xiàng)式簡(jiǎn)記式*應(yīng)用舉例CRC-4x4+x+13ITUG.704CRC-12x12+x11+x3+x+1CRC-16x16

11、+x15+x2+18005IBMSDLCCRC-ITU*x16+x12+x5+11021ISOHDLC,ITUX.25.34/V.41/V.42,PPP-FCSCRC-32x32+x26+x23+.+x2+x+104C11DB7ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCSCRC-32cx32+x28+x27+.+x8+x6+11EDC6F41SCTP*生成多項(xiàng)式的最高幕次項(xiàng)系數(shù)是固定的 1,故在簡(jiǎn)記式中，將最高的 1 統(tǒng)一去掉了， 如 04C11DB7實(shí)際上是104C11DB7*前稱 CRC-CCITTITU的前身是CCITT備注：( (1)生成多項(xiàng)式是標(biāo)準(zhǔn)

12、規(guī)定的(2)CRCK 驗(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ò)誤，只有沒有余數(shù)的校驗(yàn)才是正確的。( (3)名稱生成多項(xiàng)式簡(jiǎn)記式*標(biāo)準(zhǔn)引用CRC-4x4+x+13ITUG.704CRC-8x8+x5+x4+10 x31CRC-8x8+x2+x1+10 x07CRC-8x8+x6+x4+x3+x2+x10 x5CRC-12x12+x11+x3+x+180FCRC-16x16+x