海明碼例舉詳解

海明碼詳解以D=101101這個(gè)數(shù)字的海明碼推導(dǎo)為例海明碼步驟：一、確定校驗(yàn)碼的位數(shù)k二、確定校驗(yàn)碼的位置三、數(shù)據(jù)的位置四、求出校驗(yàn)位的值數(shù)據(jù)的位數(shù)m=6，公式來(lái)計(jì)算滿(mǎn)足條件的k的最小值2的k次方-1>=m+k即：2的k次方-1>=6+k解此不等式得：滿(mǎn)足不等式的最小k=4，也就是D=101101這個(gè)數(shù)字的海明碼應(yīng)該有6+4=10位，其中原數(shù)據(jù)6位，校驗(yàn)碼4位。一、確定校驗(yàn)碼的位數(shù)k設(shè)這4為校驗(yàn)碼分別為P1、P2、P3、P4數(shù)據(jù)從左到右為D1、D2、……、D6編碼后的數(shù)據(jù)共有6+4=10位，設(shè)為M1、M2、……M10校驗(yàn)碼Pi（這里i=1,2,3,4）在編碼中的位置為2的（i-1）次方，值是這樣的1,2,4,8,16……即：P1在M1位置，P2在M2位置，P3在M4位置，P4在M8位置，這里一共有10位,所以排不到M16，見(jiàn)下圖中“甲”行紅色字體二、確定校驗(yàn)碼的位置M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101圖1這個(gè)很簡(jiǎn)單，除了校驗(yàn)碼的位置其余的就是數(shù)據(jù)的位置，填充進(jìn)去就可以了，見(jiàn)圖中“甲”行的藍(lán)色字體，于是可以先把數(shù)據(jù)信息填進(jìn)去，見(jiàn)“丙”行，下面就是最關(guān)鍵的部分，求出校驗(yàn)位的值三、數(shù)據(jù)的位置M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101丙101101這里會(huì)用到一個(gè)公式，先回顧一下二進(jìn)制的表達(dá)，對(duì)于一個(gè)4位二進(jìn)制數(shù)，可以表達(dá)16個(gè)值，0000B~1111B，“B”代表二進(jìn)制，“D”代表十進(jìn)制，假定這4位二進(jìn)制數(shù)，從左到右分別為S4、S3、S2、S1，請(qǐng)向左歪90°看下圖：1D=0001B，所以M1在S1那一行，4D=0100B，所以M4在S3那一行，5D=0101B，這就不能用一個(gè)格子來(lái)表達(dá)了，所以需要S3和S1共同表達(dá)，即4+1=5，看圖中黃色的部分，是不是M5？M后邊的數(shù)字都可以拆為由2的n次方的數(shù)相加來(lái)表達(dá)，在舉一個(gè)例子M7：4+2+1=7即：7D=0111B，看圖中橙色的部分，都是M7吧!這個(gè)公式在驗(yàn)證糾錯(cuò)的時(shí)候還會(huì)用得到，只要記住這個(gè)公式的推導(dǎo)就可以解決所有問(wèn)題了。四、求出校驗(yàn)位的值S1=M1⊕M3⊕M5⊕M7⊕M9S2=M2⊕M3⊕M6⊕M7⊕M10S3=M4⊕M5⊕M6⊕M7S4=M8⊕M9⊕M10圖2接下來(lái)就是代入求值的過(guò)程了，注意“⊕”這個(gè)符號(hào)，這是異或符號(hào)。按照?qǐng)D1中的指示，把相應(yīng)的值代入到圖2的公式里，可以得到如下內(nèi)容S1=M1⊕M3⊕M5⊕M7⊕M9=P1⊕D1⊕D2⊕D4⊕D5S2=M2⊕M3⊕M6⊕M7⊕M10=P2⊕D1⊕D3⊕D4⊕D6S3=M4⊕M5⊕M6⊕M7=P3⊕D2⊕D3⊕D4S4=M8⊕M9⊕M10

=P4⊕D5⊕D6 如果海明碼沒(méi)有錯(cuò)誤信息，S1、S2、S3、S4都為0，等式右邊的值也得為0，由于是異或，所以Pi（i=1,2,3…）的值跟后邊的式子必須一樣才能使整個(gè)式子的值為零，即：Pi=后邊的式子的值,即：P1 =D1⊕ D2⊕ D4⊕ D5P2 =D1⊕ D3⊕ D4⊕ D6P3 =D2⊕ D3⊕ D4 P4 =D5⊕ D6 仔細(xì)想一下異或的含義，以S4=P4⊕D5⊕D6為例,S4=0,就是說(shuō)P4⊕D5⊕D6=0，那么P4和（D5⊕D6）必須一樣（即P4=D5⊕D6），那么異或的結(jié)果才能為零！（不要以算術(shù)加減法來(lái)理解，要用邏輯數(shù)學(xué)的思維！）那么可以算出Pi的值了吧？P1 =D1⊕D2⊕D4⊕D5=1⊕0⊕1⊕0=0P2 =D1⊕D3⊕D4⊕D6=1⊕1⊕1⊕1=0P3 =D2⊕D3⊕D4=0⊕1⊕1=0P4

=D5⊕D6=0⊕1=1把Pi的值填寫(xiě)到圖1中，看“丙”行，就可以得到haimming（海明）編碼！M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101丙0010011101現(xiàn)在我們得到了D=101101的正確海明碼就是那么出錯(cuò)的時(shí)候是怎么驗(yàn)證出來(lái)的呢？比如第5位錯(cuò)了，第5位現(xiàn)在的值是0，如果錯(cuò)了，它只能是1，二進(jìn)制就這兩種值即：我們得到了這樣的一組編碼，現(xiàn)在要找出錯(cuò)誤的位置（假定你不知道哪里錯(cuò)）五、海明碼校驗(yàn)過(guò)程0010011101M1M2M3M4M5M6M7M8M9M100010111101M1M2M3M4M5M6M7M8M9M100010111101現(xiàn)在又要用到公式了，請(qǐng)看圖S1=M1⊕M3⊕M5⊕M7⊕M9S2=M2⊕M3⊕M6⊕M7⊕M10S3=M4⊕M5⊕M6⊕M7S4=M8⊕M9⊕M10M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101把圖4中的值，帶入