幕雪

ldpc码从结构到应用的全方位解析


理解 LDPC 码：从其核心结构说起

LDPC码（Low-Density Parity-Check Code），即低密度奇偶校验码，是一种线性分组码。要理解LDPC码“是什么”，最核心的一点在于其名称中的“低密度”和“奇偶校验”。

低密度： 这指的是定义LDPC码的奇偶校验矩阵（Parity-Check Matrix），通常记为H，是一个极其稀疏的矩阵。也就是说，在这个矩阵中，绝大部分的元素是零，非零元素（通常是1）的数量相对非常少。这种稀疏性是LDPC码许多优良特性的基础，尤其是在译码端。

奇偶校验： 与其他线性分组码一样，LDPC码的码字必须满足一系列奇偶校验方程。每个校验方程对应H矩阵中的一行，它规定了码字中某些比特的模2和必须为零。而H矩阵的列对应于码字的比特位置。由于H矩阵是低密度的，这意味着每个校验方程只涉及码字中少数几个比特（H的行非常稀疏），同时，每个码字比特也只参与到少数几个校验方程中（H的列也非常稀疏）。

可以用一个二分图（Tanner图）来直观地表示LDPC码的结构。图中有两类节点：

  • 变量节点 (Variable Nodes)： 代表码字中的每一个比特。
  • 校验节点 (Check Nodes)： 代表每一个奇偶校验方程。

图中的边连接变量节点和校验节点，如果H矩阵中对应位置的元素是1，则在相应的变量节点和校验节点之间就存在一条边。LDPC码的低密度特性体现在这个Tanner图中的边非常少。

正是这种由稀疏校验矩阵决定的独特图结构，使得LDPC码的译码过程能够以一种高效且并行的方式进行。

LDPC码与其他纠错码有何不同？

相比于传统的纠错码，如Reed-Solomon码或卷积码：

  • 结构： LDPC码是基于大型稀疏矩阵定义的，结构非常灵活，可以构造任意长度和码率的码。Reed-Solomon码基于代数域，卷积码基于移位寄存器和状态机。
  • 译码： LDPC码主要采用迭代译码算法，特别是基于软信息的算法（如Sum-Product算法，也称信念传播算法）。这种迭代特性使其性能随着迭代次数增加而逼近理论极限。传统的码通常使用硬判决译码（如Reed-Solomon）或非迭代的软判决译码（如Viterbi对卷积码），迭代译码是LDPC码性能优越的关键。
  • 性能： 在接近香农极限的低信噪比区域，LDPC码通常能获得比Turbo码更好的性能，且在实现上更容易获得高吞吐量。
  • 复杂度： 编码相对简单，但译码计算量通常较大，不过由于其并行性好，适合硬件高速实现。

为何选择 LDPC 码：性能优势是核心

选择LDPC码的最主要原因在于其卓越的性能，尤其是在处理由高斯白噪声（AWGN）或 Rayleigh 衰落信道引起的随机错误时。

逼近香农极限： 在理论上，香农极限定义了在给定信噪比下，无误传输数据的最大速率。LDPC码被证明是一类能够非常逼近这个理论极限的码，特别是在码长很长的情况下。这意味着在同样的可靠性要求下，使用LDPC码可以比使用许多其他纠错码更有效地利用信道带宽和发射功率。

迭代译码的增益： LDPC码的性能增益很大程度上来源于其迭代译码过程。译码器在变量节点和校验节点之间反复传递“软信息”（关于比特是0还是1的概率或似然信息）。每一次迭代，这些信息都会被更新和精炼，错误比特的概率会逐渐收敛到正确的值。这种“众人拾柴火焰高”的信息协作机制，使得LDPC码能够非常有效地纠正大量的随机错误。

误码率悬崖特性： LDPC码的误码率（BER）曲线通常表现出“悬崖效应”。在达到某个信噪比阈值之前，误码率可能仍然较高，但一旦超过这个阈值，误码率会急剧下降。这种特性对于要求极低误码率的应用（如数据存储）非常有利。

简单来说，LDPC码之所以被广泛采用，是因为它能在有限的复杂度和延迟下，帮助通信或存储系统以接近理论最佳的效率可靠地传输数据。

LDPC码如何工作：编码与译码的流程

如何编码？

LDPC码的编码过程相对直接。给定一个K比特的信息向量 u，编码器的目标是生成一个N比特的码字 c (N > K)，使得 c 满足奇偶校验矩阵 H 定义的所有校验方程，即 H * cT = 0 (模2运算)。码率R = K/N。

通常，LDPC码采用系统编码，这意味着信息比特 u 直接包含在码字 c 的一部分中。码字 c 可以被分成信息部分和校验部分：c = [u | p]，其中 p 是需要计算的 (N-K) 个校验比特。

通过对H矩阵进行特定的行/列操作（类似于高斯消元，或者更常见的，对于具有特定结构的H矩阵进行简化），可以将H矩阵转换为一个更易于计算校验位的形式。如果H矩阵可以系统化表示为 H = [P | I]，其中I是单位矩阵，那么校验部分p可以通过 P * uT = pT 直接计算得到（这里涉及矩阵的转置和模2运算）。对于结构化的LDPC码，编码过程可以做得非常高效。

如何译码？

LDPC码的译码是其核心和复杂之处，主要采用迭代的软判决算法。最经典的算法是Sum-Product算法（SPA）。以下是其基本流程：

  1. 初始化： 从接收到的信号（通常是模拟或量化的）计算每个接收比特的初始软信息。这通常以对数似然比（LLR – Log-Likelihood Ratio）的形式表示。LLR是一个实数值，其符号表示对该比特是0还是1的倾向性，其绝对值表示这种倾向的可靠性。初始LLR反映了信道的噪声水平。
  2. 变量节点到校验节点的消息传递： 每个变量节点根据其接收到的来自信道的初始LLR以及前一次迭代中从所有连接的校验节点接收到的消息，计算并向其连接的每个校验节点发送消息。这个消息是对该变量节点取值的新的“信念”或估计。
  3. 校验节点到变量节点的消息传递： 每个校验节点根据其连接的所有变量节点接收到的消息，计算并向其连接的每个变量节点发送消息。校验节点的消息传递是为了满足它所代表的奇偶校验方程。这个计算涉及到所有输入消息的组合（对于SPA，是非线性的组合）。
  4. 更新变量节点的外部信息和总信念： 每个变量节点接收到所有连接的校验节点发来的新消息后，更新其关于自身取值的“外部信息”和总的“信念”（即总的LLR）。总LLR是初始LLR和所有校验节点消息的总和。
  5. 判决与停止： 根据每个变量节点的总LLR做出硬判决（LLR > 0 判为 0， LLR < 0 判为 1），形成一个候选码字。检查这个候选码字是否满足所有的奇偶校验方程（即计算H * 候选码字T 是否等于0）。如果满足，或者达到预设的最大迭代次数，则停止译码，输出硬判决结果。否则，返回步骤2进行下一轮迭代。

整个过程通过在Tanner图上的节点之间反复传递和更新消息来逼近真实码字的后验概率。校验节点负责传播校验约束信息，变量节点负责结合信道信息和校验信息更新对每个比特的估计。这种迭代过程使得信息在整个图上“扩散”，纠正错误。

LDPC码的应用场景：它们被部署在哪里？

由于其接近香农极限的优异性能和适合硬件高速实现的特点，LDPC码已成为现代通信和数据存储系统中不可或缺的一部分。它被部署在许多需要高可靠性和高效率传输的场景中。

以下是一些典型的应用“哪里”：

  • 无线通信：
    • Wi-Fi： 在 IEEE 802.11n、802.11ac、802.11ax (Wi-Fi 6/6E) 等高吞吐量无线局域网标准中，LDPC码是强制或可选的信道编码方案。
    • 蜂窝通信： 在 4G (LTE Advanced) 和 5G (NR) 标准中，LDPC码被选定用于数据信道的编码，替代了部分Turbo码的应用，以满足更高的速率和更低的延迟要求。
  • 卫星通信：
    • DVB-S2/S2X： 数字视频广播的第二代和扩展标准，广泛用于卫星电视传输，采用了LDPC码以提高传输效率和可靠性，使得卫星能传输更高清晰度或更多频道的内容。
  • 有线通信：
    • 以太网： 在高速有线以太网标准中，如 10GBASE-T (万兆以太网)，LDPC码被用于在物理层进行信道纠错。
  • 数据存储：
    • SSD/HDD： 现代固态硬盘 (SSD) 和高性能机械硬盘 (HDD) 广泛采用LDPC码来提高存储密度和可靠性。随着存储单元（如NAND闪存）的擦写次数增加，错误率会上升，LDPC码能够更有效地纠正这些错误，延长设备寿命并保证数据完整性。
  • 光通信： 在一些高速光通信系统中，LDPC码也被考虑或采纳作为前向纠错（FEC）方案。

这些应用都要求在噪声和干扰存在的情况下，能够以尽可能高的效率可靠地传输大量数据，而LDPC码恰好满足了这些需求。

关于LDPC码的“多少”：复杂度与性能的权衡

“多少”可以指代多个方面：一个LDPC码有多少参数？它的性能能达到多少？它的实现复杂度有多少？

LDPC码的参数有多少？

一个LDPC码通常由以下几个核心参数定义：

  • 码长 (N)： 码字的长度，即编码后的比特总数。
  • 信息位长 (K)： 原始信息比特的数量。
  • 码率 (R)： 定义为 K/N。表示编码效率，码率越高，冗余越少，对信道要求越高。
  • 奇偶校验矩阵 (H)： 最根本的定义，其维度是 (N-K) x N。低密度体现在非零元素的数量。
  • 节点度分布： 在Tanner图中，变量节点和校验节点连接的边数称为它们的度。LDPC码可以是正则的（所有变量节点度相同，所有校验节点度相同）或非正则的（节点度不同）。非正则LDPC码通过优化度分布，通常能获得更好的性能，但设计和分析更复杂。

LDPC码的性能能达到多少？

在理想信道条件下，LDPC码的性能可以非常接近香农极限。这通常通过误码率(BER)或误帧率(FER)曲线来衡量。在典型的AWGN信道下，长码字的LDPC码可以在距离香农容量仅0.0X dB 到 1 dB 的范围内达到极低的误码率（如 10-5 或更低）。这个差距取决于码长、码率、H矩阵结构、译码算法的精度和迭代次数。码长越长，理论上越接近香农极限，但实现复杂度也会增加。

LDPC码的实现复杂度有多少？

编码复杂度相对较低，通常与矩阵乘法相关，对于结构化码可以做得非常高效，接近线性复杂度 O(N)。
译码复杂度是主要的计算瓶颈。对于迭代译码，每轮迭代的计算量与Tanner图的边数成正比。Tanner图的边数等于H矩阵中非零元素的数量，对于一个(N-K)xN的H矩阵，如果平均列重（变量节点平均度）为dv，平均行重（校验节点平均度）为dc，那么非零元素总数约为 N * dv ≈ (N-K) * dc。因此，单次迭代的复杂度大约是 O(N * dv)。总的译码复杂度是 O(N * dv * I)，其中I是迭代次数。

与Turbo码相比，LDPC码的译码通常需要更多的计算资源（尤其是在软件实现中），但其并行性更好，更适合在硬件中实现超高速的吞吐量。现代通信系统之所以从Turbo码转向LDPC码，部分原因就在于LDPC码在高速硬件实现上的优势。

如何设计一个好的LDPC码？

设计一个高性能的LDPC码，关键在于构造或选择一个具有良好特性的奇偶校验矩阵H。好的H矩阵应该满足以下条件：

  1. 低密度： 保证译码算法的计算效率和可行性。
  2. 具有良好的图结构： 对应的Tanner图不应该包含短环（特别是长度为4或6的环）。短环会使得迭代译码中的消息传递产生强相关性，降低译码性能。Girth（图中最小环的长度）越大越好。
  3. 具有良好的度分布： 特别是非正则LDPC码，通过优化变量节点和校验节点的度分布，可以显著提升译码性能，使得误码率曲线更加陡峭，逼近香农极限。
  4. 满足特定的结构： 为了简化编码和硬件实现，实际应用的LDPC码通常具有一定的结构，而不是完全随机的。

设计方法主要有以下几类：

  • 随机构造法： 理论分析的起点，证明了随机构造的长LDPC码能够逼近香农极限。但在实际中，完全随机构造的大码可能包含短环，且编码和管理不便。
  • 代数构造法： 基于有限域、有限几何等数学结构来构造H矩阵，可以避免短环，得到结构规则且性能较好的码，如基于循环群、准循环（QC-LDPC）等。QC-LDPC码因其结构规律性，特别适合硬件实现，是目前广泛应用的LDPC码类型。
  • 图论构造法： 直接基于图的特性来构造H矩阵。
  • Protograph-based LDPC (PG-LDPC)： 这是一种非常重要的结构化LDPC码构造方法。它通过定义一个小的“基础图”（Protograph），然后通过“提升”（Lifting，即将每个节点或边复制多次并进行置换连接）的方式生成大型的Tanner图和对应的H矩阵。这种方法结合了随机码的优良性能和结构化码的易实现性，并且可以通过优化基础图来优化度分布，是5G等标准中LDPC码的主要构造思路。

LDPC码怎么实现？

LDPC码的实现主要涉及编码器和译码器的设计与制造。由于其计算需求和高速应用场景，通常在硬件中实现。

硬件实现 (ASIC/FPGA)：

高速通信系统要求编码和译码的吞吐量达到Gbps甚至Tbps级别。这需要高度并行的硬件架构。LDPC译码器的并行性是其主要优势之一。硬件实现的关键在于：

  • 并行计算单元： 设计大量的并行处理单元来同时执行变量节点更新和校验节点更新的计算。
  • 内存访问： 合理设计内存结构和访问调度，以高效地存取大量的LLR值和消息，避免内存瓶颈。LDPC码的H矩阵稀疏性使得只需存储非零元素的位置。
  • 消息传递网络： 构建高效的网络来连接变量节点处理单元和校验节点处理单元，以传递迭代消息。QC-LDPC码的环形移位结构特别有助于简化这个网络的布线。
  • 流水线设计： 将整个译码流程（包括多次迭代）设计成流水线，以最大化吞吐率。

硬件实现需要权衡性能（吞吐量、延迟、误码率）与资源消耗（门电路数量、内存大小、功耗）。不同的应用场景（如Wi-Fi、5G、SSD）对这些权衡有不同的侧重。

软件实现：

LDPC码的译码算法也可以在通用处理器（CPU）或数字信号处理器（DSP）上通过软件实现。软件实现的灵活性高，易于修改和升级算法。然而，由于迭代译码计算量较大，软件实现的吞吐量通常远低于硬件实现，适用于对速度要求不高的场景，或者作为硬件实现的辅助（例如用于研究和仿真）。软件实现需要高度优化的代码和对处理器并行特性的利用（如SIMD指令）。

在具体的系统设计中，通常会根据所需的吞吐量、延迟、功耗和成本来决定采用何种实现方式，以及选择特定结构的LDPC码（如QC-LDPC或PG-LDPC）来简化实现。


ldpc码