通信工程 / 系统课时

用消息传递迭代求解 LDPC 码字

用消息传递迭代求解 LDPC 码字

给定校验矩阵和接收端的软信息,本课用对数似然比(LLR)实现 LDPC 求和积译码:沿 Tanner 图的边交换消息,逐轮硬判决,再用校验子判断是否停止。最后运行一个 3×6 示例,观察为什么第一轮判决不变也不能提前结束。

学习目标

  • 根据校验矩阵找出变量节点与校验节点之间的消息通路。
  • 用 LLR 完成两类节点的更新,并排除目标边自身传来的信息。
  • 运行迭代译码,区分校验通过和达到迭代上限两种停止原因。

从校验约束确定消息边

使用一个 3 行、6 列的二元校验矩阵作为教学样例。变量节点 v1v_1 至 v6v_6 对应六个待判决比特;每个校验节点要求其相邻比特的异或结果为 0。

校验节点 相连变量节点 对应约束
c1c_1 v1,v2,v4v_1,v_2,v_4 v1⊕v2⊕v4=0v_1\oplus v_2\oplus v_4=0
c2c_2 v2,v3,v5v_2,v_3,v_5 v2⊕v3⊕v5=0v_2\oplus v_3\oplus v_5=0
c3c_3 v1,v3,v6v_1,v_3,v_6 v1⊕v3⊕v6=0v_1\oplus v_3\oplus v_6=0

矩阵里每一个 1 对应 Tanner 图的一条边,因此本例共有 9 条边。消息只沿这些边传递,且同一条边的两个方向要分别保存;这里的消息是带符号的可靠度,不是已经判定的 0 或 1。

LDPC 校验关系与双向消息迭代

用外信息规则更新 LLR

定义 Ljch=ln⁡P(yj∣xj=0)P(yj∣xj=1)L_j^{ch}=\ln\frac{P(y_j\mid x_j=0)}{P(y_j\mid x_j=1)}:正值支持比特 0,负值支持比特 1。对 0 映射为 +1、1 映射为 -1 的 BPSK 加性高斯白噪声信道,噪声方差为 σ2\sigma^2 时,有 Ljch=2yj/σ2L_j^{ch}=2y_j/\sigma^2。初始化每条变量到校验的消息 qj→i=Ljchq_{j\to i}=L_j^{ch}。

校验节点 cic_i 更新发往 vjv_j 的消息时,只使用其他邻居传入的消息:

ri→j=2atanh⁡(∏k∈N(ci)∖{j}tanh⁡qk→i2)r_{i\to j}=2\operatorname{atanh}\left(\prod_{k\in N(c_i)\setminus\{j\}}\tanh\frac{q_{k\to i}}{2}\right)

收齐本轮校验消息后,计算每个比特的后验 LLR;下一轮变量节点发往校验节点的消息,则必须排除来自目标校验的那一项:

Ljpost=Ljch+∑i∈N(vj)ri→j,qj→i=Ljch+∑ℓ∈N(vj)∖{i}rℓ→jL_j^{post}=L_j^{ch}+\sum_{i\in N(v_j)}r_{i\to j},\qquad q_{j\to i}=L_j^{ch}+\sum_{\ell\in N(v_j)\setminus\{i\}}r_{\ell\to j}

例如取信道 LLR 为 [1.3,3.7,3.4,1.7,2.5,−1.7][1.3,3.7,3.4,1.7,2.5,-1.7]。首轮 c3c_3 发往 v6v_6 的消息约为 +1.194+1.194,于是 v6v_6 的后验 LLR 约为 −0.506-0.506,仍被判作 1。继续交换外信息后,它才可能翻转为 0。

运行两轮收敛的 Python 示例

以下代码适用于 Python 3.8 及以上版本,只用标准库。采用同步更新:每轮全部校验节点先读取上一轮的 q 计算 r,再统一硬判决。为防止浮点数导致 atanh 输入落到正负 1,计算前将乘积限制在开区间内。

python
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('初始判决已满足全部校验')

预期输出:

text
初始:000001,校验子=001
第1轮:000001,校验子=001
第2轮:000000,校验子=000
校验通过,提前停止

用校验子确定停止边界

每轮把后验 LLR 大于或等于 0 的位置判为 0,小于 0 的位置判为 1,然后按 s=Hx^T mod 2s=H\hat{x}^{T}\bmod 2 计算校验子。仅当所有分量为 0 时才视为通过校验;否则只要轮数未达到 max_iter,就继续更新下一轮的变量消息。

本例首轮的硬判决与初始值相同,校验子却仍为 001,说明“本轮判决没变”不能代替校验通过。把代码中的 max_iter 改成 1,会看到“达到最大迭代次数,未通过校验”;恢复为 10,则会在第 2 轮提前停止。

本例每轮沿 9 条边分别传递两类消息。代码为便于理解,计算每条出边时重新遍历邻居;工程实现通常复用中间结果并处理大幅度 LLR 的数值稳定性,而停止规则仍以校验结果和迭代预算为准。

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

目录与阅读设置

阅读设置

17

记录一个想法

用消息传递迭代求解 LDPC 码字

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

登录哪都通