ldpc码编解码原理基本概念与操作流程详解

低密度奇偶校验码（LDPC码）是现代通信系统中一种性能优秀的纠错码。与传统的块码或卷积码相比，LDPC码以其逼近香农极限的纠错性能和相对较低的解码复杂度而著称。理解LDPC码的关键在于掌握其编码和解码的基本原理，特别是围绕其核心结构——低密度奇偶校验矩阵（H矩阵）和基于图的迭代解码算法。

什么是LDPC码？

从原理上讲，LDPC码是一种线性分组码，由一个具有“低密度”特性的校验矩阵H定义。这里的“低密度”指的是矩阵H中非零元素的数量相对于矩阵的总大小非常少。通常，矩阵的行重（每行非零元素数量）和列重（每列非零元素数量）都很小且相对均匀。

校验矩阵 H (Parity-Check Matrix): LDPC码由一个m行n列的二元矩阵H定义，其中m是校验方程的数量，n是码字的长度。一个合法的码字c必须满足方程 Hc^T = 0（在GF(2)域上进行运算，即异或运算）。矩阵H的稀疏性是LDPC码的根本特征。
生成矩阵 G (Generator Matrix): 与所有线性分组码一样，LDPC码也有一个生成矩阵G，用于将k位信息比特u编码成n位码字c (c = uG)。然而，对于LDPC码，生成矩阵G通常不如校验矩阵H那样稀疏，因此在编码时，我们往往更倾向于利用H矩阵的结构，尤其是在系统码中。
Tanner图 (Tanner Graph): 为了更直观地理解和进行解码，LDPC码通常用一个二部图表示，称为Tanner图。图中有两种类型的节点：
- 变量节点 (Variable Nodes, VN): 对应于码字的每个比特位（共n个）。
- 校验节点 (Check Nodes, CN): 对应于校验矩阵H的每个校验方程（共m个）。
在Tanner图中，如果校验矩阵H的第i行第j列的元素H_i,j是非零的（即为1），则在Tanner图中连接第j个变量节点和第i个校验节点。Tanner图的稀疏性直接反映了H矩阵的低密度特性。

编码原理：如何将信息变成LDPC码字？

LDPC码的编码是将k个信息比特u转化为n个码字c的过程，使得Hc^T=0。虽然可以使用生成矩阵G进行编码(c=uG)，但这需要复杂的G矩阵计算。更常见且高效的方法是利用H矩阵进行系统编码。

系统编码基于H矩阵

系统编码将码字c分为两部分：k个信息比特u和p=n-k个校验比特b。即 c = [u | b]。目标是找到b，使得H[u | b]^T = 0。

如果校验矩阵H可以经过列置换和高斯消元转化为以下形式：

H = [P | I_p]

其中 I_p 是p×p的单位矩阵，P是m×k（此时m=p）的矩阵。在这种规范形式下，校验方程 Hc^T = 0 变为：

[P | I_p] [u | b]^T = Pu^T + I_pb^T = Pu^T + b^T = 0

因此，校验比特可以简单计算为：

b^T = Pu^T (在GF(2)域上运算)

实际应用中的H矩阵可能不是这种规范形式，但可以通过高斯消元（可能会破坏稀疏性）或更先进的结构化编码技术（如PEG算法构建的准循环LDPC码，QC-LDPC）来找到一个等价的、适合系统编码的H矩阵形式，或者通过迭代方法求解校验比特。

总的来说，编码的原理是找到一个满足校验方程组 Hc^T = 0 的码字c，其中c的前k位通常就是信息比特u（系统码的情况下）。

解码原理：如何从噪声中恢复原始信息？

LDPC码最强大之处在于其高效的迭代解码算法，尤其是基于概率的“信念传播”（Belief Propagation, BP）算法，也称为“和积算法”（Sum-Product Algorithm, SPA）。这种算法利用了Tanner图的结构和接收到的带有噪声的软信息（通常是对数似然比 LLR）。

为什么使用迭代解码和软信息？

传统的硬判决解码只使用接收信号的硬比特值（0或1），丢弃了信号的可靠性信息。软判决解码则利用接收信号的模拟值，通过计算每个比特是0或1的概率（或LLR）来进行决策，这能显著提高解码性能。

迭代解码则是在Tanner图上，让变量节点和校验节点之间通过交换可靠性信息（信念）来逐步修正对每个码字比特的估计。这种迭代过程允许信息在图上传播和聚合，利用了码字的全局约束（校验方程）来纠正局部错误。

信念传播 (Sum-Product Algorithm) 工作流程

BP算法在Tanner图上进行，核心思想是变量节点向连接的校验节点发送关于其对应比特是0或1的“信念”，校验节点根据接收到的信念和自身的校验方程规则，计算并发送更新的信念回变量节点。这个过程重复进行，直到找到一个有效的码字（满足所有校验方程）或达到最大迭代次数。

在LLR域进行和积算法是实现上的标准做法，避免了概率域乘法带来的数值稳定性问题。

1. 初始化

对于每个接收到的软信号y_j（对应码字比特c_j），计算其初始的对数似然比L_j：

L_j = log( P(y_j | c_j=0) / P(y_j | c_j=1) )

这个初始LLR表示接收端对第j个比特是0（正LLR）还是1（负LLR）的原始置信度。这些LLR被发送到Tanner图上对应的变量节点VN_j。

2. 迭代过程

迭代包含两个主要步骤：

a. 变量节点到校验节点的更新 (VN -> CN)

每个变量节点VN_j向其连接的每个校验节点CN_i发送一个LLR消息 R_j→i。这个消息表示VN_j除了从CN_i接收到的信息外，结合所有其他信息源（初始LLR和来自其他CNs的信息）后，对比特c_j的信念。

R_j→i = L_j + Σ_{k ∈ N(j) \ {i}} Q_k→j

其中：

L_j 是初始的接收端对比特j的LLR。
N(j) 是与VN_j连接的所有校验节点的集合。
Σ_{k ∈ N(j) \ {i}} Q_k→j 是VN_j从除了CN_i之外的所有其他连接的校验节点接收到的LLR之和。
Q_k→j 是CN_k发送给VN_j的LLR消息（在CN -> VN 更新步骤中计算）。

本质上，R_j→i 是对比特c_j的“外部信息”（extrinsic information），即不包含来自CN_i自身的信息。

b. 校验节点到变量节点的更新 (CN -> VN)

每个校验节点CN_i向其连接的每个变量节点VN_j发送一个LLR消息 Q_i→j。这个消息表示CN_i根据其校验方程以及从除VN_j之外所有连接的变量节点接收到的信息，对比特c_j的信念。

校验节点执行的运算在LLR域有点特殊，它是基于如下事实：对于一个校验方程 Σ c_k = 0 (mod 2)，如果除一个比特外的所有比特值都已知，那么这个未知比特的值也就确定了。

LLR域的CN更新公式是：

Q_i→j = artanh( Π_{k ∈ M(i) \ {j}} tanh(R_k→i / 2) ) * 2

或者使用更数值稳定的形式：

Q_i→j = ( Π_{k ∈ M(i) \ {j}} sign(R_k→i) ) * min_{k ∈ M(i) \ {j}} |R_k→i|

其中：

M(i) 是与CN_i连接的所有变量节点的集合。
Π_{k ∈ M(i) \ {j}} sign(R_k→i) 是除了VN_j之外所有连接的变量节点发送给CN_i的LLR消息符号的乘积。
min_{k ∈ M(i) \ {j}} |R_k→i| 是除了VN_j之外所有连接的变量节点发送给CN_i的LLR消息绝对值的最小值。

这个Q_i→j消息是对比特c_j的外部信息，由校验节点i根据其校验方程和其他输入变量节点的信息计算得出。

3. 计算后验LLR (A Posteriori LLR)

在每次迭代结束时（通常是在CN到VN更新后），每个变量节点VN_j计算其对应比特c_j的后验LLR L_post_j。这个后验LLR结合了所有的信息来源（初始接收信息和所有连接的校验节点发来的信息）。

L_post_j = L_j + Σ_{i ∈ N(j)} Q_i→j

其中 Σ_{i ∈ N(j)} Q_i→j 是VN_j从所有连接的校验节点接收到的LLR之和。

4. 硬判决与收敛检查

根据后验LLR L_post_j 进行硬判决：

ĉ_j = 0 如果 L_post_j >= 0

ĉ_j = 1 如果 L_post_j < 0

形成一个估计的码字 ĉ = [ĉ₁, ĉ₂, …, ĉ_n]。然后进行收敛检查，即检查这个估计码字是否满足所有的校验方程：

H ĉ^T = 0

如果在GF(2)域上计算的结果是全零向量，说明解码成功，输出 ĉ 并停止迭代。否则，进行下一次迭代，从步骤 2a 开始，使用上一步计算出的Q消息进行VN -> CN更新。

5. 停止条件

迭代过程在以下任一条件满足时停止：

估计码字通过校验（H ĉ^T = 0）。
达到预设的最大迭代次数。

如果在达到最大迭代次数时仍未通过校验，解码可能失败。

总结一下：BP解码是一个在Tanner图上，变量节点和校验节点通过交换代表比特可靠性的LLR消息，从而迭代更新对每个比特的信念的过程。消息从接收到的原始软信息开始，在图的边上流动，在节点处根据特定规则合并和更新，最终收敛到一个合法的码字估计（如果成功）。

为什么“低密度”对于原理至关重要？

LDPC码的“低密度”特性不仅仅是一个名称，它是其高性能和高效实现的关键。

简化编码： 对于某些结构化的LDPC码（如QC-LDPC），低密度的H矩阵使得系统编码的实现更为简单高效，通常涉及矩阵乘法和一些移位操作，避免了复杂的高斯消元。
简化解码： BP算法的计算复杂度主要取决于Tanner图中的边数。H矩阵的低密度意味着图中的边数相对较少（每行/每列的平均非零元素少），这直接降低了每次迭代中节点运算的总量，使得解码器能够在合理的计算能力下工作，特别适合高速通信系统。
改善迭代解码性能： 稀疏性有助于减少Tanner图中的短环。短环（特别是长度为4的环）会在迭代解码中引入相关的信念信息，可能导致算法提前收敛到错误的码字，降低性能。虽然低密度本身不保证没有短环，但设计良好的LDPC码会尽量避免短环，而稀疏性使得这种设计更容易实现。

编码和解码的计算量“有多少”？

编码和解码的计算量与码的长度n、码率R（或校验比特数p=n-k）以及H矩阵的密度（或Tanner图的边数）有关。

编码计算量：
- 使用G矩阵：O(nk) 或 O(n²)，取决于G的结构，通常较复杂。
- 使用结构化H矩阵进行系统编码：对于QC-LDPC等，编码可以通过快速傅里叶变换(FFT)等技术加速，计算量可降低到 O(n log n) 或接近 O(n)。一般非结构化稀疏H矩阵的系统编码可能需要O(np)或更高，但仍受益于稀疏性。
解码计算量（BP/SPA）：
- 主要取决于每次迭代中变量节点和校验节点的更新运算。
  - VN更新：对于连接到度为dv的VN，涉及dv-1次加法（LLR域）。总VN运算次数与总边数有关。
  - CN更新：对于连接到度为dc的CN，涉及dc-1次符号乘法和dc-1次绝对值最小值运算（LLR域简化算法）。总CN运算次数与总边数有关。
- Tanner图的总边数等于H矩阵中’1’的数量，对于一个(n, k)的LDPC码，大约是 n * (平均列重) 或 m * (平均行重)。因为H是低密度的，这个边数远小于 n*m。
- 假设平均列重为dv_avg，平均行重为dc_avg，则总边数约等于 n * dv_avg 或 m * dc_avg。每次迭代的总计算量大致与边数成正比，即 O(n * dv_avg + m * dc_avg)。
- 总解码计算量是 O(迭代次数 * 边数)。迭代次数通常在几十到几百次，取决于信噪比和码的设计。

相比于许多其他具有类似纠错性能的码（如Turbo码），LDPC码的解码算法（BP）具有高度的并行性，VN更新和CN更新可以在各自的节点集合中同时进行，这非常适合硬件实现，进一步提升了其在实际系统中的效率。

总而言之，LDPC码的编解码原理紧密围绕其稀疏的校验矩阵和基于图的迭代消息传递。编码利用H矩阵的结构来有效地生成码字；解码则通过在Tanner图上进行软信息的迭代交换来逼近最优的后验概率决策。低密度特性是实现高效编解码和优异性能的基石。

ldpc码编解码原理