海明碼
基本概念
海明碼：能糾正所有單個比特的高效線性分組碼。
最大似然譯碼：接收到的碼字，最像某一允許碼，就判決為這個碼。
碼元：碼字中的二進制位。
碼字：碼元的組合。
碼長：碼字中碼元的個數。
碼組：所有許用碼字構成的碼字空間。
碼距：兩碼字間對應位上的碼元取值不同的位數。
海明距離（d）：碼組中的最小碼字。決定了碼組的糾錯能力。
對于3位編碼的碼距，可用三維空間表示，每個碼字對應立方體的各個頂點，碼距可用對應兩頂點間沿立方體各棱行走的最短幾何距離表示。如果僅用“000”和“111”為許用碼，則碼距為3。
海明距離與糾錯能力的關系：
1、當碼組用于檢錯時：設檢錯個數為e，則：d>=e+1。
說明：碼字a和b出現e個錯誤時，仍沒有變成對方，和對方至少有一個碼元位不同。
2、當碼組用于糾正t重錯時：則：d>=2t+1。
說明：碼字a和b同時出現t個錯誤時，仍能看出出錯後的碼字最像誰（最大似然譯碼）。
3、當碼組用于糾正t重錯，同時檢測e個錯誤時，要求（e>t），則：d>=e+t+1。
碼字a和b出現e個錯誤時，仍沒有變成對方，且碼字a和b同時出現t個錯誤時，仍能看出出錯後的碼字最像誰。
海明碼糾正單比特差錯。
原理：在d位資訊位後增加r位備援位，構成一個n=d+r位的碼字，且滿足關系：2r>=d+r+1，即用r個監督關系式産生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯。将r位備援位安插在碼字的2的幂次方的位置，将碼字中資訊位的位置用二進制表示，備援位的值是碼字中位置相應位為“1”的資訊位的異或。接收方按上述方法進行校驗，并降序排列備援位，值不為“0”則表示對應位置的碼元出錯。
海明碼的編碼效率為：r=d/d+r)
式中 d為資訊位位數，為增加備援位位數。
海明碼的生成與接收
方法一：（按教科書）
1)海明碼的生成。
例1.已知：資訊碼為："0010"。海明碼的監督關系式為：
s2=a2+a4+a5+a6
s1=a1+a3+a5+a6
s0=a0+a3+a4+a6
求：海明碼碼字。
解：1)由監督關系式知備援碼為a2a1a0。
2)備援碼與資訊碼合成的海明碼是："0010a2a1a0"。
設s2=s1=s0=0,由監督關系式得：
a2=a4+a5+a6=1
a1=a3+a5+a6=0
a0=a3+a4+a6=1
是以，海明碼碼字為："0010101"
2)海明碼的接收。
例2.已知：海明碼的監督關系式為：
接收碼字為："0011101"(n=7)
求：發送端的資訊碼。
解：1)由海明碼的監督關系式計算得s2s1s0=011。
2)由監督關系式可構造出下面錯碼位置關系表：
s2s1s0 000 001 010 100 011 101 110 111
錯碼位置 無錯 a0 a1 a2 a3 a4 a5 a6
3)由s2s1s0=011查表得知錯碼位置是a3。
4)糾錯--對碼字的a3位取反得正确碼字："0 0 1 0 1 0 1"
5)把備援碼a2a1a0删除得發送端的資訊碼："0010"
***方法二：(不用查表，友善程式設計)
1)海明碼的生成（順序生成法）。
例3.已知：資訊碼為：" 1 1 0 0 1 1 0 0 "(d=8)
解：1)把備援碼a、b、c、…，順序插入資訊碼中，得海明碼
碼字:" a b 1 c 1 0 0 d 1 1 0 0 "
碼位: 1 2 3 4 5 6 7 8 9 10 11 12
其中a,b,c,d分别插于2k位(k=0,1,2,3)。碼位分别為1,2,4,8。
111.jpg (15.23 kb)
2007-10-26 10:54
2)備援碼a,b,c,d的線性碼位是：(相當于監督關系式)
a->1,3,5,7,9,11；
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)把線性碼位的值的偶校驗作為備援碼的值(設備援碼初值為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"
例4.已知：接收的碼字為："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)
解：1)設錯誤累加器(err)初值=0
2)求出備援碼的偶校驗和，并按碼位累加到err中：
a=∑(1,0,1,0,1,0)=1
b=∑(0,0,0,0,1,0)=1
c=∑(1,1,0,0,0)=0
由err≠0可知接收碼字有錯，
3)碼字的錯誤位置就是錯誤累加器(err)的值dcba=0011：3。
4)糾錯--對碼字的第3位值取反得正确碼字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位于2k位的備援碼删除得資訊碼："1 1 0 0 1 1 0 0"