查看“︁汉明码”︁的源代码

{{original research|time=2019-11-12T02:13:02+00:00}}
{{More footnotes|time=2019-11-12T02:13:02+00:00}}
{{noteTA
|G2=Communication
}}
在[[電信]]領域中，'''漢明碼'''（{{lang-en|'''hamming code'''}}），也称为'''海明码'''，是{{le|(7,4)汉明码|Hamming(7,4)}}推广得到的一種线性纠错码，由[[理查德·衛斯里·漢明]]于1950年發明。相比而言，簡單的[[奇偶檢驗碼]]除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。汉明码是{{le|完备码|perfect code}}，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。<ref>{{Cite web |url=http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf |title=See Lemma 12 of |access-date=2016-09-01 |archive-date=2021-04-17 |archive-url=https://web.archive.org/web/20210417092043/http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf |dead-url=no }}</ref>

用數學术语来说，漢明碼是一種二元線性碼。對於所有整數 {{Math|''r'' ≥ 2}}，存在一个分组长度 {{Math|''n'' {{=}} 2<sup>''r''</sup> − 1}}、{{Math|''k'' {{=}} 2<sup>''r''</sup> − ''r'' − 1}} 编码。因此汉明码的码率为 {{Math|''R'' {{=}} ''k'' / ''n'' {{=}} 1 − ''r'' / (2<sup>''r''</sup> − 1)}}，对于最小距离为3、分组长度为 {{Math|2<sup>''r''</sup> − 1}} 的码来说是最高的。漢明碼的[[奇偶檢驗矩陣]]的是通過列出所有长度为 {{Math|''r''}} 的非零列向量构成的。

== 歷史 ==
漢明碼的發明者[[理查德·衛斯里·漢明]]在1948年，運用[[貝爾模型V]]（Bell Model V）電腦於[[貝爾實驗室]]（Bell Labs）工作。輸入端是依靠[[打孔卡]]（Punched Card），這不免會造成些讀取錯誤。在工作日，當機器檢測到錯誤將停止並閃燈（flash lights），使得操作員能夠解決這個錯誤。在週末和下班期間，沒有操作者的情況下，機器只會簡單地轉移到下一個工作。

漢明在週末工作，他對於不可靠的[[讀卡機]]發生錯誤後，總是不得不重新啟動程序變得愈來愈沮喪。在接下来的幾年中，他为了解決偵錯的問題，開發了功能日益強大的偵錯[[演算法]]。在1950年，他發表了今日所稱的'''漢明碼'''，並且時至今日仍在[[纠错内存|修正錯誤記憶體]]上顯示其應用價值。

=== 漢明碼之前 ===
人們在漢明碼出現之前使用過多種檢查错誤的編碼方式，但是沒有一個可以在和漢明碼在相同空間消耗的情况下，得到相等的效果。

==== 奇偶 ====
{{main|奇偶校驗位}}

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

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

==== 五取二代碼 ====
五取二代碼使用由3個0和2個1組成的五個位，以此提供十種可能的組合來表示數字 0-9。 該方案可以檢測所有單比特錯誤、所有奇數位錯誤和一些偶數位錯誤（例如兩個 「1」位的翻轉）。 但是它無法自行糾正這些錯誤。

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

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

===通用算法===
下列通用算法可以为任意位数字产生一个可以纠错一位（{{lang-en|'''S'''ingle '''E'''rror '''C'''orrecting}}）的漢明碼。
# 從1开始给數字的數據位（从左向右）标上序号, 1，2，3，4，5...
# 将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。
# 数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的二进制表示中只有一个1）是校验位
# 所有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是新的数据位
# 每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决于这些数据位的位置数值的二进制表示
## 校验位1覆盖了所有数据位位置序號的二進制表示倒数第一位是1的数据：1（校验位自身，这里都是二进制，下同），11，101，111，1001，等
## 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据：10（校验位自身），11，110，111，1010，1011，等
## 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据：100（校验位自身），101，110，111，1100，1101，1110，1111，等
## 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据：1000（校验位自身），1001，1010，1011，1100，1101，1110，1111，等
## 简而言之，所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。

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

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

:{| class="wikitable" style="text-align:center;"
|-
!colspan="2"| 数据位位置
! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 !! 17 !! 18 !! 19 !! 20
|rowspan="7"| ...
|-
!colspan="2"| 编码后数据位置
!style="background-color: #90FF90;"| p1
!style="background-color: #90FF90;"| p2 !! d1
!style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4
!style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11
!style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15
|-
!rowspan="5"|奇偶校驗位<br />覆蓋率
!style="background-color: #90FF90;"| p1
| X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X || 
|-
!style="background-color: #90FF90;"| p2
|   || X || X ||   ||   || X || X ||   ||   || X || X ||   ||   || X || X ||   ||   || X || X || 
|-
!style="background-color: #90FF90;"| p4
|   ||   ||   || X || X || X || X ||   ||   ||   ||   || X || X || X || X ||   ||   ||   ||   || X
|-
!style="background-color: #90FF90;"| p8
|   ||   ||   ||   ||   ||   ||   || X || X || X || X || X || X || X || X ||   ||   ||   ||   || 
|-
!style="background-color: #90FF90;"| p16
|   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   || X || X || X || X || X
|}

表中只给出了20个编码后的位（5个奇偶校验位，15个数据位）。观察上表可发现一个比较直观的规律：第i个检验位是第2<sup>i-1</sup>位，从该位开始，检验2<sup>i-1</sup>位，跳过2<sup>i-1</sup>位……依次类推。例如上表中第3个检验位p4从第2<sup>3-1</sup>=4位开始，检验4、5、6、7共4位，然后跳过8、9、10、11共4位，再检验12、13、14、15共4位……

要检查某一位的错误，则需检查某一位所包含的所有奇偶校验位。这种错误的模式被叫做[[译码方法#校正子译码|伴随式错误]]。如果所有奇偶校验位是正确的，就没有错误。除此以外的情况，错误的奇偶校验位的位置的和将识别错误的位。例如，如果位置为1、2、8的奇偶校验位指示了一个错误，那么位置为1+2+8=11的位出错了。如果只有一个奇偶校验位指示了错误，那么该奇偶校验位自身出错了。

=== 例子 ===
对11000010进行汉明编码，求编码后的码字。

1.列出表格，从左往右（或从右往左）填入数字，但2的次方的位置不填。
{| class="wikitable"
|-
| 位置|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12 
|-
| 数据||  ||  || 1||  || 1|| 0|| 0||  || 0|| 0 || 1 || 0    
|}

2.把'''数据'''行有1的列的'''位置'''写为二进制。
{| class="wikitable"
|-
| 位置|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12 
|-
| 数据||  ||  || 1||  || 1|| 0|| 0||  || 0|| 0 || 1 || 0     
|-
| 二进制|| || ||0011 || ||0101|| || || || ||   ||1011||     
|}

3.收集所有二进制数字，求[[异或]]。<math>0011 \oplus 0101 \oplus 1011 =1101</math>

4.把1101依次填入表格中2的次方的位置（低位在左）。
{| class="wikitable"
|-
| 位置|| 1|| 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9|| 10|| 11|| 12  
|-
| 数据||  ||  || 1||  || 1|| 0|| 0||  || 0|| 0 || 1 || 0     
|-
| 二进制|| || ||0011 || ||0101|| || || || ||   ||1011||     
|-
|校验||1  || 0||  || 1||  ||  ||  || 1||  ||  ||    ||      
|}

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

==带附加奇偶校验码的汉明码（SECDED）==
加一個位元在數列的最前面，採用奇校验码或偶校验码， 用以檢驗後面的汉明码是否有錯。

==(7,4)漢明碼==
[[File:Hamming(7,4).svg|thumb|300px|Graphical depiction of the 4 data bits and 3 parity bits and which parity bits apply to which data bits]]

{{main|(7,4)漢明碼}}

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

== 建立奇偶檢驗矩陣 ==

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

和<math>\mathbf{H} := \begin{pmatrix}
A | I_{n-k} \\
\end{pmatrix}</math>被稱為[[奇偶檢驗矩陣]]。

== 編碼 ==

範例

从上述矩阵我们有2<sup>k</sup>=2<sup>4</sup>=16码词。

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

故此码表即是所有4个三元组（k个三元组）。

因而，（1,0,1,1）编码为（''0'',''1'',1,0,''0'',1,1）。

==(8,4)漢明碼==

[[File:Hamming(8,4).svg|thumb|300px|The same (7,4) example from above with an extra parity bit]]

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

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

:<math>\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}</math>

和

:<math>
\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}
</math>。

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

:<math>
\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}
</math>。

==(11,7)漢明碼==

==相關條目==
* [[格雷碼]]
* [[漢明距離]]
* [[前向錯誤更正]]
* [[里德-所罗门码]]

== 參考文獻 ==
* {{cite book
  |last=Moon
  |first=Todd K.
  |coauthors=
  |title=Error Correction Coding
  |publisher=[[John Wiley & Sons]]
  |year=2005
  |location=[[New Jersey]]
  |url=http://www.neng.usu.edu/ece/faculty/tmoon/eccbook/book.html
  |isbn=978-0-471-64800-0
  |access-date=2009-06-18
  |archive-date=2008-04-06
  |archive-url=https://web.archive.org/web/20080406042820/http://www.neng.usu.edu/ece/faculty/tmoon/eccbook/book.html
  |dead-url=no
  }}
* {{cite book
 |last=MacKay 
 |first=David J.C. 
 |authorlink=David MacKay (scientist) 
 |coauthors= 
 |title=Information Theory, Inference and Learning Algorithms 
 |publisher=[[Cambridge University Press]] 
 |date=2003-09 
 |location=[[Cambridge]] 
 |url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html 
 |isbn=0-521-64298-1 
 |deadurl=yes 
 |archiveurl=https://web.archive.org/web/20160217105359/http://www.inference.phy.cam.ac.uk/mackay/itila/book.html 
 |archivedate=2016-02-17 
}}
* {{cite conference
  |author=D.K. Bhattacharryya, S. Nandi
  |title=An efficient class of SEC-DED-AUED codes
  |pages=410–415
  |booktitle=1997 International Symposium on Parallel Architectures, Algorithms and Networks（ISPAN '97）
  |doi=10.1109/ISPAN.1997.645128

}}

== 外部連結 ==
* [http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl CGI script for calculating Hamming distances（from R. Tervo, UNB, Canada）] {{Wayback|url=http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl |date=20200801121256 }}

[[Category:美国发明]]
[[Category:编码理论]]
[[Category:错误检测与校正]]
[[Category:計算機算術]]