通信工程 / 系统课时

从稀疏校验矩阵建立 LDPC 约束

从稀疏校验矩阵建立 LDPC 约束

给定一张 LDPC 校验矩阵,怎样知道哪几个比特共同受到一条校验约束?本课用 3 行 6 列的示例,逐行写出模二校验方程,把矩阵中的 1 转成 Tanner 图的边,并用 Python 检查合法码字与单比特翻转后的结果。

学习目标

  • 按校验矩阵的行与列写出对应的异或约束。
  • 将非零矩阵元素映射为 Tanner 图中的边,并计算节点度数。
  • 使用综合症验证约束连接与比特翻转的影响。

从矩阵读出校验方程

LDPC(低密度奇偶校验码)用二元域 GF(2)GF(2) 上的校验矩阵 HH 描述码字约束。长度为 nn 的码字 xx 必须满足 HxT=0Hx^\mathsf{T}=0;矩阵运算中的加法是异或,不能用普通整数求和代替。

下面是一个便于手算的 3×63\times 6 教学矩阵。行对应校验节点,列对应码字比特;实际 LDPC 的矩阵通常更大,非零元素占比也更低。

校验行 v1v_1 v2v_2 v3v_3 v4v_4 v5v_5 v6v_6
c1c_1 1 1 0 1 0 0
c2c_2 0 1 1 0 1 0
c3c_3 1 0 0 0 1 1

把每行的 1 所在列挑出来,得到三条必须同时成立的偶校验约束:

  • c1c_1:x1⊕x2⊕x4=0x_1\oplus x_2\oplus x_4=0。
  • c2c_2:x2⊕x3⊕x5=0x_2\oplus x_3\oplus x_5=0。
  • c3c_3:x1⊕x5⊕x6=0x_1\oplus x_5\oplus x_6=0。

例如第一条要求 x1,x2,x4x_1,x_2,x_4 中的 1 有偶数个;其他未出现的位不参与这条校验。

将每个 1 变为 Tanner 图的边

Tanner 图是一张二部图:6 个变量节点 v1v_1~v6v_6 代表码字的 6 位,3 个校验节点 c1c_1~c3c_3 代表 3 条约束。仅当 Hij=1H_{ij}=1,才连接校验节点 cic_i 与变量节点 vjv_j,同类节点之间不连边。

具体画图时,c1c_1 连接 v1,v2,v4v_1,v_2,v_4;c2c_2 连接 v2,v3,v5v_2,v_3,v_5;c3c_3 连接 v1,v5,v6v_1,v_5,v_6。因此共有 9 条边,正好等于矩阵中 1 的总数。

3×6 校验矩阵与 Tanner 图的九条对应边

读图时还可反向核查某一列:例如 v5v_5 仅连接 c2,c3c_2,c_3,说明第 5 位同时影响第 2、3 条约束。后续迭代译码正是沿这些边在变量节点与校验节点之间交换信息。

用综合症验证局部约束

接收向量 rr 的综合症为 s=HrTs=Hr^\mathsf{T}(模 2)。si=1s_i=1 表示第 ii 条校验未满足;所有分量为 0 表示满足当前校验矩阵的约束,但不保证收到的就是原始发送码字。

下面的 Python 3 示例不需要第三方库,会同时输出校验节点邻接表和翻转比特前后的综合症。

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

def syndrome(bits):
    # 每一行只对参与该校验的比特做模二求和
    return [sum(h * b for h, b in zip(row, bits)) % 2 for row in H]

for i, row in enumerate(H, 1):
    neighbors = [f"v{j}" for j, h in enumerate(row, 1) if h == 1]
    print(f"c{i}: {', '.join(neighbors)}")

word = [1, 0, 1, 1, 1, 0]
print("原码字:", syndrome(word))
received = word.copy()
received[4] ^= 1  # Python索引4对应第5位v5
print("翻转v5:", syndrome(received))

预期输出:

text
c1: v1, v2, v4
c2: v2, v3, v5
c3: v1, v5, v6
原码字: [0, 0, 0]
翻转v5: [0, 1, 1]

翻转 v5v_5 只让 c2c_2 与 c3c_3 失效,与矩阵第五列的数值 [0,1,1]T[0,1,1]^\mathsf{T} 一致。多比特错误可能产生相同综合症,因此不能将这个验证程序误当成通用 LDPC 译码器。

检查节点度数与短环

节点的度数就是相连边的数量。本图三个校验节点的度数都是 3,六个变量节点的度数依次为 2、2、1、1、2、1。两侧度数和都等于 9,若画出的图不满足这个计数,就有漏边或重边。

还可用矩阵直接筛查四环:若任意两行同时在至少两列取值为 1,就会产生长度为 4 的环。本例任意两行最多只共享一个 1 的列,因此没有四环;但存在 c1→v2→c2→v5→c3→v1→c1c_1\to v_2\to c_2\to v_5\to c_3\to v_1\to c_1 这条六环。实际 LDPC 设计会关注短环,因为沿环循环传递的消息可能带来相关性,影响迭代译码效果。

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

目录与阅读设置

阅读设置

17

记录一个想法

从稀疏校验矩阵建立 LDPC 约束

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

登录哪都通