海明碼校驗(yàn)培訓(xùn)資料

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

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

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