空间耦合 LDPC 码

形式陈述 ​

空间耦合 LDPC 码从一个底层 $(\ell ,r)$-regular LDPC公理库低密度奇偶校验码Low-density parity-check code · LDPC code由非零元总数随块长线性增长的稀疏校验矩阵族定义的线性纠错码。 protograph 或 ensemble 出发，把变量与校验复制到位置 $-L,\dots ,L$，再将原本同位置的边分散到宽度 $w$ 的相邻位置。每个位置通常有 $M$ 个 lifted 变量副本；两端不补成环，而是终止连接，所以边界校验的有效度较低。一个完整 ensemble 必须同时声明 $(\ell ,r,L,w,M)$、edge spreading 规则和终止方式，只写“把 LDPC 排成链”不足以确定码率或密度演化。

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

对 Kudekar–Richardson–Urbanke 的 $(\ell ,r,L,w)$ BEC ensemble，$\ell \ge 3$ 且 $w$ 足够大时，先在固定 $L,w$ 下取 lifting 极限 $M\to \mathrm{\infty }$，使有限图行为由位置型密度演化刻画；再固定 $w$ 令 $L\to \mathrm{\infty }$，最后令 $w\to \mathrm{\infty }$。标准终止的设计码率损失量级为 $O(w/L)$，常数依 edge spreading 和边界约定；实际矩阵若有相关校验，实际码率还可能高于设计值。在这一次序下有

$$R(\ell ,r,L,w)⟶1-\frac{\ell }{r}$$

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

直觉

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

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

例子与边界

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

$$v_1\oplus v_2=0,v_2\oplus v_3=0,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.
• 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.