通信工程 / 系统课时
从汉明距离推导纠错能力
从汉明距离推导纠错能力
发送端增加校验位后,究竟能发现多少位错误、又能恢复多少位错误?本篇以汉明(7,4)码为例,从码字间的比特差异推导两种能力的保证边界,再用 Python 穷举验证一位和两位翻转的结果。
学习目标
- 计算码字间的汉明距离与码的最小距离。
- 根据最小距离推导保证检错和保证纠错的位数。
- 识别“两位错误可检出”与“两位错误可纠正”的区别,并运行验证。
码字的最小距离如何确定
汉明距离是两个等长比特串在多少个位置上不同。例如,合法码字 A=0000000、B=1000110 在第 1、5、6 位不同,所以 。汉明距离只统计位置,不关心这些位置相隔多远。
一组合法码字构成码本 ,其最小距离是任意两个不同码字之间的最小汉明距离:
仅知道 A、B 相距 3,还不能断言整个码的最小距离为 3;必须检查所有码字对。对于线性分组码,也可以求所有非零合法码字的最小汉明重量,结果相同。后面的程序会对含 16 个码字的汉明(7,4)码完成穷举。
最小距离给出什么保证
若任意两合法码字至少相差 位,那么翻转少于 位不可能恰好变成另一个合法码字。因此,保证检错上限为 位;这里的“检出”指接收字不属于码本,接收端能报告异常,但未必知道原码字。
纠错要求接收字离真实码字足够近,且不能同时落入其他码字的纠错范围。两个码字中心之间至少相距 ,所以保证纠错上限为:
| 最小距离 | 保证检错位数 | 保证纠错位数 |
|---|---|---|
| 2 | 1 | 0 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 4 | 2 |
这些是任意错误位置下的保证值,不是随机噪声一定产生的错误数。汉明(7,4)码的 ,因此可保证检出至多两位错误,却只能保证纠正一位错误。
为什么两位错误会被误纠
假定发送 A=0000000,而 B=1000110 也是合法码字。收到 1000000 时,它离 A 只有 1 位、离 B 有 2 位,最近邻译码选择 A,成功恢复。
若第 1、5 位同时翻转,接收字成为 1000100:它距 A 为 2,距 B 却只有 1。合法码字检查能够发现它不在码本中;但若直接使用“纠正一位错误”的最近邻译码器,就会错误输出 B。检错能力不能直接当作纠错能力使用。
再翻转第 6 位,接收字恰好成为 B。三位翻转已经把 A 变成另一个合法码字,即使检查码本成员资格也无法发现这个错误。

用 Python 穷举验证边界
以下示例适用于 Python 3,采用系统形生成矩阵 :前四位是信息位,后三位由矩阵 模 2 计算。程序生成全部 16 个合法码字,再逐一检验每个码字的 7 种单比特翻转和 21 种双比特翻转。
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)预期输出:
码字数: 16
最小距离: 3
单比特全部纠正: True
双比特全部可检出: True
双比特最近邻结果: 1000110
三比特恰好变为合法码字: True验证时要分别观察“码本成员检查”和“最近邻译码”的结果。双比特模式均可被前者识别为非法码字,但最近邻仍可能误纠;三位错误可能直接落在另一合法码字上。最小距离描述的是最坏情况下的能力边界,具体误码率仍须结合信道模型与译码算法测量。