低密度奇偶校验码 | Codeboy's Blog

形式陈述

二元低密度奇偶校验码由校验矩阵 $H\in\mathbb F_2^{m\times n}$ 的零空间

C=\{x\in\mathbb F_2^n:Hx^T=0\}

给出。名称中的“低密度”是码族而非一张有限矩阵的性质：对块长 $n\to\infty$ 的矩阵列 $(H_n)$ ，非零元总数应为 $O(n)$ ，常见的更强假设是行重、列重都被与 $n$ 无关的常数控制。这样每轮校验或消息更新只需处理线性数量的边。矩阵的秩可能小于行数，所以实际维数是 $k=n-\operatorname{rank}H$ ；仅从 $m$ 条已写出的校验只能得到设计码率下界 $1-m/n$ ，不能自动认定实际码率恰好等于它。

规则 $(d_v,d_c)$ 家族要求每列重量为 $d_v$ 、每行重量为 $d_c$ ，其设计码率为 $1-d_v/d_c$ 。不规则家族通常用边视角度分布

\lambda(x)=\sum_i\lambda_i x^{i-1},\qquad \rho(x)=\sum_j\rho_j x^{j-1}

描述随机选一条边后所见的变量度与校验度；相应设计码率为

R_{\mathrm{des}} =1-\frac{\int_0^1\rho(x)\,dx}{\int_0^1\lambda(x)\,dx}.

校验矩阵可画成Tanner 图：列是变量节点，行是校验节点，非零元是边。稀疏性因此成为有界度局部约束，而不是“矩阵里看起来有很多零”的视觉判断。

直觉

LDPC 码用大量很小的局部约束塑造一个全局码空间。每个校验只检查少数符号，每个符号也只参加少数校验；单条约束很弱，但许多约束按合适图结构交叠后，可以产生正的相对距离，并让局部软信息在图上逐轮传播。稀疏同时解释了译码为何便宜，也解释了性能为何敏感于图结构：若局部邻域在若干轮内像树，消息携带的证据近似独立；短圈密集时，同一证据会很快绕回原处。

“低密度”不意味着生成矩阵也稀疏。由 $H$ 消元得到的生成矩阵往往是稠密的，朴素编码仍可能需要二次时间。实际系统会选择准循环、近三角或可分块消元的校验结构，把容易实现的编码器与适合迭代译码的图同时纳入设计。

例子与边界

考虑

H= \begin{pmatrix} 1&1&1&0&0&0\\ 0&0&1&1&1&0\\ 1&0&0&0&1&1 \end{pmatrix}.

三行线性无关，所以这是一个 $[6,3]$ 码。令 $x_1=a,x_3=b,x_5=c$ ，三条校验依次给出

x=(a,a+b,b,b+c,c,a+c).

取 $(a,b,c)=(1,0,1)$ 得到码字 110110；逐行相加分别是 $0,0,0$ 。矩阵每行重量为 $3$ ，列重量交替为 $2$ 与 $1$ ，适合展示局部约束，却不能凭这一张六列矩阵宣称得到了 LDPC 家族。若以它作 protograph 并做越来越大的 lift，同时保持每个节点度数不变，才得到符合渐近稀疏定义的候选家族。

稀疏性本身不保证好距离或接近容量。两列完全相同会立刻产生重量二码字；短圈、stopping set 与 trapping set 会造成有限长度 error floor。增加冗余校验不改变码空间，却会改变图和迭代过程。相反，删除线性相关行可能保持码不变，但破坏原先有利的消息传播结构。因此讨论“某个 LDPC 码”时，应分别声明码空间、采用的校验表示、信道以及译码算法。

推论与应用

有界度使综合计算和一轮消息传递都只需 $O(n)$ 次局部操作。适当设计的不规则 ensemble 可在特定无记忆信道上逼近容量，而准循环 LDPC 便于存储校验连接并并行实现。现代无线、卫星链路和存储系统使用的往往不是任意稀疏矩阵，而是经过 girth、度分布、最小距离、lifting 与硬件互连共同约束的结构化实例。

后续分析要保持三个层次分离：码由 $Hx^T=0$ 定义；图由所选 $H$ 定义；概率译码的阈值还依赖信道、调度与块长极限。把三者压成一句“LDPC 因为稀疏所以接近容量”，会遗漏真正需要证明的条件。

参考资料

Robert G. Gallager, Low-Density Parity-Check Codes, MIT Press, 1963.
Tom Richardson and Rüdiger Urbanke, Modern Coding Theory, Cambridge University Press, 2008, Chs. 3–4.
David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, Ch. 47.

形式陈述 ​

反向链接

形式陈述