目錄
1.海明碼的原理
2.海明碼的生成與接收
3.海明碼的計算
4.海明碼校驗程序設計原理分析參考
編輯本段1.海明碼的原理
在數據中間加入幾個校驗碼，碼距均勻拉大，將數據的每個二進制位分配在幾個奇偶校驗組裏，當某壹位出錯，會引起幾個校驗位的值發生變化。
海明不等式：
校驗碼個數為K，2的K次方個信息，1個信息用來指出“沒有錯誤”，其余（2^K)-1個指出錯誤發生在那壹位，但也可能是校驗位錯誤，故有N<=(2^K)-1-K能被校驗。
海明碼的編碼規則：
1.每個校驗位Ri被分配在海明碼的第2的i次方的位置上，
2.海明碼的每壹位（Hi)是由多個/1個校驗值進行校驗的，被校驗碼的
位置碼是所有校驗位的校驗位位置碼之和。
壹個例題：
4個數據位d0,d1,d2,d3, 3個校驗位r0,r1,r2，對應的位置為：
d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1
校驗位的取值，就是他所能校驗的數據位的異或
b1為b3,b5,b7的異或，b2為b3,b6,b7 b4為b5,b6,b7
海明v傳送到接受方後，將上三式的右邊（b1,b2,b4)的邏輯表達式分別
異或上左邊的值就得到了校驗方程，如果上題采用偶校驗
G1=b1 b3 b5 b7的異或
G2=b2 b3 b6 b7的異或
G3=b4 b5 b6 b7的異或
若G1G2G3為001是第壹位錯
若為011是第三位錯
編輯本段2.海明碼的生成與接收
特註：以下的+均代表異或
方法壹：
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"
對以上這道題目的第二問的疑問：
冗余碼與信息碼合成的海明碼是："0010a2a1a0"。為什麽a2a1a0直接加在信息碼後面，而不是按照1,2,4,8位的順序加在信息碼後面例如：001(a2)0(a1)(a0)=0011001
2)海明碼的接收。
例2.已知：海明碼的監督關系式為：
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
接收碼字為："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 " (k=4代表冗余位數，即校驗碼位數)
求：海明碼碼字。
解：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分別插於2的k次方位(k=0,1,2,3)。碼位分別為1,2,4,8。
2)冗余碼A,B,C,D的線性碼位是：(相當於監督關系式)
監督關系式的推導：
D C B A
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
根據上面表格得到 A B C D
需要說明的是公式中參與計算的是表格中出現"1"的那個位 右邊是數據位的二進制數,公式中的"+"表示異或
故此有如下表達式：
A->1,3,5,7,9,11；(這裏的1 3 5 7 9 11均為A那壹列出現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。
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"
2)海明碼的接收。
例4.已知：接收的碼字為："1 0 0 1 1 0 0 0 1 1 0 0"(k=4代表冗余位數，即校驗碼位數)
求：發送端的信息碼。
解：1)設錯誤累加器(err)初值=0
2)求出冗余碼的偶校驗和，並按碼位累加到err中：
A=∑(1,0,1,0,1,0)=1 err=err+2^0=1
B=∑(0,0,0,0,1,0)=1 err=err+2^1=3
C=∑(1,1,0,0,0) =0 err=err+0 =3
D=∑(0,1,1,0,0) =0 err=err+0 =3
由err≠0可知接收碼字有錯，
3)碼字的錯誤位置就是錯誤累加器(err)的值3。
4)糾錯--對碼字的第3位值取反得正確碼字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位於2的k次方位的冗余碼刪除得信息碼："1 1 0 0 1 1 0 0"
編輯本段3.海明碼的計算
海明碼(Hamming Code )編碼的關鍵是使用多余的奇偶校驗位來識別壹位錯誤。
碼字(Code Word) 按如下方法構建：
1、把所有2的冪次方的數據位標記為奇偶校驗位(編號為1, 2, 4, 8, 16, 32, 64等的位置)
2、其他數據位用於待編碼數據. (編號為3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置)
3、每個奇偶校驗位的值代表了代碼字中部分數據位的奇偶性，其所在位置決定了要校驗和跳過的比特位順序。
位置1：校驗1位，跳過1位，校驗1位，跳過1位(1,3,5,7,9,11,13,15,…)
位置2：校驗2位，跳過2位，校驗2位，跳過2位 (2,3,6,7,10,11,14,15,…)
位置4：校驗4位，跳過4位，校驗4位，跳過4位 (4,5,6,7,12,13,14,15,20,21,22,23,…)
位置8：校驗8位，跳過8位，校驗8位，跳過8位(8-15,24-31,40-47,…)
…
如果全部校驗的位置中有奇數個1，把該奇偶校驗位置為1；如果全部校驗的位置中有偶數個1，把該奇偶校驗位置為0.
舉例說明：
壹個字節的數據：10011010
構造數據字(Data Word),對應的校驗位留空_ _ 1 _ 0 0 1 _ 1 0 1 0
計算每個校驗位的奇偶性 ( ?代表要設置的比特位):
位置1檢查1,3,5,7,9,11:
_ 1 _ 0 0 1 _ 1 0 1 0. 偶數個1，因此位置1設為0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0位置2檢查2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇數個1，因此位置2設為1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0
位置4檢查4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. 奇數個1，因此位置4設為1，即: 0 1 1 1 0 0 1 _ 1 0 1 0
位置8檢查8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. 偶數個1，因此位置8設為0，即: 0 1 1 1 0 0 1 0 1 0 1 0
因此碼字為: 011100101010.
查找並糾錯壹位錯誤
上例中構建了壹個碼字 011100101010，假定實際接收到的數據是011100101110. 則接收方可以計算出哪壹位出錯並對其進行更正。方法就是驗證每壹個校驗位。記下所有出錯的校驗位，可以發現校驗位2和8的數據不正確. 錯誤校驗位 2 + 8 = 10, 則位置10的數據出錯。壹般說來，對所有校驗位進行檢查, 將所有出錯的校驗位置相加, 得到的就是錯誤信息所在的位置.
編輯本段4.海明碼校驗程序設計原理分析參考
海明碼校驗是為了保證數據傳輸正確而提出的，本來就是壹串要傳送的數據，如：D7,D6,D5,D4,D3,D2,D1,D0，這裏舉的是八位數據，可以是n位數據。就這樣傳送數據，不知道接收到後是不是正確的。所以，要加入校驗位數據才能檢查是否出錯。這裏涉及到壹個問題，要多少位校驗數據才能查出錯誤呢？
我們只要能檢測出壹位出錯，則對於8位信息數據，校驗位為4位。滿足下列條件：2的k次方大於等於n+k+1，其中k為校驗位位數，n為信息數據位位數。驗證壹下，2的4次方等於16，n+k+1等於8+4+1等於13。 8位信息數據與4位校驗位總***有12位數據，怎麽排列呢？我們先把校驗位按P4,P3,P2,P1排列，用通式Pi表示校驗位序列，i為校驗位在校驗序列中的位置。 傳送的數據流用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1表示，接下來的問題是如何用D7,D6,D5,D4,D3,D2,D1,D0與P4,P3,P2,P1來表M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1了。校驗位在傳送的數據流中位置為2的i－1次方，則P1在M1位，P2在M2位，P3在M4位，P4在M8位。其余的用信息數據從高到低插入。 傳送的數據流為D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1。 接下來，我們要弄明白如何找出錯誤位的問題。引進4位校驗和序列S4,S3,S2,S1。S4,S3,S2,S1等於0,0,0,0表示傳送的數據流正確；如S4,S3,S2,S1等於0,0,1,0則表示傳送的數據流中第2位出錯；如S4,S3,S2,S1等於0,0,1,1則表示傳送的數據流中第3位出錯；依次類推。
用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1如何表示S4,S3,S2,S1呢，簡單的方法就是S1=1時，S4,S3,S2從0,0,0到1,1,1的所有的Mx異或。即S1等於M1異或M3異或M5異或M7異或M9異或M11。也就是S1等於P1異或D0異或D1異或D3異或D4異或D6。S2=1時，S4,S3,S1從0,0,0到1,1,1的所有的Mx異或。即S2等於M2異或M3異或M6異或M7異或M10異或M11。S3=1時，S4,S2,S1從0,0,0到1,1,1的所有的Mx異或。即S3等於M4異或M5異或M6異或M7異或M12。S4=1時，S3,S2,S1從0,0,0到1,1,1的所有的Mx異或。即S4等於M8異或M9異或M10異或M11異或M12。這樣，對於壹串碼流，知道幾位校驗位，可以很快確定哪壹位出錯。而在發送端，可以根據S4,S3,S2,S1的表達式求出P4,P3,P2,P1的表達式，只要把式子右邊的P4或P3或P2或P1移到左邊替換掉S4或S3或S2或S1就可以了。面舉例說明：用^表示異或
D7,D6,D5,D4,D3,D2,D1,D0=11010001
S4=M8^M9^M10^M11^M12=D7^D6^D5^D4^P4; P4=D7^D6^D5^D4;
S3=M4^M5^M6^M7^M12 =D7^D3^D2^D1^P3; P3=D7^D3^D2^D1;
S2=M2^M3^M6^M7^M10^M11 =D6^D5^D3^D2^D0^P2; P2=D6^D5^D3^D2^D0;
S1=M1^M3^M5^M7^M9^M11=D6^D4^D3^D1^D0^P1; P1=D6^D4^D3^D1^D0;
所以，
P4=D7^D6^D5^D4=1^1^0^1=1
P3=D7^D3^D2^D1=1^0^0^0=1
P2= D6^D5^D3^D2^D0=1^0^0^0^1=0 P1=D6^D4^D3^D1^D0=1^1^0^0^1=1
故，傳送碼流為D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1等於
110110001101
若接收端收到110110001101，則
S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
S3=M4^M5^M6^M7^M12=1^0^0^0^1=0
S2=M2^M3^M6^M7^M10^M11=0^1^0^0^0^1=0
S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
故，接收碼流正確。
若M6出錯，由0變為1。則
S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
S3=M4^M5^M6^M7^M12=1^0^1^0^1=1
S2=M2^M3^M6^M7^M10^M11=0^1^1^0^0^1=1 S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
即S4S3S2S1=0110，此為十進制的6，說明第六位出錯，也就是M6出錯。完全符合。
5.海明碼的表格計算
如果對於m位的數據，增加k位冗余位，則組成位n=m+k位的糾錯碼。對於2^m個有效碼字中的每壹個，都有n個無效但可以糾錯的碼字。這些可糾錯的碼字與有效碼字的距離是1，含單個錯誤位。這樣，對於壹個有效的消息總***有n+1個可識別的碼字。這n+1個碼字相對於其他2^m-1個有效消息的距離都大於1。這意味著總***有2^m（n+1）個有效的或是可糾錯的碼字。顯然這個數應小於等於碼字的所有的可能的個數2^n。於是我們有
2^m（n+1）<2^n
因為n=m+k，我們得出
m+k+1<2^k
對於給定的數據位m，上式給出了k的下界，即要糾正單個錯誤，k必須取最小的值。海明建議了壹種方案，可以達到這個下界，並能直接指出錯在哪壹位。首先把碼字的位從1到n編號，，並把這個編號表示成二進制數，即2的冪之和。然後對2的每壹個冪設置壹個奇偶位。例如對於6號位，由於6=110（二進制），所以6號位參加第2位和第4位的奇偶校驗，而不參加第1位奇偶校驗。類似的9號位參加第1位和第8位的奇偶校驗而不參加第2位和第4位的奇偶校驗。海明把奇偶校驗分配在1,2,4,8等位置上，其他位置放數據。下面根據海明編碼的例圖，舉例說明編碼的方法
海明編碼的例
海明編碼的例
例如傳送的消息為：1001011
我們把數據放在3,5,6,7,9,10,11等位置上，1,2,4,8則為校驗位。
1
0 0 1
0 1 1
1 2 3 4 5 6 7 8 9 10 11
根據海明編碼的例，3、5、7、9、11的二進制編碼的第壹位為1，所以3、5、7、9、11號位參加第壹位校驗位，若按偶校驗計算，1號位應為1
1
1
0 0 1
0 1 1
1 2 3 4 5 6 7 8 9 10 11
類似的，3、6、7、10、11號位參加2號位校驗，5、6、7號位參加4號位校驗，9、10、11號位參加8號位校驗，全部按偶校驗計算，最終得到如下結果
1 0 1 1 0 0 1 0 0 1 1
1 2 3 4 5 6 7 8 9 10 11
如果這個碼字傳輸中有錯誤，比如說6號位出錯。就會變成
√ ╳ ╳ √
1 0 1 1 0 1 1 0 0 1 1
1 2 3 4 5 6 7 8 9 10 11
當接收端按照同樣的規則計算奇偶位時，就會發現1號位和8號位的奇偶性正確而2號位和4號位的奇偶性不對，於是2+4=6,，立即可以判斷錯在6號位。
上例中k=4，因而m<2^4-4-1=11,即數據位可以用到11位，***組成15位的碼字，可檢測出單個位置的錯誤。