通信工程 / 系统课时

用伴随式定位单比特错误

用伴随式定位单比特错误

接收端拿到七位比特后,校验失败只能说明接收序列不满足码字约束,还不能直接知道哪一位出错。利用线性分组码的伴随式,可以把校验结果映射为具体的错误位置。本课以 (7,4) 汉明码为例,完成伴随式计算、单比特错误定位、码字恢复和 Python 验证。

学习目标

  • 理解伴随式与校验矩阵列向量之间的对应关系。
  • 根据三位伴随式定位七位码字中的单比特错误,并通过翻转恢复原码字。
  • 使用 Python 验证纠错过程,识别多比特错误造成的误纠正风险。

约定校验矩阵与位序

线性分组码使用校验矩阵 HH 判断接收序列是否满足奇偶校验约束。对于 (7,4) 汉明码,每个码字包含 4 位信息位和 3 位校验位,因此校验矩阵有 3 行、7 列。

本例采用系统形式,码字从左到右依次为第 1 至第 7 位,前 4 位是信息位,后 3 位是校验位。使用以下校验矩阵:

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

该矩阵采用 H=[PT∣I3]H=[P^{\mathsf T}\mid I_3] 的结构,对应的系统形生成矩阵为 G=[I4∣P]G=[I_4\mid P]。其中 I4I_4 和 I3I_3 分别是四阶、三阶单位矩阵。

观察 HH 的七个列向量:

码字位置 对应列向量
第 1 位 110
第 2 位 101
第 3 位 011
第 4 位 111
第 5 位 100
第 6 位 010
第 7 位 001

七个列向量恰好是全部七种非零三位二进制向量,而且互不相同。因此,只要能计算出一个非零的三位伴随式,就可以在假设最多发生一位错误的情况下,找到唯一匹配的列。

例如,合法发送码字取 c=(1,0,1,1,0,1,0)c=(1,0,1,1,0,1,0),即 1011010。它满足 HcT=0Hc^{\mathsf T}=0,三条奇偶校验均通过。

计算接收字的伴随式

假设发送码字为 1011010,传输中从左往右数第 3 位由 1 翻转为 0,接收端得到 1001010。

将接收向量记为 rr,在二元域 GF(2)GF(2) 上计算伴随式:

s=HrT mod 2s=Hr^{\mathsf T}\bmod 2

这里的乘法按普通二进制位乘法进行,加法按模二运算进行,即 0+0=00+0=0、0+1=10+1=1、1+1=01+1=0。计算时也可以直接使用异或操作。

对于当前接收字,三条校验分别为:

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

因此,伴随式为:

s=[011]s=\begin{bmatrix}0\\1\\1\end{bmatrix}

也就是 011。因为伴随式不为零,接收字没有通过校验,需要进一步定位错误。

按列定位并翻转错误位

伴随式之所以能定位单比特错误,来自线性分组码的一个性质:所有合法码字都满足 HcT=0Hc^{\mathsf T}=0。

设只有第 jj 位出错,错误向量 eje_j 仅在第 jj 位为 1,其余位均为 0。接收字为 r=c⊕ejr=c\oplus e_j,则:

s=HrT=H(c⊕ej)T=HejT=H:,js=Hr^{\mathsf T}=H(c\oplus e_j)^{\mathsf T}=He_j^{\mathsf T}=H_{:,j}

其中 H:,jH_{:,j} 表示校验矩阵的第 jj 列。因为合法码字的校验结果为零,伴随式实际上只保留了错误向量产生的校验结果。

本例得到 011,它与 HH 的第 3 列完全相同,因此定位到第 3 位错误。

七位汉明码利用伴随式查找错误位置并恢复码字的数据流示意图

实际纠错只需要三个步骤:

  1. 将伴随式 011 与校验矩阵的七列逐一比较,找到第 3 列。
  2. 翻转接收字的第 3 位,将 1001010 改为 1011010。
  3. 对恢复后的码字重新计算 HcTHc^{\mathsf T},确认伴随式变为 000。

由于采用系统码,恢复后的前四位 1011 就是原始信息位,不需要再执行额外的逆矩阵运算。

用 Python 验证纠错过程

使用 Python 3 标准库即可完成这个实验,不需要安装 NumPy 等第三方依赖。下面的程序定义校验矩阵、模拟单比特翻转、计算伴随式,并自动建立列向量到错误位置的映射。

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

# 使用满足 Hc^T=0 的合法七位码字
c = [1, 0, 1, 1, 0, 1, 0]
r = c.copy()
r[2] ^= 1  # 模拟第3位发生翻转

def syndrome(bits):
    return tuple(
        sum(row[j] * bits[j] for j in range(7)) % 2
        for row in H
    )

s = syndrome(r)

# 按实际矩阵列建立查找表,索引从0开始
column_to_position = {
    tuple(row[j] for row in H): j
    for j in range(7)
}

error_position = (
    column_to_position.get(s)
    if s != (0, 0, 0) else None
)

corrected = r.copy()
if error_position is not None:
    corrected[error_position] ^= 1

print("发送码字:", "".join(map(str, c)))
print("接收码字:", "".join(map(str, r)))
print("伴随式:", "".join(map(str, s)))
print("错误位置:", "未发现" if error_position is None
      else f"第{error_position + 1}位")
print("纠正码字:", "".join(map(str, corrected)))
print("复验伴随式:", "".join(map(str, syndrome(corrected))))

预期输出:

text
发送码字: 1011010
接收码字: 1001010
伴随式: 011
错误位置: 第3位
纠正码字: 1011010
复验伴随式: 000

程序使用 r[2] 操作第三位,因为 Python 列表下标从 0 开始;输出位置时使用 error_position + 1,转换为读者习惯的从 1 开始计数。

syndrome 函数逐行执行模二点积,返回长度为 3 的元组。查找表以矩阵列向量作为键、列表下标作为值,能够避免对错误位置进行硬编码。

可以把 r[2] ^= 1 改为 r[5] ^= 1 再执行程序。此时应得到伴随式 010,错误位置变为第 6 位,纠正码字仍是 1011010。这能检查列映射是否真的覆盖了不同错误位置。

识别多比特错误的边界

标准 (7,4) 汉明码的最小码距为 3,因此可以保证纠正任意一个比特错误,但不能可靠地纠正两个比特错误。非零伴随式不代表接收字一定只错了一位。

例如,若原码字 1011010 的第 1 位和第 2 位同时翻转,接收字将变为 0111010。两处错误产生的伴随式为:

s=110⊕101=011s=110\oplus101=011

这个结果恰好等于校验矩阵的第 3 列。单比特纠错算法会错误地认为第 3 位出错,进而将接收字改为 0101010。虽然修改后的伴随式也等于 000,但它并不是原始发送码字。

因此,需要区分以下情形:

伴随式与实际错误 处理结果
000,实际没有错误 直接接受码字
非零,实际只有一位错误 可以唯一定位并纠正
非零,实际有两位错误 可能被误判为另一处单比特错误
000,实际有多位错误 可能存在未被发现的错误

如果系统要求纠正一位错误并检测两位错误,可以增加整体奇偶校验位,采用扩展汉明码,例如 (8,4) SECDED(单错纠正、双错检测)。对于存在更多随机错误或突发错误的通信系统,还需要结合 CRC、交织或重传机制进行设计。

实际实现中应同时检查伴随式、错误位置映射和纠错能力边界。只要固定校验矩阵与位序,单比特错误就能通过一次矩阵乘法、一次列匹配和一次比特翻转完成恢复。

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

目录与阅读设置

阅读设置

17

记录一个想法

用伴随式定位单比特错误

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

登录哪都通