LDPC 码

LDPC 码（low-density parity-check code，低密度奇偶校验码）由 Robert Gallager 在 1962 年提出：校验矩阵里 1 的密度随码长趋于零，译码靠迭代消息传递。这个比 turbo 码早 31 年的方案因当年算力不可行被遗忘三十余年，1996–1999 年经 MacKay 等人复兴后成为逼近信道容量的主流技术，2001 年密度演化设计把差距缩到 0.0045 dB。它同时是量子 LDPC 码的直接模板：把稀疏校验矩阵的行换成 Pauli 校验算符即得量子版。

定义与码率

Gallager 的 $(n,j,k)$ 正则 LDPC 码：码长 $n$，校验矩阵 $H$ 的每一列恰有 $j$ 个 1、每一行恰有 $k$ 个 1，且 $j\ll k\ll n$（典型选择 $j=3$）。$H$ 共 $m=nj/k$ 行，行空间独立时码率取到下界

$R=1-\frac{j}{k}$

（(3,6) 正则码即 $R=1/2$；行相关只会抬高码率，故 $R\ge 1-j/k$）Gallager 1962 (IRE Trans. Inf. Theory)。“低密度”是关键修饰：固定 $j,k$ 增大 $n$ 时，$H$ 中 1 的占比 $nj/(mn)=k/n\to 0$。

Gallager 的两个译码器

Gallager 原文给出两种译码算法Gallager 1962 (IRE Trans. Inf. Theory)：

• 比特翻转（bit-flipping）：反复统计每个比特牵涉的失败校验数，把”多数校验失败”的比特翻转，直到综合征归零——硬判决、线性时间的贪心算法，是扩张码翻转译码的直系前身；
• 概率译码：变量节点与校验节点之间迭代交换对数似然比消息，软判决逼近最大后验——这正是在Tanner 图上运行的置信传播（和积算法），Gallager 的更新式与 1962 年后 40 年通行的 tanh 规则逐字相同。

Gallager 还证明了固定 $j,k$ 时正则族的最小距离随 $n$ 线性增长——随机码式的”好码”性质（见GV 界），这在当时是孤立的先知结果。

稀疏性的三重意义

$H$ 稀疏不只为省存储：(i) 每次迭代译码的计算量正比于边数，即 $O(n)$；(ii) Tanner 图在局部呈树状（girth 受限时消息独立性保持，见tanner-graphs），使 BP 近似精确；(iii) 稀疏结构可直接量子化——把 $H$ 的行换成对易的 Pauli 算符、配 X/Z 两套校验并要求 $H_X{H}_Z^{\mathsf{T}}=0$，就是量子 LDPC 码（见qldpc-overview）。稠密随机码虽达 GV 界，但三条全部落空——稀疏性是”好且可译”的关键。

复兴史：从遗忘到 0.0045 dB

1960 年代算力无法迭代译码，LDPC 沉寂；1993 年 turbo 码证明迭代译码能逼近容量，MacKay 与 Neal 于 1996 年重新发现 LDPC 的性能MacKay & Neal 1996 (Electron. Lett.)，MacKay 1999 年系统构造稀疏矩阵码族（列重固定 $j=3$、消除 4 环），码率 1/2、$n=10^4$ 时距 Shannon 限约 0.3 dB 量级，并指出 LDPC 相对 turbo 的优势：无需交织器、有 Gallager 的理论根基、并行度高MacKay 1999 (IEEE Trans. Inf. Theory)。

2001 年 Richardson–Shokrollahi–Urbanke 的密度演化（density evolution）把设计变成科学：树近似下 BP 消息分布沿计算树递推，信道参数低于临界阈值时错误密度趋于零；配合不规则度分布（列重/行重按多项式 $\lambda (x),\rho (x)$ 分布）优化，正则码 dB 级的容量差距被突破到任意小Richardson, Shokrollahi & Urbanke 2001 (IEEE Trans. Inf. Theory)。同年 Chung 等人设计出码率 1/2、块长 $10^7$ 的不规则码，仿真门限距 Shannon 限仅 0.0045 dB（BIAWGN 信道）——编码理论的标志性终点数字Chung et al. 2001 (IEEE Commun. Lett.)。

结构化构造与 girth 军规

迭代译码的第一军规是避免 4 环（两列内积 $\ge 2$，等价 $H{H}^{\mathsf{T}}$ 非对角元非零），否则消息沿短环回流被重复计数（见tanner-graphs）。工程上更偏好结构化矩阵：准循环（QC）构造用循环置换矩阵（CPM）拼装 $H$，但 CPM 型子阵不可避免的 2×3 块使其 girth 上限为 12。Kasai 2025 年用仿射置换矩阵（APM）加随机序贯消环把 girth 推到 16，非二元 LDPC 经 CSS 正交条件 ${\hat{H}}_X{\hat{H}}_Z^{\mathsf{T}}=0$ 打包为量子码后，girth-16 构造 $[[806400,403200,\le 14]]$ 与 girth-12 的 $[[806400,403200,\le 9]]$ 相比：瀑布区略有损失、错误地板区大幅改善——瀑布/地板权衡的直接实验证据Kasai 2025 (arXiv)。

图:girth-16（APM 构造,码 $[[806400,403200,\le 14]]$）与 girth-12（CPM 构造,$[[806400,403200,\le 9]]$）的帧错误率对比——girth 增大以瀑布区少量损失换取错误地板的大幅下降(来源:QE030)

局限与量子去向

LDPC 的长块长带来译码延迟，错误地板来自码字谱中的低重量项（也是 girth 治理的对象）；这两点在量子侧都有对应物——量子 LDPC 的 BP 译码受简并性困扰，需要 OSD 后处理兜底（见bp-osd-decoding），而”稀疏 + 大 girth + 结构化”的构造纲领从经典到量子一脉相承（见qldpc-overview）Albert & Faist 2026 (arXiv)。

延伸阅读

• tanner-graphs
• belief-propagation
• channel-capacity
• qldpc-overview
• bp-osd-decoding