电机工程

首页 > 电机工程

汉明码

2018-08-21 09:50:56     所属分类:电信

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

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

目录

  • 1 历史
    • 1.1 汉明码之前
      • 1.1.1 奇偶
  • 2 汉明码
    • 2.1 通用算法
    • 2.2 例子
  • 3 带附加奇偶校验码的汉明码(SECDED)
  • 4 (7,4)汉明码
  • 5 建立奇偶检验矩阵
  • 6 编码
  • 7 (8,4)汉明码
  • 8 (11,7)汉明码
  • 9 相关条目
  • 10 参考文献
  • 11 外部链接

历史

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.收集所有二进制数字,求异或。

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)汉明码可以检测并纠正单比特差错,且也能检测双比特差错。

建立奇偶检验矩阵

矩阵被称为(标准)生成矩阵线性(n,k)码。

被称为奇偶检验矩阵。

编码

范例

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

二进制码的码词可以从得到。对存在(一个只有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)汉明码)上附加一个额外的奇偶位。

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

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

(11,7)汉明码

相关条目

  • 格雷码
  • 汉明距离
  • 前向纠错
  • 里德-所罗门码

参考文献

  • Moon, Todd K. Error Correction Coding. New Jersey: John Wiley & Sons. 2005. ISBN 978-0-471-64800-0. 
  • 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. 

外部链接

  • CGI script for calculating Hamming distances(from R. Tervo, UNB, Canada)
  • ^ See Lemma 12 of
  • 感谢您的支持,我会继续努力的!

    扫码支持
    1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

    愿你每天温暖如春!!!

    显示全文

    取消

    感谢您的支持,我会继续努力的!

    扫码支持
    无需打赏可直接关闭阅读全文
    1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

    愿你每天温暖如春!!!


    上一篇:节点B
    相关推荐