通信工程 / 系统课时

用校验矩阵检验接收码字

用校验矩阵检验接收码字

收到 7 位二进制序列后,怎样快速判断它是否符合编码规则?本篇用一个 (7,4) 汉明码示例,把接收比特代入校验矩阵,计算三位校验子,再用 Python 复现判断,并说明为什么校验通过不等于传输一定没有错误。

学习目标

  • 理解校验矩阵、合法码字和校验子之间的关系。
  • 手算一组接收比特的校验子,并使用 Python 检查结果。
  • 区分“发现违反校验约束”和“确认错误位置”的适用条件。

合法码字满足哪些约束

在线性分组码中,接收向量 rr 的每一位都是 0 或 1。校验矩阵 HH 的每一行是一条奇偶校验约束;计算时在二元域 GF(2) 上运算,即按位相乘后求和取模 2,加法也可写成异或 ⊕\oplus。

以 (7,4) 汉明码为例,7 位码字中有 4 位独立信息,使用下面的 3×73\times7 校验矩阵。矩阵列从左到右对应码字第 1~7 位。

H=[101010101100110001111]H=\begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

对接收向量 rr 计算校验子:

s=HrT(mod2)s=Hr^{\mathsf T}\pmod 2

若 s=(0,0,0)Ts=(0,0,0)^{\mathsf T},则 rr 满足全部约束,是该码中的合法码字;若有任意一位不为 0,则 rr 不属于该码,说明传输中至少出现了使校验失效的差错。

手算三条奇偶校验

取发送码字 c=0110011c=0110011。它代入三条校验约束都得到 0。假设第 5 位由 0 翻转成 1,接收端得到 r=0110111r=0110111,每条约束只检查矩阵对应行中系数为 1 的位置:

  • 第 1 行检查第 1、3、5、7 位:0⊕1⊕1⊕1=10\oplus1\oplus1\oplus1=1。
  • 第 2 行检查第 2、3、6、7 位:1⊕1⊕1⊕1=01\oplus1\oplus1\oplus1=0。
  • 第 3 行检查第 4、5、6、7 位:0⊕1⊕1⊕1=10\oplus1\oplus1\oplus1=1。

因此 s=(1,0,1)Ts=(1,0,1)^{\mathsf T},接收序列未通过校验。对应地,HH 的第 5 列恰好是 (1,0,1)T(1,0,1)^{\mathsf T};只有假设至多发生一位错误时,才能据此把第 5 位判为错误位置。

七位接收序列经过三条奇偶校验得到校验子

用 Python 验证校验子

使用 Python 3.9 或更新版本,保存为 check_hamming.py 并执行 python check_hamming.py。代码不需要安装第三方库。

python
H = [
    [1, 0, 1, 0, 1, 0, 1],
    [0, 1, 1, 0, 0, 1, 1],
    [0, 0, 0, 1, 1, 1, 1],
]

def syndrome(bits):
    # 每一行与接收向量相乘后取模 2
    return tuple(sum(a * b for a, b in zip(row, bits)) % 2 for row in H)

sent = [0, 1, 1, 0, 0, 1, 1]
received = sent.copy()
received[4] ^= 1  # Python 索引 4 对应码字第 5 位

for name, bits in [("发送", sent), ("接收", received)]:
    s = syndrome(bits)
    print(f"{name} {''.join(map(str, bits))}:校验子{s},合法={s == (0, 0, 0)}")

# 单比特差错时,校验子等于出错位置对应的 H 列
s = syndrome(received)
positions = [i + 1 for i in range(7)
             if tuple(row[i] for row in H) == s]
print("单比特错误假设下的位置:", positions)

预期输出:

text
发送 0110011:校验子(0, 0, 0),合法=True
接收 0110111:校验子(1, 0, 1),合法=False
单比特错误假设下的位置: [5]

验证时可把 received[4] ^= 1 改成 received[0] ^= 1,校验子应变为 (1, 0, 0),对应第 1 列。这里的列匹配只是在单比特差错模型下提供定位依据,不能用于无条件纠正任意接收序列。

零校验子也可能漏检

校验矩阵判断的是接收序列是否属于码空间,而不是它与原始发送序列是否完全一致。(7,4) 汉明码的最小距离为 3,因此能检测任意 1 位或 2 位错误,但存在无法检测的 3 位错误。

例如,原码字 01100110110011 的第 1、2、3 位同时翻转后得到 10000111000011,新的三条校验结果仍全为 0。接收端只看 s=000s=000,无法发现这次变化。

另一个边界是:若第 1、2 位同时翻转,得到 10100111010011,校验子会是 (1,1,0)T(1,1,0)^{\mathsf T},刚好等于 HH 的第 3 列。若误当作单比特错误去翻转第 3 位,就会把两位错误变成三位错误。

因此,做检错时按校验子是否为零判断是否违反校验;要做单比特纠错,还必须明确采用至多一位错误的假设。对于多位错误风险,应结合码的检错能力与其他完整性校验机制,而不是盲目依据某列执行翻转。

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

目录与阅读设置

阅读设置

17

记录一个想法

用校验矩阵检验接收码字

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

登录哪都通