空间耦合 LDPC 码 | Codeboy's Blog

形式陈述

空间耦合 LDPC 码从一个底层 $(\ell,r)$ -regular LDPC protograph 或 ensemble 出发，把变量复制到位置 $-L,\ldots,L$ ，再把它们的边分散到宽度 $w$ 的相邻校验位置；校验位置须随所选窗口延伸到边界之外，不能默认与变量位置完全相同。每个位置通常有 $M$ 个 lifted 变量副本；两端不补成环，而是终止连接，所以边界校验的有效度较低。一个完整 ensemble 必须同时声明 $(\ell,r,L,w,M)$ 、edge spreading 规则和终止方式，只写“把 LDPC 排成链”不足以确定码率或密度演化。固定度数和位置参数、令 $M$ 增长时，每个 lift 仍有 $O(n)$ 条边，因此构成 LDPC 码族的一个特殊构造。

对 BEC $(\epsilon)$ ，位置相关的变量到校验擦除概率组成向量 $x_i^{(t)}$ 。一次更新先在耦合窗口内平均相邻变量消息，经校验变换 $1-(1-x)^{r-1}$ ，再跨窗口平均并取变量幂 $\ell-1$ ；边界外位置视为已知，因此靠近端点的擦除率先下降。精确递推依所选 edge spreading 而异，不能用未耦合的单标量公式代替。其阈值由LDPC 密度演化在 $M\to\infty$ 后定义。

对 Kudekar–Richardson–Urbanke 的 $(\ell,r,L,w)$ BEC ensemble，下面采用正设计码率范围 $3\le\ell<r$ ，并取正整数 $L,w$ 及满足构造整除条件的 $M$ 。其变量位置为 $[-L,L]$ ；位置 $i$ 的变量向 $i,\ldots,i+w-1$ 的校验窗口随机连接，所以可能关联的校验位置延伸到 $L+w-1$ 。当 $w$ 满足原定理的充分大条件时，先在固定 $L,w$ 下取 lifting 极限 $M\to\infty$ ，在固定迭代轮数下使有限图行为由位置型密度演化刻画，随后按迭代轮数趋于无穷定义逐比特擦除阈值；再固定 $w$ 令 $L\to\infty$ ，最后令 $w\to\infty$ 。标准终止的设计码率损失量级为 $O(w/L)$ ，常数依 edge spreading 和边界约定；实际矩阵若有相关校验，实际码率还可能高于设计值。在这一次序下有

R(\ell,r,L,w)\longrightarrow1-\frac\ell r

且耦合 ensemble 的 BP 阈值趋于底层未耦合 $(\ell,r)$ ensemble 的 MAP 阈值。这是 threshold saturation；它比较的是同一底层 ensemble 的 BP 与 MAP 阈值，不是把阈值无条件提升到任意信道的 Shannon 容量。

直觉

终止边界缺少来自链外的未知变量，因而局部约束相对更强。BP 先在边界获得可靠消息，随后已解区域又成为下一位置的新边界，形成向链内部推进的译码波。长链中边界只占很小比例，所以码率损失趋零；但边界产生的“成核点”仍能改变整条链的算法阈值。

这不是简单地把许多独立 LDPC 块串接起来。耦合边跨越多个位置，单个校验同时联系相邻截面的变量；译码波依赖这种重叠。若改用环形 tail-biting 消除边界，设计码率损失消失，天然成核点也随之消失，通常需要 doping、已知 seed 或非均匀信道来重新触发波。

空间耦合 LDPC 码：终止 Tanner 链上的四步 peeling 译码波 — 空间耦合 LDPC 码示意图

例子与边界

一个刻意缩小的 peeling 轨迹能显示波的方向。设变量 $v_1,v_2,v_3,v_4$ 起初都在 BEC 中擦除，终止产生边界 degree-one 校验 $v_1=0$ ，并有相邻校验

v_1\oplus v_2=0,\quad v_2\oplus v_3=0,\quad v_3\oplus v_4=0.

边界先恢复 $v_1$ ，随后三条二元校验依次恢复 $v_2,v_3,v_4$ 。这个小链的码率损失被夸大，不能用来计算真实 ensemble 阈值，却可逐步核对“低度边界—波前推进”的机制。

数值上，BEC 上未耦合 $(3,6)$ ensemble 的 BP 阈值约为 $0.42944$ ，MAP 阈值约为 $0.488151$ ；适当耦合并扩大 $L,w$ 后，BP 阈值趋近后者，同时设计码率趋近 $1/2$ 。有限 $L$ 有非零 rate loss，有限 $w,M$ 有波速和缩放效应；窗口译码还在内存、时延与性能间折衷。BEC 上的严格定理也不能省略技术条件后宣称适用于所有 BMS 或有记忆信道。

推论与应用

空间耦合把一个全局较强、算法较难达到的 MAP 阈值转化为局部 BP 可达的传播现象，并在一系列稀疏图模型中呈现类似的势垒消失机制。工程上可用 sliding-window decoder 只保存波前附近的位置，使延迟不随整条链长度线性增长；窗口过小则可能让波停滞。

讨论容量逼近时还需区分两个极限：固定 $(\ell,r)$ 的饱和目标是其 MAP 阈值；再让度数增长并控制设计码率，MAP 阈值才可能逼近 BEC 容量。把这两步合并，会掩盖 ensemble、顺序极限和复杂度的实际代价。

参考资料

A. Jiménez Felström and Kamil Sh. Zigangirov, “Time-Varying Periodic Convolutional Codes with Low-Density Parity-Check Matrix,” IEEE Transactions on Information Theory 45(6), 1999, 2181–2191.
Shrinivas Kudekar, Tom Richardson, and Rüdiger Urbanke, “Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so Well over the BEC,” IEEE Transactions on Information Theory 57(2), 2011, 803–834，§II 的 ensemble 定义、Theorem 10 的顺序极限与充分大窗口条件。
Shrinivas Kudekar, Tom Richardson, and Rüdiger Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation,” IEEE Transactions on Information Theory 59(12), 2013, 7761–7813.

形式陈述 ​

形式陈述