通信工程 / 系统课时

验证汉明码(7,4)的纠错效果

验证汉明码(7,4)的纠错效果

把 4 位消息编码成 7 位码字,再人为翻转接收比特,使用综合症定位和纠正错误。通过 Python 遍历全部信息组合与错误位置,可以验证汉明码的单错纠正能力,并观察双错为何可能被误纠,从而明确这种译码方法的适用边界。

学习目标

  • 实现汉明码(7,4)的偶校验编码、综合症计算和单错纠正。
  • 使用具体码字验证单比特错误的定位与恢复过程。
  • 穷举单错和双错组合,解释双错误纠原因及 SECDED 改进方案。

确定码字位序与偶校验规则

汉明码(7,4)将 4 位信息映射成 7 位码字,其中 3 位是校验位,码率为 R=4/7≈0.571R=4/7\approx0.571。本例采用从左到右编号 1~7 的约定,校验位位于第 1、2、4 位,信息位依次放入第 3、5、6、7 位。

采用偶校验规则:每组参与校验的比特进行异或运算,结果必须为 0。三个校验位分别覆盖以下位置:

  • 校验位 p1p_1:位置 1、3、5、7。
  • 校验位 p2p_2:位置 2、3、6、7。
  • 校验位 p4p_4:位置 4、5、6、7。

例如,输入信息位 1011,依次放入第 3、5、6、7 位,计算得到 p1=0p_1=0、p2=1p_2=1、p4=0p_4=0,最终码字为 0110011。对上述三组比特重新计算异或,结果全部为 0,说明生成的码字满足校验约束。

这三个校验关系对应一个具有 3 行、7 列的校验矩阵。第 1~7 列分别是各位置编号的三位二进制表示,按 s4,s2,s1s_4,s_2,s_1 的顺序排列,因此每个单比特错误都会产生独一无二的非零综合症。

根据综合症定位并纠正错误

接收码字记为 r1,r2,…,r7r_1,r_2,\ldots,r_7。接收端无需知道原始信息,只需要重新计算三组奇偶校验:

  • s1=r1⊕r3⊕r5⊕r7s_1=r_1\oplus r_3\oplus r_5\oplus r_7
  • s2=r2⊕r3⊕r6⊕r7s_2=r_2\oplus r_3\oplus r_6\oplus r_7
  • s4=r4⊕r5⊕r6⊕r7s_4=r_4\oplus r_5\oplus r_6\oplus r_7

将三个校验结果合成整数综合症 S=s1+2s2+4s4S=s_1+2s_2+4s_4。当 S=0S=0 时,不执行纠错;当 SS 为 1~7 时,在最多发生一个比特错误的前提下,直接翻转码字的第 SS 位。

例如,把码字 0110011 的第 6 位翻转,得到 0110001。此时 s1=0s_1=0、s2=1s_2=1、s4=1s_4=1,所以 S=6S=6。接收端翻转第 6 位后恢复原码字,再读取第 3、5、6、7 位,得到信息 1011。

汉明码(7,4)的综合症定位、单错纠正与双错误纠示意图

这里最重要的前提是最多只有一位出错。非零综合症只说明校验未通过,并不能保证接收序列中恰好存在一个错误。如果存在两位错误,它们的综合症也可能对应某个合法的单错位置。

使用 Python 穷举验证纠错效果

下面使用 Python 3.8 或更新版本的标准库,实现编码、综合症译码和错误注入。代码先展示一个具体消息的无错、单错、双错结果,再穷举所有 16 种四位信息、7 个单错位置及 21 组双错位置。

将代码保存为 hamming74.py,执行 python hamming74.py。不需要安装第三方依赖。

python
from itertools import combinations, product

DATA = (3, 5, 6, 7)
CHECK = (1, 2, 4)


def encode(data):
    # 使用1起始的下标,与码字位置编号保持一致
    word = [0] * 8
    for pos, bit in zip(DATA, data):
        word[pos] = bit

    # 计算校验位,使对应校验组的异或结果为0
    for mask in CHECK:
        for pos in range(1, 8):
            if pos != mask and pos & mask:
                word[mask] ^= word[pos]
    return word[1:]


def syndrome(word):
    s = 0
    for mask in CHECK:
        check = 0
        for pos in range(1, 8):
            if pos & mask:
                check ^= word[pos - 1]
        if check:
            s |= mask
    return s


def decode(received):
    corrected = received.copy()
    position = syndrome(corrected)
    # 仅在最多单错的假设下,综合症才是可靠的错误位置
    if position:
        corrected[position - 1] ^= 1
    return tuple(corrected[p - 1] for p in DATA), position


def corrupt(word, positions):
    output = word.copy()
    for pos in positions:
        output[pos - 1] ^= 1
    return output


data = (1, 0, 1, 1)
code = encode(data)
print('编码码字:', ''.join(map(str, code)))

for label, positions in [
    ('无错', ()),
    ('单错(第6位)', (6,)),
    ('双错(第3、5位)', (3, 5)),
]:
    restored, s = decode(corrupt(code, positions))
    decoded_str = ''.join(map(str, restored))
    print(f'{label}: S={s}, 信息位={decoded_str}, 正确={restored == data}')

# 穷举所有消息及单错、双错位置组合
single_ok = double_wrong = 0
for message in product((0, 1), repeat=4):
    word = encode(message)
    assert syndrome(word) == 0

    for pos in range(1, 8):
        restored, _ = decode(corrupt(word, (pos,)))
        single_ok += restored == message

    for pair in combinations(range(1, 8), 2):
        restored, _ = decode(corrupt(word, pair))
        double_wrong += restored != message

print(f'单错正确: {single_ok}/112')
print(f'双错误纠: {double_wrong}/336')

预期输出:

text
编码码字: 0110011
无错: S=0, 信息位=1011, 正确=True
单错(第6位): S=6, 信息位=1011, 正确=True
双错(第3、5位): S=6, 信息位=0101, 正确=False
单错正确: 112/112
双错误纠: 336/336

这里的枚举数量可以直接核对:单错样本数为 16×7=11216\times7=112;双错样本数为 16×(72)=33616\times\binom{7}{2}=336。每种信息都经过相同的编码、错误注入和译码流程,避免只测试一条消息而误判算法能力。

结果显示,112 组单错全部正确恢复;336 组双错在当前纠错策略下全部得到错误信息。后一个数字不是随机信道中的误码率,而是在恰好翻转两个比特的测试条件下,这个单错译码器发生误纠的次数。

理解双错局限与改进方法

汉明码(7,4)的最小码距为 3,因此可以保证纠正一个比特错误;如果只做错误检测而不尝试纠正,最多可以保证检测两个比特错误。但是使用综合症直接定位并翻转时,双错会被当成某个单错,无法可靠地区分。

以第 3、5 位同时出错为例,两次错误对应的综合症分别是 3 和 5,组合后的综合症为 3⊕5=63\oplus5=6。译码器会错误翻转第 6 位,造成总共三个位置与原码字不同。即使再次检查综合症得到 0,也无法证明恢复的信息正确。

一种常用改进是增加一个覆盖全部 7 位码字的总体偶校验位,形成扩展汉明码(8,4),也称 SECDED(单错纠正、双错检测)。在假设最多两位错误时,可联合判断原有综合症和整体奇偶校验:

原综合症 总体奇偶校验 处理方式
S=0S=0 偶数 判定无错
S≠0S\ne0 奇数 纠正前7位中的第S位
S=0S=0 奇数 纠正新增的总体校验位
S≠0S\ne0 偶数 判定双错,报告不可纠正

可以进一步修改 corrupt() 的错误位置组合,验证不同双错产生的综合症。对于标准汉明码(7,4),关键验收结论是:7 个单错位置都能被正确纠正,而双错不能交给同一个单错纠正规则安全处理;如果业务要求双错可检测,需要增加总体校验位或选择纠错能力更强的编码方案。

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

目录与阅读设置

阅读设置

17

记录一个想法

验证汉明码(7,4)的纠错效果

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

登录哪都通