補(bǔ)海明碼校驗(yàn)

1、奇偶校驗(yàn)碼1.奇偶校驗(yàn)概念 奇偶校驗(yàn)碼是一種最簡(jiǎn)單的數(shù)據(jù)校驗(yàn)碼，它的碼距等于2，可以檢測(cè)出一位錯(cuò)誤(cuw)（或奇數(shù)位錯(cuò)誤(cuw)），但不能確定出錯(cuò)的位置，也不能檢測(cè)出偶數(shù)位錯(cuò)誤(cuw)。 奇偶校驗(yàn)實(shí)現(xiàn)方法是：由若干位有效信息（如一個(gè)字節(jié)），再加上一個(gè)二進(jìn)制位（校驗(yàn)位）組成校驗(yàn)碼。 圖:奇偶校驗(yàn)碼共二十五頁(yè)奇偶校驗(yàn)規(guī)律(gul) 校驗(yàn)位的取值（0或1）將使整個(gè)(zhngg)校驗(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ù)。 共二十五頁(yè)2.簡(jiǎn)單(jindn)奇偶校驗(yàn) 簡(jiǎn)單奇偶校

2、驗(yàn)(xio yn)僅實(shí)現(xiàn)橫向的奇偶校驗(yàn)(xio yn)，下表給出幾個(gè)字節(jié)的奇偶校驗(yàn)(xio yn)碼的編碼結(jié)果。最高一位為校驗(yàn)(xio yn)位，其余8位為信息位。在實(shí)際應(yīng)用中，多采用奇校驗(yàn)(xio yn)，因?yàn)槠嫘ｒ?yàn)(xio yn)中不存在全“0”代碼，在某些場(chǎng)合下更便于判別。 有效信息（8位）奇校驗(yàn)碼（9位）偶校驗(yàn)碼（9位）00000000100000000000000000010101000010101001010101000111111100111111110111111111111111111111111011111111共二十五頁(yè)2.簡(jiǎn)單(jindn)奇偶校驗(yàn)（續(xù)） 校驗(yàn)位形成(x

3、ngchng) 當(dāng)要把一個(gè)字節(jié)的代碼D7D0寫(xiě)入主存時(shí)，就同時(shí)將它們送往奇偶校驗(yàn)邏輯電路，該電路產(chǎn)生的“奇形成”信號(hào)就是校驗(yàn)位。它將與8位代碼一起作為奇校驗(yàn)碼寫(xiě)入主存。 若D7D0中有偶數(shù)個(gè)“1”，則“奇形成”=1， 若D7D0中有奇數(shù)個(gè)“1”，則“奇形成”=0。共二十五頁(yè)奇偶校驗(yàn)(xio yn)位的形成及校驗(yàn)(xio yn)電路圖: 奇偶校驗(yàn)位的形成(xngchng)及校驗(yàn)電路共二十五頁(yè)2.簡(jiǎn)單(jindn)奇偶校驗(yàn)（續(xù)） 校驗(yàn)檢測(cè) 讀出時(shí)，將讀出的9位代碼（8位信息位和1位校驗(yàn)位）同時(shí)送入奇偶校驗(yàn)電路檢測(cè)。若讀出代碼無(wú)錯(cuò)，則“奇校驗(yàn)出錯(cuò)”=0；若讀出代碼中的某一位上出現(xiàn)錯(cuò)誤，則“奇校驗(yàn)出錯(cuò)

4、”=1，從而指示這個(gè)9位代碼中一定(ydng)有某一位出現(xiàn)了錯(cuò)誤，但具體的錯(cuò)誤位置是不能確定的。共二十五頁(yè)3.交叉(jioch)奇偶校驗(yàn) 計(jì)算機(jī)在進(jìn)行大量字節(jié)（數(shù)據(jù)塊）傳送時(shí)，不僅每一個(gè)(y )字節(jié)有一個(gè)(y )奇偶校驗(yàn)位做橫向校驗(yàn)，而且全部字節(jié)的同一位也設(shè)置一個(gè)(y )奇偶校驗(yàn)位做縱向校驗(yàn)，這種橫向、縱向同時(shí)校驗(yàn)的方法稱為交叉校驗(yàn)。 第1字節(jié) 1 1 0 0 1 0 1 1 1 第2字節(jié) 0 1 0 1 1 1 0 0 0 第3字節(jié) 1 0 0 1 1 0 1 0 0 第4字節(jié) 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0共二十五頁(yè)3.交叉(jioch)奇偶校驗(yàn)（續(xù)）

5、交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時(shí)出錯(cuò)的情況，假設(shè)第2字節(jié)的A6、A4兩位均出錯(cuò)，橫向校驗(yàn)位無(wú)法(wf)檢出錯(cuò)誤，但是第A6、A4位所在列的縱向校驗(yàn)位會(huì)顯示出錯(cuò)，這與前述的簡(jiǎn)單奇偶校驗(yàn)相比要保險(xiǎn)多了。 共二十五頁(yè)海明校驗(yàn)碼 海明碼是一種可以糾正一位差錯(cuò)(chcu)的編碼。它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來(lái)區(qū)分無(wú)錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。它必需滿足以下關(guān)系式： 2r k+r+1 或 2r n+1共二十五頁(yè)海明校驗(yàn)碼 海明碼(Hamming Code )編碼的關(guān)鍵是使用多余的奇偶校驗(yàn)位來(lái)識(shí)別一位錯(cuò)誤。 碼字(Code Wor

6、d) 按如下方法構(gòu)建： 1、把所有2的冪次方的數(shù)據(jù)位標(biāo)記(bioj)為奇偶校驗(yàn)位(編號(hào)為1, 2, 4, 8, 16, 32, 64等的位置) 2、其他數(shù)據(jù)位用于待編碼數(shù)據(jù). (編號(hào)為3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置) 共二十五頁(yè)海明校驗(yàn)碼 3、每個(gè)奇偶校驗(yàn)位的值代表了代碼字中部分(b fen)數(shù)據(jù)位的奇偶性，其所在位置決定了要校驗(yàn)和跳過(guò)的比特位順序。 位置1：校驗(yàn)1位，跳過(guò)1位，校驗(yàn)1位，跳過(guò)1位(1,3,5,7,9,11,13,15,) 位置2：校驗(yàn)2位，跳過(guò)2位，校驗(yàn)2位，跳過(guò)2位 (2,3,6,7,10,11,14,15,) 位

7、置4：校驗(yàn)4位，跳過(guò)4位，校驗(yàn)4位，跳過(guò)4位 (4,5,6,7,12,13,14,15,20,21,22,23,) 位置8：校驗(yàn)8位，跳過(guò)8位，校驗(yàn)8位，跳過(guò)8位(8-15,24-31,40-47,) 共二十五頁(yè)海明校驗(yàn)碼 采用偶校驗(yàn)，如果全部校驗(yàn)的位置(wi zhi)中有奇數(shù)個(gè)1，把該奇偶校驗(yàn)位置(wi zhi)為1；如果全部校驗(yàn)的位置(wi zhi)中有偶數(shù)個(gè)1，把該奇偶校驗(yàn)位置(wi zhi)為0. 共二十五頁(yè)海明校驗(yàn)碼 舉例說(shuō)明： 一個(gè)字節(jié)的數(shù)據(jù)(shj)：10011010 構(gòu)造數(shù)據(jù)字(Data Word),對(duì)應(yīng)的校驗(yàn)位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 計(jì)算每個(gè)校驗(yàn)位

8、的奇偶性 ( ?代表要設(shè)置的比特位): 共二十五頁(yè)海明校驗(yàn)碼 位置(wi zhi)1檢查1,3,5,7,9,11: ? _ 1 _ 0 0 1 _ 1 0 1 0. 偶數(shù)個(gè)1，因此位置1設(shè)為0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0位置2檢查2,3,6,7,10,11: 0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇數(shù)個(gè)1，因此位置2設(shè)為1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0 共二十五頁(yè)海明校驗(yàn)碼 位置(wi zhi)4檢查4,5,6,7,12: 0 1 1 ? 0 0 1 _ 1 0 1 0. 奇數(shù)個(gè)1，因此位置4設(shè)為1，即: 0 1 1 1 0 0 1

9、 _ 1 0 1 0位置8檢查8,9,10,11,12: 0 1 1 1 0 0 1 ? 1 0 1 0. 偶數(shù)個(gè)1，因此位置8設(shè)為0，即: 0 1 1 1 0 0 1 0 1 0 1 0因此碼字為: 011100101010. 共二十五頁(yè)海明校驗(yàn)碼 上例中構(gòu)建了一個(gè)碼字 011100101010，假定實(shí)際接收到的數(shù)據(jù) 011100101110. 則接收方可以計(jì)算出哪一位出錯(cuò)并對(duì)其進(jìn)行更正。方法就是驗(yàn)證每一個(gè)校驗(yàn)位。記下所有(suyu)出錯(cuò)的校驗(yàn)位，可以發(fā)現(xiàn)校驗(yàn)位2和8的數(shù)據(jù)不正確. 錯(cuò)誤校驗(yàn)位 2 + 8 = 10, 則位置10的數(shù)據(jù)出錯(cuò)。一般說(shuō)來(lái)，對(duì)所有(suyu)校驗(yàn)位進(jìn)行檢查, 將所有

10、(suyu)出錯(cuò)的校驗(yàn)位置相加, 得到的就是錯(cuò)誤信息所在的位置. 共二十五頁(yè)海明校驗(yàn)碼 例1.已知：信息碼為： 1 1 0 0 1 1 0 0 (k=4代表冗余(rn y)位數(shù)，即校驗(yàn)碼位數(shù)) 求：海明碼碼字。 共二十五頁(yè)海明校驗(yàn)碼 解：1)把冗余(rn y)碼A、B、C、，順序插入信息碼中，得海明碼 碼字: A B 1 C 1 0 0 D 1 1 0 0 碼位: 1 2 3 4 5 6 7 8 9 10 11 12 其中A,B,C,D分別插于2的k次方位(k=0,1,2,3)。碼位分別為1,2,4,8。 共二十五頁(yè)海明校驗(yàn)碼 2)冗余碼A,B,C,D的線性碼位是：(相當(dāng)于監(jiān)督關(guān)系式) 監(jiān)督關(guān)

11、系式的推導(dǎo)： D C B A 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 根據(jù)上面表格(biog)得到 A B C D 共二十五頁(yè)海明校驗(yàn)碼 需要說(shuō)明的是公式中參與計(jì)算的是表格中出現(xiàn)1的那個(gè)位 右邊(yu bian)是數(shù)據(jù)位的二進(jìn)制數(shù),公式中的+表示異或 故此有如下表達(dá)式： A-1,3,5,7,9,11；(這里的1 3 5 7 9 11均為A那一列出現(xiàn)1的位) B-2,3,6,7,10,11；

12、C-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4) D-8,9,10,11,12。 共二十五頁(yè)海明校驗(yàn)碼 3)把線性碼位的值的偶校驗(yàn)(xio yn)作為冗余碼的值(設(shè)冗余碼初值為0)： A=(0,1,1,0,1,0)=1 B=(0,1,0,0,1,0)=0 C=(0,1,0,0,0) =1 D=(0,1,1,0,0) =0 4)海明碼為:1 0 1 1 1 0 0 0 1 1 0 0 共二十五頁(yè)海明校驗(yàn)碼 例2.已知：接收的碼字為：1 0 0 1 1 0 0 0 1 1 0 0(k=4代表(dibio)冗余位數(shù)，即校驗(yàn)碼位數(shù)) 求：發(fā)送端的信息碼。 共二十五

13、頁(yè)海明校驗(yàn)碼 解：1)設(shè)錯(cuò)誤(cuw)累加器(err)初值=0 2)求出冗余碼的偶校驗(yàn)和，并按碼位累加到err中： A=(1,0,1,0,1,0)=1 err=err+20=1 B=(0,0,0,0,1,0)=1 err=err+21=3 C=(1,1,0,0,0) =0 err=err+0 =3 D=(0,1,1,0,0) =0 err=err+0 =3 共二十五頁(yè)海明校驗(yàn)碼 由err0可知接收碼字有錯(cuò)， 3)碼字的錯(cuò)誤位置就是錯(cuò)誤累加器(err)的值3。 4)糾錯(cuò)-對(duì)碼字的第3位值取反得正確(zhngqu)碼字： 1 0 1 1 1 0 0 0 1 1 0 0 5)把位于2的k次方位的冗余碼刪除得信息碼：1 1 0 0 1 1 0 0 共二十五頁(yè)內(nèi)容摘要奇偶校驗(yàn)碼。奇校驗(yàn)整個(gè)校驗(yàn)碼（有效信息