通信工程 / 系统课时

从汉明距离推导纠错能力

从汉明距离推导纠错能力

发送端增加校验位后,究竟能发现多少位错误、又能恢复多少位错误?本篇以汉明(7,4)码为例,从码字间的比特差异推导两种能力的保证边界,再用 Python 穷举验证一位和两位翻转的结果。

学习目标

  • 计算码字间的汉明距离与码的最小距离。
  • 根据最小距离推导保证检错和保证纠错的位数。
  • 识别“两位错误可检出”与“两位错误可纠正”的区别,并运行验证。

码字的最小距离如何确定

汉明距离是两个等长比特串在多少个位置上不同。例如,合法码字 A=0000000、B=1000110 在第 1、5、6 位不同,所以 dH(A,B)=3d_H(A,B)=3。汉明距离只统计位置,不关心这些位置相隔多远。

一组合法码字构成码本 CC,其最小距离是任意两个不同码字之间的最小汉明距离:

dmin⁡=min⁡x≠y, x,y∈CdH(x,y)d_{\min}=\min_{x\ne y,\ x,y\in C}d_H(x,y)

仅知道 A、B 相距 3,还不能断言整个码的最小距离为 3;必须检查所有码字对。对于线性分组码,也可以求所有非零合法码字的最小汉明重量,结果相同。后面的程序会对含 16 个码字的汉明(7,4)码完成穷举。

最小距离给出什么保证

若任意两合法码字至少相差 dmin⁡d_{\min} 位,那么翻转少于 dmin⁡d_{\min} 位不可能恰好变成另一个合法码字。因此,保证检错上限为 dmin⁡−1d_{\min}-1 位;这里的“检出”指接收字不属于码本,接收端能报告异常,但未必知道原码字。

纠错要求接收字离真实码字足够近,且不能同时落入其他码字的纠错范围。两个码字中心之间至少相距 dmin⁡d_{\min},所以保证纠错上限为:

t=⌊dmin⁡−12⌋t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor
最小距离 dmin⁡d_{\min} 保证检错位数 保证纠错位数
2 1 0
3 2 1
4 3 1
5 4 2

这些是任意错误位置下的保证值,不是随机噪声一定产生的错误数。汉明(7,4)码的 dmin⁡=3d_{\min}=3,因此可保证检出至多两位错误,却只能保证纠正一位错误。

为什么两位错误会被误纠

假定发送 A=0000000,而 B=1000110 也是合法码字。收到 1000000 时,它离 A 只有 1 位、离 B 有 2 位,最近邻译码选择 A,成功恢复。

若第 1、5 位同时翻转,接收字成为 1000100:它距 A 为 2,距 B 却只有 1。合法码字检查能够发现它不在码本中;但若直接使用“纠正一位错误”的最近邻译码器,就会错误输出 B。检错能力不能直接当作纠错能力使用。

再翻转第 6 位,接收字恰好成为 B。三位翻转已经把 A 变成另一个合法码字,即使检查码本成员资格也无法发现这个错误。

七位汉明码的码字距离与误纠对比

用 Python 穷举验证边界

以下示例适用于 Python 3,采用系统形生成矩阵 G=[I4∣P]G=[I_4\mid P]:前四位是信息位,后三位由矩阵 PP 模 2 计算。程序生成全部 16 个合法码字,再逐一检验每个码字的 7 种单比特翻转和 21 种双比特翻转。

python
from itertools import combinations, product

P = ((1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1))

def encode(message):
    # 系统形编码:保留4位信息,并计算3位校验
    parity = tuple(sum(message[i] * P[i][j] for i in range(4)) % 2
                   for j in range(3))
    return message + parity

def distance(a, b):
    return sum(x != y for x, y in zip(a, b))

def flip(word, positions):
    result = list(word)
    for i in positions:
        result[i] ^= 1
    return tuple(result)

words = [encode(m) for m in product((0, 1), repeat=4)]
word_set = set(words)
d_min = min(distance(a, b) for a, b in combinations(words, 2))

def nearest(received):
    return min(words, key=lambda c: distance(c, received))

# 对全部码字和全部错误位置检查最坏情况保证
single_ok = all(nearest(flip(c, (i,))) == c
                for c in words for i in range(7))
double_ok = all(flip(c, (i, j)) not in word_set
                for c in words for i, j in combinations(range(7), 2))

zero = (0,) * 7
two_errors = flip(zero, (0, 4))
three_errors = flip(zero, (0, 4, 5))
print("码字数:", len(words))
print("最小距离:", d_min)
print("单比特全部纠正:", single_ok)
print("双比特全部可检出:", double_ok)
print("双比特最近邻结果:", "".join(map(str, nearest(two_errors))))
print("三比特恰好变为合法码字:", three_errors in word_set)

预期输出:

text
码字数: 16
最小距离: 3
单比特全部纠正: True
双比特全部可检出: True
双比特最近邻结果: 1000110
三比特恰好变为合法码字: True

验证时要分别观察“码本成员检查”和“最近邻译码”的结果。双比特模式均可被前者识别为非法码字,但最近邻仍可能误纠;三位错误可能直接落在另一合法码字上。最小距离描述的是最坏情况下的能力边界,具体误码率仍须结合信道模型与译码算法测量。

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

目录与阅读设置

阅读设置

17

记录一个想法

从汉明距离推导纠错能力

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

登录哪都通