2.2 LDPC码原理

LDPC码是一种特定的线性分组码，1962年由Gallager ^[4] 提出。LDPC码与Turbo码具有类似的纠错能力，是一种可以逼近信道容量极限的码。遗憾的是，由于当时计算能力的限制，LDPC码被忽略了30多年。值得一提的是，Tanner ^[5] 提出的采用二分图（也称为Tanner图）模型表示LDPC码，成为LDPC码的标准表示工具。1999年，英国卡文迪许实验室的Mackay ^[6] 重新发现LDPC码具有优越的纠错性能，从而掀起了LDPC码研究的新热潮。

2.2.1 基本概念

LDPC码的特征是校验矩阵为稀疏矩阵，即1的个数很少，0的个数很多。Gallager最早设计的 LDPC 码是一种规则编码。给定码率 ，码长 N =10的（3，6）规则LDPC码，其校验矩阵如式（2-1）所示。

这里，校验矩阵 H 包含5行10列，每一行对应一个校验关系，称为校验节点，每一列对应一个编码比特，称为变量节点。（3，6）是指校验矩阵 H 的每一列含有3个1，每一行含有6个1，即列重为3，行重为6，行重与列重的分布相同，只是1的位置不同。只要码长充分长，则行重与列重显著小于码长 N 与信息位长度 K ，因此 H 具有稀疏性。需要指出的是LDPC码构造具有随机性，只要在校验矩阵中随机分布的1的位置满足行重与列重要求即可，这样得到的是一组码字集合，而并非单个编码约束关系，并且，校验矩阵不严格要求满秩。

上述（3，6）规则LDPC码的校验矩阵可表示为Tanner图，如图2-1所示。

图2-1中含有10个变量节点，分别对应校验矩阵的一列；含有5个校验节点，分别对应校验矩阵的一行。集合 表示第 i 个变量节点连接的校验节点集合，集合 表示第 j 个校验节点连接的变量节点集合。例如， 对应式（2-1）所示校验矩阵的第一列， 对应校验矩阵的第2行。

校验矩阵的行重对应变量节点的连边数，称为变量节点度分布；列重对应校验节点度分布。对比式（2-1）与图2-1的Tanner图，可以发现二者是一一对应的。Tanner图中的环与式（2-1）中的1构成的连接关系完全对应。例如，图2-1中虚线构成了长度为4的环（ v ₂ → c ₃ → v ₄ → c ₁ → v ₂ ）对应式（2-1）中含有4个1的虚线环。

定义2.1 Tanner 图中一条闭环路径的长度定义为环长，在所有闭环中，长度最小的环长称为Tanner图的围长。

一般地，对于（ N ， K ）规则的LDPC码，行重与列重分别为 d _c 与 d _v ，我们通常称这样的LDPC码为（ d _v ， d _c ）码，它的行重与列重满足关系式（2-2）。

这样，对应的 Tanner 图可表示为 ，其中，V是变量节点集合，节点数满足 ;C是校验节点集合，节点数满足 ；ε是边集合，边数满足 。进一步地，（ d _v ， d _c ）码的码率可表示为

上述概念可以进一步推广到不规则 LDPC 码，其中， d _c 为最大行重， d _v 为最大列重。

定义2.2 Tanner图的变量节点与校验节点的度分布生成函数为

其中， λ _i 与 ρ _i 为度分布系数，表示度为 i 的节点连边数占总边数的比例。进一步地，可以定义变量节点与校验节点的度分布倒数的均值分别为

由于总边数相等，因此有

由此，给定度分布（ λ ，） ρ ，非规则LDPC码的码率为

本质上，LDPC码的设计符合信道编码定理中随机编码的思想。Tanner图中变量节点与校验节点之间的连接关系具有随机性，我们可以把度分布系数 λ _i 与 ρ _j 看作变量节点与校验节点连边的概率。因此，Tanner图实际上是符合度分布要求的随机图，变量节点与校验节点之间的连边关系也可以看作一种交织操作。只要码长充分长，Tanner图的规模充分大，这种随机连接就可以反映随机编码特征，暗合了信道编码定理证明的假设：（1）码长无限长；（2）随机化编码。因此，LDPC码与Turbo码在结构设计上，具有类似的伪随机编码特征。

2.2.2 置信传播译码算法

1.算法原理

LDPC码的译码一般采用迭代结构，其译码器结构如图2-2所示。LDPC码译码器包括变量节点译码器与校验节点译码器，通过交织与解交织操作在两个译码器之间传递外信息，经过多次迭代后，变量节点译码器的输出进行判决，得到最终译码结果。

LDPC码典型的译码算法是置信传播（belief propagation，BP）算法。BP算法是在变量节点与校验节点之间传递外信息，经过多次迭代后算法收敛。它是一种典型的后验概率（a posteriori probability，APP）译码算法，经过充分迭代逼近最大后验（maximum a posteriori，MAP）译码性能。

给定二元离散无记忆对称信道（B-DMC） W :X →y，X =｛0，1｝→｛±1｝，假设似然概率为 ，则信道软信息为

反解得到两个似然概率为

定理2.1 比特软估计值为 ，其中 t 是双曲正切函数。

证明 由于采用二进制相移键控（binary phase-shift keying，BPSK）调制，因此信号的软估计值可以表示为

将式（2-8）代入式（2-9），可得

证毕。

另外，利用双曲正切的反函数可得

下面分析校验节点向变量节点传递的外信息。令 表示变量节点 i 取值为1时第 j 个校验方程满足约束的概率。显然，这个校验方程如果满足约束，则剩余的变量节点有奇数个比特取值为1。因此，这个概率表示为

其中， P _j，i＇ 表示变量节点 i ＇取值为1时，校验节点 j 的估计概率。相应地，当变量节点 i 的取值为0时，满足校验节点 j 的约束的概率为 。

设 E _j，i 表示当变量节点 i 取值为1时从校验节点 j 到所连接的变量节点 i 传递的外信息，计算式为

将式（2-12）代入式（2-13）可得

其中， M _{j ，i＇} 是变量节点 i ＇向校验节点 j 传递的外信息，其定义为

注意，式（2-14）的连乘中要去掉从变量节点 i 传来的外信息，这样可以避免自环。

根据定理2.1可得

再利用式（2-11），外信息可以进一步变换为

或者得到等价变换形式，即

然后，分析变量节点向校验节点传递的外信息。假设各边信息相互独立，则从变量节点 i 向校验节点 j 发送的外信息可以表示为

其中， L _i 是信道接收的对数似然比（logarithm likelihood ratio，LLR）信息。需要注意的是，上述外信息计算中，需要去掉从校验节点 j 传来的外信息，这样不会产生自环，避免信息之间相关。

变量节点对应的比特LLR为

相应的判决准则为

注意，比特 LLR Λ _i 需要将信道软信息与所有校验节点的外信息叠加。根据上述描述，BP算法可以总结如下。

（1）根据式（2-7）计算信道软信息 L _i 序列，初始化变量节点到校验节点的外信息 M _{j ， i} = L _i ，并传递到校验节点。

（2）在校验节点处，根据式（2-17）计算校验节点到变量节点的外信息 E _{j， i} ，并传递到变量节点。

（3）在变量节点处，根据式（2-19）计算变量节点到校验节点的外信息 M _{j， i} ，并传递到校验节点。

（4）根据式（2-20）计算比特 LLR，并利用式（2-21）判决准则得到码字估计向量ˆ c 。

（5）如果迭代次数达到最大值 I _max 或者满足校验关系 ，则终止迭代；否则，返回第（2）步。

BP算法在变量节点的计算是累加所有的信道信息与外信息；而在校验节点的计算则是将所有基于外信息得到的软估计值相乘，再求解反双曲正切函数。因此，BP算法也称为和积算法。

BP算法在校验节点处的计算式（2-17）可以简化。首先，将 M _{j ， i ＇} 分解为两项，即

其中，sgn（ x ）是符号函数。利用这一分解，可以得到

这样，式（2-17）可以写为

可以将式（2-24）中的连乘改写为求和，推导如下。

定义函数

由于该函数满足 ，因此可知 θ （ x ）= θ ^-1 （ x ）。代入式（2-25），可得

这样，符号连乘可以用每个变量节点到校验节点的外信息 M _{j ， i ＇} 的硬判决模2加得到，而函数 θ （ x ）可以查表得到。

上述校验节点外信息计算式还可以进一步简化。考虑到最小项决定了乘积结果，因此式（2-27）可近似为

这种算法在变量节点涉及求和运算，在校验节点只涉及最小化运算，因此被称为最小和（minimum sum，MS）算法。与标准BP算法相比，最小和算法性能稍有损失，但外信息计算得到了大幅简化。

对于BP算法或MS算法，由于外信息都是沿变量节点与校验节点的连边传递，因此，单次迭代的计算量为

一般地，LDPC码的平均度分布为 ，则BP算法的计算复杂度为 O （ I _max N log ₂ N ）。

BP算法和MS算法是软信息译码算法，如果只考虑硬判决信息，可以进一步简化为比特翻转算法。这时算法复杂度更低，但性能损失较大。

2.消息传递机制

从实用化角度来看，BP算法的消息传递机制非常重要。一般而言，BP算法的消息传递机制可分为4种，简述如下。

（1）全串行译码

全串行译码是标准的 BP 译码，在一次迭代过程中，变量节点按顺序启动，等所有外信息都计算完成后，再按照连边顺序在校验节点按顺序计算相应外信息。基于这种方法的硬件译码器只需要一个计算单元就能够完成译码，但需要存储所有外信息，空间资源消耗大。

（2）全并行译码

全并行译码也称为洪泛调度，需要采用硬件电路实现全部的计算单元，这样每个变量节点、校验节点都可以单独启动，快速计算与传递外信息。这种译码器结构能够获得最高的吞吐量，但硬件资源开销大，并且码长很长时，Tanner图连边非常多，芯片内部单元间的布局非常复杂。

（3）部分并行译码

部分并行译码是全串行译码和全并行译码的折中，采用硬件电路实现一组译码单元，每次迭代时，同时读取一组变量节点与校验节点信息，并行运算并相互传递外信息。这种机制能够达到译码性能与吞吐量、硬件资源开销的较好折中，是LDPC码译码器常用的消息传递机制。

（4）洗牌译码

LDPC码的洗牌译码方案 ^[7] 与Turbo码类似，它的基本思想是校验节点尽早利用变量节点更新后的外信息计算输出信息。令 分别表示第 l 次与第 l 1-次迭代变量节点向校验节点传递的外信息， 表示第 l 次迭代校验节点向变量节点传递的外信息。则校验节点外信息计算式修正为

显然，式（2-30）中，变量节点向校验节点传递的外信息按序号分为了两组，即 i ＇＜ i 与 i ＇＞ i 。前者外信息已经更新，因此采用第 l 次迭代结果；而后者由于外信息还未更新，因此采用前一次，即第 l -1次迭代的结果。由于用到了最新的外信息计算结果，这种机制可以与前3种机制组合，加速译码收敛。

2.2.3 密度进化与高斯近似算法

密度进化（density evolution，DE）的基本思想是由Gallager ^[4] 提出的。Richardson等 ^[8-9] 和Chung等 ^[10] 最早利用密度进化分析LDPC码采用BP算法的渐近行为。他们的研究表明，对于许多重要的信道，例如加性白高斯噪声（additive white Gaussian noise，AWGN）信道，当码长无限长时，针对随机构造的 LDPC 码集合，可以用DE算法计算出无差错译码的门限值。因此，DE算法能够比较与分析LDPC码的渐近性能，是一种重要的理论分析工具。

1.密度进化

所谓密度进化，就是在Tanner图上计算与跟踪LLR的概率密度函数（probability density function，PDF）。假设信道LLR的概率密度函数为 p （ L ）；第 l 次迭代，变量节点到校验节点外信息的PDF为 p （ M _l ），校验节点到变量节点外信息的PDF为 p （ E _l ）。随着迭代次数的增加，外信息的PDF会演化。

DE成立的两个独立性假设如下。

（1）信道无记忆，这个假设是指各个接收信号相互独立，因此互不相关。

（2）Tanner图不存在长为2 l 或更短的环，这样保证了各节点传递的外信息相互独立。

首先，观察（3，6）规则LDPC码的BP译码过程。以某个检验节点为根节点构成的消息传递树如图2-3所示。

如图2-3所示，在一次迭代中，作为根节点的校验节点向连接到它的某个变量节点传递信息，这个变量节点接收到两路校验节点信息以及信道信息后生成外信息，传递到与之相连的下一层的 d _v -1=2个校验节点。而这两个校验节点又可以进一步扩展 d _c -1=5个变量节点。这样经过两次迭代，根节点的信息传递到了（ d _v -1）（ d _c -1）= 2 × 5=10个变量节点。注意，在变量节点处的计算还需要考虑信道信息。

一般地，对于（ d _v ， d _c ）规则LDPC码，BP算法的迭代计算式为

对于变量节点向校验节点传递的消息，由于各消息相互独立，因此外信息的PDF是各个消息PDF的卷积，表示为

其中，*表示卷积运算。由于式（2-32）涉及 d _v -1个卷积运算，复杂度较高，通常用快速傅里叶变换（fast Fourier transform，FFT）代替，从而降低计算复杂度。

类似地，根据式（2-31），校验节点向变量节点传递的消息可以分解为两部分，即

其中， 是模2加运算，而 是普通的代数求和运算。由于各个变量节点输入的外信息相互独立，因此 的概率密度函数表示为

上述计算涉及 d _c -1个卷积运算，也可用FFT代替。

最终，译码比特LLR的PDF可表示为

上述规则LDPC码的PDF计算可以进一步推广到非规则LDPC码。此时变量与校验节点信息的PDF计算式为

由此，DE算法过程可以简述如下。给定一组度分布（ λ （ x ）， ρ （ x ）），针对B-DMC，利用信道对称性条件 ，假设发送全零码字，给定信道条件，例如二进制输入加性白高斯噪声（binary input additive white Gaussian noise，BI-AWGN）信道的均方根噪声 σ ，反复进行式（2-27）的概率密度函数迭代运算。当迭代次数充分大时，比特 LLR Λ ＜0对应的概率就是译码的差错概率，即 。

信噪比（signal-to-noise ratio，SNR）为 ，BI-AWGN信道下，（3，6）规则LDPC码 p （ M _l ）与 p （ E _l ）演化结果分别如图2-4和图2-5所示。

由图2-4可知，初始分布 p （ L ）为高斯分布，随着迭代次数增加， p （ M _l ）仍然为高斯分布，并且LLR均值逐渐增大，其小于0的拖尾逐步减少，直至趋于0。

由图2-5可知，在迭代早期，例如第1次迭代， p （ E _l ）并不是高斯分布，但随着迭代次数增大，函数形状越来越接近高斯分布，并且随着LLR均值逐渐增大，小于0的拖尾趋于消失。

利用密度进化算法，我们可以针对特定度分布计算其译码无差错的噪声门限。

定义2.3 对于BI-AWGN，噪声门限定义为

仍然以（3，6）规则LDPC码为例，在BI-AWGN信道下，不同信噪比的误码率（bit error ratio，BER）性能如图2-6所示。当 （ σ =0.881）时，随着迭代次数的增加，误码率不收敛；而当 （ σ =0.879）时，迭代次数超过100后，误码率已经趋于0。由此可见，噪声门限必然满足0.879＜ σ ^* ＜0.881。我们可以通过DE算法确定其精确值为 σ ^* =0.88（ ）。

码率 ，反解BI-AWGN信道容量，可以得到极限信噪比 ，相应的噪声门限 σ ^* =0.978 69。由此可知，（3，6）规则LDPC码的噪声门限与信道容量极限还有很大差距。这种码性能受限的关键原因是度分布过于规则，为了逼近信道容量极限，需要对变量节点、校验节点的度分布进行优化，设计高度不规则的 LDPC 码。研究者借助密度进化工具，采用差分演化或迭代线性规划算法，得到了高性能的度分布。其中最著名的是Chung等 ^[10] 基于DE算法得到的优化分布，如式（2-38）所示，其变量节点度分布为2～8 000，具有高度不规则性。

上述分布对应的信噪比 ，噪声门限 σ ^* =0.978 186 9，与信道容量极限的差距为0.004 5 dB。

需要注意的是，上述分析的是码长与迭代次数趋于无穷大的极限信噪比，即 N →∞， l →∞。从渐近性能来看，即使码长无限长、迭代次数无限大，这种不规则LDPC码仍与信道容量极限有0.004 5 dB的差距，因此这种不规则LDPC码只能逼近BI-AWGN信道的容量极限，但严格意义上讲是容量不可达的。从有限码长性能来看，Chung等 ^[10] 构造了最大度为100与200的不规则LDPC码，码长 N =10 ⁷ ，迭代2 000次，误比特率为10 ^-6 ，距离香农限约0.04 dB，远未达到信道容量极限。

尽管如此，基于DE算法构造渐近性能优越的度分布为设计逼近信道容量极限的 LDPC 码提供了完整的理论框架。沿着这一思路，人们构造了众多的高性能的LDPC码。

2.高斯近似

密度进化是一个良好的理论工具，能够精确分析给定度分布的渐近性能，但其计算结果的准确性依赖于LLR分布的量化精度。一般而言，只有高量化精度才能获得准确的门限值估计，但即使采用FFT，计算复杂度仍然巨大。

作为一种替代分析工具，高斯近似（Gaussian approximation，GA） ^[11] 虽然牺牲了一些准确性，但显著降低了计算复杂度。高斯近似假设变量节点与校验节点的外信息近似服从高斯分布，因此这些信息的方差是均值的一半，它们的概率密度函数完全由均值决定。这样我们只要在迭代过程中跟踪外信息的均值，就能够预测渐近性能。

对于（ d _v ， d _c ）规则的LDPC码，假设变量节点 v 与校验节点 u 消息的均值分别为 m _v 与 m _u ，则第 l 次迭代变量节点消息的均值递推式为

其中，第0次迭代（即初始分布）对应的校验节点消息均值为0，即 。

而校验节点消息的均值递推式为

其中，函数 ϕ （ x ）定义为

在实际应用中，函数 ϕ （ x ）涉及复杂的数值积分，一般采用两段近似公式，即

对于度分布为（ λ （ x ）， ρ （ x ））的非规则LDPC码，其变量节点消息的递推式为

而校验节点消息的递推式为

综上所述，密度进化与高斯近似是两种分析迭代译码渐近性能的理论工具，不仅可以用于 LDPC码的性能分析与优化设计，也可用于 Turbo码的性能分析与设计。

2.2.4 LDPC码差错性能

影响LDPC码性能的两个重要参数是最小汉明距离 d _min 与最小停止集/陷阱集。理论上，LDPC码的最佳译码算法是最大似然（maximum likelihood，ML）算法，此时性能主要由 d _min 与相应的距离谱决定。对于不存在环长为4的LDPC码校验矩阵，假设最小列重为 w _min ，则这个码的最小汉明距离满足如下不等式。

由于ML算法复杂度太高，LDPC码更常用的译码算法是和积算法，在二进制删除信道（binary erasure channel，BEC）下，和积算法退化为硬判决消息传递算法（message passing algorithm，MPA）；在一般的B-DMC中，和积算法就是BP算法。对于前者，决定迭代终止的是停止集，对于后者，影响性能的主要是陷阱集。

停止集是变量节点的子集，在该集合中的变量节点的相邻校验节点连接到该集合至少两次。停止集的大小称为停止集规模。BEC下采用迭代译码算法，最小停止集限制决定了LDPC码的性能。

图2-7给出了一个停止集示例，其中，｛ v ₁ ， v ₃ ， v ₄ ｝构成了一个停止集。如果这3个节点对应的比特都被删除，则迭代译码将终止，无法判决其中的任意一个比特。这就是停止集得名的由来。

图2-8与图2-9分别给出了AWGN信道下，采用（3，6）规则LDPC码与5G NR标准中的LDPC码，码长分别为 N =1 008与 N =4 000，码率 R 分别为 时的块差错率（block error rate，BLER）性能仿真结果，最大迭代次数为50次。

由图2-8可以看出， N =1 008、BLER=10 ^-3 时，同等条件下，5G NR LDPC码与（3，6）规则LDPC码相比大约有0.4 dB的编码增益。类似地，由图2-9可以看出， N =4 000、BLER=10 ^-3 时，同等条件下，5G NR LDPC码与（3，6）规则LDPC码相比大约有0.64 dB的编码增益。

2.2.5 LDPC码构造

如前文所述，LDPC码的性能由其Tanner图结构决定。理论上，只要码长充分长（例如 N= 10 ⁷ ），随机构造的LDPC码都是好码。但考虑到实用化，一般编码的码长小于10 ⁴ ，此时需要考虑Tanner图与编码结构对性能的影响。

通常，较小的环长会导致变量节点、校验节点交互的消息很快出现相关性，从而限制纠错性能。一般而言，LDPC码的构造要求消除长度为2与4的环，也就是说，Tanner图的围长至少为6。但从另一方面来看，Tanner图上的环长、围长的值也并非越大越好。理论上，只有无环图才是严格的 MAP 译码，如果图上存在环，则和积算法是APP译码算法，只是MAP译码的近似。由于受到最小汉明距离的限制，严格无环图的性能很差。因此，增大环长或围长并非LDPC码设计的唯一优化目标，需要综合考虑Tanner图结构与编码结构参数进行优选。

LDPC码主流的构造与编码方法如图2-10所示。LDPC码的编码方法根据结构特点可分为5类，分别简述如下。

1.伪随机构造

从实际应用来看，这一类LDPC码构造大多是考虑去除某些限制条件的伪随机编码，例如去掉长度为4的环。在Gallager ^[4] 的原始研究中，（3，6）规则LDPC码的构造就是一种伪随机构造。他将校验矩阵的行等分为多段，通过在不同段中随机排列1的位置实现伪随机构造。MacKay与Neal ^[6] 构造的基本思路是按列重随机选择列进行叠加，观察行重是否满足度分布要求，通过反复迭代操作最终实现构造，这种构造能够消除长度为4的环。

比特填充构造 ^[12] 是指在Tanner图每次添加变量节点时，要检查新增连边是否构成特定长度（例如4）的环，通过避免短环出现，得到增大围长的Tanner图结构。

渐近边增长（progressive edge growth，PEG）算法 ^[13] 是比特填充构造的对偶方法。其基本思想是每次在Tanner图上添加新边时，都选择最大化本地围长的变量节点，这样能够保证围长充分大。

上述方法都是从不同角度随机构造Tanner图或相应的校验矩阵 H 。但是LDPC码的编码需要使用生成矩阵 G 。我们可以采用高斯消元法得到生成矩阵 G ，但由于这种结构的生成矩阵往往不稀疏，因此LDPC码的编码复杂度是 O （ N ² ）。为了降低编码复杂度，Richardson与Urbanke ^[14] 证明了如果校验矩阵为近似下三角矩阵形式，则编码复杂度为 O （ N + g ² ），其中， g 是校验矩阵与下三角矩阵之间的归一化距离，对于很多编码 g ≪1。

2.结构化编码

伪随机构造编码能达到较好的纠错性能，但一般编译码复杂度较高。与之相反，结构化编码也称确定性编码，编译码复杂度更具有优势。结构化编码的一类主要思路是采用几何设计或组合设计。其中，几何设计的代表性方法是文献[15]提出的有限几何构造；组合设计有很多方法，包括平衡不完全区组方法 ^[16] 、Kirkman 系统设计 ^[17] 以及正交拉丁方设计 ^[18] 等。这些方法都需要用到几何或组合理论，具有良好的数学分析基础。

结构化编码的另一类思路是采用线性结构设计，代表性方法包括 Lu 等 ^[19] 提出的 Turbo 结构设计与 Fossorier ^[20] 提出的准循环（QC）-LDPC 码。由于利用了线性编码特征，这两种方法的编码比较简单规整。

3.嵌套构造

伪随机构造是在整个Tanner图上进行设计，另一种设计思路是将Tanner图上的边分类，首先优化子图，然后扩展到全图。由于全图与子图具有嵌套结构，因此被称为嵌套构造。

这种构造的代表是Richardson等 ^[21] 提出的多边类型LDPC码，其中一个重要的子类就是原模图（protograph）LDPC 码。Thorpe ^[22] 提出了原模图的概念。Divsalar等 ^[23] 设计的AR3A与AR4JA码是两种代表性的原模图码，它们具有线性编码复杂度与快速译码算法，能够逼近信道容量极限，被应用在美国深空探测标准中。5G NR移动通信标准中也采用了基于原模图的LDPC码编码方案。

图2-11给出了原模图构造示例。图2-11（a）所示为一个原模图，与普通的Tanner图不同，原模图中允许存在重边。该原模图有4个变量节点、3个校验节点和9条边，由于有重边，因此图2-11（a）所示的原模图对应8种不同类型的边。其对应的基础矩阵如下。

图2-11（b）给出了两次拷贝示意，经过同类型边之间的重排，可以得到图2-11（c）所示的导出图。

一般地，假设原模图有 M _P 个校验节点、 N _P 个变量节点，经过 z 次拷贝与边重排操作得到的全图称为导出图，其规模为 M × N = zM _P × zN _P 。这种“拷贝重排”操作称为自举，操作次数 z 称为自举因子。原模图的性能不能直接应用外部信息传递（extrinsic information transfer，EXIT）图分析，需要采用修正的原模图外部信息传递（protograph extrinsic information transfer，PEXIT）图分析 ^[24] 。导出图中的边连接优化可以用PEG算法得到。

4.多进制编码

上述讨论的LDPC码都是二进制编码。Davey与MacKay ^[25] 提出了基于有限域的多进制LDPC码，称为Q-LDPC码。由于引入了有限域的额外编码约束，相对于二进制编码而言，Q-LDPC 码能够获得更好的纠错能力。但这种编码的最大问题是译码复杂度较高，限制了其工程应用。

另外一类多进制编码是广义构造，称为 G-LDPC 码，由 Lentmaier 与Zigangirov ^[26] 提出。G-LDPC码将传统LDPC码中简单校验的校验节点替换为经典的线性分组码校验，例如，采用Hamming码、BCH码或RS码作为校验节点。进一步，Liva等 ^[27] 考虑了不规则G-LDPC码，由于Tanner图上存在强纠错节点，其被称为掺杂LDPC码。

5.扩展构造

近年来，人们扩展LDPC码设计思想，针对具体应用构造新型编码。其中，代表性的编码是低密度生成矩阵（low density generative matrix，LDGM）码、无速率（rateless）码与空间耦合LDPC（spatial coupling-LDPC，SC-LDPC）码，下面分别介绍其基本思想与性质。

（1）LDGM码

Cheng与McEliece ^[28] 提出了LDGM码的设计思想。一般而言，LDPC码的校验矩阵是低密度的，生成矩阵是高密度的，而LDGM码的设计利用了对偶性，它是一种系统码，生成矩阵是稀疏的，校验矩阵是稠密的。因此，LDGM码主要应用于高码率场景，它具有线性的编译码复杂度。

早期研究表明，由于最小汉明距离较小，LDGM码是渐近坏码，有显著的错误平台现象。但如果将两个LDGM码进行串行级联，或者将LDGM码与其他LDPC码级联，则可以显著降低错误平台。

由于LDGM码编码简单，可以应用于信源压缩与编码，也可以与星座调制联合设计，或者应用于多输入多输出（multiple-input multiple-output，MIMO）传输，逼近高频谱效率下的信道容量极限。

（2）无速率码

无速率码最早来源于纠删应用。在固定/无线互联网中，由于某种原因（拥塞或差错），介质访问控制（medium access control，MAC）层会产生丢包，但丢包数量并不固定。固定编码码率进行纠删时，如果码率高于删余率，则纠删能力较差；如果码率低于删余率，则冗余较大。总之，由于实际系统中删余率无法先验确知或者存在动态变化，因此固定的码率无法匹配。

Luby ^[29] 提出的Luby变换（Luby transform，LT）码是一种是实用化的无速率码。它是一种数据包编码，主要用于 MAC 层或应用层数据传输。也有人称其为喷泉（fountain）码，即将每个编码数据包比喻为一滴水，根据传输条件动态变化，接收机收到不同的水量（数据包），就可以开始纠删译码，因此其码率不固定。

理论上可以证明，当码长趋于无限长时，LT码能够达到BEC的信道容量，它是一种容量可达的构造性编码。但已有研究表明，码长有限时，LT 码具有显著的错误平台现象。为了降低错误平台，Shokrollahi ^[30] 提出了Raptor码，这种编码使用一个高码率的LDPC码作为外码，级联LT码，获得了显著的性能提升。Raptor码已经应用于3G的应用层编码标准中。

（3）空间耦合LDPC码

空间耦合LDPC码借鉴卷积编码结构。Jimenez与Zigangirov ^[31] 最早提出了卷积LDPC 码。它的基本思想是将基本校验矩阵作为移位寄存器的抽头系数，设计卷积型的编码结构，从而获得周期性时变的编码序列。

Kudekar 等 ^[32] 认识到卷积在各个码段之间引入了编码约束关系，产生了“空间耦合”效应。他们证明，即使采用规则的（3，6）码约束，只要引入适当的空间耦合关系，当编码长度趋于无穷时，密度进化的译码门限将趋于BEC的信道容量的门限值。这意味着，空间耦合LDPC码也是一种能够达到BEC的信道容量的构造性编码。研究者发现，空间耦合LDPC码对于一般的B-DMC都是渐近容量可达的，这是一个LDPC 编码理论的重大突破，经过多年的研究，人们终于发现了可以达到信道容量极限的LDPC码。空间耦合LDPC码掀起了LDPC码新的研究热潮，尤其是有限码长下的高性能编译码算法是学术界关注的重点。

2.2.6 LDPC码设计准则

LDPC 码的设计理论众多，众多学者提出了各种设计理论与方法。我们可以依据码长不同，分两种情况探讨。

对于超长码长，例如 N =10 ⁶ ～10 ⁷ ，则伪随机构造（例如MacKay与Neal构造）的LDPC码具有优越的性能，能够逼近信道容量极限。但这种方法得到的校验矩阵0/1分布规律，难以存储与实现。

对于短码长到中等码长，例如 N =10 ² ～10 ⁴ ，则代数构造、嵌套构造比伪随机构造性能更优，并且前两者的编译码算法复杂度较低，有利于工程实现。

总之，LDPC码的设计需要考虑多种参数与因素，其设计准则归纳如下。

（1）环长与围长

Tanner图上的环会影响迭代译码的收敛性，围长的值越小，影响越大。但是消除所有的环，既无工程必要，也无法提高性能。因此，在LDPC码的Tanner图设计中，最好的方法是尽量避免短环，尤其是长度为2与4的环。

（2）最小汉明距离

最小汉明距离决定了高信噪比条件下，LDPC 码的差错性能。因此，为了降低错误平台，要尽可能增大最小汉明距离。

（3）停止集分布

小规模的停止集会影响BEC下迭代译码的有效性。因此，从工程应用看，需要优化停止集分布，增加最小停止集规模。

（4）校验矩阵稀疏性

校验矩阵的系数结构对应Tanner图上的低复杂度译码。但校验矩阵的设计需要综合考虑最小汉明距离、最小停止集与稀疏性之间的折中。

（5）编码复杂度

对于伪随机构造的LDPC码，主要的问题是编码复杂度较高。由于采用高斯消元法得到的下三角形式的生成矩阵不再是稀疏矩阵，即使采用反向代换进行编码，其编码复杂度量级仍是 O （ N ² ）。因此，从实用化角度来看，LDGM码与原模图编码是两种具有吸引力的编码方案。在实际通信系统中，这两种编码得到了普遍应用。

（6）译码器实现的便利性

从译码器的硬件设计来看，由于大规模Tanner图没有规则结构，伪随机构造的LDPC 码面临高存储量、布局布线复杂的问题。因此，嵌套构造、结构化设计更有利于硬件译码器的实现，在工程应用中更具优势。 p3FRlN7eiDE5a9oedCECcscsA3/p9waLw/wd3rBkkibw7VmuqqNMO5KhiO+5oEpC