海明碼原理說明

海明碼：是由R·Hamming在1950年首次提出的，它也是一種可以糾正一位差錯的編碼，但它的編碼效率要比正反碼高得多（當信息位足夠長時）。基礎知識：二進制數表示二進制邏輯運算數的表示方法奇偶校驗奇偶校驗碼；若信息的位數為k＝n－1位，可表示為an-1an-2…a1，加上一位偶校驗位a0，構成一個n位的碼字an-1an-2…a1a0

。在接收端校驗時，可按下列關系式來計算：

S=an-1+an-2+…a1+a0（a0

用以湊成偶數個“1”）結果：若S＝0，則無錯，若S＝1，則有錯。上式可稱為監督關系式，S稱為校正因子。在奇偶校驗情況下，只有一個監督關系式，一個校正因子，其取值只有兩種（0或l），分別代表了無錯和有錯兩種情況，而不能指出差錯所在的位置。可以增加冗余位，就相應地增加監督關系式和校正因子，就能區分更多的情況。例如，若有兩個（2位）校正因子，則其取值就有4種可能：00、01、10或11，就能區分4種不同情況。若其中一種表示無錯，另外三種不但可以用來指出有錯，還可用來區分錯誤的情況，如指出是哪一位錯等。一般而言，信息位為k位，增加r位冗余位，構成n＝k＋r位碼字。若希望用r個監督關系式產生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯，則要求：

2r≥n＋1或者2r≥k＋r＋1注:(n=k+r)如果用k＝4為例來說明，要滿足上述不等式，則r＞3。假設取r＝3則n＝k＋r＝7，即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，構成7位碼字a6a5a4a3a2a1a0

。a2、

a1和a0分別由4位信息位中某幾位半加得到。校驗時，a2、

a1和a0

就分別和這些位半加構成三個不同的監督關系式。規定：無錯時，這三個關系式的值S2、S1和S0全為“0”。若a2錯，則S2＝1，而S1

＝S0＝0；若a1錯，則S1＝1，而S2＝S0＝0；若a0錯，則S0＝1，而S2＝S1＝0。S2S1S0這三個校正因子其它4種編碼值可用來區分a6a5a4a3一位錯，該對應關系可以規定如表1．3S2S1S0000

001

010100011101110111

錯碼位置 無a0a1a2a3a4a5a6由表可見，a2、a4、a5或a6的一位錯都應使S2＝1，由此得到監督關系式：S2

＝a2＋a4十a5十a6同理還有：

S1

＝a1＋a3十a5十a6S0

＝a0＋a3十a4十a6在發送端編碼時，信息位a6a5a4和a3的值取決于輸入信號，是隨機值。冗余位a2a1和a0的值應根據信息位的取值按監督關系式來決定，便上述三式中的S2S1

和S0

取值為零，即：

a2＋a4＋a5

＋a6

＝0 a1＋a3

＋a5

＋a6

＝0 a0

＋a3

＋a4

＋a6

＝0由此可求得：

a2＝a4十a5十a6 a1＝a3十a5十a6 a0＝a3十a4十a6已知信息位后，按此三式即可算出各冗余位。a6a5a4a3a2ala0a6a5a4a3a2ala00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111對于各種信息位算出的冗余位如表：在接收端收到每個碼字后，按監督關系式算出S2、S1和S0，若全為“0”則認為無錯。若不全為“0”，在一位錯的情況下，可查表來判定是哪一位錯，從而糾正之。例如碼字0010101傳輸中發生一位錯，在接收端收到的為0011101，代入監督關系式：

S2

＝a2＋a4十a5十a6 S1

＝a1＋a3十a5十a6 S0

＝a0＋a3十a4十a6可算得S2＝0、S1＝1和S0

＝1，由表：S2S1S0000

001

010100011101110111

錯碼位置 無a0a1a2a3a4a5a6可查得S2S1和S0

＝011對應于a3錯，因而可將0011101糾正為0010101。上述海明碼的編碼效率為4／7。若K＝7，按2r≥k十r＋1可算得r至少為4，此時編碼效率為7／11。結論：信息位長度越長時編碼效率越高。照例海明碼只能糾正一位錯，若用下述方法排列可以糾正傳輸中出現的突發性錯誤。將連續P個碼字排成一個矩陣，每行一個碼字，如圖所示 信息位冗余位

0001 011 1010 010 1011 001 0100 110 P個碼字組成矩陣

0100 110 每