通信工程 / 系统课时

汉明码

汉明码

汉明码通过精心安排监督矩阵的列,使每一个单比特错误都产生唯一伴随式,从而在较少冗余下完成错误定位。本节以经典 (7,4)(7,4) 汉明码完成编码和单比特纠错,并进一步说明为什么可靠的双比特检测需要增加总体奇偶校验位。

学习目标

  • 能按汉明码的校验位位置完成 (7,4)(7,4) 编码。
  • 能根据伴随式定位并纠正一个出错比特。
  • 能利用扩展汉明码区分单比特错误和双比特错误。

汉明码如何安排校验关系

经典 (7,4)(7,4) 汉明码包含 4 个信息位和 3 个校验位,最小码距为 3,因此能够纠正一个比特错误。常用编号方式把位置 1、2、4 留给校验位,其余位置 3、5、6、7 放置信息位。

监督矩阵可以取为:

H=[[1,0,1,0,1,0,1],[0,1,1,0,0,1,1],[0,0,0,1,1,1,1]]H=[[1,0,1,0,1,0,1],[0,1,1,0,0,1,1],[0,0,0,1,1,1,1]]。

矩阵第 jj 列就是位置 jj 的二进制编号,其中第一行对应最低位。七个非零三比特列恰好对应位置 1 到 7,所以任意单比特错误都会产生不同的三比特伴随式。

完成一次七位编码

设四个信息位依次为 d1,d2,d3,d4d_1,d_2,d_3,d_4,分别放在位置 3、5、6、7。三个偶校验位的计算式为:

p1=d1⊕d2⊕d4p_1=d_1\oplus d_2\oplus d_4

p2=d1⊕d3⊕d4p_2=d_1\oplus d_3\oplus d_4

p4=d2⊕d3⊕d4p_4=d_2\oplus d_3\oplus d_4

例如信息字为 10111011,即 d1=1,d2=0,d3=1,d4=1d_1=1,d_2=0,d_3=1,d_4=1。由此得到 p1=0p_1=0、p2=1p_2=1、p4=0p_4=0,最终七位码字按照位置 1 到 7 排列为 01100110110011。

可以分别检查位置集合 1、3、5、7,位置集合 2、3、6、7,以及位置集合 4、5、6、7;三个集合中的 1 都应为偶数,这与条件 cHT=0cH^T=0 完全一致。

用伴随式定位单比特错误

假设发送码字 01100110110011 的第 5 位发生翻转,接收字变为 01101110110111。接收端计算 s=rHTs=rH^T,得到伴随式 [1,0,1]T[1,0,1]^T。

按照最低位在前的约定,[1,0,1][1,0,1] 对应二进制位置 101101,也就是十进制 5。接收端因此判断第 5 位出错,将该位再次翻转后恢复为原码字 01100110110011。

汉明码伴随式定位与扩展双错检测流程

为什么普通汉明码不能可靠区分双错

(7,4)(7,4) 汉明码的最小码距为 3,理论上可以检测最多两个比特错误,但它只能纠正一个比特。关键限制在于:两个错误列异或后的结果可能恰好等于另一列,因此双比特错误产生的非零伴随式可能看起来像某个单比特错误。

如果接收端看到非零伴随式后无条件执行单比特纠正,就可能把双比特错误误改成另一个错误码字。因此“能够检测到双错”不等于“能够在纠错流程中可靠地区分双错和单错”。工程中常用扩展汉明码解决这一问题。

增加总体奇偶位实现 SECDED

扩展汉明码在原来的 7 位之外再增加一个总体奇偶校验位,使全部 8 位具有偶校验。接收端同时观察三比特伴随式 ss 和八位总体奇偶检查结果,就能形成 SECDED,即单错纠正、双错检测。

伴随式 总体奇偶检查 判断 处理
s=0s=0 正确 无错误 直接接收
s≠0s\neq0 错误 前 7 位单比特错误 按伴随式纠正
s=0s=0 错误 总体校验位错误 翻转总体校验位
s≠0s\neq0 正确 双比特错误 报错,不执行纠正

这一判定之所以成立,是因为单比特翻转会改变总体奇偶性,而两个比特同时翻转不会改变总体奇偶性。伴随式负责回答“前七位校验约束是否被破坏以及指向哪里”,总体奇偶位负责回答“错误比特数量的奇偶性是否变化”。

解题时保持同一套位序约定

汉明码题目最容易出错的地方不是异或运算,而是监督矩阵列顺序、伴随式位序和码字位置编号没有保持一致。有的教材把最高有效位写在综合的左侧,有的把最低有效位写在左侧,两种表示都可以使用,但不能混用。

计算时先明确校验位位于哪些位置,再写出对应监督矩阵或校验集合;编码后先验证三个校验式全部为 0,接收后再计算伴随式。需要同时完成单错纠正和可靠双错检测时,应明确使用带总体奇偶位的扩展汉明码,而不是把普通 (7,4)(7,4) 汉明码直接当作 SECDED 使用。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

汉明码

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通