1、奇偶校驗(yàn)碼,1.奇偶校驗(yàn)概念 奇偶校驗(yàn)碼是一種最簡(jiǎn)單的數(shù)據(jù)校驗(yàn)碼，它的碼距等于2，可以檢測(cè)出一位錯(cuò)誤（或奇數(shù)位錯(cuò)誤），但不能確定出錯(cuò)的位置，也不能檢測(cè)出偶數(shù)位錯(cuò)誤。 奇偶校驗(yàn)實(shí)現(xiàn)方法是：由若干位有效信息（如一個(gè)字節(jié)），再加上一個(gè)二進(jìn)制位（校驗(yàn)位）組成校驗(yàn)碼。 圖2-1奇偶校驗(yàn)碼,奇偶校驗(yàn)規(guī)律,校驗(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ù)。,2.簡(jiǎn)單奇偶校驗(yàn),簡(jiǎn)單奇偶校驗(yàn)僅實(shí)現(xiàn)橫向的奇偶校驗(yàn)，下表給出幾個(gè)字節(jié)的奇偶校驗(yàn)碼的編碼結(jié)果。最高一位為校驗(yàn)位

2、，其余8位為信息位。在實(shí)際應(yīng)用中，多采用奇校驗(yàn)，因?yàn)槠嫘ｒ?yàn)中不存在全“0”代碼，在某些場(chǎng)合下更便于判別。,2.簡(jiǎn)單奇偶校驗(yàn)（續(xù)）, 校驗(yàn)位形成 當(dāng)要把一個(gè)字節(jié)的代碼D7D0寫入主存時(shí)，就同時(shí)將它們送往奇偶校驗(yàn)邏輯電路，該電路產(chǎn)生的“奇形成”信號(hào)就是校驗(yàn)位。它將與8位代碼一起作為奇校驗(yàn)碼寫入主存。 若D7D0中有偶數(shù)個(gè)“1”，則“奇形成”=1， 若D7D0中有奇數(shù)個(gè)“1”，則“奇形成”=0。,奇偶校驗(yàn)位的形成及校驗(yàn)電路,圖2-2 奇偶校驗(yàn)位的形成及校驗(yàn)電路,2.簡(jiǎn)單奇偶校驗(yàn)（續(xù)）,校驗(yàn)檢測(cè) 讀出時(shí)，將讀出的9位代碼（8位信息位和1位校驗(yàn)位）同時(shí)送入奇偶校驗(yàn)電路檢測(cè)。若讀出代碼無錯(cuò)，則“奇校驗(yàn)出錯(cuò)

3、”=0；若讀出代碼中的某一位上出現(xiàn)錯(cuò)誤，則“奇校驗(yàn)出錯(cuò)”=1，從而指示這個(gè)9位代碼中一定有某一位出現(xiàn)了錯(cuò)誤，但具體的錯(cuò)誤位置是不能確定的。,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é) 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,3.交叉奇偶校驗(yàn)（續(xù)）,交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時(shí)出

4、錯(cuò)的情況，假設(shè)第2字節(jié)的A6、A4兩位均出錯(cuò)，橫向校驗(yàn)位無法檢出錯(cuò)誤，但是第A6、A4位所在列的縱向校驗(yàn)位會(huì)顯示出錯(cuò)，這與前述的簡(jiǎn)單奇偶校驗(yàn)相比要保險(xiǎn)多了。,海明校驗(yàn)碼,海明碼是一種可以糾正一位差錯(cuò)的編碼。它是利用在信息位為k位，增加r位冗余位，構(gòu)成一個(gè)n=k+r位的碼字，然后用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)。它必需滿足以下關(guān)系式： 2r k+r+1 或 2r n+1,海明校驗(yàn)碼,海明碼(Hamming Code )編碼的關(guān)鍵是使用多余的奇偶校驗(yàn)位來識(shí)別一位錯(cuò)誤。 碼字(Code Word) 按如下方法構(gòu)建： 1、把所有2的冪次方的數(shù)據(jù)位標(biāo)記為奇偶校

5、驗(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àn)碼,3、每個(gè)奇偶校驗(yàn)位的值代表了代碼字中部分?jǐn)?shù)據(jù)位的奇偶性，其所在位置決定了要校驗(yàn)和跳過的比特位順序。 位置1：校驗(yàn)1位，跳過1位，校驗(yàn)1位，跳過1位(1,3,5,7,9,11,13,15,) 位置2：校驗(yàn)2位，跳過2位，校驗(yàn)2位，跳過2位 (2,3,6,7,10,11,14,15,) 位置4：校驗(yàn)4位，跳過4位，校驗(yàn)4位，跳過4位 (4,5,6,7,12,13,14,15,20,21,

6、22,23,) 位置8：校驗(yàn)8位，跳過8位，校驗(yàn)8位，跳過8位(8-15,24-31,40-47,) ,海明校驗(yàn)碼,采用偶校驗(yàn)，如果全部校驗(yàn)的位置中有奇數(shù)個(gè)1，把該奇偶校驗(yàn)位置為1；如果全部校驗(yàn)的位置中有偶數(shù)個(gè)1，把該奇偶校驗(yàn)位置為0.,海明校驗(yàn)碼,舉例說明： 一個(gè)字節(jié)的數(shù)據(jù)：10011010 構(gòu)造數(shù)據(jù)字(Data Word),對(duì)應(yīng)的校驗(yàn)位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 計(jì)算每個(gè)校驗(yàn)位的奇偶性 ( ?代表要設(shè)置的比特位):,海明校驗(yàn)碼,位置1檢查1,3,5,7,9,11: ? _ 1 _ 0 0 1 _ 1 0 1 0. 偶數(shù)個(gè)1，因此位置1設(shè)為0，即: 0 _ 1 _ 0

7、 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àn)碼,位置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 _ 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àn)

8、碼,上例中構(gòu)建了一個(gè)碼字 011100101010，假定實(shí)際接收到的數(shù)據(jù) 011100101110. 則接收方可以計(jì)算出哪一位出錯(cuò)并對(duì)其進(jìn)行更正。方法就是驗(yàn)證每一個(gè)校驗(yàn)位。記下所有出錯(cuò)的校驗(yàn)位，可以發(fā)現(xiàn)校驗(yàn)位2和8的數(shù)據(jù)不正確. 錯(cuò)誤校驗(yàn)位 2 + 8 = 10, 則位置10的數(shù)據(jù)出錯(cuò)。一般說來，對(duì)所有校驗(yàn)位進(jìn)行檢查, 將所有出錯(cuò)的校驗(yàn)位置相加, 得到的就是錯(cuò)誤信息所在的位置.,海明校驗(yàn)碼,例1.已知：信息碼為： 1 1 0 0 1 1 0 0 (r=4代表冗余位數(shù)，即校驗(yàn)碼位數(shù)) 求：海明碼碼字。,海明校驗(yàn)碼,解：1)把冗余碼A、B、C、，順序插入信息碼中，得海明碼 碼字: A B 1 C

9、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àn)碼,2)冗余碼A,B,C,D的線性碼位是：(相當(dāng)于監(jiān)督關(guān)系式) 監(jiān)督關(guān)系式的推導(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ù)上面表格得到 A B C D,海明校驗(yàn)碼,需要說明的是公式

10、中參與計(jì)算的是表格中出現(xiàn)1的那個(gè)位 右邊是數(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； 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àn)碼,3)把線性碼位的值的偶校驗(yàn)作為冗余碼的值(設(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àn)碼,例2.已知：接收的碼字為： 1 0 0 1 1 0 0 0 1 1 0 0(r=4代表冗余位數(shù)，即校驗(yàn)碼位數(shù)) 求：發(fā)送端的信息碼。,海明校驗(yàn)碼,解：1)設(shè)錯(cuò)誤累加器(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=e