低密度奇偶校验码 (LDPC)
- 提出者
- Robert Gallager
- 年份
- 1962
- 类型
- linear error-correcting code
- 类别
- Coding theory
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
LDPC码由Robert Gallager于1962年发明,并在20世纪90年代由MacKay重新发现,它是由稀疏奇偶校验矩阵定义的线性纠错码。通过迭代信念传播译码,其性能可接近香农极限0.4 dB,并已成为现代无线通信(WiFi-6、5G NR、数字视频广播)的标准。与Turbo码不同,LDPC码具有更优雅的图论结构和更成熟的理论分析。
方法背后的直觉
标准的线性码使用稠密的奇偶校验矩阵,使得译码在计算上非常密集。LDPC码则相反:奇偶校验矩阵是稀疏的(大多数元素为零),因此每次奇偶校验只涉及少量比特。在接收端,构建一个二分图,其中变量节点代表传输的比特,校验节点代表奇偶校验约束。译码就变成了图上的迭代消息传递:每个变量节点从其邻居收集信息,更新其关于比特值的信念,并发送精炼后的估计值回去。稀疏性保证了快速收敛和接近香农的性能。
历史学
Gallager于1962年发明了LDPC码,但理论发展滞后于实际应用。1995年,MacKay重新发现了它们,并通过仿真证明了其接近香农的性能。21世纪初的广泛研究开发了高效的编码、译码和图构造算法。LDPC码被采用于WiFi-6 (802.11ax, 2021) 和5G NR标准 (2018)。由于性能更好、结构更清晰,它们在新系统中比Turbo码更普遍。
何时使用
在现代系统中,LDPC码因其更好的性能和更简单的架构而优于Turbo码。LDPC码适用于宽SNR范围(无阈值悬崖);它们在低SNR到高SNR下都能很好地工作。LDPC码是WiFi-6、卫星和5G NR的标准。除非需要遗留兼容性而必须使用Turbo码,否则应避免使用Turbo码。LDPC码也适用于非常短的分组(>30比特),因为其码结构是可分离的。
局限与注意事项
- 对于非常长的码(>10k比特),图构造和矩阵存储会变得复杂
- 性能对小规模图结构(环长、吸收集)敏感;需要仔细设计
- 信念传播假设无环图,但图存在环;收敛到最优解不保证
- 译码延迟(迭代次数)随SNR对数增长;不像某些经典码那样是零延迟
- 消息的量化(在定点硬件中)会影响性能;需要仔细的比特分配
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 性能接近香农极限0.4 dB(略优于Turbo码)
- 比Turbo码具有更简单的图论结构;更清晰的理论分析
- 迭代译码避免了悬崖式阈值行为(与Turbo码不同)
- 通过图构造实现灵活的码设计;易于针对特定应用进行定制
- 高效的并行译码硬件;消息传递适合VLSI/GPU实现
- 适用于长码字和中等长度码字
应用
- WiFi-6 (802.11ax):提供可靠数据传输的高吞吐量无线局域网,采用LDPC
- 5G NR:数据和控制信道的信道编码,取代了4G的Turbo码
- 卫星通信:数字视频广播 (DVB-S2) 和深空任务使用长码字LDPC
- 电力线通信 (PLC):在有噪声的电网上传输鲁棒的数据
- 闪存系统:NAND闪存存储的纠错,无需因频繁刷新而磨损
使用方式
使用方式
信息比特使用稀疏奇偶校验矩阵H进行编码;编码后的比特是满足H*c = 0 (mod 2)的解,其中c是码字。
奇偶校验矩阵H的结构被设计成稀疏的(例如,每行/每列具有恒定的低权重3-5)。这种结构被用于高效编码。
编码后的比特通过有噪声信道传输;接收到的比特是软值(似然比或对数似然比)。
构建一个二分图:左侧节点=变量节点(比特),右侧节点=校验节点(奇偶校验方程)。边连接变量与它们所属的校验。
迭代信念传播:变量节点聚合来自校验节点的消息,更新比特估计,并将精炼后的消息发送回去。经过若干次迭代后,做出硬判决;如果奇偶校验得到满足,则译码成功。
常见陷阱
- 使用具有短环的糟糕设计的稀疏图;短环会导致信念传播振荡
- 超出收敛范围进行过度迭代;不必要的迭代会浪费电力而无改进
- 假设和积译码与积和译码一样好;近似会带来性能损失,尤其是在低SNR下
- 忽略有限长度效应;为渐近分析设计的图在短分组上可能表现不佳
- 在硬件实现中未考虑量化;浮点仿真与定点实际情况不同
常见问题
与通用线性码相比,LDPC译码为何如此高效?
奇偶校验矩阵的稀疏性意味着每个比特只参与少数几个奇偶校验。在译码时,二分图上的消息传递是与边数成线性关系,而不是码长。对于稠密码,译码需要矩阵求逆,其复杂度与码长成立方关系。稀疏性使得译码近似线性且对长码是可行的。
什么是吸收集?它为什么重要?
吸收集是图中的一个小子集,它会困住信念传播译码,阻止其收敛到正确解。它们是错误地板(低SNR下BER的非指数下降)的主要来源。码设计者通过仔细的图构造来避免短吸收集;分析工具(例如,停止集分析)可以识别有问题的结构。
LDPC码与Polar码相比如何?
两者都能达到接近香农的性能。Polar码具有递归结构,在无限码长下通过连续消除译码可证明最优。LDPC码更灵活,并且经验上具有更好的有限长度性能。5G NR为控制信道(短分组)使用Polar码,为数据信道(长分组)使用LDPC码,利用了各自的优势。
为什么图的环长在LDPC码中很重要?
环长是二分图中最短环的长度。短环(环长 < 6)会导致信念传播使用相关信息(消息循环),从而降低性能。高环长码(环长 ≥ 6)能更好地打破相关性。码的设计通常是在稀疏性约束下最大化环长。
相关方法
参考文献
Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.
打开 DOI 文献已复制。Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.
打开 DOI 文献已复制。