Skip to content
返回搜索结果

低密度奇偶校验码 (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闪存存储的纠错,无需因频繁刷新而磨损

使用方式

使用方式

1

信息比特使用稀疏奇偶校验矩阵H进行编码;编码后的比特是满足H*c = 0 (mod 2)的解,其中c是码字。

2

奇偶校验矩阵H的结构被设计成稀疏的(例如,每行/每列具有恒定的低权重3-5)。这种结构被用于高效编码。

3

编码后的比特通过有噪声信道传输;接收到的比特是软值(似然比或对数似然比)。

4

构建一个二分图:左侧节点=变量节点(比特),右侧节点=校验节点(奇偶校验方程)。边连接变量与它们所属的校验。

5

迭代信念传播:变量节点聚合来自校验节点的消息,更新比特估计,并将精炼后的消息发送回去。经过若干次迭代后,做出硬判决;如果奇偶校验得到满足,则译码成功。

常见陷阱

  • 使用具有短环的糟糕设计的稀疏图;短环会导致信念传播振荡
  • 超出收敛范围进行过度迭代;不必要的迭代会浪费电力而无改进
  • 假设和积译码与积和译码一样好;近似会带来性能损失,尤其是在低SNR下
  • 忽略有限长度效应;为渐近分析设计的图在短分组上可能表现不佳
  • 在硬件实现中未考虑量化;浮点仿真与定点实际情况不同

常见问题

与通用线性码相比,LDPC译码为何如此高效?

奇偶校验矩阵的稀疏性意味着每个比特只参与少数几个奇偶校验。在译码时,二分图上的消息传递是与边数成线性关系,而不是码长。对于稠密码,译码需要矩阵求逆,其复杂度与码长成立方关系。稀疏性使得译码近似线性且对长码是可行的。

什么是吸收集?它为什么重要?

吸收集是图中的一个小子集,它会困住信念传播译码,阻止其收敛到正确解。它们是错误地板(低SNR下BER的非指数下降)的主要来源。码设计者通过仔细的图构造来避免短吸收集;分析工具(例如,停止集分析)可以识别有问题的结构。

LDPC码与Polar码相比如何?

两者都能达到接近香农的性能。Polar码具有递归结构,在无限码长下通过连续消除译码可证明最优。LDPC码更灵活,并且经验上具有更好的有限长度性能。5G NR为控制信道(短分组)使用Polar码,为数据信道(长分组)使用LDPC码,利用了各自的优势。

为什么图的环长在LDPC码中很重要?

环长是二分图中最短环的长度。短环(环长 < 6)会导致信念传播使用相关信息(消息循环),从而降低性能。高环长码(环长 ≥ 6)能更好地打破相关性。码的设计通常是在稀疏性约束下最大化环长。

相关方法

参考文献

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    打开 DOI 文献
    已复制。
  2. 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 文献
    已复制。