通信工程 / 系统课时

用汉明码纠正单比特错误

用汉明码纠正单比特错误

本课用偶校验汉明(7,4)码,把4位信息1011编码成7位码字,故意翻转其中一位,再借助伴随式确定出错位置并恢复原文。随后制造两位错误,观察普通单错纠正器为何可能误修;示例可用Python 3.10及以上版本运行。

学习目标

  • 把4位数据放进汉明(7,4)码的正确位置,并求出3个校验位。
  • 从接收码字计算伴随式,定位并修正一个翻转位。
  • 复现双比特错误时的误纠正,说明纠错能力边界。

把信息位与校验位排进七个位置

汉明(7,4)码包含4个信息位和3个校验位,码字位置从1编号到7。位置1、2、4用于校验,位置3、5、6、7依次存放信息位1、0、1、1。全部使用偶校验,即每组中1的数量必须为偶数。

  • P1覆盖位置1、3、5、7,求得0。
  • P2覆盖位置2、3、6、7,求得1。
  • P4覆盖位置4、5、6、7,求得0。

所以从位置1到7的编码结果为0110011。每个位置的二进制编号决定它参加哪些校验组:例如位置6是二进制110,同时被P2与P4覆盖,不被P1覆盖。

汉明七四码校验覆盖关系与第六位错误定位

用伴随式找到翻转位置

假设传输时第6位从1变成0,收到0110001。重新计算三组偶校验的结果分别为:s1=0、s2=1、s4=1。把它们按(s4,s2,s1)的顺序拼成110,作为二进制数就是十进制6。

因此翻转接收码字的第6位,可以恢复0110011;提取位置3、5、6、7便得到原信息1011。这里不能把伴随式的三位从左往右当作位置1、2、4:它们对应的是权重4、2、1。伴随式为000只表示三个校验式均通过,不保证没有多位错误。

用Python执行编码与纠正

下面的代码用长度8的列表让下标直接等于码字位置,索引0不参加编码。syndrome把未通过校验的权重相加,得到单错译码器认定的位置。

python
GROUPS = {
    1: (1, 3, 5, 7),
    2: (2, 3, 6, 7),
    4: (4, 5, 6, 7),
}

def encode(data: str) -> list[int]:
    if len(data) != 4 or any(bit not in "01" for bit in data):
        raise ValueError("need exactly four binary digits")
    code = [0] * 8
    for position, bit in zip((3, 5, 6, 7), map(int, data)):
        code[position] = bit
    # 偶校验:覆盖位置的异或结果必须为0
    for parity_position, covered in GROUPS.items():
        code[parity_position] = sum(code[i] for i in covered) % 2
    return code

def syndrome(code: list[int]) -> int:
    return sum(parity_position for parity_position, covered in GROUPS.items()
               if sum(code[i] for i in covered) % 2)

def correct_one(code: list[int]) -> tuple[list[int], int]:
    restored = code.copy()
    position = syndrome(restored)
    if position:
        restored[position] ^= 1
    return restored, position

def bits(code: list[int]) -> str:
    return "".join(map(str, code[1:]))

original = encode("1011")
single = original.copy()
single[6] ^= 1
fixed, single_position = correct_one(single)

double = original.copy()
for position in (3, 6):
    double[position] ^= 1
wrong, double_position = correct_one(double)

print("data:", "1011")
print("codeword:", bits(original))
print("single:", bits(single), "syndrome:", f"{syndrome(single):03b}",
      "position:", single_position, "corrected:", bits(fixed))
print("double:", bits(double), "syndrome:", f"{syndrome(double):03b}",
      "position:", double_position, "decoded:", bits(wrong),
      "matches original:", wrong == original)

预期输出:

text
data: 1011
codeword: 0110011
single: 0110001 syndrome: 110 position: 6 corrected: 0110011
double: 0100001 syndrome: 101 position: 5 decoded: 0100101 matches original: False

双比特错误的边界

汉明(7,4)码的最小码距为3,因此能保证纠正任意一个比特错误。但如果同时翻转位置3和6,伴随式变为101,单错译码器会误认为第5位出错,再翻转一次,结果反而与原码字不同。

普通汉明(7,4)码仅靠伴随式不能区分“一位错误”和“两位错误”。若系统必须区分这两种情况,可增加一位全局偶校验,改用扩展汉明(8,4)的SECDED(单错纠正、双错检出)方案。它可以报告双错,但不能保证修复双错;发生该类错误时应丢弃数据块或请求重传。

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

目录与阅读设置

阅读设置

17

记录一个想法

用汉明码纠正单比特错误

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

登录哪都通