海明碼校驗 (1).ppt

1、奇偶校驗碼,1.奇偶校驗概念 奇偶校驗碼是一種最簡單的數(shù)據(jù)校驗碼，它的碼距等于2，可以檢測出一位錯誤（或奇數(shù)位錯誤），但不能確定出錯的位置，也不能檢測出偶數(shù)位錯誤。 奇偶校驗實現(xiàn)方法是：由若干位有效信息（如一個字節(jié)），再加上一個二進制位（校驗位）組成校驗碼。 圖2-1奇偶校驗碼,奇偶校驗規(guī)律,校驗位的取值（0或1）將使整個校驗碼中“1”的個數(shù)為奇數(shù)或偶數(shù)，所以有兩種可供選擇的校驗規(guī)律： 奇校驗整個校驗碼（有效信息位和校驗位）中“1”的個數(shù)為奇數(shù)。 偶校驗整個校驗碼中“1”的個數(shù)為偶數(shù)。,2.簡單奇偶校驗,簡單奇偶校驗僅實現(xiàn)橫向的奇偶校驗，下表給出幾個字節(jié)的奇偶校驗碼的編碼結(jié)果。最高一位為校驗位

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

3、”=0；若讀出代碼中的某一位上出現(xiàn)錯誤，則“奇校驗出錯”=1，從而指示這個9位代碼中一定有某一位出現(xiàn)了錯誤，但具體的錯誤位置是不能確定的。,3.交叉奇偶校驗,計算機在進行大量字節(jié)（數(shù)據(jù)塊）傳送時，不僅每一個字節(jié)有一個奇偶校驗位做橫向校驗，而且全部字節(jié)的同一位也設(shè)置一個奇偶校驗位做縱向校驗，這種橫向、縱向同時校驗的方法稱為交叉校驗。 第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.交叉奇偶校驗（續(xù)）,交叉校驗可以發(fā)現(xiàn)兩位同時出

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

5、驗位(編號為1, 2, 4, 8, 16, 32, 64等的位置) 2、其他數(shù)據(jù)位用于待編碼數(shù)據(jù). (編號為3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置),海明校驗碼,3、每個奇偶校驗位的值代表了代碼字中部分數(shù)據(jù)位的奇偶性，其所在位置決定了要校驗和跳過的比特位順序。 位置1：校驗1位，跳過1位，校驗1位，跳過1位(1,3,5,7,9,11,13,15,) 位置2：校驗2位，跳過2位，校驗2位，跳過2位 (2,3,6,7,10,11,14,15,) 位置4：校驗4位，跳過4位，校驗4位，跳過4位 (4,5,6,7,12,13,14,15,20,21,

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

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

10、中參與計算的是表格中出現(xiàn)1的那個位 右邊是數(shù)據(jù)位的二進制數(shù),公式中的+表示異或 故此有如下表達式： 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。,海明校驗碼,3)把線性碼位的值的偶校驗作為冗余碼的值(設(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,海明校驗碼,例2.已知：接收的碼字為： 1 0 0 1 1 0 0 0 1 1 0 0(r=4代表冗余位數(shù)，即校驗碼位數(shù)) 求：發(fā)送端的信息碼。,海明校驗碼,解：1)設(shè)錯誤累加器(err)初值=0 2)求出冗余碼的偶校驗和，并按碼位累加到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