第7講-校驗(yàn)碼教材

計(jì)算機(jī)組成原理PrinciplesofComputerOrganization廣義雙語(yǔ)教學(xué)課程09/skyclass25/青島理工大學(xué)

校級(jí)精品課程/ec/C84/1jlsheng@第3章運(yùn)算方法和運(yùn)算部件Errordetectionistheabilitytodetectthepresenceoferrorscausedbynoiseorotherimpairmentsduringtransmissionfromthetransmittertothereceiver:Errorcorrectionistheadditionalabilitytoreconstructtheoriginal,error-freedata.(6)§3.7

數(shù)據(jù)校驗(yàn)碼2jlsheng@海明校驗(yàn)碼HammingCode海明校驗(yàn)碼是1種能檢測(cè)1位或幾位錯(cuò)誤，又能自動(dòng)糾正1位錯(cuò)誤的線性分組碼。在數(shù)據(jù)中加入若干個(gè)校驗(yàn)位，把各個(gè)數(shù)據(jù)位分在幾個(gè)奇偶校驗(yàn)組中，把數(shù)據(jù)代碼的碼距比較均勻地拉大。任一位出錯(cuò)都會(huì)引起有關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，從而發(fā)現(xiàn)錯(cuò)誤。設(shè)m位校驗(yàn)碼中數(shù)據(jù)為k位，校驗(yàn)位為r位。把校驗(yàn)碼分成r組作奇偶校驗(yàn)。所產(chǎn)生的r位檢錯(cuò)信息構(gòu)成一個(gè)指誤字，可指出2r種狀態(tài)。指誤字全0表示無(wú)錯(cuò)，其余2r－1種狀態(tài)能指明k+r位中的某一位出錯(cuò)。即指誤字應(yīng)能表示k位數(shù)據(jù)哪一位出錯(cuò)，r個(gè)校驗(yàn)位哪一位出錯(cuò)和無(wú)錯(cuò)這k+r+1種情況。AHammingcodeisalinear

error-correctingcodenamedafteritsinventor,RichardHamming.Hammingcodescandetectuptotwosimultaneousbiterrors,andcorrectsingle-biterrors;3jlsheng@若要求海明碼能指出并糾正一位錯(cuò)，則數(shù)據(jù)位的位數(shù)k和校驗(yàn)位的位數(shù)r應(yīng)滿足如下關(guān)系（海明不等式）：2r≥k＋r+1此時(shí)碼距為3

，海明碼中的每一信息位至少要參加兩組奇偶校驗(yàn)并至少影響兩個(gè)校驗(yàn)位。若要求海明碼能檢測(cè)發(fā)現(xiàn)2位錯(cuò)并能自動(dòng)糾正一位錯(cuò)，則數(shù)據(jù)位的位數(shù)k和校驗(yàn)位的位數(shù)r應(yīng)滿足如下關(guān)系：2r-1≥k＋r滿足這個(gè)不等式的海明碼稱為：擴(kuò)展海明碼

/推廣海明碼此時(shí)碼距為4

，推廣海明碼中的每一信息位至少要參加3組奇偶校驗(yàn)并至少影響3個(gè)校驗(yàn)位。(1)校驗(yàn)位的位數(shù)

海明校驗(yàn)碼HammingCode4(2)分組原則（編碼規(guī)則）設(shè)：海明碼HmHm-1……H2H1的最高位號(hào)為m，最低位號(hào)為1。m=k＋r①每個(gè)校驗(yàn)位Pi在海明碼中被分配在位號(hào)2i－1的位置，其余各位為數(shù)據(jù)位，并按從低向高逐位依次排列的關(guān)系分配。②海明碼的每一位碼Hi由多個(gè)校驗(yàn)位作校驗(yàn)，被校驗(yàn)的每一位的海明碼位號(hào)等于校驗(yàn)它的各校驗(yàn)位的海明碼位號(hào)之和，以便使校驗(yàn)的結(jié)果能正確反映出錯(cuò)位的位號(hào)。③在增大合法碼的碼距時(shí)，盡量使所有碼的碼距均勻的增大，以保證對(duì)所有碼的檢錯(cuò)能力平衡提高。5jlsheng@[例1]8位數(shù)據(jù)的海明碼（能指出并糾正一位錯(cuò)）的編碼和校驗(yàn)①編碼數(shù)據(jù)位k＝8，按海明不等式算出r＝4，m=k+r=12各位對(duì)應(yīng)關(guān)系如下：數(shù)據(jù)位/校驗(yàn)位

參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)H12H11H10H9H8H7H6H5H4H3H2H1D8D7D6D5P4D4D3D2P3D1P2P14,81,2,82,81,881,2,42,41,441,221按Pi的位號(hào)等于2i－1的關(guān)系，校驗(yàn)位P1,P2,P3,P4對(duì)應(yīng)的海明碼的位號(hào)分別為H1

，H2，H4，H8

。12位海明碼分成4組進(jìn)行偶校驗(yàn)。被校驗(yàn)的每一位的海明碼位號(hào)等于校驗(yàn)它的各校驗(yàn)位的海明碼位號(hào)之和。2r≥k＋r+1各校驗(yàn)位與數(shù)據(jù)位的關(guān)系（本例為偶校驗(yàn)）為：數(shù)據(jù)位/校驗(yàn)位

參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)H12H11H10H9H8H7H6H5H4H3H2H1D8D7D6D5P4D4D3D2P3D1P2P14,81,2,82,81,881,2,42,41,441,221每個(gè)小組只有一個(gè)校驗(yàn)位。每個(gè)校驗(yàn)位校驗(yàn)其自身和4~5個(gè)數(shù)據(jù)位，不參與其它校驗(yàn)位的校驗(yàn)。每個(gè)數(shù)據(jù)位至少出現(xiàn)在兩個(gè)Pi值的形成關(guān)系中。當(dāng)任一數(shù)據(jù)位發(fā)生變化時(shí)，必將引起二或三個(gè)Pi值跟著變化。不同信息位出現(xiàn)在Pi項(xiàng)中的次數(shù)不同。D4和D7出現(xiàn)3次，而D1、D2、D3、D5、D6、D8僅出現(xiàn)2次，使不同代碼的海明碼的碼距不等。

例如，數(shù)據(jù)11010011的海明碼為001010011011海明碼P1P2D1P3D2D3D4P4D5D6D7D8數(shù)據(jù)位/校驗(yàn)位H1H2H3H4H5H6H7H8H9H10H11H12海明碼位號(hào)偶校驗(yàn)8jlsheng@如果要求海明碼能檢測(cè)發(fā)現(xiàn)2位錯(cuò)并能自動(dòng)糾正一位錯(cuò)，則推廣海明碼的校驗(yàn)位位數(shù)r＝5。海明碼的總位數(shù)m=k+r=13。13位海明碼分成4組進(jìn)行偶校驗(yàn)。各位對(duì)應(yīng)關(guān)系如下：數(shù)據(jù)位/校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1134,81,2,82,81,881,2,42,41,441,221增加的一個(gè)校驗(yàn)位P5只能在H13。每個(gè)信息位都均勻地出現(xiàn)在3個(gè)Pi值的形成關(guān)系中。當(dāng)任一信息位發(fā)生變化時(shí)，必將引起3個(gè)Pi值跟著變化。2r-1≥k＋r或者例如，數(shù)據(jù)11010011的推廣海明碼為0010100110110推廣海明碼P1P2D1P3D2D3D4P4D5D6D7D8P5數(shù)據(jù)位/校驗(yàn)位H1H2H3H4H5H6H7H8H9H10H11H12H13海明碼位號(hào)10jlsheng@②校驗(yàn)數(shù)據(jù)接收方按以下關(guān)系對(duì)收到的海明碼進(jìn)行校驗(yàn)（本例為偶校驗(yàn)），產(chǎn)生指誤字（SyndromeWord）：校驗(yàn)得到的結(jié)果S4S3S2S1的值構(gòu)成指誤字，能反映該12位海明碼出錯(cuò)情況：11jlsheng@①S4S3S2S1＝0000，表明無(wú)錯(cuò)誤。②S4S3S2S1中只有一位不為0，表明是某一校驗(yàn)位出錯(cuò)，出錯(cuò)的是該Si對(duì)應(yīng)的Pi位，不需糾正。也可能是3位海明碼（包括數(shù)據(jù)位和校驗(yàn)位）同時(shí)出錯(cuò)，但無(wú)法指出是哪3位錯(cuò)。由于多位代碼同時(shí)出錯(cuò)的概率比僅一位代碼出錯(cuò)的概率小得多，故認(rèn)為是一位錯(cuò)。③S4S3S2S1中有兩位或三位不為0，表明是一位數(shù)據(jù)位出錯(cuò)，出錯(cuò)位的位號(hào)由S4~S1這4位的編碼值指明（例如，S4~S1＝1011，則H11位出錯(cuò)），因此可將其糾正過(guò)來(lái)?；蛘呖赡苁侨齻€(gè)校驗(yàn)位同時(shí)出錯(cuò)，但此種出錯(cuò)的概率極小，故認(rèn)為是一位錯(cuò)。

④當(dāng)S4S3S2S1中有4位不為0時(shí)，表明出錯(cuò)情況嚴(yán)重。指誤字（SyndromeWord）12jlsheng@D8H120011D7H111101D6H100101D5H91001P4H80001D4H71110D3H60110D2H51010P3H40010D1H31100P2H20100P1H110000000數(shù)據(jù)位/校驗(yàn)位出錯(cuò)位S1S2S3S4對(duì)于推廣海明碼

S5~S1的值構(gòu)成指誤字，反映該13位海明碼出錯(cuò)情況：①S5S4S3S2S1＝00000，表明無(wú)錯(cuò)誤。②S5S4S3S2S1中只有一位不為0，表明是某一校驗(yàn)位出錯(cuò)，出錯(cuò)的是該Si對(duì)應(yīng)的Pi位，不需糾正。也可能是3位海明碼(包括數(shù)據(jù)位和校驗(yàn)位)同時(shí)出錯(cuò)，但無(wú)法指出是哪3位錯(cuò)。由于多位代碼同時(shí)出錯(cuò)的概率比僅一位代碼出錯(cuò)的概率小得多，故認(rèn)為是一位錯(cuò)。

14jlsheng@對(duì)于推廣海明碼

③S5S4S3S2S1

中有兩位不為0，表明是2位海明碼同時(shí)出錯(cuò)，但不能確定出錯(cuò)位的位號(hào)。④S5S4S3S2S1中有三位不為0，表明是一位數(shù)據(jù)位出錯(cuò)，出錯(cuò)位的位號(hào)由S4~S1這4位的編碼值指明（例如，S5~S1＝01011，則H11位出錯(cuò)），因此可將其糾正過(guò)來(lái)?；蛘呖赡苁侨齻€(gè)校驗(yàn)位同時(shí)出錯(cuò)，但此種出錯(cuò)的概率極小，故認(rèn)為是一位錯(cuò)。⑤S5S4S3S2S1中有4位或5位不為0時(shí)，表明出錯(cuò)情況嚴(yán)重。15jlsheng@P5H1300001D8H1200111D7H1111010D6H1001011D5H910011P4H800010D4H711100D3H601101D2H510101P3H400100D1H311001P2H201000P1H11000000000數(shù)據(jù)位/校驗(yàn)位出錯(cuò)位S1S2S3S4S5HomeworkCRCsarenot,bythemselves,suitableforprotectingagainstintentionalalterationofdata(forexample,inauthenticationapplicationsfordatasecurity),becausetheirconvenientmathematicalpropertiesmakeiteasytocomputetheCRCadjustmentrequiredtomatchanygivenchangetothedata.Allerrordetectioncodes(whichincludeallerror-detection-and-correctioncodes)transmitmorebitsthanwereintheoriginaldata.Anerror-correctingcode(ECC)orforwarderrorcorrection(FEC)codeisredundantdatathatisaddedtothemessageonthesenderside.3-26,17jlsheng@測(cè)驗(yàn)1請(qǐng)寫好自己的姓名、學(xué)號(hào)、班級(jí)18jlsheng@測(cè)驗(yàn)1一.（10分）

求[X]補(bǔ)、[X/2]補(bǔ)、[X/4]補(bǔ)、[2X]補(bǔ)=？

X=-43/64

二.（12分）定點(diǎn)數(shù)的表示范圍。

32位整數(shù)原碼。25位小數(shù)原碼。

28位整數(shù)補(bǔ)碼。27位小數(shù)補(bǔ)碼。三．（16分）定點(diǎn)補(bǔ)碼加減法。求X+Y，X—YX=-0.5625，Y=+39/64請(qǐng)不要抄題，只寫題號(hào)

19五．（16分）移碼加減法。求X+Y，X—YX=-69，

Y=+57四.（8分）求浮點(diǎn)數(shù)表示范圍。尾數(shù)12位原碼，階碼8位補(bǔ)碼。寫出該浮點(diǎn)數(shù)能表示的：最大正數(shù)，絕對(duì)值最大負(fù)數(shù)，最小正數(shù)，絕對(duì)值最小負(fù)數(shù)。測(cè)驗(yàn)1請(qǐng)不要抄題，只寫題號(hào)

三．（16分）定點(diǎn)補(bǔ)碼加減法。求X+Y，X—YX=-0.5625，Y=+39/6420jlsheng@五．（16分）移碼加減法。求X+Y，X—YX=-69，

Y=+57六．（23分）浮點(diǎn)數(shù)，尾數(shù)8位補(bǔ)碼，階碼6位移碼（都包括符號(hào)位）。

X=-4.75，Y=+28.75，

(1)求X和Y的規(guī)格化浮點(diǎn)機(jī)器數(shù)（2）求X+Y測(cè)驗(yàn)1請(qǐng)不要抄題，只寫題號(hào)

21jlsheng@七、（共7分）判斷題（請(qǐng)?jiān)谡_的句子前寫T，錯(cuò)誤的句子前寫F）請(qǐng)不要抄題，只寫題號(hào)

（）1．零的原碼表示形式不是唯一的。（）2．兩個(gè)符號(hào)相同的浮點(diǎn)數(shù)相加后必須進(jìn)行一次右規(guī)。（）4．帶符號(hào)機(jī)器數(shù)的符號(hào)位都用0表示正數(shù)，1表示負(fù)數(shù)。（）5．補(bǔ)碼加減法運(yùn)算，符號(hào)位產(chǎn)生的進(jìn)位是模。（）3．計(jì)算機(jī)的ALU是用加法和部分積右移操作實(shí)現(xiàn)乘法運(yùn)算的。（）7．“右規(guī)”是將尾數(shù)右移一位，并將階碼的值減1。（）6．若補(bǔ)碼加法運(yùn)算結(jié)果的雙符號(hào)位為01，表示發(fā)生正溢出。22八、（共8分）填空題1．原碼加法運(yùn)算，符號(hào)位與數(shù)值部分

。若兩數(shù)的符號(hào)不同，做

，和的符號(hào)

，若兩數(shù)的符號(hào)相同，做

。2．算術(shù)移位應(yīng)保持?jǐn)?shù)據(jù)的

不變，只改變數(shù)據(jù)的

。數(shù)據(jù)左移一位將使數(shù)值

；數(shù)據(jù)右移一位相當(dāng)于

。請(qǐng)不要抄題，只寫題號(hào)

Theend.23jlsheng@循環(huán)冗余校驗(yàn)碼(CRC碼)Thecyclicredundancycheckconsidersablockofdataasthecoefficientstoapolynomialandthendividesbyafixed,predeterminedpolynomial.Thecoefficientsoftheresultofthedivisionistakenastheredundantdatabits,theCRC.Acyclicredundancycheck(CRC)isanon-securehashfunctiondesignedtodetectaccidentalchangestorawcomputerdata,andiscommonlyusedindigitalnetworksandstoragedevicessuchasharddiskdrives.ACRC-enableddevicecalculatesashort,fixed-lengthbinarysequence,knownastheCRCcodeorjustCRC,foreachblockofdataandsendsorstoresthembothtogether.Itscomputationresemblesalongdivisionoperationinwhichthequotientisdiscardedandtheremainderbecomestheresult,withtheimportantdistinctionthatthearithmeticusedisthecarry-lessarithmeticofafinitefield24jlsheng@循環(huán)冗余校驗(yàn)碼

CyclicRedundancyCheck1．模2運(yùn)算

模2加減按位加，沒(méi)有進(jìn)位和借位?？捎卯惢蜻壿媽?shí)現(xiàn)。0±0=0，0±1=1，1±0=1，1±1=0模2乘部分積求和按模2加。例如：1010×101=

1010×101100010CRC碼在編碼、譯碼時(shí)采用模2運(yùn)算。10100000101010001025jlsheng@模2除按模2減求余數(shù)。規(guī)則：每求1位商應(yīng)使部分余數(shù)減少1位。當(dāng)部分余數(shù)的首位為1時(shí)，上商1。當(dāng)部分余數(shù)的首位為0時(shí)，上商0。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時(shí)結(jié)束。例如：1100000÷1011=余數(shù)為010

11101011110000010111110101110101011001000000101110循環(huán)冗余校驗(yàn)碼

CyclicRedundancyCheck26jlsheng@2．CRC的編碼方法

CRC碼是由n位信息碼和k位校驗(yàn)碼拼接成的，稱（k+n，n）碼。編碼方法如下：①把待編碼的n位信息表示為多項(xiàng)式：式中Ci

=0或1②把M(x)左移k位，得到M(x)·Xk，空出低k位以便拼接校驗(yàn)位。

③選取一個(gè)k+1位的生成多項(xiàng)式G(x)。用G(x)對(duì)M(x)·Xk做模2除④把余數(shù)R(x)與M(x)·Xk做模2加，拼接成CRC碼。為了得到k位的余數(shù)，G(x)必須是k+1位的。27[例2]4位有效信息1100。生成多項(xiàng)式1011。求CRC碼。n=4，k=3，（7，4）碼M(x)=1100=X3+X2

M(x)·x3=1100000=X6+X5

G(x)=1011=X3+X+1CRC碼：M(x)·x3+R(x)=CRC碼可被G(x)除盡。把M(x)左移k位1100000+010=1100010

28jlsheng@3．CRC碼的校驗(yàn)與糾錯(cuò)

把接收到的CRC碼用約定的生成多項(xiàng)式G(x)去除，如果余數(shù)為0，說(shuō)明碼字正確。如果余數(shù)不為0，則某位出錯(cuò)。不同的位數(shù)出錯(cuò)時(shí)，余數(shù)不同。余數(shù)和出錯(cuò)位序號(hào)之間有唯一的對(duì)應(yīng)關(guān)系，只與碼制和生成多項(xiàng)式有關(guān)。7654321001010100011110111101110001111000001100110110101011100101000010

0100010出錯(cuò)的CRC碼—0001100010正確的CRC碼出錯(cuò)位余數(shù)A1A2A3A4A5A6A7

（7，4）CRC的出錯(cuò)模式（生成多項(xiàng)式G(x)=1011）7654321001010100011110111101110