汉明码

维基百科，自由的百科全书
（重定向自Hamming code）
跳转到导航 跳转到搜索

在电信领域中，汉明码（英语：hamming code），也称为海明码，是(7,4)汉明码（英语：Hamming(7,4)）推广得到的一种线性纠错码，由理查德·卫斯里·汉明于1950年发明。相比而言，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。汉明码是完备码（英语：perfect code），它在于它分组长度相同、最小距离为3的码中能达到最高的码率。[1]

用数学术语来说，汉明码是一种二元线性码。对于所有整数 r ≥ 2，存在一个分组长度 n = 2r − 1、k = 2r − r − 1 编码。因此汉明码的码率为 R = k / n = 1 − r / (2r − 1)，对于最小距离为3、分组长度为 2r − 1 的码来说是最高的。汉明码的奇偶检验矩阵的是通过列出所有长度为 r 的非零列向量构成的。

历史[编辑]

汉明码的发明者理查德·卫斯里·汉明在1948年，运用贝尔模型V（Bell Model V）电脑于贝尔实验室（Bell Labs）工作。输入端是依靠打孔卡（Punched Card），这不免会造成些读取错误。在工作日，当机器检测到错误将停止并闪灯（flash lights），使得操作员能够解决这个错误。在周末和下班期间，没有操作者的情况下，机器只会简单地转移到下一个工作。

汉明在周末工作，他对于不可靠的读卡器发生错误后，总是不得不重启程序变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码，并且时至今日仍在修正错误存储器上显示其应用价值。

汉明码之前[编辑]

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

奇偶[编辑]

主条目：奇偶校验位

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

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

五取二码[编辑]

五取二码使用由3个0和2个1组成的五个比特，以此提供十种可能的组合来表示数字 0-9。 该方案可以检测所有单比特错误、所有奇数字元错误和一些偶数字元错误（例如两个 “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

表中只给出了20个编码后的比特（5个奇偶校验比特，15个数据比特）。观察上表可发现一个比较直观的规律：第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位......

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

例子[编辑]

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

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

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

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

位置 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的次方的位置（低比特在左）。

位置 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
Graphical depiction of the 4 data bits and 3 parity bits and which parity bits apply to which data bits
主条目：(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>被称为奇偶检验矩阵。

编码[编辑]

示例

从上述矩阵我们有2k=24=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
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)汉明码[编辑]

相关条目[编辑]

参考文献[编辑]

  • Moon, Todd K. Error Correction Coding. New Jersey: John Wiley & Sons. 2005 [2009-06-18]. ISBN 978-0-471-64800-0. （原始内容存档于2008-04-06）. 
  • MacKay, David J.C. Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. 2003-09. ISBN 0-521-64298-1. （原始内容存档于2016-02-17）. 
  • D.K. Bhattacharryya, S. Nandi. An efficient class of SEC-DED-AUED codes. 1997 International Symposium on Parallel Architectures, Algorithms and Networks（ISPAN '97）: 410–415. doi:10.1109/ISPAN.1997.645128. 

外部链接[编辑]

  1. ^ See Lemma 12 of (PDF). [2016-09-01]. （原始内容存档 (PDF)于2021-04-17）. 
检索自“https://arolstar52-zhtest.hf.space/index.php?title=汉明码&oldid=458801”