汉明码

✍ dations ◷ 2025-10-14 03:48:54 #电信,错误检测与校正

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

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

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

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

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

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

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

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

汉明研究了包括五取二码在内的编码方案,并归纳了他们的想法。

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

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

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

表中只给出了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的次方的位置不填。

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

3.收集所有二进制数字,求异或。 0011 0101 1011 = 1101 {\displaystyle 0011\oplus 0101\oplus 1011=1101} ,,1,0,,1,1)。

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

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

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

相关

  • 淀粉酶淀粉酶(拼音:diàn-fěn méi;注音:ㄉㄧㄢˋ ㄈㄣˇ ㄇㄟˊ;法语, 德语, 英文:Amylase)是一种水解酶,是目前发酵工业上应用最广泛的一类酶。淀粉酶一般作用于可溶性淀粉、直链淀粉、
  • 溴化碘一溴化碘是一种卤素互化物,化学式为IBr。它是暗黑色晶体,有刺激性气味,可溶于水、乙醇、乙醚。它被用作碘化试剂。它可由溴单质与碘单质直接反应制备,需要将两者在稀有气体保护
  • 人殉殉葬又称陪葬,是指以器物、畜牲甚至活人陪同死者葬入墓穴,以保证死者亡魂的冥福。以活人陪葬,是古代丧葬常有的习俗。人殉并不同于人祭,并不具有人祭的宗教性质,且人殉中也会有自
  • 巨河狸属巨河狸(学名:),是啮齿目的巨型种,长达2.5米及估计重60-100公斤,有些估计甚至达220公斤。它们生存于更新世的北美洲,在1万年前最后一次的冰河时期末灭绝。巨河狸的灭绝可能是因更新
  • 行政院秘书长行政院秘书长,系行政院依《行政院组织法》规定设置之职位,由行政院院长任命,综理行政院幕僚事务。
  • 长春市 (中华人民共和国直辖市)长春直辖市,中华人民共和国已撤消的直辖市。1949年时,中国大陆共设有12个直辖市,分别为:南京、上海、武汉(今武汉三镇)、鞍山、抚顺、沈阳、本溪、西安、北平(今北京)、天津、重庆、
  • 仪亲王和硕仪亲王(满语:ᡥᠣᡧᠣᡳ ᠶᠣᠩᠰᠣ ᠴᡳᠨ ᠸᠠᠩ,穆麟德:),清朝世袭亲王。乾隆四十四年(1779年),乾隆帝第八子永璇封郡王(后进亲王),封号仪,死后谥号慎,未得世袭罔替,每次袭封需递
  • 黄少春黄少春(1831年-1911年),湖南宁乡人,字芍岩,晚清将领。少孤苦,为太平天国军队所虏为兵,后降清加入左宗棠湘军,善用大刀,年未三十即积战功任浙江提督。1864年六月,太平天国堵王黄文金护卫
  • 林大钦林大钦(1512年-1545年),字敬夫,号东莆(东峯?),小名大茂。广东潮州府海阳县东莆都(潮州潮安县金石镇)人,祖籍福建莆田,明代状元。幼时嗜学,师从叶蓁,12岁时喜读苏洵的《嘉佑集》。嘉靖十年(15
  • 张彦泽张彦泽(?-947年),突厥人,先后徙居阴山、太原,五代后晋时为镇国军节度使,为人残暴,以投降契丹,祸乱中原,为人所不耻,后因故被契丹主耶律德光处死。张彦泽据称骁悍残忍,眼睛呈现黄色并且会