計算機(jī)組成原理第7講_校驗(yàn)碼第一頁，共31頁。第3章運(yùn)算方法和運(yùn)算部件Errordetectionistheabilitytodetectthepresenceoferrorscausedbynoiseorotherimpairmentsduringtransmissionfromthetransmittertothereceiver:Errorcorrectionistheadditionalabilitytoreconstructtheoriginal,error-freedata.(6)§3.7數(shù)據(jù)校驗(yàn)碼2第二頁，共31頁。海明校驗(yàn)碼HammingCode海明校驗(yàn)碼是1種能檢測1位或幾位錯誤，又能自動糾正1位錯誤的線性分組碼。在數(shù)據(jù)中加入若干個校驗(yàn)位，把各個數(shù)據(jù)位分在幾個奇偶校驗(yàn)組中，把數(shù)據(jù)代碼的碼距比較均勻地拉大。任一位出錯都會引起有關(guān)的幾個校驗(yàn)位的值發(fā)生變化，從而發(fā)現(xiàn)錯誤。設(shè)m位校驗(yàn)碼中數(shù)據(jù)為k位，校驗(yàn)位為r位。把校驗(yàn)碼分成r組作奇偶校驗(yàn)。所產(chǎn)生的r位檢錯信息構(gòu)成一個指誤字，可指出2r種狀態(tài)。指誤字全0表示無錯，其余2r－1種狀態(tài)能指明k+r位中的某一位出錯。即指誤字應(yīng)能表示k位數(shù)據(jù)哪一位出錯，r個校驗(yàn)位哪一位出錯和無錯這k+r+1種情況。AHammingcodeisalinearerror-correctingcodenamedafteritsinventor,RichardHamming.Hammingcodescandetectuptotwosimultaneousbiterrors,andcorrectsingle-biterrors;3第三頁，共31頁。若要求海明碼能指出并糾正一位錯，則數(shù)據(jù)位的位數(shù)k和校驗(yàn)位的位數(shù)r應(yīng)滿足如下關(guān)系（海明不等式）：2r≥k＋r+1此時碼距為3，海明碼中的每一信息位至少要參加兩組奇偶校驗(yàn)并至少影響兩個校驗(yàn)位。若要求海明碼能檢測發(fā)現(xiàn)2位錯并能自動糾正一位錯，則數(shù)據(jù)位的位數(shù)k和校驗(yàn)位的位數(shù)r應(yīng)滿足如下關(guān)系：2r-1≥k＋r滿足這個不等式的海明碼稱為：擴(kuò)展海明碼/推廣海明碼此時碼距為4，推廣海明碼中的每一信息位至少要參加3組奇偶校驗(yàn)并至少影響3個校驗(yàn)位。(1)校驗(yàn)位的位數(shù)

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

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

，H2，H4，H8

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

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

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

④當(dāng)S4S3S2S1中有4位不為0時，表明出錯情況嚴(yán)重。指誤字（SyndromeWord）12第十二頁，共31頁。D8H120011D7H111101D6H100101D5H91001P4H80001D4H71110D3H60110D2H51010P3H40010D1H31100P2H20100P1H110000000數(shù)據(jù)位/校驗(yàn)位出錯位S1S2S3S4第十三頁，共31頁。對于推廣海明碼

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

14第十四頁，共31頁。對于推廣海明碼

③S5S4S3S2S1中有兩位不為0，表明是2位海明碼同時出錯，但不能確定出錯位的位號。④S5S4S3S2S1中有三位不為0，表明是一位數(shù)據(jù)位出錯，出錯位的位號由S4~S1這4位的編碼值指明（例如，S5~S1＝01011，則H11位出錯），因此可將其糾正過來?；蛘呖赡苁侨齻€校驗(yàn)位同時出錯，但此種出錯的概率極小，故認(rèn)為是一位錯。⑤S5S4S3S2S1中有4位或5位不為0時，表明出錯情況嚴(yán)重。15第十五頁，共31頁。P5H1300001D8H1200111D7H1111010D6H1001011D5H910011P4H800010D4H711100D3H601101D2H510101P3H400100D1H311001P2H201000P1H11000000000數(shù)據(jù)位/校驗(yàn)位出錯位S1S2S3S4S5第十六頁，共31頁。HomeworkCRCsarenot,bythemselves,suitableforprotectingagainstintentionalalterationofdata(forexample,inauthenticationapplicationsfordatasecurity),becausetheirconvenientmathematicalpropertiesmakeiteasytocomputetheCRCadjustmentrequiredtomatchanygivenchangetothedata.Allerrordetectioncodes(whichincludeallerror-detection-and-correctioncodes)transmitmorebitsthanwereintheoriginaldata.Anerror-correctingcode(ECC)orforwarderrorcorrection(FEC)codeisredundantdatathatisaddedtothemessageonthesenderside.3-26,17第十七頁，共31頁。測驗(yàn)1請寫好自己的姓名、學(xué)號、班級18第十八頁，共31頁。測驗(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請不要抄題，只寫題號

19第十九頁，共31頁。五．（16分）移碼加減法。求X+Y，X—YX=-69，Y=+57四.（8分）求浮點(diǎn)數(shù)表示范圍。尾數(shù)12位原碼，階碼8位補(bǔ)碼。寫出該浮點(diǎn)數(shù)能表示的：最大正數(shù)，絕對值最大負(fù)數(shù)，最小正數(shù)，絕對值最小負(fù)數(shù)。測驗(yàn)1請不要抄題，只寫題號

三．（16分）定點(diǎn)補(bǔ)碼加減法。求X+Y，X—YX=-0.5625，Y=+39/6420第二十頁，共31頁。五．（16分）移碼加減法。求X+Y，X—YX=-69，Y=+57六．（23分）浮點(diǎn)數(shù)，尾數(shù)8位補(bǔ)碼，階碼6位移碼（都包括符號位）。X=-4.75，Y=+28.75，

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

21第二十一頁，共31頁。七、（共7分）判斷題（請在正確的句子前寫T，錯誤的句子前寫F）請不要抄題，只寫題號

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

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

，和的符號

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

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

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

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

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

。請不要抄題，只寫題號

Theend.23第二十三頁，共31頁。循環(huán)冗余校驗(yàn)碼(CRC碼)Thecyclicredundancycheckconsidersablockofdataasthecoefficientstoapolynomialandthendividesbyafixed,predeterminedpolynomial.Thecoefficientsoftheresultofthedivisionistakenastheredundantdatabits,theCRC.Acyclicredundancycheck(CRC)isanon-securehashfunctiondesignedtodetectaccidentalchangestorawcomputerdata,andiscommonlyusedindigitalnetworksandstoragedevicessuchasharddiskdrives.ACRC-enableddevicecalculatesashort,fixed-lengthbinarysequence,knownastheCRCcodeorjustCRC,foreachblockofdataandsendsorstoresthembothtogether.Itscomputationresemblesalongdivisionoperationinwhichthequotientisdiscardedandtheremainderbecomestheresult,withtheimportantdistinctionthatthearithmeticusedisthecarry-lessarithmeticofafinitefield24第二十四頁，共31頁。循環(huán)冗余校驗(yàn)碼CyclicRedundancyCheck1．模2運(yùn)算

模2加減按位加，沒有進(jìn)位和借位?？捎卯惢蜻壿媽?shí)現(xiàn)。0±0=0，0±1=1，1±0=1，1±1=0模2乘部分積求和按模2加。例如：1010×101=1010×101100010CRC碼在編碼、譯碼時采用模2運(yùn)算。10100000101010001025第二十五頁，共31頁。模2除按模2減求余數(shù)。規(guī)則：每求1位商應(yīng)使部分余數(shù)減少1位。當(dāng)部分余數(shù)的首位為1時，上商1。當(dāng)部分余數(shù)的首位為0時，上商0。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時結(jié)束。例如：1100000÷1011=余數(shù)為01011101011110000010111110101110101011001000000101110循環(huán)冗余校驗(yàn)碼CyclicRedundancyCheck26第二十六頁，共31頁。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)位。

③選取一個k+1位的生成多項(xiàng)式G(x)。用G(x)對M(x)·Xk做模2除④把余數(shù)R(x)與M(x)·Xk做模2加，拼接成CRC碼。為了得到k位的余數(shù)，G(x)必須是k+1位的。27第二十七頁，共31頁。[例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

28第二十八頁，共31頁。3．CRC碼的校驗(yàn)與糾錯

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