組成原理課件2 6數(shù)據(jù)校驗(yàn)碼

第2章北京理工大學(xué)計(jì)算機(jī)學(xué)院2.1

數(shù)值數(shù)據(jù)的表示機(jī)器數(shù)的定點(diǎn)表示與浮點(diǎn)表示非數(shù)值數(shù)據(jù)的表示十進(jìn)制數(shù)和數(shù)串的表示不同類型的數(shù)據(jù)表示舉例數(shù)據(jù)校驗(yàn)碼2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)校驗(yàn)碼是指那些能夠發(fā)現(xiàn)錯(cuò)誤或能夠自動(dòng)糾正錯(cuò)誤的數(shù)據(jù)編碼，又稱之為“檢錯(cuò)糾錯(cuò)編碼”。任何一種編碼都由許多碼字構(gòu)成，任意兩個(gè)碼字之間最少變化的二進(jìn)制位數(shù)，被稱為數(shù)據(jù)校驗(yàn)碼的碼距。例如，用四位

二進(jìn)制表示16種狀態(tài)，則有16個(gè)不同的碼

字，此時(shí)碼距為1，即兩個(gè)碼字之間最少僅有一個(gè)二進(jìn)制位不同（如0000與0001之間）。這種編碼沒有檢錯(cuò)能力，因?yàn)楫?dāng)某一個(gè)合法碼字中有一位或幾位出錯(cuò)，就變成為另一個(gè)合法碼字了。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院具有檢、糾錯(cuò)能力的數(shù)據(jù)校驗(yàn)碼的實(shí)現(xiàn)原理是：在編碼中，除去合法的碼字外，再加進(jìn)一些非法的碼字，當(dāng)某個(gè)合法碼字出現(xiàn)錯(cuò)誤時(shí)，就變成為非法碼字。合理地安排非法碼字的數(shù)量和編碼規(guī)則，就能達(dá)到糾錯(cuò)的目的。例如，若用四位二進(jìn)制表示八個(gè)狀態(tài)，其中只有八個(gè)碼字是合法碼字，而另八個(gè)碼字為非法碼字，此時(shí)碼距為2。對于碼距≥2的數(shù)據(jù)校驗(yàn)碼，開始具有檢錯(cuò)的能力。碼距越大，檢、糾錯(cuò)能力就越強(qiáng)，而且檢錯(cuò)能力總是大于或等于糾錯(cuò)能力。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院2.6.1

奇偶校驗(yàn)碼1.奇偶校驗(yàn)概念奇偶校驗(yàn)碼是一種最簡單的數(shù)據(jù)校驗(yàn)碼，它可以檢測出一位（或奇數(shù)位）錯(cuò)誤。奇偶

校驗(yàn)碼的碼距等于2

。奇偶校驗(yàn)實(shí)現(xiàn)方法是：由若干位有效信息（如一個(gè)字節(jié)），再加上一個(gè)二進(jìn)制位（校驗(yàn)位）組成校驗(yàn)碼，然后根據(jù)校驗(yàn)碼的奇偶性質(zhì)進(jìn)行校驗(yàn)。奇偶校驗(yàn)碼（N+1位）=N位有效信息+1位校驗(yàn)位N位1位2.6

數(shù)據(jù)校驗(yàn)碼奇偶校驗(yàn)位北京理工大學(xué)計(jì)算機(jī)學(xué)院N位1位2.6

數(shù)據(jù)校驗(yàn)碼奇偶校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院2.6

數(shù)據(jù)校驗(yàn)碼校驗(yàn)位的取值（0或1）將使整個(gè)校驗(yàn)碼中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)，所以有兩種可供選擇的校驗(yàn)規(guī)律：奇校驗(yàn)──整個(gè)校驗(yàn)碼（有效信息位和校驗(yàn)位）中“1”的個(gè)數(shù)為奇數(shù)。偶校驗(yàn)──整個(gè)校驗(yàn)碼中“1”的個(gè)數(shù)為偶數(shù)。有效信息（8位）奇檢驗(yàn)碼（9位）偶檢驗(yàn)碼（9位）00000000100000000000000000010100010010100011010100010111111100111111110111111111111111111111111011111111北京理工大學(xué)計(jì)算機(jī)學(xué)院CPU奇偶校驗(yàn)主存2.6

數(shù)據(jù)校驗(yàn)碼8位8位9位9位101010101101010101101010111101010101101010111電路有4個(gè)有15個(gè)正確出錯(cuò)1北京理工大學(xué)計(jì)算機(jī)學(xué)院01010101

1

01010101有16個(gè)01010101中斷處理2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院2.簡單奇偶校驗(yàn)（以奇校驗(yàn)為例）(1)校驗(yàn)位形成當(dāng)要把一個(gè)字節(jié)的代碼D7～D0寫入主存時(shí)，就同時(shí)將它們送往奇偶校驗(yàn)邏輯電路，該電路產(chǎn)生的“奇形成”信號(hào)就是校驗(yàn)位。它將與8位代碼一起作為奇校驗(yàn)碼寫入主存。若D7～D0中有偶數(shù)個(gè)“1”，則“奇形成”=1，若D7～D0中有奇數(shù)個(gè)“1”，則“奇形成”=0。2.6

數(shù)據(jù)校驗(yàn)碼D7

D6D5

D4D3

D2D1

D0

D校偶校驗(yàn)奇校驗(yàn)奇形成 偶形成 出錯(cuò) 出錯(cuò)AB=1=1=1=1=1=1=1=111北京理工大學(xué)計(jì)算機(jī)學(xué)院2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院(2)校驗(yàn)檢測讀出時(shí)，將讀出的9位代碼（8位信息位和1位校驗(yàn)位）同時(shí)送入奇偶校驗(yàn)電路檢測。若讀出代碼無錯(cuò)，則“奇校驗(yàn)出錯(cuò)”=0；若讀出代碼中的某一位上出現(xiàn)錯(cuò)誤，則“奇校驗(yàn)出錯(cuò)”=1，從而指示這個(gè)9位代碼中一定有某一位出現(xiàn)了錯(cuò)誤，但具體的錯(cuò)誤位置是不能確定的。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院3.交叉奇偶校驗(yàn)計(jì)算機(jī)在進(jìn)行大量字節(jié)（數(shù)據(jù)塊）傳送時(shí)，不僅每一個(gè)字節(jié)有一個(gè)奇偶校驗(yàn)位

做橫向校驗(yàn)，而且全部字節(jié)的同一位也設(shè)

置一個(gè)奇偶校驗(yàn)位做縱向校驗(yàn)，這種橫向、縱向同時(shí)校驗(yàn)的方法稱為交叉校驗(yàn)。第1字節(jié)11001011→1第2字節(jié)01011100→0第3字節(jié)10011010→0第4字節(jié)10010101→0↓↓↓↓↓↓↓↓100110002.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時(shí)出錯(cuò)的情況，假設(shè)第2字節(jié)的a6、a4兩位均出錯(cuò)，橫向校驗(yàn)位無法檢出錯(cuò)誤，但是第a6、a4位所在列的縱向校驗(yàn)位會(huì)顯示出錯(cuò)，這與前述的簡單奇偶校驗(yàn)相比要保險(xiǎn)多了。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院2.6.2

海明校驗(yàn)碼海明碼實(shí)際上是一種多重奇偶校驗(yàn)，其實(shí)現(xiàn)原理是：在有效信息位中加入幾個(gè)校驗(yàn)位形成海明碼，并把海明碼的每一個(gè)二進(jìn)制位分配到幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，這不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出錯(cuò)誤的位置，為自動(dòng)糾錯(cuò)提供了依據(jù)。能檢測和自動(dòng)校正一位錯(cuò)，并能發(fā)現(xiàn)兩位錯(cuò)的海明碼的編碼原理。此時(shí)校驗(yàn)位的位數(shù)K和信息位的位數(shù)N

應(yīng)滿足下列關(guān)系：2K-1≥N+K+1。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院(1)編碼一個(gè)字節(jié)由8位二進(jìn)制位組成，此時(shí)N=8，K=5，故海明碼的總位數(shù)為13位，可表示為：H13

H12…H2

H1五個(gè)校驗(yàn)位P5～P1對應(yīng)的海明碼位號(hào)應(yīng)分別為：H13 、H8 、H4 、H2 、H1 ，除P5

外，其余四位都滿足Pi的位號(hào)等于2i-1的關(guān)系，而P5只能放在H13上，因?yàn)樗呀?jīng)是海明碼的最高位了。因此，有如下排列關(guān)系：P5

D8

D7

D6

D5

P4

D4

D3

D2

P3

D1

P2

P12.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院各個(gè)信息位形成Pi

值的偶校驗(yàn)的結(jié)果：P1=D1ˉ

D2ˉ

D4ˉ

D5ˉ

D7P2=D1ˉ

D3ˉ

D4ˉ

D6ˉ

D7P3=D2ˉ

D3ˉ

D4ˉ

D8P4=D5ˉ

D6ˉ

D7ˉ

D8依據(jù)各信息位形成Pi（i=1～4）值時(shí)，不同信息位出現(xiàn)在Pi項(xiàng)中的次數(shù)是不一樣的，其中D4和D7都出現(xiàn)三次，而D1、D2、D3、D5、D6、D8僅出現(xiàn)兩次，為此，還要補(bǔ)充一位P5校驗(yàn)位，使：P5=D1ˉ

D2ˉ

D3ˉ

D5ˉ

D6

ˉ

D82.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院(2)校驗(yàn)將接收到的海明碼按如下關(guān)系進(jìn)行偶校驗(yàn)：S1=P1ˉ

D1ˉ

D2ˉ

D4ˉ

D5ˉ

D7S2=P2ˉ

D1ˉ

D3ˉ

D4ˉ

D6ˉ

D7S3=P3ˉ

D2ˉ

D3ˉ

D4ˉ

D8S4=P4ˉ

D5ˉ

D6ˉ

D7ˉ

D8S5=P5ˉ

D1ˉ

D2ˉ

D3ˉ

D5ˉ

D6

ˉ

D8校驗(yàn)得到的結(jié)果值S5～S1（指誤字），它能反映13位海明碼的出錯(cuò)情況：2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院①當(dāng)S5～S1為00000時(shí)，表明無錯(cuò)。②當(dāng)S5～S1中僅有一位不為0，表明是某一校驗(yàn)位出錯(cuò)或三位海明碼（包括信息位和校驗(yàn)位）同時(shí)出錯(cuò)。③當(dāng)S5～S1中有兩位不為0，表明是兩位海明碼同時(shí)出錯(cuò)，此時(shí)只能發(fā)現(xiàn)錯(cuò)誤，而無法確定出錯(cuò)的位置。④當(dāng)S5～S1中有三位不為0，表明是一位信息位出錯(cuò)或三位校驗(yàn)位同時(shí)出錯(cuò)，出錯(cuò)位的位號(hào)由S4～S1四位編碼值指明，此時(shí)不僅能檢查出一位錯(cuò)，而且能準(zhǔn)確地定位，因此可以糾正這個(gè)錯(cuò)誤（將該位變反）。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院⑤當(dāng)S5～S1中有四位或五位不為0時(shí)，表明出錯(cuò)情況嚴(yán)重，系統(tǒng)工作可能出現(xiàn)故障，應(yīng)檢查系統(tǒng)硬件的正確性。當(dāng)五個(gè)Si位有三個(gè)為1時(shí)，表示是某一信息位Di出錯(cuò)。出錯(cuò)信息位的海明碼位號(hào)由S4～S1這四位的譯碼值指出（分別為12、11、10、9、7、6、5、3）。例如，當(dāng)S5～S1=00111時(shí)，S4～S1的譯碼值為7，即對應(yīng)H7（也就是D4

）位出錯(cuò)。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院例：設(shè)有一個(gè)8位信息為10101100，試求海明編碼的生成和校驗(yàn)過程。(1)編碼生成按偶校驗(yàn)有：

P1=0ˉ

0ˉ

1ˉ

0ˉ

0=1P2=0ˉ

1ˉ

1ˉ

1ˉ

0=1P3=0ˉ

1ˉ

1ˉ

1=1P4=0ˉ

1ˉ

0ˉ

1=0P5=0ˉ

0ˉ

1ˉ

0ˉ

1ˉ

1=1∴可得到用二進(jìn)制表示的海明碼為：1

1

0

1

0

0

1

1

01

0

1

12.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院(2)校驗(yàn)假設(shè)傳送后H11（D7）位發(fā)生了錯(cuò)誤：11

1

1

0

0

1

1

0

1

0

1

1出錯(cuò)檢錯(cuò)的過程很簡單，只要將接受到的碼字重新進(jìn)行偶校驗(yàn)：S1=1ˉ

0ˉ

0ˉ

1ˉ

0ˉ

1=1S2=1ˉ

0ˉ

1ˉ

1ˉ

1ˉ

1=1S3=1ˉ

0ˉ

1ˉ

1ˉ

1=0S4=0ˉ

0ˉ

1ˉ

1ˉ

1=1S5=1ˉ

0ˉ

0ˉ

1ˉ

0ˉ

1ˉ

1=02.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院所以指誤字為01011，其中低4位有效，相應(yīng)的十進(jìn)制數(shù)是11，指出H11出錯(cuò)?，F(xiàn)在H11錯(cuò)成了“1”，糾錯(cuò)就是將H11位取反讓它恢復(fù)為“0”。即：錯(cuò)誤碼：1

11

1

0

0

1

1

0

1

0

1

1↓糾正后：1

10

1

0

0

1

1

0

1

0

1

12.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院2.6.3

循環(huán)冗余校驗(yàn)碼除了奇偶校驗(yàn)碼和海明碼外，在計(jì)算機(jī)網(wǎng)絡(luò)、同步通信以及磁表面存儲(chǔ)器中廣泛使用循環(huán)冗余校驗(yàn)碼，簡稱CRC碼。循環(huán)冗余校驗(yàn)碼是通過除法運(yùn)算來建立有效信息位和校驗(yàn)位之間的約定關(guān)系的。假設(shè)，待編碼的有效信息以多項(xiàng)式

M(X)表示，用另一個(gè)約定的多項(xiàng)式G(X)去除，所產(chǎn)生的余數(shù)R(X)就是檢驗(yàn)位。有效信息和檢驗(yàn)位相拼接就構(gòu)成了CRC碼。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院當(dāng)整個(gè)CRC碼被接收后，仍用約定的多項(xiàng)式G(X)去除，若余數(shù)為0表明該代碼是正確的；若余數(shù)不為0表明某一位出錯(cuò)，再進(jìn)一步由余數(shù)值確定出錯(cuò)的位置，以便進(jìn)行糾正。循環(huán)冗余校驗(yàn)碼編碼規(guī)律如下：①把待編碼的N位有效信息表示為多項(xiàng)式M(X)。②把M(X)左移K位，得到M(X)×XK，這樣空出了K位，以便拼裝K位余數(shù)（即校驗(yàn)位）。2.6

數(shù)據(jù)校驗(yàn)碼北京理工大學(xué)計(jì)算機(jī)學(xué)院③選取一個(gè)K+1位的產(chǎn)生多項(xiàng)式G(X)，對M(X)×XK

作模2除。④把左移K位以后的待編有效信息與余數(shù)

R(X)作模2加減，拼接為CRC碼，此時(shí)的