漢明編碼

漢明碼是一種線性分組碼。線性分組碼是指將信息序列劃分為長度為k的序列段，在每一段後面附加r位的監督碼，且監督碼和信息碼之間構成線性關係，即它們之間可由線性方程組來聯繫。這樣構成的抗干擾碼稱為線性分組碼。

漢明碼、漢明碼計算、漢明碼解碼

設碼長為n，信息位長度為k，監督位長度為r=n-k。如果需要糾正一位出錯，因為長度為n的序列上每一位都可能出錯，一共有n種情況，另外還有不出錯的情況，所以我們必須用長度為r的監督碼錶示出n+1種情況。而長度為r的監督碼一共可以表示2^r種情況。因此

2^r >= n + 1， 即r >= log(n+1)

我們以一個例子來說明漢明碼。假設k=4，需要糾正一位錯誤，則

2^r >= n + 1 = k + r + 1 = 4 + r + 1

解得r >= 3。我們取r=3，則碼長為3+4=7。用a6,a5,...a0表示這7個碼元。用S1,S2,S3表示三個監關係式中的校正子。我們作如下規定（這個規定是任意的）：

S1 S2 S3 錯碼的位置

0 0 1 a0

0 1 0 a1

1 0 0 a2

0 1 1 a3

1 0 1 a4

1 1 0 a5

1 1 1 a6

0 0 0 無錯

按照表中的規定可知，僅當一個錯碼位置在a2,a4,a5或a6時校正子S1為1，否則S1為0。這就意味著a2,a4,a5,a6四個碼元構成偶校驗關係：

S1 = a6⊕a5⊕a4⊕a2 (1)式

同理，可以得到：

S2 = a6⊕a5⊕a3⊕a1 (2)式

S3 = a6⊕a4⊕a3⊕a0 (3)式

在傳送信號時，信息位a6,a5,a4,a3的值取決於輸入信號，是隨機的。監督為a2,a1,a0應該根據信息位的取值按照監督關係決定，即監督位的取值應該使上述(1)(2)(3)式中的S1,S2,S3為0，這表示初始情況下沒有錯碼。即

a6⊕a5⊕a4⊕a2 = 0

a6⊕a5⊕a3⊕a1 = 0

a6⊕a4⊕a3⊕a0 = 0

由上式進行移項運算，得到：

a2 = a6⊕a5⊕a4

a1 = a6⊕a5⊕a3

a0 = a6⊕a4⊕a3

已知信息位後，根據上式即可計算出a2,a1,a0三個監督位的值。

接收端受到每個碼組後，先按照(1)~(3)式計算出S1,S2,S3，然後查表可知錯碼情況。

例如，若接收到的碼字為0000011，按照(1)~(3)計算得到：

S1 = 0, S2 = 1, S3 = 1

查表可得在a3位有一個錯碼。

這種編碼方法的最小漢明距離為d=3，所以這種編碼可以糾正一個錯碼或者檢測兩個錯碼。

現以數據碼1101為例講講漢明碼的編碼原理，此時D8=1、D4=1、D2=0、D1=1，在P1編碼時，先將D8、D4、D2的二進制碼相加，結果為偶數2，漢明碼對奇數結果編碼為1，偶數結果為0，因此P1值為0，D8+D4+D1=3，為奇數，那么P2值為1，D8+D2+D1=2，為偶數，P3值為0。這樣，參照上文的位置表，漢明碼處理的結果就是1101-010。在這個4位數據碼的例子中，我們可以發現每個漢明碼都是以三個數據碼為基準進行編碼的。下面就是它們與前面的規定的對應表：

A6 A5 A4 A3 A2 A1 A0

D8 D4 D2 D1 P1 P2 P3

P1=D8^D4^D2

P2 =D8^D4^D1

P3 =D8^D2^D1

從編碼形式上，我們可以發現漢明碼是一個校驗很嚴謹的編碼方式。在這個例子中，通過對4個數據位的3個位的3次組合檢測來達到具體碼位的校驗與修正目的（不過只允許一個位出錯，兩個出錯就無法檢查出來了，這從下面的糾錯例子中就能體現出來）。在校驗時則把每個漢明碼與各自對應的數據位值相加，如果結果為偶數（糾錯代碼為0）就是正確，如果為奇數（糾錯代碼為1）則說明當前漢明碼所對應的三個數據位中有錯誤，此時再通過其他兩個漢明碼各自的運算來確定具體是哪個位出了問題。　還是剛才的1101的例子，正確的編碼應該是1101-010，如果第三個數據位D2在傳輸途中因干擾而變成了1，就成了1111-010。檢測時，P1+D8+D4+D2的結果是奇數3，第一位糾錯代碼為1。P2+D8+D4+D1的結果是偶數4，第二位糾錯代碼為0，P3+D8+D2+D1的結果是奇數3，第三但糾錯代碼代碼為1，有錯誤。那么具體是哪個位有錯誤呢？101查上面錯碼位置的表可得A4也就是D2位置出錯了。