漢明編碼

漢明碼

漢明碼是一種線性分組碼。線性分組碼是指將信息序列劃分為長度為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，所以這種編碼可以糾正一個錯碼或者檢測兩個錯碼。