LDPC 密度演化 | Codeboy's Blog

形式陈述

密度演化研究的对象不是一张固定校验图，而是给定度分布的随机 LDPC ensemble 在无记忆信道上运行置信传播译码时的消息分布。严格的渐近次序是：先固定迭代轮数 $t$ ，令块长 $n\to\infty$ ；随机抽取一条边后，其深度 $2t$ 邻域以高概率是一棵按度分布生长的计算树，且实际错误率集中在树模型期望附近。得到每个固定 $t$ 的确定递推后，才令 $t\to\infty$ 定义 BP 阈值。

在 BEC $(\epsilon)$ 上，消息只有“已知”与“擦除”两类。设 $x_t$ 是第 $t$ 轮变量到校验消息的擦除概率，边视角度多项式为 $\lambda,\rho$ ，则

x_{t+1} =\epsilon\,\lambda\!\left(1-\rho(1-x_t)\right), \qquad x_0=\epsilon.

解释每一层即可复得公式：校验发出的消息被擦除，当其余邻居至少一个被擦除，概率为 $1-\rho(1-x_t)$ ；变量发出的消息只有在信道符号本身擦除且其余校验消息都擦除时才擦除。最终 bit 擦除率用节点视角变量度多项式 $L$ 写为

p_t=\epsilon L\!\left(1-\rho(1-x_{t-1})\right).

BEC 的 BP 阈值是

\epsilon_{\mathrm{BP}} =\sup\{\epsilon:x_t\to0\}.

一般二元输入无记忆对称信道上，标量 $x_t$ 要换成对称 LLR 概率密度，并用变量节点卷积与校验节点的 box-plus 运算演化；只追踪平均 LLR 通常不足以闭合递推。

直觉

有限图上的消息彼此相关，直接列出联合分布几乎不可行。密度演化把观察尺度限制在固定轮数：当整体图越来越大，有限深邻域还来不及撞上圈，于是每个分支带来的信道观测独立，复杂的图算法化为一维时间递推。阈值不是某个码字突然失效的点，而是这套无限树递推的零错误不动点失去全局吸引力的位置。

这种分析同时包含 ensemble 平均与浓缩两步。仅算一棵树的期望并不能说明典型有限码；还需要证明随机图和信道噪声下的实际轨迹以高概率靠近该期望。固定轮数条件也不可删除，因为让轮数与 $n$ 同时任意增长时，计算邻域最终必然遇到圈。

例子与边界

对 $(3,6)$ -regular ensemble， $\lambda(x)=x^2$ 、 $\rho(x)=x^5$ ，所以

x_{t+1}=\epsilon[1-(1-x_t)^5]^2.

取 BEC $(0.4)$ 且 $x_0=0.4$ ，第一轮为

x_1=0.4(1-0.6^5)^2 =0.34021064704,

第二轮为

x_2 =0.4[1-(1-0.34021064704)^5]^2 \approx0.30622652488.

下降说明前两轮在清除擦除，却不能单凭两个数证明最终收敛。改变 $\epsilon$ 后可能出现正的不动点；阈值由完整递推和不动点稳定性决定。

密度演化预测的是渐近 waterfall 区域，不完整描述 finite-length error floor。短圈、stopping set、量化与最大迭代数都可能使实际曲线偏离。对 BSC、AWGN 或非对称信道直接使用上述 BEC 多项式是模型错误；对固定人工构造图直接宣称“密度演化精确”则混淆了 ensemble 极限与实例行为。

推论与应用

密度演化把度分布设计变成可计算的优化问题：调整 $\lambda,\rho$ ，可提升指定信道上的 BP 阈值，同时还要约束码率、最大度和实现成本。稳定性条件从零不动点附近的线性化给出必要或局部充分信息，EXIT/GEXIT 曲线则把不动点与面积关系可视化。空间耦合 ensemble 的阈值饱和仍以位置相关的多类型密度演化为分析核心，而不是把单一标量阈值平移。

在数值实现中，BEC 可直接迭代多项式；一般信道需离散化密度、population dynamics 或 Gaussian approximation。近似方法必须报告网格、截断与误差，否则“算得阈值”并非可复核的数学陈述。

参考资料

Thomas J. Richardson and Rüdiger L. Urbanke, “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding,” IEEE Transactions on Information Theory 47(2), 2001, 599–618.
Thomas J. Richardson, M. Amin Shokrollahi, and Rüdiger L. Urbanke, “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,” IEEE Transactions on Information Theory 47(2), 2001, 619–637.
Tom Richardson and Rüdiger Urbanke, Modern Coding Theory, Cambridge University Press, 2008, Chs. 4–5.

形式陈述 ​

反向链接

形式陈述