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

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

2、誤收為011,因011仍是表中的合法碼字，接收機(jī)仍將認(rèn)為011是正確的信息。然而，如果用四個(gè)二進(jìn)數(shù)字來(lái)編8個(gè)碼字，那么在碼字間的最小距離可以增加到2,如圖信息序號(hào)二進(jìn)碼字a2alaO0000100120103011410051016110FTi111圖2注意， 圖8-2的8個(gè)碼字相互間最少有兩bit因此， 如果任何信息的一個(gè)數(shù)位被顛倒，碼字，接收機(jī)能檢查出來(lái)。例如信息是1001,誤收為1011接收機(jī)知道發(fā)生了一個(gè)差錯(cuò)，因?yàn)?011不是一個(gè)碼字（表中沒有）。然而，差錯(cuò)不能被糾正。信息序號(hào)二進(jìn)碼字aSa2 al aO00000110012101030011411005010160110FTi11_

3、1I碼距碼能力檢錯(cuò)糾錯(cuò)10023456f102或12加12加23加23加3的，正確碼字可以是1001,1111,0011或1010能確定原來(lái)到底是這4個(gè)碼字中的那一個(gè)。也可看到，這個(gè)系統(tǒng)中，偶數(shù)個(gè)（2或4）差錯(cuò)也無(wú)法發(fā)現(xiàn)。為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò)，必須至少是“3：最小距離為3時(shí)，或能糾正一個(gè)錯(cuò)，或能檢二個(gè)錯(cuò)，但不能同時(shí)糾一個(gè)錯(cuò)和檢二個(gè)錯(cuò)。錯(cuò)和檢錯(cuò)能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。圖8-3的表概括了最小距離為1至7的碼的糾錯(cuò)和檢錯(cuò)能力。圖3碼距越大，糾錯(cuò)能力越強(qiáng)，但數(shù)據(jù)冗余也越大，即編碼效率低了。所以，選擇碼距要取決于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計(jì)者必須考慮信息發(fā)生差錯(cuò)的

4、概率和該系統(tǒng)能容許的最小差錯(cuò)率等因素。要有專門的研究來(lái)解決這些問題。二、奇偶校驗(yàn)奇偶校驗(yàn)碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡(jiǎn)單和廣泛采用的方法。例如，單個(gè)的奇偶校驗(yàn)將使碼的最小距離由一增加到二。一個(gè)二進(jìn)制碼字，如果它的碼元有奇數(shù)個(gè)1,就稱為具有奇性。例如，碼字“1011010K五個(gè)1,因此，這個(gè)碼字具有奇性。同樣，偶性碼字具有偶數(shù)個(gè)1。注意奇性檢測(cè)等效于所有碼元的模二加，并能夠由所有碼元的異或運(yùn)算來(lái)確定。對(duì)于一個(gè)n位字，奇性由下式給出：奇性=a0a1a2an奇偶校驗(yàn)可描述為：給每一個(gè)碼字加一個(gè)校驗(yàn)位，用它來(lái)構(gòu)成奇性或偶性校驗(yàn)。例如，在圖8-2中，就是這樣做的。可以看出，附加碼元d2,是簡(jiǎn)單地

5、用來(lái)使每個(gè)字成為偶性的。因此，若有一個(gè)碼元是錯(cuò)的，就可以分辨得出，因?yàn)槠媾夹ｒ?yàn)將成為奇性。奇偶校驗(yàn)編碼通過(guò)增加一位校驗(yàn)位來(lái)使編碼中1個(gè)個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或者為偶數(shù)（偶校驗(yàn)），從而使碼距變?yōu)?。因?yàn)槠淅玫氖蔷幋a中1的個(gè)數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。再以數(shù)字0的七位ASCII碼（0110000）為例，如果傳送后右邊第一位出錯(cuò)，0變成1。接收端還認(rèn)為是一個(gè)合法的代碼0110001（數(shù)字1的ASCII碼）。若在最左邊加一位奇校驗(yàn)位，編碼變?yōu)?0110000,如果傳送后右邊第一位出錯(cuò)，則變成10110001,1的個(gè)數(shù)變成偶數(shù)，就不是合法的奇校驗(yàn)碼了。但若有兩位（假設(shè)是第1、2位）出錯(cuò)就

6、變成10110011,1的個(gè)數(shù)為5,還是奇數(shù)。接收端還認(rèn)為是一個(gè)合法的代碼（數(shù)字3的ASCII碼）。所以奇偶校驗(yàn)不能發(fā)現(xiàn)。奇偶校驗(yàn)位可由硬件電路（異或門）或軟件產(chǎn)生：偶校驗(yàn)位an=a0a1a2an-1,奇校驗(yàn)位an=NOT（a0a1a2an-1）0在一個(gè)典型系統(tǒng)里，在傳輸以前，由奇偶發(fā)生器把奇偶校驗(yàn)位加到每個(gè)字中。原有信息中的數(shù)字在接收機(jī)中被檢測(cè)，如果沒有出現(xiàn)正確的奇、偶性，這個(gè)信息標(biāo)定為錯(cuò)誤的，這個(gè)系統(tǒng)將把錯(cuò)誤的字拋掉或者請(qǐng)求重發(fā)。在實(shí)際工作中還經(jīng)常采用縱橫都加校驗(yàn)奇偶校驗(yàn)位的編碼系統(tǒng)-分組奇偶校驗(yàn)碼。現(xiàn)在考慮一個(gè)系統(tǒng)，它傳輸若干個(gè)長(zhǎng)度為m位的信息。如果把這些信息都編成每組n個(gè)信息的分組，則

7、在這些不同的信息問，也如對(duì)單個(gè)信息一樣，能夠作奇偶校驗(yàn)。圖4中n個(gè)信息的一個(gè)分組排列成矩形式樣，并以橫向奇偶（HP）及縱向奇偶（VP）的形式編出奇偶校驗(yàn)m位數(shù)字橫向奇偶位n個(gè)碼字ala2*tam-1amHP1blb2,-*ii,-*iibm-1bmHP2clc29-9curdcmHP3 *fe*fe*4縱向奇偶位nln2-nm-1runHPnVP1 VP2VPm-1 VPmHPn+17位ASCII碼|麗圖4用綜橫奇偶校驗(yàn)的分組奇偶校驗(yàn)碼研究圖4可知：分組奇偶校驗(yàn)碼不僅能檢測(cè)許多形式的錯(cuò)誤。并且在給定的行或列中產(chǎn)生孤立的錯(cuò)誤時(shí)，還可對(duì)該錯(cuò)誤進(jìn)行糾正。在初級(jí)程序員試題中（早期也出現(xiàn)在程序員試題中）

8、，經(jīng)常有綜橫奇偶校驗(yàn)的題目。一般解法應(yīng)該是這樣：先找一行或一列已知數(shù)據(jù)完整的，確定出該行（或列）是奇校驗(yàn)還是偶校驗(yàn)。并假設(shè)行與列都采用同一種校驗(yàn)（這個(gè)假設(shè)是否正確，在全部做完后可以得到驗(yàn)證）。然后找只有一個(gè)未知數(shù)的行或列，根據(jù)校驗(yàn)性質(zhì)確定該未知數(shù)，這樣不斷做下去，就能求出所有未知數(shù)?！纠?001年初級(jí)程序員試題由6個(gè)字符的7位ASCII編碼排列，再加上水平垂直奇偶校驗(yàn)位構(gòu)成下列矩陣（最后:30 XIX20010Y1100100 X31十X41010110Y201X5X61111D100X710 X80ZZ0 X9111 X1011VP00111 XII1X12則X1X2X3X4處的比特分別為

9、_(36)_;X5X6X7X8處的比特分另1J為;X9X10XI1X12處的比特分別為_(38)_;Y1和Y2處的字符分別為_(39)_和_(40)_。解從ASCII碼左起第5列可知垂直為偶校驗(yàn)。則：從第1列可知X4=0;從第3行可知水平也是偶校驗(yàn)。從第2行可知X3=1;從第7列可知X8=0;從第8列可知X12=1;從第7行可知X11=1;從第6列可知X10=0;從第6行可知X9=1;從第2列可知X1=1;從第1行可知X2=1;從第3列可知X5=1;從第4行可知X6=0;從第4列(或第5行)可知X7=0;整理一下：(36)X1X2X3X4=1110(37)X5X6X7X8=1000(38)X9

10、X10X11X12=1011(39)由字符Y1的ASCII碼1001001=49H知道，Y1即是“I(由D的ASCII碼是1000100=44H推得)(40)由字符Y2的ASCII碼0110111=37H知道，Y2即是“7”(由3的ASCII碼是0110011=33H推得)假如你能記住“0的ASCII碼是0110000=30H;A的ASCII碼是1000001=41H,則解起來(lái)就更方便了。2、海明校驗(yàn)我們?cè)谇懊嬷赋鲞^(guò)要能糾正信息字中的單個(gè)錯(cuò)誤，所需的最小距離為3。實(shí)現(xiàn)這種糾正的方法之一是海明碼。海明碼是一種多重（復(fù)式）奇偶檢錯(cuò)系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯(cuò)和糾錯(cuò)。用在海明碼中的全部

11、傳輸碼字是由原來(lái)的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這種奇偶位被編在傳輸碼字的特定位置上。實(shí)現(xiàn)得合適時(shí)，這個(gè)系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無(wú)論是原有信息位中的，還是附加校驗(yàn)位中的都能把它分離出來(lái)。推導(dǎo)并使用長(zhǎng)度為m位的碼字的海明碼，所需步驟如下：1、確定最小的校驗(yàn)位數(shù)k,將它們記成D1、D2、Dk,每個(gè)校驗(yàn)位符合不同的奇偶測(cè)試規(guī)定。2、原有信息和k個(gè)校驗(yàn)位一起編成長(zhǎng)為m+k位的新碼字。選擇k校驗(yàn)位（0或1）以滿足必要的奇偶條件。3、對(duì)所接收的信息作所需的k個(gè)奇偶檢查。4、如果所有的奇偶檢查結(jié)果均為正確的，則認(rèn)為信息無(wú)錯(cuò)誤。如果發(fā)現(xiàn)有一個(gè)或多個(gè)錯(cuò)了，則錯(cuò)誤的位由這些檢查的結(jié)果來(lái)唯一地確定。校驗(yàn)位數(shù)的位數(shù)推

12、求海明碼時(shí)的一項(xiàng)基本考慮是確定所需最少的校驗(yàn)位數(shù)k0考慮長(zhǎng)度為m位的信息，若附加了k個(gè)校驗(yàn)位，則所發(fā)送的總長(zhǎng)度為m+k。在接收器中要進(jìn)行k個(gè)奇偶檢查，每個(gè)檢查結(jié)果或是真或是偽。這個(gè)奇偶檢查的結(jié)果可以表示成一個(gè)k位的二進(jìn)字，它可以確定最多2k種不同狀態(tài)。這些狀態(tài)中必有一個(gè)其所有奇偶測(cè)試試都是真的，它便是判定信息正確的條件。于是剩下的（2k-1）種狀態(tài)，可以用來(lái)判定誤碼的位置。于是導(dǎo)出下一關(guān)系：2k-1m+剛字格式從理論上講，校驗(yàn)位可放在任何位置，但習(xí)慣上校驗(yàn)位被安排在1、2、4、8、的位置上。碼字位碼字位WB1B2B3B1B556B7 校驗(yàn)位校驗(yàn)位XX XX X一一M位位I IX XX XX X

13、. .仔碼仔碼子子 31F2D1巴巴 D2| 以以 圖5海明碼中校驗(yàn)位和信息位的定位校驗(yàn)位的確定k個(gè)校驗(yàn)位是通過(guò)對(duì)m+k位復(fù)合碼字進(jìn)行奇偶校驗(yàn)而確定的。其中：P1位負(fù)責(zé)校驗(yàn)海明碼的第1、3、5、7、（P1、D1、D2、D4、）位,（包括P1自己）P2負(fù)責(zé)校驗(yàn)海明碼的第2、3、6、7、（P2、D1、D3、D4、）位，（包括P2自己）P3負(fù)責(zé)校驗(yàn)海明碼的第4、5、6、7、（P3、D2、D3、D4、）位，（包括P3自己）Xtm=4,k=3,偶校驗(yàn)的例子，只要進(jìn)行三次偶性測(cè)試。這些測(cè)試（以A、B、C表示）圖6奇偶校驗(yàn)位置因此可得到三個(gè)校驗(yàn)方程及確定校驗(yàn)位的三個(gè)公式：A=B1B3B5B7=0得P1=D1

14、D2D4B=B2B3B6B7=0得P2=D1D3D4C=B4B5B6B7=0得P3=D2D3D4若四位信息碼為1001,利用這三個(gè)公式可求得三個(gè)校驗(yàn)位P1、P2、P3值。和海明碼，如圖7則表示了信息碼為1001時(shí)的海明碼編碼的全部情況。而圖8中則列出了全部16種信息碼字位置B1B2B3B4B5B6BFT1碼位類型P1P2D1P3D2.D3D4信息碼一11-001校驗(yàn)位001編碼后的海明碼0011001P1P2D1P3D2D3D1000000011010010101010100001110011000100101110011000011111110000001100110110100110011

15、0111100101010100101101111111圖8未編碼信息的海明碼上面是發(fā)送方的處理在接收方，也可根據(jù)這三個(gè)校驗(yàn)方程對(duì)接收到的信息進(jìn)行同樣的奇偶測(cè)試：A=B1B3B5B7=0;B=B2B3B6B7=0;C=B4B5B5B7=0。若三個(gè)校驗(yàn)方程都成立，即方程式右邊都等于0,則說(shuō)明沒有錯(cuò)。若不成立即方程式右邊不等于0,說(shuō)明有錯(cuò)。從三個(gè)方程式右邊的值，可以判斷那一位出錯(cuò)。例如，如果第3位數(shù)字反了，則C=0（此方程沒有B3）,A=B=1（這兩個(gè)方程有B3）?？蓸?gòu)成二進(jìn)數(shù)CBA,以A為最低有效位，則錯(cuò)誤位置就可簡(jiǎn)單地用二進(jìn)數(shù)CBA=011指出。同樣，若三個(gè)方程式右邊的值為001,說(shuō)明第1位出

16、錯(cuò)。若三個(gè)方程式右邊的值為100,說(shuō)明第4位出錯(cuò)。海明碼的碼距應(yīng)該是3,所以能糾正1位出錯(cuò)。而奇偶校驗(yàn)碼的碼距才是2,只能發(fā)現(xiàn)1位出錯(cuò)，但不能糾正（不知道那一位錯(cuò)）。無(wú)校驗(yàn)的碼距是1,它出任何一位出錯(cuò)后還是合法代碼，所以也就無(wú)法發(fā)現(xiàn)出錯(cuò)。這是關(guān)于海明碼的經(jīng)典說(shuō)法，即碼距為3,可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)。應(yīng)滿足2k-1m+k但在清華的王愛英主編的計(jì)算機(jī)組成與結(jié)構(gòu)(該書已成為國(guó)內(nèi)的權(quán)威)中還提出了一種碼距為4的海明碼，可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)。應(yīng)滿足2(k-1)m+k由于王愛英書上對(duì)這兩種概念沒有很仔細(xì)解釋(特別對(duì)碼距為3的海明碼)，過(guò)渡很突然。有些書簡(jiǎn)單抄襲時(shí)沒有仔細(xì)消化，所以出現(xiàn)一些概念

17、錯(cuò)。對(duì)于一般碼距為3的海明碼，應(yīng)該是可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)”，而不是可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)”。在試題中出現(xiàn)過(guò)類似的錯(cuò)誤。3.CRC在串行傳送(磁盤、通訊)中，廣泛采用循環(huán)冗余校驗(yàn)碼(CRC)。CRC也是給信息碼加上幾位校驗(yàn)碼，以增加整個(gè)編碼系統(tǒng)的碼距和查錯(cuò)糾錯(cuò)能力。CRC的理論很復(fù)雜，一般書上只介紹已有生成多項(xiàng)式后計(jì)算校驗(yàn)碼的方法。檢錯(cuò)能力與生成多項(xiàng)式有關(guān)，只能根據(jù)書上的結(jié)論死記。循環(huán)冗余校驗(yàn)碼(CRC)的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼又叫(N,K)碼。對(duì)于一個(gè)給定的(N,K)碼，可以證明存在一個(gè)最高次幕為N-K=R的多項(xiàng)式G(x)

18、0根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R,這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。幾個(gè)基本概念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,無(wú)此幕次項(xiàng)對(duì)應(yīng)00可以看出：x的最高幕次為R,轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制數(shù)有R+1位。多項(xiàng)式包括生成多項(xiàng)式G(x)和信息多項(xiàng)式C(x)0如生成多項(xiàng)式為G(x)=

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

20、的。但可以從有關(guān)資料查到常用的對(duì)應(yīng)于不同碼制K碼即碼即dG（x）當(dāng)項(xiàng)式當(dāng)項(xiàng)式G(x)713工工3十工十十工十1101143x3+12+1IWi34Ii+x3+i2+l11101734xi+x2+x+l1011115113xl+i+1won15*d511101000131263I5+I2+110010131215x1Q+工工g+工工6+x5W11110110100163573ib+i+l100001163515x12+x10+x5+xl+x2+l101000011010110411024xl6+il5+t2+lIIOOOOOOOOOOO0101圖9常用的生成多項(xiàng)式3、/K2除（按位除）模2除做法

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

22、式C(x)*2R3、用生成多項(xiàng)式(二進(jìn)制數(shù))對(duì)信息碼做模2除，得到R位的余數(shù)。4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼?！纠纠考僭O(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。4位的原始報(bào)文為1010,求編碼后的報(bào)文。解：解：1、將生成多項(xiàng)式G(x)=x3+x+1轉(zhuǎn)換成對(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ì)左移4位后的原始報(bào)文進(jìn)行模2除：1001商10100001011除數(shù)10001011011余數(shù)(校驗(yàn)位)5、編碼后白報(bào)文(CRC碼)：1010000+011101001

23、1CRC的和糾錯(cuò)在接收端收到了CRC碼后用生成多項(xiàng)式為G(x)去做模2除，若得到余數(shù)為0,則碼字無(wú)誤。若如果有一位出錯(cuò)，則余數(shù)不為0,而且不同位出錯(cuò)，其余數(shù)也不同?？梢宰C明，余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系只與碼制及生成多項(xiàng)式有關(guān)，而與待測(cè)礁字(信息位)無(wú)關(guān)。圖10給出了G(x)=1011,C(x)=1010的出錯(cuò)模式，改變C(x)(碼字)，只會(huì)改變表中碼字內(nèi)容，不改變余數(shù)收到的收到的CRC碼字碼字余數(shù)余數(shù)出錯(cuò)位出錯(cuò)位碼位碼位A7A6A5AlA3A2A1正確正確1010011000無(wú)無(wú)00111010010010210100011003耨耨1010111* *1 11 1誤誤10110110114100

24、00111105111001111160010011101r,圖10(7,4)CRC碼的出錯(cuò)模式(G(x)=1011)如果循環(huán)碼有一位出錯(cuò)，用G(x)作/K2除將得到一個(gè)不為0的余數(shù)。如果對(duì)余數(shù)補(bǔ)0繼續(xù)除下去，我們將發(fā)現(xiàn)一個(gè)有趣的結(jié)果；各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯(cuò)， 余數(shù)將為001,補(bǔ)0后再除(補(bǔ)0后若最高位為1,則用除數(shù)做模2減取余；若最高位為0,則其最低3位就是余數(shù))，得到第二次余數(shù)為010。以后繼續(xù)補(bǔ)0作模2除，依次得到余數(shù)為100,011；反復(fù)循環(huán)，這就是循環(huán)碼”名稱的由來(lái)。這是一個(gè)有價(jià)值的特點(diǎn)。如果我們?cè)谇蟪鲇鄶?shù)不為0后，一邊對(duì)余數(shù)補(bǔ)0繼續(xù)做模2除，同時(shí)讓被檢測(cè)的校驗(yàn)碼

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

26、到最高位A7,將最高位1取反后變成01110100再將它循環(huán)左移3位，補(bǔ)足7次，出錯(cuò)位回到A3位，就成為一個(gè)正確的碼字1010011。通信與網(wǎng)絡(luò)中常用的CRC在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常k相當(dāng)大，由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀，而后采用CRC碼產(chǎn)生r位的校驗(yàn)位。它只能檢測(cè)出錯(cuò)誤，而不能糾正錯(cuò)誤。一般取r=16,標(biāo)準(zhǔn)的16位生成多項(xiàng)式有CRC-16=x16+x15+x2+1和CRC-CCITT=x16+x15+x2+1。一般情況下，r位生成多項(xiàng)式產(chǎn)生的CRC碼可檢測(cè)出所有的雙錯(cuò)、奇數(shù)位錯(cuò)和突發(fā)長(zhǎng)度小于等于r的突發(fā)錯(cuò)以及(1-2-(r-1)的突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)和(1-2-r)的突發(fā)長(zhǎng)度大于r+1的

27、突發(fā)錯(cuò)。例如，對(duì)上述r=16的情況，就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于16的突發(fā)錯(cuò)以及99.997%的突發(fā)長(zhǎng)度為17的突發(fā)錯(cuò)和99.998%的突發(fā)長(zhǎng)度大于17的突發(fā)錯(cuò)。所以CRC碼的檢錯(cuò)能力還是很強(qiáng)的。這里，突發(fā)錯(cuò)誤是指幾乎是連續(xù)發(fā)生的一串錯(cuò)， 突發(fā)長(zhǎng)度就是指從出錯(cuò)的第一位到出錯(cuò)的最后一位的長(zhǎng)度(但是， 中間并不一定每一位都錯(cuò))?！纠?1某循環(huán)冗余碼(CRC)的生成多項(xiàng)式G(x)=x3+x2+1,用此生成多項(xiàng)式產(chǎn)生的冗余位，加在信息位后形成CRC碼。若發(fā)送信息位1111和1100則它的CRC碼分別為_A_和_B_。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯(cuò)的CRC碼，例如碼字C、D、和E。(1998年試題11)供選擇的答案A:lllll00B:1100100111110111001011111110110011000101111010001111111111001111011000CE:0000000000110010001101001111解：A: G(x)=1101,C(x)=1111C(x)*23G(x)=1111000千101=1011余111得到的CRC碼為1111111B: G(x)=1101,C(x)=1100C(x)*23G(x)=11000004101=1001余101得到的CRC碼為1100101CE:分別用G(x)=1101對(duì)作模2除：