第2章
5G信号先进编码技术

2.1　低密度奇偶校验码信道编码技术

低密度奇偶校验码（LDPC码）是Robert Gallager博士提出的逼近香农极限的线性分组纠错码，又被称为Gallager码。该码于1962年在IRE Transactions on Information Theory发表，并于1963年由麻省理工学院出版社作为单行本出版发行，但是由于当时的技术条件限制及没有合适的译码算法，LDPC码在此后的30多年里并未被人们所开发利用，直到1996年MacKay和Neal等人在研究Turbo码时，将用在Turbo码上的思路引入LDPC码，实现了对LDPC码的重新利用，这才使LDPC码获得了人们的广泛关注，从而开始飞速发展。时至今日，LDPC码的相关技术日趋成熟，并且成为欧洲DVB-S2、IEEE 802.11等多个领域标准的信道编码方案。在即将到来的5G移动通信时代，LDPC码更是被确定为增强移动宽带（eMBB）场景中数据信道的编码方案。本章将着重介绍LDPC码的译码算法。

LDPC码有多种译码算法，它的核心思想是基于二分图上的消息传递（Massage Passing，MP）译码算法。译码算法的方式千差万别，依据消息传送的方式不同，LDPC码的译码算法可以分为硬判决和软判决两类。最主要的硬判决译码算法是Gallager提出的比特翻转（Bit Flipping，BF）译码算法，该算法虽然计算复杂度低，但是译码性能却达不到需求。软判决译码算法的译码性能明显好于硬判决译码算法，但是计算复杂度较大，和积（Sum Product，SP）译码算法是消息传递（MP）译码算法中的一种软判决算法，因为该算法传输的是消息节点的概率密度，所以该算法还称为置信传播（Belief Propagation，BP）算法。

2.1.1　比特翻转译码算法

硬判决译码算法最早是Gallager在提出LDPC码软判决算法时的一种补充。硬判决译码算法的基本假设是当校验方程不成立时，说明此时必定有比特位发生了错误，而所有可能发生错误的比特位中不满足校验方程个数最多的比特位发生错误的概率最大。比特翻转（BF）译码算法在每次迭代时均翻转发生错误概率最大的比特位，并用更新之后的码字重新进行译码。比特翻转译码算法的具体步骤如下。

（1）设置初始迭代次数k1及其上限kmax。对获得的码字y=(y1, y2, ..., yn)按照式（2-1）展开二元硬判决，得到接收码字的硬判决序列Zn。

（2）若k1=kmax，则译码结束。否则，计算伴随式s=(s0, s1, ..., sm-1)，sm表示第m个校验方程的值。若伴随式的值均为0，说明码字正确，译码成功；否则说明有比特位错误。

（3）对每个比特位，统计其不符合校验方程的数量fn（1≤n≤N）

（4）将最大fn所对应的比特位进行翻转，然后使k=k+1，返回步骤2。

BF译码算法的理论假设是基于校验方程的个数的，它选择进行翻转的比特位是最可能出错的比特位，而最可能出错的比特位也就是最不满足校验方程的比特位，具体程度可用校验方程个数来表示。图2-1和图2-2分别为50×100BF和500×1000BF译码算法误码率分析。BF译码算法单纯地对码字进行硬判决，这种方法操作简单，但是性能也最差，尤其是当两次迭代翻转函数的判定结果是同一个比特位时，就会陷入死循环，这对译码来说是极大的损害。

2.1.2　置信传播算法

置信传播（BP）译码算法的核心是消息传递（MP）算法。消息传递算法并不是一种单一的算法，它是最开始运用在人工智能领域的一类算法，后来科研工作者将其应用在LDPC码中，作为置信传播算法广为人们所知。置信传播算法的判决是通过Tanner图来实现的，其主要思想是在迭代过程中，“消息”在Tanner图中的变量节点和校验节点之间来回传递，经过多次迭代之后，消息值趋于稳定，这个稳定值就是最佳的。置信传播译码算法的基本流程如下。

在迭代前，译码器收到信道传送来的实值序列y=(y1, y2, ..., yn)，所有变量节点bi接收到对应的接收值yi。

第1次迭代：每个变量节点给所有与之相邻的校验节点传送一个可靠性消息，这个可靠性消息就是信道传送过来的值；每个校验节点收到消息之后会进行相应处理，然后返回一个新的可靠性信息给与之相邻的变量节点，这样就完成了第1次迭代。第1次迭代结束时，即可进行判决，此时如果满足校验方程，则迭代到此为止，直接输出判决结果，否则还需要进行第2次迭代。

第2次迭代：每个变量节点处理第1次迭代完成时校验节点传送来的可靠性消息，处理完成后将新的消息发送给校验节点。同理，校验节点处理完成后，返回给变量节点，这样就完成了第2次迭代。同样也是在完成迭代后进行判决，如果满足校验方程则结束，如果不满足则需要继续进行迭代，直到满足校验方程或者达到最大迭代次数时结束译码。此外，在每次迭代过程中，为了保证发送的信息和接收节点收到的消息相互独立，无论是变量节点传送给校验节点的信息，还是校验节点传送给变量节点的信息，都不能包括前面迭代过程中所发送的消息。

图2-3和图2-4分别为50×100BP和500×1000BP译码算法误码率分析。目前，LDPC码研究领域的主要工作集中在译码算法的改进、编码方法的优化等问题上，虽然现在对LDPC码的研究如火如荼，且在各方面都取得了不错的进展，但还有很多问题需要继续研究，如LDPC码校验矩阵的构造、编码系统的联合优化、无线衰落信道和MIMO技术下的性能分析，以及LDPC码的链路自适应技术等，这些都是非常值得研究的课题。

2.1.3　LDPC码的校验矩阵

LDPC码是一种线性分组码，通常的线性分组码是由生成矩阵表示的，但LDPC码不是，LDPC码由校验矩阵表示，规则的LDPC码可以用(n, j, k)来表示。简单地说，LDPC码可以描述成校验矩阵有n列，即有nbit；每列有j个1；每行有k个1，它可以用校验矩阵H(1, 2, 3, 4)来表示。

校验矩阵H的每行都是一个校验方程（check）；表示比特的约束关系，H中有12bit，每列表示这个比特收到几个校验方程的约束。例如，第1列，x1受check2、check5、check7三个校验方程的约束，即j的意义就是每比特受j个校验方程的约束。第1行即x3⊕x6⊕x7⊕x8，⊕表示模2加运算，k表示一个check约束kbit。

同时，如果用变量节点表示比特，用校验节点表示校验方程，则可以引进二分图来更直观地描述H矩阵结构，对应校验矩阵H的二分图如图2-5所示。

在图2-5中，一个变量节点就是1bit，每个变量节点的度数为3，对应H矩阵相应列中1的个数；一个校验方程就是一个校验节点，每个校验节点的度数为4，对应H矩阵相应行中1的个数。

当然，非规则LDPC码也可以用二分图来表示，但是每个变量节点或校验节点的度数不同。

谈到二分图就不得不说Tanner图，Tanner图是二分图的具体化，是由Tanner在1981年提出的用图模型来描述码字的方法。Tanner图是研究低密度奇偶校验码的重要工具，Tanner图中顶点分为变量节点和校验节点两类。在Tanner图中，因为变量节点和校验节点的连线是基于与码字比特有关的校验方程的，因此连线的数量与校验矩阵中1的个数相同。在Tanner图中，圆形节点表示变量节点，方形节点表示校验节点。

停止集S是变量节点集合V的子集，与这个子集相邻的校验节点至少与其中的两个变量节点相邻。

与Turbo码相比，LDPC码的主要优势如下：

（1）LDPC码的译码算法计算复杂度远低于Turbo码的译码算法，并且由于稀疏矩阵结构并行的特点，比较容易在硬件上实现，因此LDPC码在大容量通信中的应用程度更高。

（2）LDPC码的码率灵活，而Turbo码只能通过凿孔来实现任意码率的构造，且凿孔位置选择不当会造成性能损失。

（3）LDPC码具有更低的错误平层，远低于Turbo码的10-6量级，可以应用于有线通信、深空通信及磁盘存储工业等对误码率要求十分苛刻的场合，而Turbo码想实现此类目标只能通过与其他码进行级联。

（4）LDPC码发明的时间较早，它是20世纪60年代发明的，不存在知识产权方面的问题，对于某些企业和国家是很好的发展机会。

LDPC码的劣势如下：

LDPC码具有全并行的译码结构，对硬件的要求和需求都比较高；虽然LDPC码的译码方便，但是编码却比较复杂。