海明碼例舉詳解

海明碼詳解以D=101101這個數(shù)字的海明碼推導(dǎo)為例海明碼步驟：一、確定校驗碼的位數(shù)k二、確定校驗碼的位置三、數(shù)據(jù)的位置四、求出校驗位的值數(shù)據(jù)的位數(shù)m=6，公式來計算滿足條件的k的最小值2的k次方-1>=m+k即：2的k次方-1>=6+k解此不等式得：滿足不等式的最小k=4，也就是D=101101這個數(shù)字的海明碼應(yīng)該有6+4=10位，其中原數(shù)據(jù)6位，校驗碼4位。一、確定校驗碼的位數(shù)k設(shè)這4為校驗碼分別為P1、P2、P3、P4數(shù)據(jù)從左到右為D1、D2、……、D6編碼后的數(shù)據(jù)共有6+4=10位，設(shè)為M1、M2、……M10校驗碼Pi（這里i=1,2,3,4）在編碼中的位置為2的（i-1）次方，值是這樣的1,2,4,8,16……即：P1在M1位置，P2在M2位置，P3在M4位置，P4在M8位置，這里一共有10位,所以排不到M16，見下圖中“甲”行紅色字體二、確定校驗碼的位置M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101圖1這個很簡單，除了校驗碼的位置其余的就是數(shù)據(jù)的位置，填充進去就可以了，見圖中“甲”行的藍色字體，于是可以先把數(shù)據(jù)信息填進去，見“丙”行，下面就是最關(guān)鍵的部分，求出校驗位的值三、數(shù)據(jù)的位置M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101丙101101這里會用到一個公式，先回顧一下二進制的表達，對于一個4位二進制數(shù)，可以表達16個值，0000B~1111B，“B”代表二進制，“D”代表十進制，假定這4位二進制數(shù)，從左到右分別為S4、S3、S2、S1，請向左歪90°看下圖：1D=0001B，所以M1在S1那一行，4D=0100B，所以M4在S3那一行，5D=0101B，這就不能用一個格子來表達了，所以需要S3和S1共同表達，即4+1=5，看圖中黃色的部分，是不是M5？M后邊的數(shù)字都可以拆為由2的n次方的數(shù)相加來表達，在舉一個例子M7：4+2+1=7即：7D=0111B，看圖中橙色的部分，都是M7吧!這個公式在驗證糾錯的時候還會用得到，只要記住這個公式的推導(dǎo)就可以解決所有問題了。四、求出校驗位的值S1=M1⊕M3⊕M5⊕M7⊕M9S2=M2⊕M3⊕M6⊕M7⊕M10S3=M4⊕M5⊕M6⊕M7S4=M8⊕M9⊕M10圖2接下來就是代入求值的過程了，注意“⊕”這個符號，這是異或符號。按照圖1中的指示，把相應(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 如果海明碼沒有錯誤信息，S1、S2、S3、S4都為0，等式右邊的值也得為0，由于是異或，所以Pi（i=1,2,3…）的值跟后邊的式子必須一樣才能使整個式子的值為零，即：Pi=后邊的式子的值,即：P1 =D1⊕ D2⊕ D4⊕ D5P2 =D1⊕ D3⊕ D4⊕ D6P3 =D2⊕ D3⊕ D4 P4 =D5⊕ D6 仔細想一下異或的含義，以S4=P4⊕D5⊕D6為例,S4=0,就是說P4⊕D5⊕D6=0，那么P4和（D5⊕D6）必須一樣（即P4=D5⊕D6），那么異或的結(jié)果才能為零?。ú灰运阈g(shù)加減法來理解，要用邏輯數(shù)學(xué)的思維?。┠敲纯梢运愠鯬i的值了吧？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的值填寫到圖1中，看“丙”行，就可以得到haimming（海明）編碼！M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101丙0010011101現(xiàn)在我們得到了D=101101的正確海明碼就是那么出錯的時候是怎么驗證出來的呢？比如第5位錯了，第5位現(xiàn)在的值是0，如果錯了，它只能是1，二進制就這兩種值即：我們得到了這樣的一組編碼，現(xiàn)在要找出錯誤的位置（假定你不知道哪里錯）五、海明碼校驗過程0010011101M1M2M3M4M5M6M7M8M9M100010111101M1M2M3M4M5M6M7M8M9M100010111101現(xiàn)在又要用到公式了，請看圖S1=M1⊕M3⊕M5⊕M7⊕M9S2=M2⊕M3⊕M6⊕M7⊕M10S3=M4⊕M5⊕M6⊕M7S4=M8⊕M9⊕M10M1M2M3M4M5M6M7M8M9M10甲P1P2D1P3D2D3D4P4D5D6乙101101把圖4中的值，帶入