奇偶校驗碼,海明碼,循環(huán)冗余CRC

1、1、奇偶校驗碼二進(jìn)制數(shù)據(jù)經(jīng)過傳送、存取等環(huán)節(jié)，會發(fā)生誤碼（1變成0或0變成1），這就有如何發(fā)現(xiàn)及糾正誤碼的問題。所有解決此類問題的方法就是在原始數(shù)據(jù)（數(shù)碼位）基礎(chǔ)上增加幾位校驗（冗余）位。、碼距一個編碼系統(tǒng)中任意兩個合法編碼（碼字）之間不同的二進(jìn)數(shù)位（bit）數(shù)叫這兩個碼字的碼距，而整個編碼系統(tǒng)中任意兩個碼字的的最小距離就是該編碼系統(tǒng)的碼距。如圖1所示的一個編碼系統(tǒng)，用三個bit來表示八個不同信息中。在這個系統(tǒng)中，兩個碼字之間不同的bit數(shù)從1到3不等，但最小值為1，故這個系統(tǒng)的碼距為1。如果任何碼字中一位或多位被顛倒了，結(jié)果這個碼字就不能與其它有效信息區(qū)分開。例如，如果傳送信息001，而被誤

2、收為011，因011仍是表中的合法碼字，接收機(jī)仍將認(rèn)為011是正確的信息。然而，如果用四個二進(jìn)數(shù)字來編8個碼字，那么在碼字間的最小距離可以增加到2，如圖信息序號二進(jìn)碼字a2a1a0000010012010301141005101611071112的表中所示。信息序號二進(jìn)碼字a3a2a1a00000011001210103001141100501016011071111碼距碼能力檢錯糾錯100注意，圖8-2的8個碼字相互間最少有兩bit的差異。 因此，如果任何信息的一個數(shù)位被顛倒，就成為一個不用的 碼字，接收機(jī)能檢查出來。例如信息是1001,誤收為1011, 接收機(jī)知道發(fā)生了一個差錯，因為 10

3、11不是一個碼字（表21 032或142加152加263加273加3中沒有）。然而，差錯不能被糾正。假定只有一個數(shù)位是錯 的，正確碼字可以是1001, 1111, 0011或1010。接收者不 能確定原來到底是這4個碼字中的那一個。也可看到，在這個系統(tǒng)中，偶數(shù)個（2或4）差錯也無法發(fā)現(xiàn)。為了使一個系統(tǒng)能檢查和糾正一個差錯，碼間最小距離 必須至少是“ 3”。最小距離為3時，或能糾正一個錯，或 能檢二個錯，但不能同時糾一個錯和檢二個錯。編碼信息糾 錯和檢錯能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小 距離。圖8-3的表概括了最小距離為1至7的碼的糾錯和 檢錯能力碼距越大，糾錯能力越強，但數(shù)據(jù)冗余也越

4、大，即編碼效率低了。所以，選擇碼距要取決 于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計者必須考慮信息發(fā)生差錯的概率和該系統(tǒng)能容許的最小差 錯率等因素。要有專門的研究來解決這些問題。二、奇偶校驗奇偶校驗碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡單和廣泛采用的方法。例如，單個的奇偶校驗將使碼的最小距離由一增加到二。一個二進(jìn)制碼字，如果它的碼元有奇數(shù)個1，就稱為具有奇性。例如，碼字“ 10110101”有五個1，因此，這個碼字具有奇性。同樣，偶性碼字具有偶數(shù)個1。注意奇性檢測等效于所有碼元的模二加，并能夠由所有碼元的異或運算來確定。對于一個n位字，奇性由下式給出：奇性=a0 ® a1 ® a2

5、$ an奇偶校驗可描述為：給每一個碼字加一個校驗位，用它來構(gòu)成奇性或偶性校驗。例如，在圖8-2中，就是這樣做的?？梢钥闯觯郊哟a元d2，是簡單地用來使每個字成為偶性的。因此，若有一個碼元是錯的，就可以分辨得出，因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一 位校驗位來使編碼中 1個個數(shù)為奇數(shù)（奇校驗）或者為偶數(shù)（偶校驗），從而使碼距變?yōu)?。因為其利用的是編碼中1的個數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯誤。再以數(shù)字0的七位ASCII碼（0110000 ）為例，如果傳送后右邊第一位出錯，0變成1。接收端還認(rèn)為是一個合法的代碼0110001 （數(shù)字1的ASCII碼）。若在最左邊加一位奇校驗位，編

6、碼變?yōu)?0110000，如果傳送后右邊第一位出錯，則變成 10110001，1的個數(shù)變成偶數(shù)，就 不是合法的奇校驗碼了。但若有兩位（假設(shè)是第1、2位）出錯就變成10110011 ，1的個數(shù)為5，還是奇數(shù)。接收端還認(rèn)為是一個合法的代碼（數(shù)字3的ASCII碼）。所以奇偶校驗不能發(fā)現(xiàn)。奇偶校驗位可由硬件電路（異或門）或軟件產(chǎn)生:偶校驗位 an =aO ® al ® a2 $ an-1 ,奇校驗位 an =NOT (a0 ® al ® a2 ® ® an-1 )。在一個典型系統(tǒng)里，在傳輸以前，由奇偶發(fā)生器把奇偶校驗位加到每個字中。原有信息中的

7、數(shù)字在接收機(jī)中被檢測，如果沒有出現(xiàn)正確的奇、偶性，這個信息標(biāo)定為錯誤的，這個系統(tǒng)將把錯誤的字拋掉或者請求重發(fā)。-分組奇偶校驗碼。在實際工作中還經(jīng)常采用縱橫都加校驗奇偶校驗位的編碼系統(tǒng)現(xiàn)在考慮一個系統(tǒng)，它傳輸若干個長度為 m位的信息。如果把這些信息都編成每組n個信息的分組，則在這些不同的信息間，也如對單個信息一樣，能夠作奇偶校驗。圖4中n個信息的一個分組排列成矩形式樣，并以橫向奇偶（HP ）及縱向奇偶（VP ）的形式編出奇偶校驗位。m位數(shù)字橫向奇偶位n個碼字ala2am-1amHP1blb2bm-1bmHP2clc2cm-1cmHP3縱向奇偶位n1n2nm-1nmHPnVP1VP2VPm-IVP

8、r1 HPn+1圖4用綜橫奇偶校驗的分組奇偶校驗碼研究圖4可知：分組奇偶校驗碼不僅能檢測許多形式的錯誤。并且在給定的行或列中產(chǎn)生孤立的錯誤時，還可對該錯誤進(jìn)行糾正。在初級程序員試題中（早期也出現(xiàn)在程序員試題中），經(jīng)常有綜橫奇偶校驗的題目。一般 解法應(yīng)該是這樣：先找一行或一列已知數(shù)據(jù)完整的，確定出該行（或列）是奇校驗還是偶校驗。并假設(shè)行與列都采用同一種校驗（這個假設(shè)是否正確，在全部做完后可以得到驗證）。然后找 只有一個未知數(shù)的行或列，根據(jù)校驗性質(zhì)確定該未知數(shù)，這樣不斷做下去，就能求出所有未知 數(shù)?！纠?001年初級程序員試題由6個字符的7位ASCII編碼排列，再加上水平垂直奇偶校驗位構(gòu)成下列矩

9、陣（最后 一列為水平奇偶校驗位，最后一行為垂直奇偶校驗位）：|字符|7位ASCII碼HP30X1X200110Y1100100X31+X41010110Y201X5X61111D100X710X80=0X9111X1C11VP00111X111X12則X1 X2 X3 X4 處的比特分別為 _(36).X5 X6 X7 X8處的比特分別為：X9 X10 XI1 X12 處的比特分別為 _(38)_ ; Y1和Y2處的字符分別為_(39)_和 _(40)。解從ASCII碼左起第5列可知垂直為偶校驗。則：從第1列可知X4=0 ;從第3行可知水平也是偶校驗。從第2行可知X3=1 ;從第7列可知X8=

10、0 ;從第8列可知X12=1 ；從第7行可知X11=1 ;從第6列可知X10=0 ；從第6行可知X9=1 ;從第2列可知X仁1 ；從第1行可知X2=1 ;從第3列可知X5=1 ;從第4行可知X6=0 ;從第4列(或第5行)可知X7=0 ;整理一下：(36) X1X2X3X4 = 1110(37) X5X6X7X8 = 1000(38) X9X10X11X12 = 1011(39) 由字符Y1的ASCII碼100100仁49H 知道，Y1即是“ I ('由“ D的ASCII碼是1000100=44H 推得)(40) 由字符Y2的ASCII碼011011仁37H 知道，Y2即是“7”由“3

11、的 ASCII碼是011001 仁33H 推得)假如你能記住 “0的ASCII碼是0110000=30H ; “A的ASCII碼是100000仁41H，則解起 來就更方便了。2、海明校驗我們在前面指出過要能糾正信息字中的單個錯誤，所需的最小距離為3。實現(xiàn)這種糾正的方法之一是海明碼。海明碼是一種多重（復(fù)式）奇偶檢錯系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯和糾錯。 用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這種奇偶位 被編在傳輸碼字的特定位置上。實現(xiàn)得合適時，這個系統(tǒng)對于錯誤的數(shù)位無論是原有信息位中 的，還是附加校驗位中的都能把它分離出來。推導(dǎo)并使用長度為 m位的碼

12、字的海明碼，所需步驟如下：1、 確定最小的校驗位數(shù) k,將它們記成 D1、D2、Dk，每個校驗位符合不同的奇偶 測試規(guī)定。2、原有信息和k個校驗位一起編成長為 m+k位的新碼字。選擇 k校驗位（0或1）以滿 足必要的奇偶條件。3、 對所接收的信息作所需的k個奇偶檢查。4、如果所有的奇偶檢查結(jié)果均為正確的，則認(rèn)為信息無錯誤。如果發(fā)現(xiàn)有一個或多個錯了，則錯誤的位由這些檢查的結(jié)果來唯一地確定。校驗位數(shù)的位數(shù)推求海明碼時的一項基本考慮是確定所需最少的校驗位數(shù)k。考慮長度為m位的信息，若附加了 k個校驗位，則所發(fā)送的總長度為m+k。在接收器中要進(jìn)行 k個奇偶檢查，每個檢查結(jié)果或是真或是偽。這個奇偶檢查的

13、結(jié)果可以表示成一個k位的二進(jìn)字，它可以確定最多2k種不同狀態(tài)。 這些狀態(tài)中必有一個其所有奇偶測試試都是真的，它便是判定信息正確的條件。于是剩下的（2k-1 ）種狀態(tài)，可以用來判定誤碼的位置。于是導(dǎo)出下一關(guān)系：2k-1 > m+k碼字格式從理論上講，校驗位可放在任何位置，但習(xí)慣上校驗位被安排在1、2、4、&的位置上。圖 5歹U出了 m=4 , k=3 時，信息位和校驗位的分布情況。碼字位置B1B2B3B4B5B6B7校驗位xxx信息位xxxx復(fù)合碼字P1P2D1P3D2D3D4圖5海明碼中校驗位和信息位的定位校驗位的確定k個校驗位是通過對 m+k位復(fù)合碼字進(jìn)行奇偶校驗而確定的。其中

14、：P1位負(fù)責(zé)校驗海明碼的第 1、3、5、7、（ P1、D1、D2、D4、）位，（包括P1自己）P2負(fù)責(zé)校驗海明碼的第2、3、6、7、- （P2、D1、D3、D4、）位，（包括P2自己）P3負(fù)責(zé)校驗海明碼的第4、5、6、7、- （P3、D2、D3、D4、）位，（包括P3自己）對m=4 , k=3，偶校驗的例子，只要進(jìn)行三次偶性測試。這些測試（以A、B、C表示）在圖6所示各位的位置上進(jìn)行。因此可得到三個校驗方程及確定校驗位的三個公式:A=B1 ® B3 ® B5 ® B7=0 得 P1=D1 ® D2 ® D4B=B2 ® B3 

15、4; B6 ® B7=0 得 P2=D1 ® D3 ® D4C=B4 ® B5 ® B6 ® B7=0 得 P3=D2 ® D3 ® D4若四位信息碼為1001，利用這三個公式可求得三個校驗位P1、P2、P3值。和海明碼，如圖7則表示了信息碼為1001時的海明碼編碼的全部情況。而圖8中則列出了全部16種信息(D1D2D3D4=00001111 )的海明碼。置碼字位1B2B3EE45E6E7B型碼位類1P2P1)F32D3D4D信息碼-1-001校驗位00-1-編碼后的海明碼0011001圖7四位信息碼的海明編碼P1

16、P2D1P3D2D3D40000000110100101010101000011100110001001011100110000111111100000011001101101001100110111100101010100101101111111圖8未編碼信息的海明碼上面是發(fā)送方的處理在接收方，也可根據(jù)這三個校驗方程對接收到的信息進(jìn)行同樣的奇偶測試:A=B1 ® B3 ® B5 ® B7=0 ;B=B2 ® B3 ® B6 ® B7=0 ;C=B4 ® B5 ® B5 ® B7=0。若三個校驗方程都成立

17、，即方程式右邊都等于 0,則說明沒有錯。若不成立即方程式右邊不 等于0,說明有錯。從三個方程式右邊的值，可以判斷那一位出錯。例如，如果第3位數(shù)字反 了，貝y C=0(此方程沒有B3), A=B=1 (這兩個方程有 B3 )?？蓸?gòu)成二進(jìn)數(shù) CBA，以A為最 低有效位，則錯誤位置就可簡單地用二進(jìn)數(shù) CBA=011 指出。同樣，若三個方程式右邊的值為 001 ，說明第 1 位出錯。若三個方程式右邊的值為 100， 說明第 4 位出錯。海明碼的碼距應(yīng)該是 3，所以能糾正 1 位出錯。而奇偶校驗碼的碼距才是2，只能發(fā)現(xiàn) 1位出錯，但不能糾正(不知道那一位錯)。無校驗的碼距是 1 ，它出任何一位出錯后還是

18、合法 代碼，所以也就無法發(fā)現(xiàn)出錯。這是關(guān)于海明碼的經(jīng)典說法，即碼距為 3，可以發(fā)現(xiàn) 2 位，或者糾正 1 位錯。應(yīng)滿足 2k-1 > m+k。但在清華的王愛英主編的計算機(jī)組成與結(jié)構(gòu) (該書已成為國內(nèi)的權(quán)威)中還提出了一 種碼距為4的海明碼，可以發(fā)現(xiàn) 2位，并且糾正1位錯。應(yīng)滿足 2(k-1) > m+k,由于王愛英書上對這兩種概念沒有很仔細(xì)解釋 (特別對碼距為 3 的海明碼)，過渡很突然。 有些書簡單抄襲時沒有仔細(xì)消化，所以出現(xiàn)一些概念錯。對于一般碼距為3 的海明碼，應(yīng)該是“可以發(fā)現(xiàn) 2位，或者糾正 1位錯”，而不是“可以發(fā)現(xiàn) 2位，并且糾正 1位錯”。在試題中出現(xiàn) 過類似的錯誤。

19、3. CRC在串行傳送(磁盤、通訊)中，廣泛采用循環(huán)冗余校驗碼(CRC )。 CRC 也是給信息碼加上幾位校驗碼，以增加整個編碼系統(tǒng)的碼距和查錯糾錯能力。CRC 的理論很復(fù)雜，一般書上只介紹已有生成多項式后計算校驗碼的方法。檢錯能力與 生成多項式有關(guān)，只能根據(jù)書上的結(jié)論死記。循環(huán)冗余校驗碼(CRC )的基本原理是：在 K位信息碼后再拼接 R位的校驗碼，整個編 碼長度為N位，因此，這種編碼又叫(N, K)碼。對于一個給定的(N, K)碼，可以證明存 在一個最高次幕為 N-K=R的多項式G(x)。根據(jù)G(x)可以生成K位信息的校驗碼，而G(x)叫做 這個 CRC 碼的生成多項式。校驗碼的具體生成過

20、程為：假設(shè)發(fā)送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成 C(x)*2R ，這樣 C(x) 的右邊就會空出 R 位，這就是校驗碼的位置。通過 C(x)*2R 除以 生成多項式 G(x) 得到的余數(shù)就是校驗碼。幾個基本概念1 、多項式與二進(jìn)制數(shù)碼多項式和二進(jìn)制數(shù)有直接對應(yīng)關(guān)系：x的最高幕次對應(yīng)二進(jìn)制數(shù)的最高位，以下各位對應(yīng)多項式的各幕次，有此幕次項對應(yīng)1,無此幕次項對應(yīng) 0?？梢钥闯觯簒的最高幕次為 R，轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有 R+1位。多項式包括生成多項式G(x)和信息多項式C(x)。如生成多項式為 G(x)=x4+x3+x+1， 可轉(zhuǎn)換為二進(jìn)制數(shù)碼 11011。而發(fā)送信息位

21、 1111，可轉(zhuǎn)換為數(shù)據(jù)多項式為C(x)=x3+x2+x+1 。2、生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進(jìn)制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。在發(fā)送方，利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。應(yīng)滿足以下條件：a、 生成多項式的最高位和最低位必須為1。b、 當(dāng)被傳送信息(CRC碼)任何一位發(fā)生錯誤時，被生成多項式做模2除后應(yīng)該使余數(shù) 不為0。c、不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。d、對余數(shù)繼續(xù)做模 2除，應(yīng)使余數(shù)循環(huán)。將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料查到常用的對應(yīng)于不同碼制的生成

22、多項式如圖 9所示:NK碼距dG(x)多項式G(x)743x3+x+11011743x3+x2+11101734x4+x3+x2+111101734x4+x2+x+11011115113x4+x+1100111575x8+x7+x6+x4+111101000-31263x5+x2+110010131215x10+x9+x8+x6+x5+x3+11110110100163573x6+x+1100001163515x12+x10+x5+x4+x2+1101000011010110411024x16+x15+x2+111000000000000101圖9常用的生成多項式3、模2除（按位除）模2除做法

23、與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。 所以實際上就是異或。然后再移位移位做下一位的模2減。步驟如下：a、 用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。b、 除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對余數(shù)做模2減。若余數(shù)最高位為 商為0,除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)。【例】1111000除以1101 :1011商1111000-被除數(shù)1101除數(shù)010000110101010111余數(shù)1101CRC 碼的生成步驟1、將 x 的最高冪次為 R 的生成多項式 G(x) 轉(zhuǎn)換成對應(yīng)的 R+1 位二進(jìn)制數(shù)。2 、將信息碼左移 R

24、 位，相當(dāng)與對應(yīng)的信息多項式 C(x)*2R3 、用生成多項式(二進(jìn)制數(shù))對信息碼做模2 除，得到 R 位的余數(shù)。4 、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC 碼。文?！纠考僭O(shè)使用的生成多項式是 G(x)=x3+x+1 。4 位的原始報文為 1010 ，求編碼后的報解：1、將生成多項式 G(x)=x3+x+1 轉(zhuǎn)換成對應(yīng)的二進(jìn)制除數(shù) 1011 。2、 此題生成多項式有 4位(R+1 )，要把原始報文 C(x)左移3 ( R)位變成10100003、 用生成多項式對應(yīng)的二進(jìn)制數(shù)對左移4 位后的原始報文進(jìn)行模 2 除：1001 商10100001011 除數(shù)10001011011 余

25、數(shù)(校驗位)5 、編碼后的報文( CRC 碼)1010000+ 0111010011CRC 的和糾錯在接收端收到了 CRC碼后用生成多項式為 G(x)去做模2除，若得到余數(shù)為0,則碼字無誤。 若如果有一位出錯，則余數(shù)不為0，而且不同位出錯，其余數(shù)也不同?？梢宰C明，余數(shù)與出錯位的對應(yīng)關(guān)系只與碼制及生成多項式有關(guān)，而與待測碼字(信息位)無關(guān)。圖10給出了 G(x)=1011 , C(x) = 1010的出錯模式，改變 C(x)(碼字)，只會改變表中碼字內(nèi)容，不改變余數(shù) 與出錯位的對應(yīng)關(guān)系。收到的CR(碼字余數(shù)出錯位碼位A7A6A5A4A3A2A1正確1010011000無0011101001001

26、0210100011003錯101011110110110114誤100001111051110011111600100111017圖10(7, 4) CRC碼的出錯模式(G(x) = 1011 )如果循環(huán)碼有一位出錯，用G(x)作模2除將得到一個不為 0的余數(shù)。如果對余數(shù)補0繼續(xù)除下去，我們將發(fā)現(xiàn)一個有趣的結(jié)果；各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯，余數(shù)將為001，補0后再除(補0后若最高位為1，則用除數(shù)做模 2減取余；若最高位為 0,則 其最低3位就是余數(shù))，得到第二次余數(shù)為 010。以后繼續(xù)補0作模2除，依次得到余數(shù)為100 , 011，反復(fù)循環(huán)，這就是 循環(huán)碼”名稱的由來。這是一

27、個有價值的特點。如果我們在求出余數(shù) 不為0后，一邊對余數(shù)補 0繼續(xù)做模2除，同時讓被檢測的校驗碼字循環(huán)左移。圖10說明，當(dāng)出現(xiàn)余數(shù)(101)時，出錯位也移到 A7位置?？赏ㄟ^異或門將它糾正后在下一次移位時送回A1。這樣我們就不必像海明校驗?zāi)菢佑米g碼電路對每一位提供糾正條件。當(dāng)位數(shù)增多時，循環(huán)碼校 驗?zāi)苡行У亟档陀布鷥r，這是它得以廣泛應(yīng)用的主要原因?！纠繉D10的CRC碼(G(x) = 1011 ,C(x) = 1010 )，若接收端收到的碼字為1010111 ,用G(x) = 1011做模2除得到一個不為 0的余數(shù)100 ,說明傳輸有錯。將此余數(shù)繼續(xù)補 0用G(x) =1011作模2除，同

28、時讓碼字循環(huán)左移1010111 o做了 4次后，得到余數(shù)為101，這時碼字也循環(huán)左移4位，變成1111010。說明出錯位已移到最高位 A7 ,將最高位1取反后變成0111010。 再將它循環(huán)左移 3位，補足7次，出錯位回到 A3位，就成為一個正確的碼字1010011。通信與網(wǎng)絡(luò)中常用的 CRCCRC在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常 k 相當(dāng)大，由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀，而后采用 碼產(chǎn)生 r 位的校驗位。它只能檢測出錯誤，而不能糾正錯誤。一般取 r=16 ，標(biāo)準(zhǔn)的 16 位生成 多項式有 CRC-16 = x16+x15+x2+1 和 CRC-CCITT = x16+x15+x2+1。一般情況下，r

29、位生成多項式產(chǎn)生的 CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度 小于等于r的突發(fā)錯以及（1-2-（r-1）的突發(fā)長度為r+1的突發(fā)錯和（1-2-r ）的突發(fā)長度大于 r+1 的突發(fā)錯。例如，對上述 r=16 的情況，就能檢測出所有突發(fā)長度小于等于 16 的突發(fā)錯以 及99997%的突發(fā)長度為 17的突發(fā)錯和 99998%的突發(fā)長度大于 17 的突發(fā)錯。所以 CRC 碼的檢錯能力還是很強的。這里，突發(fā)錯誤是指幾乎是連續(xù)發(fā)生的一串錯，突發(fā)長度就是指從 出錯的第一位到出錯的最后一位的長度（但是，中間并不一定每一位都錯 ）?！纠?】某循環(huán)冗余碼（CRC ）的生成多項式 G（x） = x3+x2+1

30、 ,用此生成多項式產(chǎn)生的 冗余位，加在信息位后形成 CRC 碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分別為 A 和B_。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯的CRC碼，例如碼A:lllll00 1111101 11111 10 1111111B:1100100 1100101 1100110 1100111CE: 0000000 0001100 0010111 1001111 1010001 1011000供選擇的答案字C_、_ D_、和E_。（ 1998 年試題 11）1000110解：A : G(x) = 1101 , C(x) = 1111 C(x)*2

31、3 £(x) = 1111000-1101 = 1011 余 111得到的 CRC 碼為 1111111B : G(x) = 1101 , C(x) = 1100 C(x)*23 -G(x) = 1100000-1101 = 1001 余 101得到的 CRC 碼為 1100101CE:分別用 G(x) = 1101對 作模2除：0000000- 1101 余0001111101- 1101余 001 0010111-1101余 0000011010- 1101余 0001000110-1101余 000 1001111-1101余 1001010001- 1101余 0001011000-1101余 100所以 C 、D和 E的答案是、【例 2】計算機(jī)中常用的一種檢錯碼是 CRC ，即 _A_