2.2.5 LDPC码构造

如前文所述，LDPC码的性能由其Tanner图结构决定。理论上，只要码长充分长（例如N=107），随机构造的LDPC码都是好码。但考虑到实用化，一般编码的码长小于104，此时需要考虑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 2)。为了降低编码复杂度，Richardson与Urbanke[14]证明了如果校验矩阵为近似下三角矩阵形式，则编码复杂度为O(N+g2)，其中，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）所示的导出图。

一般地，假设原模图有MP个校验节点、NP个变量节点，经过z次拷贝与边重排操作得到的全图称为导出图，其规模为M × N=zM P× zNP。这种“拷贝重排”操作称为自举，操作次数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码新的研究热潮，尤其是有限码长下的高性能编译码算法是学术界关注的重点。