通信工程 / 系统课时
从稀疏校验矩阵建立 LDPC 约束
从稀疏校验矩阵建立 LDPC 约束
给定一张 LDPC 校验矩阵,怎样知道哪几个比特共同受到一条校验约束?本课用 3 行 6 列的示例,逐行写出模二校验方程,把矩阵中的 1 转成 Tanner 图的边,并用 Python 检查合法码字与单比特翻转后的结果。
学习目标
- 按校验矩阵的行与列写出对应的异或约束。
- 将非零矩阵元素映射为 Tanner 图中的边,并计算节点度数。
- 使用综合症验证约束连接与比特翻转的影响。
从矩阵读出校验方程
LDPC(低密度奇偶校验码)用二元域 上的校验矩阵 描述码字约束。长度为 的码字 必须满足 ;矩阵运算中的加法是异或,不能用普通整数求和代替。
下面是一个便于手算的 教学矩阵。行对应校验节点,列对应码字比特;实际 LDPC 的矩阵通常更大,非零元素占比也更低。
| 校验行 | ||||||
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 1 |
把每行的 1 所在列挑出来,得到三条必须同时成立的偶校验约束:
- :。
- :。
- :。
例如第一条要求 中的 1 有偶数个;其他未出现的位不参与这条校验。
将每个 1 变为 Tanner 图的边
Tanner 图是一张二部图:6 个变量节点 ~ 代表码字的 6 位,3 个校验节点 ~ 代表 3 条约束。仅当 ,才连接校验节点 与变量节点 ,同类节点之间不连边。
具体画图时, 连接 ; 连接 ; 连接 。因此共有 9 条边,正好等于矩阵中 1 的总数。

读图时还可反向核查某一列:例如 仅连接 ,说明第 5 位同时影响第 2、3 条约束。后续迭代译码正是沿这些边在变量节点与校验节点之间交换信息。
用综合症验证局部约束
接收向量 的综合症为 (模 2)。 表示第 条校验未满足;所有分量为 0 表示满足当前校验矩阵的约束,但不保证收到的就是原始发送码字。
下面的 Python 3 示例不需要第三方库,会同时输出校验节点邻接表和翻转比特前后的综合症。
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))预期输出:
c1: v1, v2, v4
c2: v2, v3, v5
c3: v1, v5, v6
原码字: [0, 0, 0]
翻转v5: [0, 1, 1]翻转 只让 与 失效,与矩阵第五列的数值 一致。多比特错误可能产生相同综合症,因此不能将这个验证程序误当成通用 LDPC 译码器。
检查节点度数与短环
节点的度数就是相连边的数量。本图三个校验节点的度数都是 3,六个变量节点的度数依次为 2、2、1、1、2、1。两侧度数和都等于 9,若画出的图不满足这个计数,就有漏边或重边。
还可用矩阵直接筛查四环:若任意两行同时在至少两列取值为 1,就会产生长度为 4 的环。本例任意两行最多只共享一个 1 的列,因此没有四环;但存在 这条六环。实际 LDPC 设计会关注短环,因为沿环循环传递的消息可能带来相关性,影响迭代译码效果。