課程資源計算機(jī)組織與結(jié)構(gòu)chapter

第二章數(shù)據(jù)的機(jī)器級表示與處理

——數(shù)據(jù)校驗碼

主要內(nèi)容概述奇偶校驗碼海明校驗碼循環(huán)冗余校驗碼主要內(nèi)容概述奇偶校驗碼海明校驗碼循環(huán)冗余校驗碼概述冗余校驗：即除原數(shù)據(jù)信息外，還增加若干位編碼，這些新增的代碼被稱為校驗位。沒有檢測到錯誤檢測到差錯，并可以糾錯檢測到錯誤，但無法確認(rèn)哪位出錯碼距由若干位代碼組成的一個字叫“碼字”，將兩個碼字逐位比較，具有不同代碼的位的個數(shù)叫做這兩個碼字間的“距離”，也稱為“海明距離”。4位二進(jìn)制編碼0000~1111表示16種狀態(tài)，則碼距為14位二進(jìn)制表示8個狀態(tài)：0000、0011、0101、0110、1001、1010、1100、1111，則碼距為2碼距與檢錯、糾錯能力之間存在一定的關(guān)系，當(dāng)碼距d≤4時，關(guān)系如下：如果碼距d為奇數(shù)，則能發(fā)現(xiàn)d–1位錯，或者能糾正(d–1)/2位錯。如果碼距d為偶數(shù)，則能發(fā)現(xiàn)d/2位錯，并能糾正(d/2–1)位錯。主要內(nèi)容概述奇偶校驗碼海明校驗碼循環(huán)冗余校驗碼奇偶校驗碼假設(shè)將數(shù)據(jù)B=bn-1bn-2...b1b0從源部件傳送至目標(biāo)部件。在目標(biāo)部件接收到的數(shù)據(jù)為B’=bn-1’bn-2’...b1’b0’。為了判斷數(shù)據(jù)B在傳送中是否發(fā)生了錯誤，可以按照如下步驟來判斷：第一步：在源部件求出奇（偶）校驗位P。P=bn-1⊕bn-2⊕...⊕b1⊕b0⊕1（奇）P=bn-1⊕bn-2⊕...⊕b1⊕b0（偶）第二步：在目標(biāo)部件求出奇（偶）校驗位P’。P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’⊕1P’=bn-1’⊕bn-2’⊕...⊕b1’⊕b0’第三步：計算最終的校驗位P*，判斷有無奇偶錯。假定P在目標(biāo)部件接受到的值為P“，則P*=P’⊕P“若P*=1，則表示有奇數(shù)位錯；若P*=0，則表示正確或有偶數(shù)個錯。10000011100000101000001奇偶校驗碼（續(xù)）在奇偶校驗碼中，若兩個數(shù)據(jù)中有奇數(shù)位不同，則它們相應(yīng)的校驗位就不同；若有偶數(shù)位不同，則雖校驗位相同，但至少有兩位數(shù)據(jù)位不同，因而任意兩個碼字之間至少有兩位不同，所以碼距d=2。根據(jù)碼距和檢/糾錯能力的關(guān)系可知，它只能發(fā)現(xiàn)奇數(shù)位出錯，不能發(fā)現(xiàn)偶數(shù)位出錯，而且也不能確定發(fā)生錯誤的位置，不具有糾錯能力。但奇偶校驗法所用的開銷小，它常被用于存儲器讀寫檢查或按字節(jié)傳輸過程中的數(shù)據(jù)校驗。主要內(nèi)容概述奇偶校驗碼海明校驗碼循環(huán)冗余校驗碼海明校驗碼（HammingCode）奇偶校驗碼檢錯能力差、沒有糾錯能力將數(shù)據(jù)按某種規(guī)律分成若干組，對每組進(jìn)行相應(yīng)的奇偶檢測，以提供多位校驗信息，從而可對錯誤位置進(jìn)行定位，并將其糾正。海明校驗碼實質(zhì)上就是一種多重奇偶校驗碼。10校驗位位數(shù)的確定

11分組方式的確定將數(shù)據(jù)位和校驗位按某種方式排列為一個(n+k)位的碼字，該碼字中每一位的出錯位置與故障字的數(shù)值建立關(guān)系故障字的值如果故障字各位全部是0，則表示沒有發(fā)生錯誤。如果故障字中有且僅有一位為1，則表示校驗位中有一位出錯，不需要糾正。如果故障字中多位為1，則表示有一個數(shù)據(jù)位出錯，其在碼字中的出錯位置由故障字的數(shù)值來確定。糾正時只要將出錯位取反即可。12分組方式的確定(cont.)假定一個8位數(shù)據(jù)M=M8M7M6M5M4M3M2M1，其相應(yīng)的4位校驗位為P=P4P3P2P1。故障字為0000時，表示無錯故障字中只有一位1，如0001、0010、0100、1000表示校驗位中第P1、P2、P3、P4位發(fā)生錯誤多位為1的故障字依次表示數(shù)據(jù)位M1~M8發(fā)生錯誤的情況M8M7M6M5P4M4M3M2P3M1P2P113校驗位的生成和檢錯、糾錯采用奇（偶）校驗，計算相應(yīng)的校驗位P計算新的校驗位P’，讀出和數(shù)據(jù)一起傳輸?shù)男ｒ炍籔”計算故障字S=P

⊕P”14P1=M1⊕M2⊕M4⊕M5⊕M7

P2=M1⊕M3⊕M4⊕M6⊕M7

P3=M2⊕M3⊕M4⊕M8P4=M5⊕M6⊕M7⊕M8例假定一個8位數(shù)據(jù)M為M8M7M6M5M4M3M2M1=01101010，其對應(yīng)的校驗位為P，M和P被存儲或經(jīng)傳送后得到的新數(shù)據(jù)和新校驗碼分別為M’和P’’。要求分別求出以下情況下的故障字并驗證其正確性。(1)M’=01101010，P’’=0011(2)M’=01111010，P’’=0011(3)M’=01101010，P’’=1011解：

P1=M1⊕M2⊕M4⊕M5⊕M7=0⊕1⊕1⊕0⊕1=1 P2=M1⊕M3⊕M4⊕M6⊕M7=0⊕0⊕1⊕1⊕1=1 P3=M2⊕M3⊕M4⊕M8=1⊕0⊕1⊕0=0 P4=M5⊕M6⊕M7⊕M8=0⊕1⊕1⊕0=0（1）故障字S=P’’⊕P’=P⊕P=0000，無錯15例（續(xù)）（2）

P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=0⊕1⊕1⊕1⊕1=0 P2’

=M1’⊕M3’⊕M4’⊕M6’⊕M7’=0⊕0⊕1⊕1⊕1=1 P3’=M2’⊕M3’⊕M4’⊕M8’=1⊕0⊕1⊕0=0 P4’

=M5’⊕M6’⊕M7’⊕M8’=1⊕1⊕1⊕0=1S1=P1’⊕P1’’=

0⊕1=1S2=P2’⊕P2’’=1⊕1=0S3=P3’⊕P3’’=0⊕0=0S4=P4’⊕P4’’=1⊕0=1故障字的值1001，可以判斷出發(fā)生錯誤的位是在12位碼字的第1001位(即第9位).例（續(xù)）（3）因為M’=M，所以P’=P，故障位S為： S1=P1’⊕P1’’=

1⊕1=0 S2=P2’⊕P2’’=1⊕1=0 S3=P3’⊕P3’’=0⊕0=0 S4=P4’⊕P4’’=0⊕1=1

故障字的值1000，可以判斷出發(fā)生錯誤的位是在12位碼字的第1000位(即第8位)糾一檢二碼n=8,k=4時，如果兩個數(shù)據(jù)有一位不同，那么由于該位至少要參與兩組校驗位的生成，因而至少會引起兩個校驗位的不同，再加上數(shù)據(jù)位本身一位的不同，所以碼距d=3。根據(jù)碼距與檢錯、糾錯能力的關(guān)系，可知這種碼制若用來判別有無錯誤，則能發(fā)現(xiàn)兩位錯；若用來糾錯，則只能對單個位出錯進(jìn)行定位和糾錯，因此被稱為單糾錯碼（SEC）。若校驗碼同時具有發(fā)現(xiàn)兩位錯和糾正一位錯的能力，則稱為單糾錯和雙檢錯碼（SEC-DED），簡稱“糾一檢二”碼。碼距需擴(kuò)大到d=4、增加一位校驗位P5P5M8M7M6M5P4M4M3M2P3M1P2P1P5=M1⊕M2⊕M3⊕M5⊕M6⊕M818糾一檢二碼(cont.)引入P5后，故障字S也增加了一位，即S=S5S4S3S2S1，根據(jù)S5S4S3S2S1的取值情況，即可按照如下規(guī)則發(fā)現(xiàn)兩位錯并糾正一位錯。當(dāng)S5S4S3S2S1為00000時，表明無錯。當(dāng)S5S4S3S2S1中僅一位不為0時，表明由S指定位置上的那個校驗位發(fā)生了錯誤，或是在數(shù)據(jù)和校驗位中有三位同時出錯，但后一種可能性很小，所以一般認(rèn)為就是發(fā)生了前一種情況。當(dāng)S5S4S3S2S1中有兩位不為0時，表明數(shù)據(jù)和校驗位中有兩位同時出錯，此時只能發(fā)現(xiàn)這種錯誤，但無法確定是哪兩位錯。當(dāng)S5S4S3S2S1中有三位不為0時，表明有一個數(shù)據(jù)位發(fā)生了錯誤，或是三個校驗位同時出錯，但后面這種可能性非常小，所以一般認(rèn)為就是發(fā)生了前一種情況。此時，出錯的位置由S4S3S2S1的數(shù)值指定。當(dāng)S5S4S3S2S1中有四位或五位都不為0時，表明出錯情況嚴(yán)重，系統(tǒng)可能出現(xiàn)故障，應(yīng)檢查系統(tǒng)硬件的正確性。19主要內(nèi)容概述奇偶校驗碼海明校驗碼循環(huán)冗余校驗碼循環(huán)冗余校驗碼ProblemofparitycheckingAdditionalcostislargeRequiretodividedataintobytesCRC（CyclicRedundancyCheck）具有較強(qiáng)檢錯、糾錯能力的校驗碼，常用于外存儲器的數(shù)據(jù)校驗通過某種數(shù)學(xué)運算來建立數(shù)據(jù)和校驗位之間的約定關(guān)系21CRC碼的檢錯方法假設(shè)要進(jìn)行校驗的數(shù)據(jù)信息M(x)為一個n位的二進(jìn)制數(shù)據(jù)，將M(x)左移k位后，用一個約定的生成多項式G(x)相除，相除后得到的k位余數(shù)就是校驗位。將校驗位拼接到M(x)的n位數(shù)據(jù)后面，形成一個n+k位的代碼，稱這個代碼為循環(huán)冗余校驗碼（CRC碼）。當(dāng)數(shù)據(jù)和校驗位一起送到接收端后，只要將接收到的數(shù)據(jù)和校驗位用同樣的生成多項式相除，如果正好除盡，表明沒有發(fā)生錯誤；若除不盡，則表明某些數(shù)據(jù)位發(fā)生了錯誤。22校驗位的生成Example假設(shè)要傳送的數(shù)據(jù)信息為100011，數(shù)據(jù)信息位數(shù)n=6，報文多項式為M(x)=x5+x+1若約定的生成多項式為G(x)=x3+1，即生成多項式位數(shù)為4位，則校驗位位數(shù)k=3生成校驗位時，用x3M(x)去除以G(x)，相除時采用“模２運算”的多項式除法校驗碼為生成校驗位時，用x3M(x)去除以G(x)，相除時采用“模２運算”的多項式除法1112310001100010011110010011000001110000