海明碼校驗培訓資料

奇偶校驗規(guī)律(guīlǜ)校驗位的取值（0或1）將使整個校驗碼中“1”的個數(shù)為奇數(shù)或偶數(shù)，所以有兩種可供選擇的校驗規(guī)律(guīlǜ)：奇校驗──整個校驗碼（有效信息位和校驗位）中“1”的個數(shù)為奇數(shù)。偶校驗──整個校驗碼中“1”的個數(shù)為偶數(shù)。第一頁，共23頁。2.簡單(jiǎndān)奇偶校驗簡單奇偶校驗僅實現(xiàn)橫向的奇偶校驗，下表給出幾個字節(jié)的奇偶校驗碼的編碼結果。最高一位為校驗位，其余8位為信息位。在實際應用中，多采用奇校驗，因為奇校驗中不存在全“0”代碼，在某些場合下更便于(biànyú)判別。有效信息（8位）奇校驗碼（9位）偶校驗碼（9位）00000000100000000000000000010101000010101001010101000111111100111111110111111111111111111111111011111111第二頁，共23頁。2.簡單(jiǎndān)奇偶校驗（續(xù)）⑴校驗位形成當要把一個字節(jié)的代碼D7～D0寫入主存時，就同時將它們(tāmen)送往奇偶校驗邏輯電路，該電路產生的“奇形成”信號就是校驗位。它將與8位代碼一起作為奇校驗碼寫入主存。若D7～D0中有偶數(shù)個“1”，則“奇形成”=1，

若D7～D0中有奇數(shù)個“1”，則“奇形成”=0。第三頁，共23頁。奇偶校驗(xiàoyàn)位的形成及校驗(xiàoyàn)電路圖2-2奇偶校驗(xiàoyàn)位的形成及校驗(xiàoyàn)電路第四頁，共23頁。2.簡單(jiǎndān)奇偶校驗（續(xù)）⑵校驗檢測讀出時，將讀出的9位代碼（8位信息位和1位校驗位）同時送入奇偶校驗電路檢測。若讀出代碼無錯，則“奇校驗出錯”=0；若讀出代碼中的某一位上出現(xiàn)錯誤(cuòwù)，則“奇校驗出錯”=1，從而指示這個9位代碼中一定有某一位出現(xiàn)了錯誤(cuòwù)，但具體的錯誤(cuòwù)位置是不能確定的。第五頁，共23頁。3.交叉(jiāochā)奇偶校驗計算機在進行大量(dàliàng)字節(jié)（數(shù)據塊）傳送時，不僅每一個字節(jié)有一個奇偶校驗位做橫向校驗，而且全部字節(jié)的同一位也設置一個奇偶校驗位做縱向校驗，這種橫向、縱向同時校驗的方法稱為交叉校驗。第1字節(jié)11001011→1第2字節(jié)01011100→0第3字節(jié)10011010→0第4字節(jié)10010101→0↓↓↓↓↓↓↓↓10011000第六頁，共23頁。3.交叉(jiāochā)奇偶校驗（續(xù)）交叉校驗可以發(fā)現(xiàn)兩位同時出錯的情況，假設(jiǎshè)第2字節(jié)的A6、A4兩位均出錯，橫向校驗位無法檢出錯誤，但是第A6、A4位所在列的縱向校驗位會顯示出錯，這與前述的簡單奇偶校驗相比要保險多了。第七頁，共23頁。海明校驗碼海明碼是一種可以糾正一位差錯的編碼。它是利用在信息位為k位，增加r位冗余位，構成一個n=k+r位的碼字，然后用r個監(jiān)督關系式產生的r個校正(jiàozhèng)因子來區(qū)分無錯和在碼字中的n個不同位置的一位錯。它必需滿足以下關系式：2r≥k+r+1或2r≥n+1第八頁，共23頁。海明校驗碼海明碼(HammingCode)編碼的關鍵是使用多余的奇偶校驗位來識別一位錯誤。碼字(CodeWord)按如下方法構建：1、把所有2的冪次方的數(shù)據位標記為奇偶校驗位(編號(biānhào)為1,2,4,8,16,32,64等的位置)2、其他數(shù)據位用于待編碼數(shù)據.(編號(biānhào)為3,5,6,7,9,10,11,12,13,14,15,17等的位置)第九頁，共23頁。海明校驗碼3、每個奇偶校驗位的值代表了代碼字中部分(bùfen)數(shù)據位的奇偶性，其所在位置決定了要校驗和跳過的比特位順序。位置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,22,23,…)位置8：校驗8位，跳過8位，校驗8位，跳過8位(8-15,24-31,40-47,…)…第十頁，共23頁。海明校驗碼采用偶校驗，如果全部(quánbù)校驗的位置中有奇數(shù)個1，把該奇偶校驗位置為1；如果全部(quánbù)校驗的位置中有偶數(shù)個1，把該奇偶校驗位置為0.第十一頁，共23頁。海明校驗碼舉例說明：一個字節(jié)的數(shù)據：10011010構造(gòuzào)數(shù)據字(DataWord),對應的校驗位留空__1_001_1010計算每個校驗位的奇偶性(?代表要設置的比特位):

第十二頁，共23頁。海明校驗碼位置(wèizhi)1檢查1,3,5,7,9,11:?_1_001_1010.偶數(shù)個1，因此位置(wèizhi)1設為0，即:0_1_001_1010位置(wèizhi)2檢查2,3,6,7,10,11:0?1_001_1010.奇數(shù)個1，因此位置(wèizhi)2設為1，即:011_001_1010第十三頁，共23頁。海明校驗碼位置4檢查4,5,6,7,12:011?001_1010.奇數(shù)個1，因此(yīncǐ)位置4設為1，即:0111001_1010位置8檢查8,9,10,11,12:0111001?1010.偶數(shù)個1，因此(yīncǐ)位置8設為0，即:011100101010因此(yīncǐ)碼字為:011100101010.第十四頁，共23頁。海明校驗碼上例中構建了一個碼字011100101010，假定實際接收到的數(shù)據011100101110.則接收方可以計算出哪一位出錯并對其進行更正。方法就是驗證每一個校驗位。記下所有出錯的校驗位，可以發(fā)現(xiàn)(fāxiàn)校驗位2和8的數(shù)據不正確.錯誤校驗位2+8=10,則位置10的數(shù)據出錯。一般說來，對所有校驗位進行檢查,將所有出錯的校驗位置相加,得到的就是錯誤信息所在的位置.第十五頁，共23頁。海明校驗碼例1.已知：信息碼為："11001100"(r=4代表(dàibiǎo)冗余位數(shù)，即校驗碼位數(shù))求：海明碼碼字。第十六頁，共23頁。海明校驗碼解：1)把冗余碼A、B、C、…，順序插入信息碼中，得海明碼碼字:"AB1C100D1100"碼位:123456789101112其中(qízhōng)A,B,C,D分別插于2的k次方位(k=0,1,2,3)。碼位分別為1,2,4,8。第十七頁，共23頁。海明校驗碼2)冗余碼A,B,C,D的線性碼位是：(相當于監(jiān)督(jiāndū)關系式)監(jiān)督(jiāndū)關系式的推導：DCBA100012001030011401005010160110701118100091001101010111011121100根據上面表格得到ABCD第十八頁，共23頁。海明校驗碼需要說明的是公式中參與計算的是表格中出現(xiàn)"1"的那個位右邊是數(shù)據位的二進制數(shù),公式中的"+"表示異或故此(gùcǐ)有如下表達式：A->1,3,5,7,9,11；(這里的1357911均為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。第十九頁，共23頁。海明校驗碼3)把線性碼位的值的偶校驗作為冗余(rǒnɡyú)碼的值(設冗余(rǒnɡyú)碼初值為0)：A=∑(0,1,1,0,1,0)=1B=∑(0,1,0,0,1,0)=0C=∑(0,1,0,0,0)=1D=∑(0,1,1,0,0)=04)海明碼為:"101110001100"第二十頁，共23頁。海明校驗碼例2.已知：接收的碼字為："100110001100"(r=4代表冗余(rǒnɡyú)位數(shù)，即校驗碼位數(shù))求：發(fā)送端的信息碼。第二十一頁，共23頁。海明校驗碼解：1)設錯誤(cuòwù)累加器(err)初值=02)求出冗余碼的偶校驗和，并按碼位累加到err中：A=∑(1,0,1,0,1,0)=1err=err+2^0=1B=∑(0,0,0,0,1,0)=1err=err+2^1=3C=∑(1,1,0,0,0)=0err=err