低密度奇偶校验码通常简称为 LDPC码,是一种由一组稀疏的奇偶校验约束定义的纠错码:每个约束只涉及相对较少的码符号,而每个符号也只参与相对较少的约束。这些局部关系共同保护一个大得多的信息块。译码器可以利用这些关系恢复在传输或存储过程中受损的数据,通常采用的方式是在符号与约束之间反复交换可靠性信息。
LDPC码的重要性在于,经过适当设计的码族能够在接近信道容量的条件下工作,同时支持高度并行的译码。信道容量是克劳德·香农确立的可靠通信的理论极限。LDPC码最早由罗伯特·加拉格于20世纪60年代初提出,在20世纪90年代重新受到关注后,成为现代编码理论的核心内容之一。如今,它们已应用于卫星广播、无线网络、第五代移动通信和存储系统。其性能取决于代数结构、图拓扑、译码算法以及实现约束的共同作用;仅有稀疏性并不能保证码的性能优良。
数学定义与奇偶校验约束
二元 LDPC 码是一种线性分组码,由具有 行、 列的稀疏奇偶校验矩阵 描述。其码字构成的集合为
其中, 是含有两个元素的有限域,所有加法和乘法运算均按模二进行。每一行规定一个奇偶校验方程:该行中值为 1 的元素所对应的码字位置,必须包含偶数个 1。该码具有线性性,因为任意两个码字按分量进行模二加法所得的结果,都满足相同的方程。如果 的秩为 ,则码的维数为 ,码率为 。因此,只有当所有行都线性无关时, 才等于实际码率。
“低密度”指的是矩阵中非零元素的数量。在通常的渐近设定下,随着码长增加,平均行重和平均列重仍保持有界,因此非零元素总数与 成正比增长,而不是与 成正比。在 正则码中,每一列的列重均为 ,每一行的行重均为 。分别按行和按列统计非零元素,可得 ,由此得到设计码率为 。因此,列重为三、行重为六的正则码,其设计码率为二分之一,不过线性相关的校验约束可能使实际码率略高一些。
下面用一个小例子加以说明。考虑矩阵
三个约束分别为 、 和 。将前三个位置选作信息位,则校验符号为 、 和 。这个矩阵只是用来说明稀疏奇偶校验方程,并不是一种在实际应用中具有竞争力的 LDPC 码设计:实际使用的码通常需要长得多的码长,以及经过更精细控制的连接结构。
对于接收到的硬判决向量 ,其伴随式译码所用的伴随式为 。伴随式中的非零分量表明某个奇偶校验约束未得到满足,但不能唯一确定出错位置。如果 ,其中 为码字,则有 。因此,纠错就是寻找一个与伴随式相符的合理错误图样,等价地说,就是寻找一个与观测结果相符的合理码字。伴随式为零只能确定该向量属于码字集合,并不能保证其正确:如果错误图样本身就是一个非零码字,这种错误便可能无法被检测出来。
发明、重新发现与理论发展
罗伯特·G. 加拉格于1960年在麻省理工学院的博士学位论文中提出了LDPC码。他的论文《低密度奇偶校验码》发表于1962年,随后又于1963年出版了专著。加拉格研究了随机构造的稀疏奇偶校验矩阵,确立了有关码距和性能的重要性质,并描述了迭代译码过程。这项开创性工作已经包含了该领域的核心特色:将稀疏约束与反复进行的局部计算相结合。它还明确指出,与分析一个逐项明确列出的码相比,分析由构造规则定义的一组码,即码集合,可能更为容易。
LDPC码在早期受到的关注程度,与当时的计算条件密切相关。采用彼时的电子技术,实现长码块以及可靠性信息的反复交换,代价十分高昂。其他编码方法,尤其是卷积码和代数分组码,在工程取舍上更具吸引力,也积累了成熟的设计技术。LDPC码并未完全销声匿迹,但其当时的受重视程度远不能与后来的重要地位相比。它们最终取得成功,并不是因为数学定义发生了变化,而是得益于算法、分析方法、存储容量和数字硬件的进步。
R. 迈克尔·坦纳于1981年开展的低复杂度码递归构造方法研究,提供了一个影响深远的图形框架。后来被称为坦纳图的这一表示方法,通过与符号变量相连的局部约束来表示一个码,而且所容纳的分量约束比单一奇偶校验更为一般。另一个转折点出现在1993年:克洛德·贝鲁、阿兰·格拉维厄和普尼亚·蒂蒂马吉希马提出了Turbo码。这类码接近信道容量的性能,展现了迭代概率译码的实际威力,也重新激发了人们对基于图的长码的兴趣。
20世纪90年代中期,戴维·麦凯和拉德福德·尼尔通过概率推断和实证性能研究,推动了稀疏奇偶校验码研究的复兴。迈克尔·卢比、迈克尔·米岑马赫、阿明·绍克罗拉希和丹尼尔·斯皮尔曼等研究者发展了非规则图的构造方法及其分析理论,尤其是在擦除信道方面。托马斯·理查森和吕迪格·厄班克在密度演化、阈值分析以及实用度分布设计方面作出了重要贡献。这些进展共同推动LDPC码从一种长期受到忽视的构造,转变为逼近通信极限的系统性框架。
进入21世纪后,LDPC码开始被纳入标准。2005年首次完成标准化的DVB-S2,将LDPC编码与外层的博斯–乔杜里–霍昆格姆码相结合。2009年获批的IEEE 802.11n将LDPC编码列为可选方案,而3GPP Release 15中的首批5G新空口规范则在主要数据信道上采用了LDPC码。这些里程碑式应用需要作出理想化渐近分析中不涉及的折中:标准需要有限的码块长度、多种码率、可复现的矩阵、高效的编码器,以及复杂度可控的译码器架构。因此,LDPC编码的发展史,也是一部将概率编码理论转化为结构化、可互操作系统的历史。
Tanner图与码的构造
Tanner图是奇偶校验矩阵的二部图表示。其中一类顶点包含 个变量节点,代表码符号;另一类顶点包含 个校验节点,代表奇偶校验方程。当且仅当 时,变量节点 与校验节点 之间有一条边。因此,列重就是变量节点的度,行重就是校验节点的度。这种表示揭示了译码信息传播所经过的邻域,也使我们能够区分矩阵的稀疏性与影响性能的更细致的拓扑结构。
环由变量节点和校验节点交替连接而成,最短环的长度称为图的围长。当两列在相同的两行中均为1时,就会形成一个四环:此时,同一对变量共同参与了两个校验。短环会使信息很快回传,从而破坏迭代译码所依赖的独立性假设。因此,避免四环是码构造中的常见目标。不过,大围长并不是衡量码质量的完整标准。度分布、扩展性、小型有害子图以及较长环的结构,都可能与最短环本身同样重要。
规则构造在图的每一侧都采用单一的节点度。非规则构造则允许多种节点度,通常将较容易确定的低度变量节点与有助于传播高可靠性信息的高度变量节点结合起来,从而改善译码门限。从边的角度定义的度分布通常写为
其中, 和 分别表示连接到度为 的变量节点和度为 的校验节点的边占全部边的比例。对应的设计码率为
优化这些分布可以使迭代译码的性能接近信道容量,但过高的节点度或过多的度为二的结构,也可能增加实现成本,或导致有限码长下的性能缺陷。
实用的构造方法包括随机布边、代数设计以及渐进边增长算法;后者在逐步添加边的同时,尽量使局部邻域保持树状结构。原模图则从一个小型二部图模板出发,模板中可以包含重边。“提升”操作将每个模板节点替换为多个副本,并将每条边替换为对应节点副本之间的一个匹配。这样既保留了模板的度结构,又能生成规模大得多的图。原模图使码族的构造具有可复现性,也便于在分析中跟踪不同类型的边。
一类尤为重要的结构化码是准循环LDPC码。它的奇偶校验矩阵由全零块和循环置换块组成,通常可以用紧凑的循环移位表来描述。这类矩阵能够减少存储需求,也很适合映射到并行硬件上。另一种重要的构造是空间耦合LDPC码,它将一条分量图链中相邻位置的节点连接起来。终止处理形成边界,使成功译码能够从边界向内部传播。耦合可以显著改善迭代译码门限,但也会带来码率、时延和窗口大小之间的权衡。
编码、码率适配与码族
奇偶校验形式的描述可直接用于校验和译码,却不一定能带来低成本的编码器。若 为生成矩阵,则消息 可编码为 ,且满足 。然而,稀疏的奇偶校验矩阵所对应的生成矩阵可能是稠密的。直接用这样的矩阵进行乘法运算,所需的计算量可能与消息长度和码长的乘积成正比,从而削弱采用稀疏构造原本希望获得的复杂度优势。因此,高效编码是一项独立的设计目标,而非低密度特性必然带来的结果。
对于系统编码,将经过适当排序的奇偶校验矩阵分块为 ,并将码字写成信息符号 在前、校验符号 在后的形式。奇偶校验约束要求
若 可逆,则有 。显式计算这个逆矩阵通常并不可取。设计者会转而将 构造成三角形、近似三角形或可递归求解的形式。例如,双对角形式的校验部分可通过类似累加器的递推运算,依次生成校验符号。更一般的预处理方法则将难以处理的部分集中到一个较小的子块中,同时使其余大部分校验计算保持稀疏。
通信系统通常需要支持多种有效码率,因为信道质量和有效载荷长度都会变化。删余与缩短提供了两种不同的适配方式。删余先编码出完整码字,但不发送选定位置上的符号。这些位置缺少信道信息,因此译码器通常将其对数似然比初始化为零。缩短则将选定的信息位置固定为已知值,通常为零,并在传输时省略这些位置。译码器将缩短位置视为已知,而非未知。删余通常会提高有效码率;缩短则会减小信息维数,而且在保留其余校验结构时,通常会降低有效码率。
码率匹配还可以重复发送选定编码位置上的符号、组合多个码块的输出,或通过循环缓冲区选择比特。这些操作必须与底层码的代数码率区分开来。一项标准可以只规定少量母码结构,却支持多种传输码块长度和有效码率。具体的映射方式至关重要:对一组在结构上重要的变量进行删余,造成的性能损失可能远大于在其他位置删去相同数量的变量。因此,码率兼容码族需要统筹图结构、传输顺序,以及译码器处理缺失观测值的方式。
非二元LDPC码将方程扩展到 等有限域上,并通过非零边标记指定域上的系数。此时,一个变量代表一个域符号,而非一个比特。这类码在短码长和中等码长下可以表现良好,也能自然地适配某些调制或存储模型。然而,其译码器传递的消息通常涉及多个符号取值的概率,而非单个二元可靠性数值。这会增加运算、存储和互连成本。因此,选择二元还是非二元构造,取决于信道、码长、目标错误概率以及可用的硬件资源。
迭代译码与可靠性消息
典型的 LDPC 译码器在 Tanner 图上使用置信传播,也称为和积算法。它以各变量的信道观测信息为起点,沿图的边反复交换局部消息。从变量节点发往校验节点的消息,将信道观测与该变量的其他校验节点提供的信息相结合。从校验节点发往变量节点的消息,则表示在已知其他变量相关信息的情况下,该奇偶校验方程对目标变量的约束。每次更新都排除接收消息的那条边所传入的信息,从而得到外信息,减少对同一证据的即时重复利用。在无环图上,这一过程可以计算出精确的边缘概率;而在有环的 LDPC 图上,所得结果通常是近似的。
对于二元输入,信道观测信息通常用对数似然比表示:
正值倾向于判为零,负值倾向于判为一,绝对值则衡量置信程度。令 表示与变量 相邻的校验节点集合, 表示与校验节点 相邻的变量节点集合。从变量节点发往校验节点的消息满足:
二元奇偶校验节点的更新公式为:
将所有传入的校验节点消息与 相加,即得到后验可靠性估计。随后进行硬判决,并检验判决结果是否满足奇偶校验约束。
直接计算双曲函数的开销较大,因此实际实现中常采用近似方法。最小和更新将各输入消息的符号相乘,并取其中最小的绝对值作为输出消息的幅度。相较于精确的和积结果,这样得到的幅度往往偏大,因此又衍生出归一化最小和与偏移最小和两种方法:前者按比例缩小幅度,后者减去一个非负偏移量,并将结果下限截为零。校验节点只需计算一次最小和次小幅度,即可在各条输出消息中重复利用。只要参数和量化方式选择得当,这些简化就能大幅减少运算量,同时通常保留完整译码器的大部分性能。
更新调度方式也会影响收敛。泛洪译码分阶段更新全部校验节点和全部变量节点。分层译码则依次处理各组校验节点,并立即将每组产生的新信息用于后续计算。分层译码通常所需的迭代次数较少,但计算之间的依赖关系可能使并行执行更加复杂。译码通常在暂定码字满足全部校验约束,或达到迭代次数上限时停止。检验伴随式是否为零是一种高效的停止判据,但不能排除收敛到错误码字的可能。额外引入一个外层检错码,可以提供独立的检验。
其他译码器则用于满足不同的成本和可靠性要求。加拉格的硬判决算法及后来的比特翻转方法,根据未满足的校验约束翻转变量值,使用的可靠性信息要少得多。在二元擦除信道上,剥离译码反复利用恰好包含一个被擦除变量的校验方程求解该变量。在复杂度范围的另一端,基于优化的方法和后处理方法可以处理普通消息传递译码未能纠正的错误。选择合适的算法,不仅取决于其本身的纠错能力,还取决于吞吐量、功耗、时延限制,以及接收机或存储设备能够提供的可靠性信息。
容量、译码门限与渐近分析
信息论区分了理论上可以达到的性能与特定译码器能够实现的性能。对于容量为 的信道,在满足渐近假设的条件下,香农编码定理表明,以低于 的速率通信,可以将差错概率降至任意低的水平。这并不意味着所有码率低于容量的码都能可靠工作,也不意味着低复杂度译码器能够达到与最优译码相同的极限。LDPC 码集具有与其迭代译码器相关的门限:粗略地说,在相应分析中,先让码长趋于无穷,再让迭代次数趋于无穷,预测的差错概率仍能趋于零时所允许的最大信道劣化程度,就是这一门限。
密度演化跟踪译码器消息的概率分布如何随迭代而变化。对于随机稀疏图集,随着码长增大,固定深度的邻域不含环的概率越来越高。因此,在码集分析中,可以将进入局部计算的消息视为相互独立。对于一般信道,这需要跟踪完整的分布,或采用适当的近似。通过改变信道条件,并判断消息分布是否收敛至能够作出可靠判决的状态,就可以确定门限。这一结果刻画的是码集和算法的性质,并不保证从该码集中抽取的每一个有限图都具有相同性能。
二元擦除信道的递推关系尤其直观。假设每个传输比特都以概率 独立地被擦除,且 表示第 次迭代中,从变量节点发往校验节点的消息被擦除的概率,则有
只有当其余所有相邻变量均已知时,校验节点才能确定一个变量的值;如果一个变量被信道擦除,且未收到任何能够确定其值的校验消息,它就仍然未知。这两点给出了上述递推关系。对于 正则码集,递推关系变为
其置信传播译码门限约为 ,低于码率为二分之一时擦除信道的容量边界 。
优化非正则度分布可以缩小这一差距,而空间耦合则提供了一种更深层的机制,称为门限饱和。在适当的信道和码集条件下,耦合码集的迭代译码门限会趋近于其底层未耦合码集的最大后验译码门限。有利的边界条件会启动一股沿链传播的译码波。这并不意味着每一种耦合码都能自动达到容量:底层码集、节点度的选择、终止方式以及渐近极限仍然十分重要。有限长度的链还可能带来码率损失,并需要相当大的译码窗口。
距离与译码门限描述的是不同性质。最小距离是非零码字的最小汉明重量,决定了最优译码下最坏情况下的纠错能力。适当的 LDPC 码集可以具有随码长线性增长的最小距离,但译码器仍可能在规模小得多的错误模式下译码失败。反过来,良好的迭代译码门限本身也不足以证明码具有优良的最小距离特性。因此,可靠的码设计既需要渐近分析,也需要有限码长研究;接近容量的程度只是性能的一个方面。
有限码长下的性能与错误平层
实际的 LDPC 码所用的图规模有限,数值精度有限,允许的迭代次数也有限。其错误率曲线通常包含一个瀑布区:信道质量稍有改善,错误率就会急剧下降;在某些情况下,随后还会出现错误平层区,错误率的下降速度在此明显放缓。瀑布区主要反映了迭代门限附近的整体收敛行为,而错误平层往往受罕见的局部结构或低重量码字支配。错误平层的位置和斜率取决于码、信道、译码器、调度方式以及数值实现,因此并不是 LDPC 编码所固有的、普遍不变的特征。
在二元擦除信道上,主要障碍是停止集:它是一组变量节点,与之相邻的每个校验节点都至少有两个邻居位于该集合中。如果恰好这些位置仍处于擦除状态,那么所有相邻的校验节点都不只含有一个待求的未知量,剥离译码便会停止。更一般地说,只要被擦除的位置中包含非空停止集,译码就会失败。最小停止集的大小决定了停止距离。这一图性质与最小距离密切相关,但两者并不相同;它描述的是某一种特定迭代恢复机制的失效。
对于观测值受到噪声干扰而非被擦除的信道,有害的结构通常用陷阱集或吸收集来描述。常见的 记法表示:由 个变量节点所诱导的子图中,存在 个奇数度校验节点。较小的 可能意味着,某种错误的局部判决模式仅违反少数校验约束,从而使相互强化的错误消息得以持续存在。吸收集还须满足额外的局部条件,这些条件有助于解释它们为何能在某些译码器下保持稳定。仅凭这类记法都无法完整预测一次译码失败,因为输入的信道观测值和具体的更新规则同样重要。
图中的环会引入相关性,但仅仅消除最短的环,并不能消除所有错误平层。两个围长相同的图,其有害结构的数量和类型可能大相径庭。因此,实际构造时可能需要排查特定子图、约束短环的连接方式、仔细选择循环移位量,或加强对易出错变量节点类型的保护。改进译码器也可能有所帮助:调整调度方式、消息限幅策略、可靠性扰动或有限的后处理,都可能使译码摆脱基准译码器无法克服的失败状态。评估这些干预措施时,必须权衡其带来的额外时延,以及把原本正确的判决改错的可能性。
极低的错误概率很难通过直接仿真测量。如果目标误块率为 ,那么通过普通的独立试验观察到足够数量的失败事件,可能需要处理极其庞大的码块数。重要性采样、解析界、定向搜索以及主导结构枚举可以减轻这一负担,但每种方法都有自身的假设和潜在盲点。报告性能时,应区分误比特率与误块率,说明译码算法和迭代次数上限,并明确所采用的信道。在短时间瀑布区仿真中表现优异的码,仍可能不适合可靠性要求深入错误平层区的存储或通信系统。
译码器架构与实现中的权衡
当节点度数有界时,一轮消息传递迭代所需的运算量与 Tanner 图的边数成正比,而边数又与码长成正比。若进行 轮迭代,基本估算为需要 次算术运算。这种有利的时间复杂度是 LDPC 译码颇具吸引力的重要原因,但它并不能反映全部实现成本。消息还需要存储、路由、更新和同步。在高吞吐量译码器中,数据搬移和互连的开销可能超过算术运算,尤其是在图结构不规则或缺乏紧凑的结构化表示时。
全并行架构为变量节点、校验节点及其连接边配置大量硬件。它可以实现极高的吞吐量,但也会消耗大量芯片面积和布线资源。部分并行设计则让较少的处理单元在图的多个部分之间复用,以增加处理周期为代价来减小面积。准循环矩阵尤其适合这种设计,因为循环置换可以通过规则的移位网络和可预测的存储器寻址来实现。基于专用集成电路的设计可以对数据通路和存储器进行专门优化,而可编程实现则更注重灵活支持多种码长和码率。
存储器访问往往是关键瓶颈。分层译码需要快速访问更新后的变量可靠度和边消息;多个单元访问同一存储体时,并行校验处理可能引发冲突。设计人员通过选择层处理顺序、划分矩阵和安排存储体来避免这些冲突。对校验节点消息采用紧凑表示可以减少存储需求,例如在最小和译码中,仅保存符号位和少数几个最小幅值。在图形处理器上,批量处理码字可以提供大量并行计算机会,但不规则访存和单个码块的处理时延可能限制效率。
有限精度算术带来了另一个设计维度。信道输入、内部消息、累积可靠度和修正因子可以采用不同的位宽。位数过少会掩盖可靠度之间的细微差异;动态范围过窄会导致饱和;精度过高则会增加存储器访问量和算术运算成本。最佳量化方案取决于具体的码和译码器,并不存在通用的最优字长。校验更新公式也需要注意数值稳定性:当自变量接近极限值时,直接以浮点运算计算反双曲函数可能变得不稳定。因此,硬件通常采用变换后的表达式、查找表、近似算法或最小和算法的变体。
吞吐量、时延和能耗必须分别报告。较长的码块可以改善编码性能并分摊控制开销,但也会推迟完整码块到齐的时间,并需要更多缓冲空间。提前终止可减少易译码块的处理工作量,而最坏情况下的迭代次数上限决定了能够保证的处理能力。自适应调整迭代次数或精度可以降低平均能耗,但会使时序设计和验证更加复杂。即使电池供电的接收机、光链路和存储控制器采用同一个 LDPC 码族,最适合其中接收机的译码器也未必适合另外两者。
通信、存储与量子扩展
卫星广播是现代 LDPC 编码较早实现大规模应用的领域之一。DVB-S2 采用长码块 LDPC 码,并以 BCH 码作为外码,在提供强大纠错能力的同时,利用外码处理残余差错。其常规和短 LDPC 帧的长度分别为 64,800 比特和 16,200 比特。多种码率使系统能够在有效载荷传输效率与所需信号质量之间作出不同权衡。这种组合至关重要:实际部署的系统并非只有一个孤立的奇偶校验矩阵,而是一套涵盖成帧、调制、码率选择、内码译码和外码纠错的完整方案。
无线系统更注重可变的有效载荷大小和时延。IEEE 802.11n 规定的 LDPC 码字长度为 648、1,296 和 1,944 比特,码率包括二分之一、三分之二、四分之三和六分之五。在 5G 新空口中,LDPC 编码用于保护上行和下行共享数据信道。通过两种基图、多种提升尺寸、码块分段和速率匹配,系统能够支持范围广泛的传输块大小和有效码率。这些数据信道编码方案与其他编码方法并存:若干控制信息功能采用极化码,这说明同一种无线通信标准可以根据不同需求选择不同的码族。
在存储领域,LDPC 码用于固态硬盘以及其他基于闪存的系统。控制器可以采用额外的阈值设置来读取存储单元,从而获得软信息,给出比单次硬判决更充分的似然估计。更强的译码能力可以使设备在更严苛的差错条件下继续工作,但额外的感测和迭代处理也会增加读取时延与能耗。实际器件的特性还会随磨损程度变化,并表现出数据保持效应和不均匀的差错模式。因此,准确的信道估计,以及将感测值恰当映射为译码器所用可靠度的方法,可能与码的标称参数同样重要。
LDPC 码与里德—所罗门码等代数码,在表示方式和典型译码策略上都有区别。里德—所罗门码以较大的符号为运算单位,具有强有力的代数保证,适于处理符号差错和突发差错。二元 LDPC 码通常利用软信息和大规模稀疏图,使性能逼近信道的概率极限。这两个码族都不能在所有场景中取代对方。级联、交织和混合架构可以结合二者互补的优势;至于是优先考虑平均译码性能、有保证的纠错半径、突发差错容忍能力,还是实现的简便性,则取决于应用需求。
这一术语在量子纠错中还有一种独特的扩展。量子 LDPC 码的稳定子校验具有有界的重量,且每个物理量子比特参与的校验数量也有界。与经典奇偶校验方程不同,量子校验必须满足对易约束。在 Calderbank–Shor–Steane 构造中,二元矩阵满足 ,从而将用于检测不同泡利错误的结构联系起来。量子译码还必须考虑简并性:不同的物理错误模式可能对编码信息产生相同的影响。帕维尔·潘捷列耶夫和格列布·卡拉切夫在 2022 年的工作确立了渐近良好量子 LDPC 码的存在性,其编码维数和码距都与码长成正比。要将此类构造转化为容错架构,还需要可实现的连接结构、反复提取伴随式,以及在测量存在差错时进行译码的能力。