《計(jì)算機(jī)組成原理》課件第二章數(shù)據(jù)的表示-2.4

第2章數(shù)據(jù)表示2.4數(shù)據(jù)校驗(yàn)碼2.4數(shù)據(jù)校驗(yàn)碼在數(shù)據(jù)編碼中，能夠發(fā)現(xiàn)錯(cuò)誤的編碼叫做檢錯(cuò)碼；能夠糾正錯(cuò)誤的編碼叫做糾錯(cuò)碼。能夠檢測(cè)或糾正編碼中錯(cuò)誤的信息編碼，稱為數(shù)據(jù)校驗(yàn)碼，可以提高計(jì)算機(jī)的可靠性。目前的數(shù)據(jù)校驗(yàn)法大多采用“冗余校驗(yàn)”的思想，即除原數(shù)據(jù)信息外，還增加若干位新編碼，這些編碼稱為校驗(yàn)碼。常用的數(shù)據(jù)校驗(yàn)碼有奇偶校驗(yàn)碼、海明校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼等。2.4.1奇偶校驗(yàn)碼奇偶校驗(yàn)法是在信息位中增加一位校驗(yàn)位代碼，能夠檢測(cè)出代碼中的奇數(shù)個(gè)位的錯(cuò)誤，但不能糾正錯(cuò)誤。常用于存儲(chǔ)器讀寫檢查或按字節(jié)傳輸數(shù)據(jù)過(guò)程中的數(shù)據(jù)校驗(yàn)。奇偶校驗(yàn)碼包括奇校驗(yàn)碼和偶校驗(yàn)碼兩種。（1）奇偶校驗(yàn)位生成過(guò)程數(shù)據(jù)在存儲(chǔ)和傳輸時(shí)首先需要加上校驗(yàn)位P。奇（偶）校驗(yàn)位的生成過(guò)程如下：假設(shè)源數(shù)據(jù)為B=bn-1bn-2……b1b0。若采用奇校驗(yàn)位，則P=bn-1⊕bn-2⊕……b1⊕b0⊕1，即若源數(shù)據(jù)B有奇數(shù)個(gè)1，則P取0，否則取1，也就是保證加上校驗(yàn)位之后的數(shù)據(jù)編碼中有奇數(shù)個(gè)1。若采用偶校驗(yàn)位，則P=bn-1⊕bn-2⊕…b1⊕b0，即若源數(shù)據(jù)B有偶數(shù)個(gè)1，則P取0，否則取1，也就是保證加上校驗(yàn)位之后的數(shù)據(jù)編碼中有偶數(shù)個(gè)1。（1）奇偶校驗(yàn)位生成過(guò)程[例2-36]要從源部件發(fā)送數(shù)據(jù)01101010到終部件。請(qǐng)寫出采用奇校驗(yàn)法的過(guò)程。解：P=0⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1=1數(shù)據(jù)增加奇校驗(yàn)位后的編碼為：011010101。（2）奇偶校驗(yàn)碼的檢錯(cuò)過(guò)程假設(shè)源數(shù)據(jù)信息和校驗(yàn)位經(jīng)存儲(chǔ)或傳送后讀出的新編碼中數(shù)據(jù)部分為B’=bn-1’bn-2’…b1’b0’，校驗(yàn)位部分為P”。為了判斷源數(shù)據(jù)B是否在存儲(chǔ)和傳送后發(fā)生了錯(cuò)誤，在奇偶校驗(yàn)電路中進(jìn)行檢錯(cuò)。1）首先對(duì)B’求新校驗(yàn)碼P’。若采用奇校驗(yàn)法：P’=bn-1’

⊕bn-2’⊕…b1’⊕b0’⊕1若采用偶校驗(yàn)法：P’=bn-1’⊕bn-2’⊕…b1’⊕b0’2）計(jì)算最終的校驗(yàn)位P*，根據(jù)其值判斷有無(wú)奇偶錯(cuò)P*=P’⊕P”。若P*=1，則表示數(shù)據(jù)存在有奇數(shù)位錯(cuò)。若P*=0，則表示數(shù)據(jù)正確或有偶數(shù)個(gè)錯(cuò)。（2）奇偶校驗(yàn)碼的檢錯(cuò)過(guò)程[例2-37]在計(jì)算機(jī)中采用奇校驗(yàn)法，數(shù)據(jù)從源部件發(fā)送到終部件，校驗(yàn)位在新編碼的最后一位。若終部件得到的編碼分別為011010100、011010110、011010111，判斷這3個(gè)數(shù)據(jù)是否發(fā)生了錯(cuò)誤。解：①編碼011010100檢錯(cuò)過(guò)程:B’=01101010，P”=0。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1=1。P*=P’⊕P”=1。該編碼有奇數(shù)位編碼錯(cuò)。 ②編碼011010110檢錯(cuò)過(guò)程:B’=01101011，P”=0。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0。P*=P’⊕P”=0。該編碼無(wú)錯(cuò)或有偶數(shù)個(gè)錯(cuò)。③編碼011010111檢錯(cuò)過(guò)程:B’=01101011，P”=1。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0。P*=P’⊕P”=1。該編碼有奇數(shù)位編碼錯(cuò)。2.4.2海明校驗(yàn)碼奇偶校驗(yàn)碼檢錯(cuò)能力差，并且沒(méi)有糾錯(cuò)能力。如果將數(shù)據(jù)按某種規(guī)律分成若干組，對(duì)每組進(jìn)行相應(yīng)的奇偶檢測(cè)，就能提供多位檢錯(cuò)信息，從而對(duì)錯(cuò)誤位置進(jìn)行定位，并對(duì)其進(jìn)行糾正。海明校驗(yàn)碼實(shí)質(zhì)上是一種多重奇偶校驗(yàn)碼，是目前廣泛被采用的校驗(yàn)法，主要用于存儲(chǔ)器中數(shù)據(jù)存取校驗(yàn)。（1）校驗(yàn)位的位數(shù)的確定海明校驗(yàn)碼和奇偶校驗(yàn)碼一樣，都是通過(guò)對(duì)原校驗(yàn)碼和新校驗(yàn)碼進(jìn)行異或操作生成的故障字來(lái)判斷數(shù)據(jù)是否發(fā)生錯(cuò)誤。要實(shí)現(xiàn)對(duì)某個(gè)數(shù)據(jù)發(fā)生的錯(cuò)誤進(jìn)行定位，則故障字應(yīng)能體現(xiàn)數(shù)據(jù)可能出現(xiàn)的狀態(tài)。假定數(shù)據(jù)位位數(shù)為n，校驗(yàn)位位數(shù)為k，則故障字位數(shù)也是k，k位故障字能夠表示的狀態(tài)有2k種，每種狀態(tài)用來(lái)說(shuō)明一種情況。數(shù)據(jù)會(huì)出現(xiàn)的狀態(tài)有無(wú)錯(cuò)、n位數(shù)據(jù)中某一位出錯(cuò)、k位校驗(yàn)位中有一位出錯(cuò)的情況（只考慮干擾造成一位出錯(cuò)的情況），共有1+n+k種情況。所以，n和k必須滿足下列關(guān)系：2k≥1+n+k（2）分組方式的確定數(shù)據(jù)位和校驗(yàn)位一起存儲(chǔ)構(gòu)成n+k位的碼字。若將校驗(yàn)位穿插在數(shù)據(jù)位中，使得某位出錯(cuò)時(shí)得到的故障字和出錯(cuò)的位置之間存在一個(gè)確定的關(guān)系，就可以根據(jù)故障字直接確定出錯(cuò)的位置，并容易地進(jìn)行糾正了。根據(jù)上述基本思想，我們按以下規(guī)則來(lái)解釋各故障字的值：1）如果故障字各位全0，則表示沒(méi)有發(fā)生錯(cuò)誤。2）如果故障字中有且僅有一位為1，則表示校驗(yàn)位中有一位出錯(cuò)。校驗(yàn)位出錯(cuò)不需要糾正。3）如果故障字中有多位為1，則表示有一個(gè)數(shù)據(jù)位出錯(cuò)。出錯(cuò)數(shù)據(jù)位的位置，由故障字的數(shù)值確定。只需根據(jù)故障字的值找到出錯(cuò)位進(jìn)行取反糾正就可以了。（2）分組方式的確定（3）校驗(yàn)位的生成根據(jù)故障字和出錯(cuò)情況對(duì)應(yīng)關(guān)系表，對(duì)12位碼字分成了4組，每組進(jìn)行奇（偶）校驗(yàn)生成一位校驗(yàn)位。在上面的分組方式中，可以看到每個(gè)數(shù)據(jù)位至少參與兩組奇（偶）校驗(yàn)位的生成。（3）校驗(yàn)位的生成[例2-39]對(duì)8位數(shù)據(jù)01101010，完成海明校驗(yàn)位生成過(guò)程，每組采用偶校驗(yàn)。解：采用前一例題的分組表，則得到校驗(yàn)位和數(shù)據(jù)位之間的關(guān)系，對(duì)每組數(shù)據(jù)進(jìn)行偶校驗(yàn)運(yùn)算。P1=M1⊕M2⊕M4⊕M5⊕M7=1P2=M1⊕M3⊕M4⊕M6⊕M7=1P3=M2⊕M3⊕M4⊕M8=0P4=M5⊕M6⊕M7⊕M8=0將數(shù)據(jù)位和校驗(yàn)位一起存儲(chǔ)，得到的碼字為M8M7M6M5P4M4M3M2P3M1P2P1=011001010011（4）海明校驗(yàn)碼的檢錯(cuò)和糾錯(cuò)數(shù)據(jù)位M和校驗(yàn)位P一起存儲(chǔ)或傳送后，讀出的數(shù)據(jù)為M’，讀出的校驗(yàn)位為P’’。對(duì)M’采用同樣的分組校驗(yàn)，得到新校驗(yàn)位P’。將P’和P”進(jìn)行異或得到故障字S。根據(jù)故障字可以確定碼字是否發(fā)生錯(cuò)誤，若發(fā)生錯(cuò)誤，根據(jù)故障字確定的錯(cuò)誤位置，若是數(shù)據(jù)位出錯(cuò)，則取反糾錯(cuò)，若是校驗(yàn)位出錯(cuò)可以不進(jìn)行糾錯(cuò)。海明校驗(yàn)碼具有發(fā)現(xiàn)兩位錯(cuò)，糾正一位錯(cuò)的能力，又稱為單糾錯(cuò)碼。（4）海明校驗(yàn)碼的檢錯(cuò)和糾錯(cuò)[例2-40]在終部件處接收到（8，4）海明碼數(shù)據(jù)011001010011，已知校驗(yàn)分組表如表2-4，完成該數(shù)據(jù)檢錯(cuò)以及糾錯(cuò)過(guò)程。解：根據(jù)海明碼字排列順序，可知M’=01101010，P”=0011。對(duì)M’數(shù)據(jù)進(jìn)行海明校驗(yàn)位生成過(guò)程，生成新校驗(yàn)位P’。P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=1P2’=M1’⊕M3’⊕M4’⊕M6‘⊕M7’=1P3’=M2‘⊕M3’⊕M4’⊕M8’=0P4’=M5’⊕M6’⊕M7‘⊕M8’=0將P’和P”異或得到故障字S。S=P’⊕P’’=0011⊕0011=0000根據(jù)分組表，故障字為0000，表明所有位都無(wú)錯(cuò)。（4）海明校驗(yàn)碼的檢錯(cuò)和糾錯(cuò)[例2-41]在終部件處接收到（8，4）海明碼數(shù)據(jù)011101010011，已知校驗(yàn)分組表如表2-4，完成該數(shù)據(jù)檢錯(cuò)以及糾錯(cuò)過(guò)程。解：根據(jù)海明碼字排列順序，可知M’=01111010，P”=0011。對(duì)M’數(shù)據(jù)進(jìn)行海明校驗(yàn)位生成過(guò)程，生成新校驗(yàn)位P’。P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=0P2’=M1’⊕M3’⊕M4’⊕M6‘⊕M7’=1P3’=M2‘⊕M3’⊕M4’⊕M8’=0P4’=M5’⊕M6’⊕M7‘⊕M8’=1將P’和P”異或得到故障字S。S=P’⊕P’’=1010⊕0011=1001根據(jù)分組表，故障字為1001，表明第9位出錯(cuò)。第9位是數(shù)據(jù)位M5，所以只需將M5’取反糾正即可得到原正確數(shù)據(jù)01101010。2.4.3循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼(CRC)，簡(jiǎn)稱循環(huán)碼，是一種具有檢錯(cuò)、糾錯(cuò)能力的校驗(yàn)碼。循環(huán)冗余校驗(yàn)碼常用于外存儲(chǔ)器和計(jì)算機(jī)同步通信的數(shù)據(jù)校驗(yàn)。奇偶校驗(yàn)碼和海明校驗(yàn)碼都是采用奇偶檢測(cè)為手段檢錯(cuò)和糾錯(cuò)的，而循環(huán)冗余校驗(yàn)則是通過(guò)某種數(shù)學(xué)運(yùn)算來(lái)建立數(shù)據(jù)位和校驗(yàn)位的約定關(guān)系的。（1）校驗(yàn)位的生成循環(huán)冗余校驗(yàn)碼由信息碼n位和校驗(yàn)碼k位構(gòu)成。K位校驗(yàn)位拼接在n位數(shù)據(jù)位后面，n+k為循環(huán)冗余校驗(yàn)碼的字長(zhǎng)，又稱這個(gè)校驗(yàn)碼(n+k，n)碼。n位信息位可以表示成為一個(gè)報(bào)文多項(xiàng)式M(x)，最高冪次是Xn-1。約定的生成多項(xiàng)式G(x)是一個(gè)k+1位的二進(jìn)制數(shù)，最高冪次是Xk。將M(x)乘以Xk，即左移k位后，除以G(x)，得到的k位余數(shù)就是校驗(yàn)位。這里的除法運(yùn)算是模2除法，即上商的原則是當(dāng)部分余數(shù)首位是1時(shí)商取1，反之商取0。然后每一位的減法運(yùn)算是按位減，不產(chǎn)生借位。（1）校驗(yàn)位的生成（2）CRC檢錯(cuò)和糾錯(cuò)CRC碼存儲(chǔ)或傳送后，在接收方進(jìn)行校驗(yàn)過(guò)程，以判斷數(shù)據(jù)是否有錯(cuò)，若有錯(cuò)則進(jìn)行糾錯(cuò)。一個(gè)CRC碼一定能被生成多項(xiàng)式整除，所以在接收方對(duì)碼字用同樣的生成多項(xiàng)式相除，如果余數(shù)為0，則碼字沒(méi)有錯(cuò)誤；若余數(shù)不為0，則說(shuō)明某位出錯(cuò)，不同的出錯(cuò)位置余數(shù)不同。對(duì)（n，k）碼制，在生成多項(xiàng)式確定時(shí)，出錯(cuò)位置和余數(shù)的對(duì)應(yīng)關(guān)系是確定的。（2）CRC檢錯(cuò)和糾錯(cuò)（2）CRC檢錯(cuò)和糾錯(cuò)CRC碼有以下特點(diǎn)：1）任何一個(gè)CRC碼循環(huán)右移一位，仍是CRC碼。校驗(yàn)碼放在信息位的右邊，形成信息碼的多余部分，所以稱為循環(huán)冗余校驗(yàn)碼。2）將表中的CRC碼按位異或，得到的結(jié)果依然是一個(gè)CRC碼。（2）CRC檢錯(cuò)和糾錯(cuò)[例2-44](7，4)循環(huán)碼中，G(x)=1011時(shí)，碼字中出錯(cuò)位和余數(shù)的對(duì)應(yīng)關(guān)系是怎樣的？若接收方的碼字為1001000，完成數(shù)據(jù)檢錯(cuò)和糾錯(cuò)過(guò)程。（2）CRC檢錯(cuò)和糾錯(cuò)（3）生成多項(xiàng)式的選取并不是所有的k位多項(xiàng)式都能作為生成多項(xiàng)式。為了能夠檢錯(cuò)和糾錯(cuò)，選取的生成多項(xiàng)式應(yīng)具備如下條件：1）當(dāng)任何一位出錯(cuò)時(shí)，都能使余數(shù)不為02）不同的位發(fā)生錯(cuò)誤，得到的余數(shù)互不相同3）對(duì)余數(shù)繼續(xù)做模2除