本页使用了标题或全文手工转换

汉明码

维基百科,自由的百科全书
跳转至: 导航搜索

漢明碼(Hamming Code),是在電信領域的一種線性偵錯碼,以發明者理查德·卫斯里·汉明的名字命名。漢明碼在傳輸的訊息流中插入驗證碼,以偵測並更正單一位元錯誤。由於漢明編碼簡單,它們被廣泛應用於内存(RAM)。其SECDED(single error correction, double error detection)版本另外加入一檢測位元,可以偵測兩個或以下同時發生的位元錯誤,並能夠更正單一位元的錯誤。因此,當傳送端與接收端的位元樣式的漢明距離Hamming distance)小於或等於1時(僅有1 bit發生錯誤),可實現可靠的通信。相對的,簡單的奇偶檢驗碼除了不能糾正錯誤之外,也只能偵測出奇數個的錯誤。

在數學方面,漢明碼是一種二元線性碼。對於每一個整數m>2,存在一个编码,带有m个奇偶校验位2^m-m-1个数据位。該奇偶檢驗矩陣的漢明碼是通過列出所有米欄的長度是兩兩獨立。

歷史[编辑]

1940年,漢明於貝爾實驗室(Bell Labs)工作,運用貝爾模型V(Bell Model V)電腦,一個週期時間在幾秒鐘內的機電繼電器機器。輸入端是依靠打孔卡(Punched Card),這不免有些讀取錯誤。在平日,特殊代碼將發現錯誤並閃燈(flash lights),使得操作者能夠糾正這個錯誤。在週末和下班期間,在沒有操作者的情況下,機器只會簡單地轉移到下一個工作。

漢明在週末工作,他對於不可靠的讀卡機發生錯誤後,總是必須重新開始專案變得愈來愈沮喪。在接下来的幾年中,他为了解決偵錯的問題,開發了功能日益強大的偵錯演算法。在1950年,他發表了今日所稱的漢明碼。现在漢明碼有着广泛的应用。

漢明碼之前[编辑]

人們在漢明碼出现之前使用過多种检查错误的编码方式,但是没有一个可以在和漢明碼在相同空间消耗的情况下,得到相等的效果。

奇偶[编辑]

奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中,有奇数个发生了改变,那么这个错误将被检测出来(注意奇偶位本身也可能改变)。一般来说,如果数据中包含有奇数个1的话,则将奇偶位设定为1;反之,如果数据中有偶数个1的话,则将奇偶位设定为0。换句话说,原始数据和奇偶位组成的新数据中,将总共包含偶数个1.

奇偶校验并不總是有效,如果数据中有偶数个位发生变化,则奇偶位仍将是正确的,因此不能检测出错误。而且,即使奇偶校验检测出了错误,它也不能指出哪一位出现了错误,从而難以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中,成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳,但是由于他只需要一位额外的空间开销,因此这是开销最小的检测方式。并且,如果知道了发生错误的位,奇偶校验还可以恢复数据。

漢明碼[编辑]

如果一條信息中包含更多用于纠错的位,且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果,那麼我們就可以找出出錯位了。在一个7位的信息中,单个位出错有7种可能,因此3个错误控制位就足以確定是否出錯及哪一位出錯了。

漢明研究了包括五取二碼在内的编碼方案,並歸納了他們的想法。

通用算法[编辑]

下列通用算法可以为任意位数字产生一个可以纠错一位(英语Single Error Correcting)的漢明碼。

  1. 從1开始给數字的數據位(从左向右)标上序号, 1,2,3,4,5...
  2. 将这些数据位的位置序号转换为二进制,1, 10, 11, 100, 101,等。
  3. 数据位的位置序号中所有为二的幂次方的位(编号1,2,4,8,等,即数据位位置序号的二进制表示中只有一个1)是校验位
  4. 所有其它位置的数据位(数据位位置序号的二进制表示中至少2个是1)是数据位
  5. 每一位的数据包含在特定的两个或两个以上的校验位中,这些校验位取决于这些数据位的位置数值的二进制表示
    1. 校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据:1(校验位自身,这里都是二进制,下同),11,101,111,1001,等
    2. 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据:10(校验位自身),11,110,111,1010,1011,等
    3. 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据:100(校验位自身),101,110,111,1100,1101,1110,1111,等
    4. 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据:1000(校验位自身),1001,1010,1011,1100,1101,1110,1111,等
    5. 简而言之,所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些,但在实践中并没有区别。

校验位一般的规律可以如下表示:

数据位位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
编码后数据位置 p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7 d8 d9 d10 d11 p16 d12 d13 d14 d15
奇偶校驗位
覆蓋率
p1 X X X X X X X X X X
p2 X X X X X X X X X X
p4 X X X X X X X X X
p8 X X X X X X X X
p16 X X X X X

观察上表可发现一个比较直观的规律:第i个检验位是第2i-1位,从该位开始,检验2i-1位,跳过2i-1位……依次类推。例如上表中第3个检验位p4从第23-1=4位开始,检验4、5、6、7共4位,然后跳过8、9、10、11共4位,再检验12、13、14、15共4位……

例子[编辑]

对11000010进行汉明编码,求编码后的码字。

1.列出表格,从左往右(或从右往左)填入数字,但2的次方的位置不填。

位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0

2.把数据行有1的列的位置写为二进制。

位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0
二进制 0011 0101 1011

3.收集所有二进制数字,求异或0011 \oplus 0101 \oplus 1011 =1101

4.把1101依次填入表格中2的次方的位置(低位在左)。

位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0
二进制 0011 0101 1011
校验 1 0 1 1

5.所以编码后的码字是101110010010。

带附加奇偶校验码的汉明码(SECDED)[编辑]

漢明(7,4)碼[编辑]

Graphical depiction of the 4 data bits and 3 parity bits and which parity bits apply to which data bits

1950年,漢明介紹了(7,4)代碼。其編碼由4資料位元到7位,增加三個奇偶校驗碼。漢明(7,4)可以檢測並糾正單位元錯誤,且也能檢測雙位元錯誤。

建立奇偶檢驗矩陣[编辑]

矩陣\mathbf{G} := \begin{pmatrix}
I_k | -A^T \\
\end{pmatrix}被稱為(標準)生成矩陣線性(n,k)碼。

\mathbf{H} := \begin{pmatrix}
A | I_{n-k} \\
\end{pmatrix}被稱為奇偶檢驗矩陣

編碼[编辑]

範例

从上述矩阵我们有2k=24=16码词。

二进制码 \overrightarrow{x}的码词可以从\overrightarrow{x}=\overrightarrow{a}G 得到。对\overrightarrow{a}=a_1a_2a_3a_4  a_i 存在 F_2 (一个只有0和1的二元域)。

故此码表即是所有4个三元组(k个三元组)。

因而,(1,0,1,1)编码为(0,1,1,0,0,1,1)。

漢明(8,4)碼[编辑]

The same (7,4) example from above with an extra parity bit

汉明(7,4)码可以很容易地编码为一个(8,4)码,通过在(7,4)编码词(参见汉明(7,4)码)上附加一个额外的奇偶位。

这可以用下面修正的矩阵相加:

\mathbf{G} := \begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 0 & 0 & 1 & 0
\end{pmatrix}_{8,4}


\mathbf{H} :=
\begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{pmatrix}_{4,8}

注意,\mathbf{H}并非用标准形式表示。为了得到\mathbf{G},原子行操作能够被用来获得一个等价的矩阵对陈形式的\mathbf{H}


\mathbf{H} =
\left(\left.\begin{array}{cccc}
0 & 1 & 1 & 1\\
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
1 & 1 & 1 & 0\end{array}\right|\begin{array}{cccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\end{array}\right)_{4,8}

漢明(11,7)碼[编辑]

相關條目[编辑]

參考文獻[编辑]

外部連結[编辑]

汉明码