通信工程 / 系统课时
用消息传递迭代求解 LDPC 码字
用消息传递迭代求解 LDPC 码字
给定校验矩阵和接收端的软信息,本课用对数似然比(LLR)实现 LDPC 求和积译码:沿 Tanner 图的边交换消息,逐轮硬判决,再用校验子判断是否停止。最后运行一个 3×6 示例,观察为什么第一轮判决不变也不能提前结束。
学习目标
- 根据校验矩阵找出变量节点与校验节点之间的消息通路。
- 用 LLR 完成两类节点的更新,并排除目标边自身传来的信息。
- 运行迭代译码,区分校验通过和达到迭代上限两种停止原因。
从校验约束确定消息边
使用一个 3 行、6 列的二元校验矩阵作为教学样例。变量节点 至 对应六个待判决比特;每个校验节点要求其相邻比特的异或结果为 0。
| 校验节点 | 相连变量节点 | 对应约束 |
|---|---|---|
矩阵里每一个 1 对应 Tanner 图的一条边,因此本例共有 9 条边。消息只沿这些边传递,且同一条边的两个方向要分别保存;这里的消息是带符号的可靠度,不是已经判定的 0 或 1。

用外信息规则更新 LLR
定义 :正值支持比特 0,负值支持比特 1。对 0 映射为 +1、1 映射为 -1 的 BPSK 加性高斯白噪声信道,噪声方差为 时,有 。初始化每条变量到校验的消息 。
校验节点 更新发往 的消息时,只使用其他邻居传入的消息:
收齐本轮校验消息后,计算每个比特的后验 LLR;下一轮变量节点发往校验节点的消息,则必须排除来自目标校验的那一项:
例如取信道 LLR 为 。首轮 发往 的消息约为 ,于是 的后验 LLR 约为 ,仍被判作 1。继续交换外信息后,它才可能翻转为 0。
运行两轮收敛的 Python 示例
以下代码适用于 Python 3.8 及以上版本,只用标准库。采用同步更新:每轮全部校验节点先读取上一轮的 q 计算 r,再统一硬判决。为防止浮点数导致 atanh 输入落到正负 1,计算前将乘积限制在开区间内。
import math
H = [
[1, 1, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0],
[1, 0, 1, 0, 0, 1],
]
llr = [1.3, 3.7, 3.4, 1.7, 2.5, -1.7]
max_iter = 10
checks = [[j for j, x in enumerate(row) if x] for row in H]
variables = [[i for i, row in enumerate(H) if row[j]] for j in range(len(llr))]
def syndrome(bits):
return [sum(bits[j] for j in cols) % 2 for cols in checks]
def report(label, bits):
sequence = ''.join(map(str, bits))
result = ''.join(map(str, syndrome(bits)))
print(f'{label}:{sequence},校验子={result}')
# 初始化变量到校验的消息
q = {(i, j): llr[j] for i, cols in enumerate(checks) for j in cols}
bits = [int(value < 0) for value in llr]
report('初始', bits)
if any(syndrome(bits)):
for iteration in range(1, max_iter + 1):
# 用上一轮 q 同步计算全部校验到变量消息
r = {}
for i, cols in enumerate(checks):
for j in cols:
product = math.prod(math.tanh(q[i, k] / 2) for k in cols if k != j)
product = max(-1 + 1e-12, min(1 - 1e-12, product))
r[i, j] = 2 * math.atanh(product)
posterior = [llr[j] + sum(r[i, j] for i in variables[j]) for j in range(len(llr))]
bits = [int(value < 0) for value in posterior]
report(f'第{iteration}轮', bits)
if not any(syndrome(bits)):
print('校验通过,提前停止')
break
# 排除目标校验送回的消息,防止重复计算自身证据
q = {
(i, j): llr[j] + sum(r[k, j] for k in variables[j] if k != i)
for i, cols in enumerate(checks)
for j in cols
}
else:
print('达到最大迭代次数,未通过校验')
else:
print('初始判决已满足全部校验')预期输出:
初始:000001,校验子=001
第1轮:000001,校验子=001
第2轮:000000,校验子=000
校验通过,提前停止用校验子确定停止边界
每轮把后验 LLR 大于或等于 0 的位置判为 0,小于 0 的位置判为 1,然后按 计算校验子。仅当所有分量为 0 时才视为通过校验;否则只要轮数未达到 max_iter,就继续更新下一轮的变量消息。
本例首轮的硬判决与初始值相同,校验子却仍为 001,说明“本轮判决没变”不能代替校验通过。把代码中的 max_iter 改成 1,会看到“达到最大迭代次数,未通过校验”;恢复为 10,则会在第 2 轮提前停止。
本例每轮沿 9 条边分别传递两类消息。代码为便于理解,计算每条出边时重新遍历邻居;工程实现通常复用中间结果并处理大幅度 LLR 的数值稳定性,而停止规则仍以校验结果和迭代预算为准。