5G NR LDPC编译码汇总

1.LDPC概述

低密度校验码（LDPC码）是一种前向纠错码，LDPC码最早在20世纪60年代由Gallager在他的博士论文中提出，但限于当时的技术条件，缺乏可行的译码算法，此后的35年间基本上被人们忽略，其间由Tanner在1981年推广了LDPC码并给出了LDPC码的图表示，即后来所称的Tanner图。1993年Berrou等人发现了Turbo码，在此基础上，1995年前后MacKay和Neal等人对LDPC码重新进行了研究，提出了可行的译码算法，从而进一步发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注。经过十几年来的研究和发展，研究人员在各方面都取得了突破性的进展，LDPC码的相关技术也日趋成熟，甚至已经开始有了商业化的应用成果，并进入了无线通信等相关领域的标准。

LDPC码是一种分组码，其校验矩阵只含有很少量非零元素。正是校验矩阵的这种稀疏性，保证了译码复杂度和最小码距都只随码长呈现线性增加。除了校验矩阵是稀疏矩阵外，码本身与任何其它的分组码并无二致。其实如果现有的分组码可以被稀疏矩阵所表达，那么用于码的迭代译码算法也可以成功的移植到它身上。然而，一般来说，为现有的分组码找到一个稀疏矩阵并不实际。不同的是，码的设计是以构造一个校验矩阵开始的，然后才通过它确定一个生成矩阵进行后续编码。

译码方法是LDPC码与经典的分组码之间的最大区别。经典的分组码一般是用ML类的译码算法进行译码的，所以它们一般码长较小，并通过代数设计以减低译码工作的复杂度。但是LDPC码码长较长，并通过其校验矩阵H的图像表达而进行迭代译码，所以它的设计以校验矩阵的特性为核心考虑之一。

总结一下：

LDPC编码从本质上是一种线性分组码，与经典的线性分组码相比的不同之处在于：

(1)LDPC通过构造校验矩阵H实现

(2)LDPC采用迭代译码算法

(3)LDPC码没有固定的结构

LDPC校验矩阵需满足如下要求：

(1)稀疏性：即校验矩阵中含有极少数量的1

(2)行列约束(R-C)：任意两行或两列同为非零元素的元素个数不超过1

2.LDPC校验矩阵的图形表示——Tanner图

Tanner图是一种二部图，其中的节点可分为两部分

(1)校验节点(约束节点)——CN

(2)变量节点(比特节点)——VN

当校验矩阵中的元素不为0时第i个校验节点与第j个比特节点相连接

 每个校验节点与一个校验方程相对应

 每个变量节点与一个编码比特相对应

由校验矩阵生成对应Tanner图举例如下：

3.非规则LDPC校验矩阵的引入——度分布多项式

非规则LDPC校验矩阵：列数与列重的比值不等于行数与行重的比值

由于非规则LDPC校验矩阵的上述性质，为衡量其对应Tanner图的各对应节点度的分布情况（若为规则码，各节点度满足均匀分布）引入度分布多项式。从边的角度来说：

4. 5G-NR中LDPC编码方法

(1)BG选择

根据TBS大小（记作A）及码率（记作R）确定LDPC基本图（BaseGraph，BG）选择和TB-CRC的长度。BG1适用于长码块高码率。BG2适用于短码块低码率。细节参照协议TS 38.212-7.2.1。

(2)LDPC校验矩阵获取

5. LDPC译码

    LDPC独特的消息传递译码算法是其区别于一般的线性分组码的主要方面，也正是这样的译码方法，使得在即使码长很长的情况下，其译码算法的复杂度仍在可控的范围内。而且，码长越长，其译码算法的性能越好。由此，为讲清楚消息传递译码算法，首先就需要知道其传递的“消息”究竟是什么。

1)外信息传递

为了讲清外信息传递的概念，首先思考这样的问题：

在上图中所示的士兵排列网络中，每个士兵只能与其相邻的士兵互通消息。那么通过怎样的消息传递方式才能使所有士兵得知士兵的总人数？

我们很容易想到通过“报数”的方法解决，当士兵排成一排时，从士兵队列的两端同时报数，每个人将从两个方向得到的士兵数加1传到另一端。如此一来，每个士兵知道了它的两端各有多少人，也就知道了士兵的总数。

其实上图中已经使用了“外信息”的思想。因为对于每个士兵而言，其最终得到的士兵数量信息是“6”，而他向其他士兵传递消息时，传递的数值为其已知的总信息减去目标士兵向他传递的信息。由此，每个士兵相当于向其相邻的士兵传递了“外信息”。

当士兵排列的拓扑发生变化时，该方法同样适用，如下图：

在上图中，每个士兵得到的最终士兵数量信息为“8”，而任意一个士兵向其他士兵传递消息时，其数值相当于“外信息”。

但是，当网络中有“环“存在时，该消息传递方法会出现问题，如下图所示：

可以看出，当消息在右端的环中传播时，其数值会无限地增长下去，造成消息传递的错误，这也是LDPC校验矩阵设计时，尽量避免产生“环“的原因

总结起来，通过外信息传递的方法，可以使一个分布式网络中的每个节点得知整个网络中的一些信息。反过来讲，当消息传递完成时，等效于整个网络将它的信息传递给了每个节点。

2)外信息传递译码器

若将上述问题中的每个士兵换成一个个级联的译码器，将各士兵间传递的“士兵数量”消息改变为各变量节点的“LLR信息”，那么这就是消息传递译码的大体结构。下图所示为每两个级联的译码器间传递消息的示意图：

3)LDPC的SPA译码器

     LDPC的SPA算法是一种典型的以外信息传递为核心的译码算法

     LDPC编码中，由于校验矩阵与tanner图对应关系的引入，各校验节点与变量节点可以看作级联的译码器，其中每个变量节点可以看作一个REP(重复码)的译码器(因为多个校验节点为一个变量节点提供信息)，其示意图如下所示：

而对于每个校验节点，则相当于一个SPC(单奇偶校验码)码译码器，其示意图如下图所示：

总结：在SPA算法中，所有VN对其输入进行处理，并将外信息传递给它们相邻的校验节点，然后校验节点对其输入进行处理，并将外信息传递给与它们相邻的变量节点；从变量节点开始，重复这个过程，直到达到最大迭代次数或者满足某个准则进行及计算判决。

在SPA译码器的推导中，内在最优准则是基于符号的最大后验概率（MAP）准则，当图上的环较大时，估计非常精确，可达到近似最优（MAP）性能。另外，SPA的演进基于独立性假设：每个节点从它的相邻节点接收到的LLR都是独立的。显然，当迭代次数超过Tanner图中围长的一半时，这种独立性假设不成立。