低密度校验码（LDPC）

2.3 准循环 LDPC 码（QC-LDPC）

2.3.4　准循环 LDPC 码的多码长设计

依据准循环LDPC码原理可知， LDPC是可以由基础矩阵、提升值和置换矩阵唯一确定。而准循环LDPC码所支持的信息长度可以依据基础矩阵的系统列数k；和提升值z确定，即K=k；xz。那么，可以通过调整这两个变量，使得准循环LDPC码可以支持灵活码长：①调整系统列数目k；②调整提升值z。如果准循环LDPC码的系统列数目不变，提升值任意变化，可以看出准循环LDPC码的码长颗粒度最小可以达到k； bit； 而如果结合采用填充比特(FillerBits) 方法[39.53-55]那么准循环LDPC码可以支持达到1bit颗粒度的码长。
在3GPP5G-NR的设计中，eM BB业务确定了两个基础矩阵并且基于每个基础矩阵各自确定了8个基础校验矩阵，其中，基础矩阵1支持的最大码块长度设为8448bit(比LTE的6144bit略大) ，最大的系统列数设为ks max=22列；基础矩阵2支持的最大码块长度为3840bit，最大的系统列数设为k imax10列。故提升值的最大值为8448/22=384。从理论上讲，提升值z的取值可以是小于384的任意自然数。但是过分灵活的提升值对增加硬件实现的复杂度，尤其是连线和管脚设计。提升值与LDPC译码器的并行度有关。当并行度为2的幂时， LDPC译码器移位网络(Shifting Network) 可以采用Banyan连线器(Banyan Switch) ， 操作简单灵活以及复杂度低。
Banyan连线器呈“蝶形结构”， 是各类移位网络中常用的一种连线方式。一个Banyan连线器包含.J=log 2(PM) 级， 每级有K=PM/2个小的“2-2开关”其中每个“2-2开关”又由两个“2-1MUX”单元(即阀门) 组成。所以一共有PM xlog 2(PM) 个“2-1MUX”单元。这里PM表示最大并行度， 等于Banyan连接线的输入端口数目。如图2-15所示， 阀门开关控制为0(Bar状态)时， 输出上管脚的“2-1MUX”单元的输出连接输入上管脚， 输出下管脚的“2-1MUX”单元的输出连接输入下管脚； 否则(Cross状态) 输出上管脚的“2-1MUX”单元的输出连接输入下管脚，输出下管脚的“2-1 MUX”单元的输出 连接输入上管脚。
如图 2-15 所示为一个最大并行度是 8 的 Banyan 连线器，每个“2-2 开 关”Sk,j,（k=1,2,…,K, j=1,2,…,J）都可通过控制信号，使得其选择工作在 “Cross”或者“Bar”两种状态之一。
对照 8×8 的标准置换矩阵（准循环矩阵），当基础矩阵中相对应的元素值为 1 时，准循环矩阵为单位矩阵右移一位，8 个输入与 8 个输出的对应关系应该为： 01234567 12345670。S2,1, S4,1, S1,2, S3,2, S1,4 需设置为“Cross”状态，剩下的 2-2 开关需设置为“Bar”状态。

Banyan 连线器对于并行度为 2 的幂时比较有效，但是当提升值不等于 2 的时候，需要用到其他的移位网络，如 QSN 连线器。QSN 连线器可以支持任 意的提升值和移位值。但是 QSN 连线器的复杂度要高于 Banyan 连线器，一个 QSN 连线器包括 log2(PM)+1 级，以及一共 PM×[2×log2(PM)−1]+1 ≈ 2×PM× log2(PM) 个“2-1 MUX”单元。图 2-16 给出了 QSN 连线器的总体结构，是由 一个左移位网络、一个右移位网络和一个合并网络共同构成。

由于在LDPC译码器复杂度中移位网络所占的比重较大， 提升值设计需要尽量考虑让LDPC译码器中移位网络可以采用Banyan网络实现， 以降低译码器的复杂度。
其中， 依据信息长度可以获取当前准循环LDPC编码所采用的提升值Zc，依据所述提升值Z.所在如表2-3所示的is索引，从而可以根据所述is索引获取LDPC码所采用的移位值矩阵； 然后， 根据获取的移位值矩阵和提升值Z.按照式(2-51) 获取准循环LDPC编码的基础矩阵对应于第i行第j列的元素值：


由于计算得到的LDPC码系统比特数目K=k； xz， 不一定能等于编码块大小CBS，则需要填充K-CBS个填充比特(FillerBits) 。如图2-17所示， 将填充的比特集中放置在信息比特尾部，并且填充比特并不参与实际的传输。结合调整提升值z和填充比特两种方法共用， 准循环LDPC码可以支持任意长度的码长。

2.3.5　基于 QC-LDPC 码的多码率设计

从理论上讲，如果对于每一种码率都设计一个基础校验矩阵，性能肯定更 优。但这会大大增加硬件复杂度和标准化的难度，尤其这些基础矩阵之间没有 任何嵌套关系时。基于某个基础校验矩阵，可以通过下面两种方法，来调整其 码率 [39,53-55]。在这一节中的多码率主要是指高于母码码率的情形，而低于母码 码率的将在后面的小节中介绍。
如图 2-18 所示，该基础矩阵的系统部分有 kb 列，校验部分有 mb 列，总共 是 nb = kb + mb 列，不传输的系统列数目为 pb；可以知道，母码码率是 kb/nb = kb/（kb+mb），而如果考虑不传输系统列，母码码率为 kb/（kb−pb+mb）。码率的增加 可以通过只取基础矩阵中的前面 mb″行，即校验部分只取前面 mb″列，这部分 矩阵所对应的码率为 kb/（kb−pb+mb″）。随着码率的不断提高，当超过 kb/（kb−pb+mb‘）时，则采用进一步打掉传输比特的方法来增加码率，直到设计的最高码率， 此时编码和译码都采用 Kernel 矩阵。

除了对基础矩阵的行列进行缩减和打掉（相当于以提升值为单位进行打孔）， 当通过扩展矩阵以后，还可以小范围内地根据调制符号个数等，打掉个别的码 字，更精细地调整码率。

2.3.6　基于 QC-LDPC 码的精细码率调整

如上节所述，通过选取基础校验矩阵的不同子集，可以生成不同的码率。 随着码率的降低，编码器产生更多的校验比特，即冗余信息。因此基于准循环 LDPC 码能够很自然地支持基于增量冗余（IR，Incremental Redundancy）的 HARQ 重传，直到当码率降到母码码率。准循环 LDPC 码可以打孔的比特数目 能精确到 1 bit 为单位，所以此时其码率可以非常精确地获取想要的任意大的母 码码率，即打孔的比特数目不为提升值的整数倍。
与 Turbo 码不同，LDPC 码的减少冗余度不是简单地打掉校验比特，而 是反映在奇偶校验矩阵中所对应的打掉的校验比特不参与校验码了，从而在 LDPC 译码器中，直接可以不进行对应这些校验比特的外信息更新，从而可以 减少译码时延，提高译码吞吐量。在数据重传中，LDPC 译码器在每次 HARQ 传输只需要取已经传输的校验比特，无需尝试解码所有的校验比特。从这点上 讲，LDPC 所支持的增量冗余 HARQ 时的解码时延比 Turbo 码要短，吞吐量 比 Turbo 码要高，其中，这也是 5G-NR 采用 LDPC 码作为数据信道编码方案 的原因之一。对于更详细的 HARQ 操作，请参见第 2.5.4 节。

2.3.7　一般 LDPC 码的短圈特性

图 2-19 为二分图中长度为 4 短圈（Girth）的示意图。其中，粗实线表示 信息比特 x1、x2 和校验比特 c1、c2 构成了一个长度为 4 的圈。

图 2-20 为二分图中长度为 6 短圈的示意图。其中，粗实线表示信息比特 x1、x2、x3 和校验比特 c1、c2、c4 构成了一个长度为 6 的圈。

环（Girth，圈）的概念用来定量描述二分图中的短圈。在图论中，二分图 的 Girth 是指一个图中最短圈的圈长，例如，某个二分图有长度为 6、8、10、 12 和长度更长的圈，则该二分图的 Girth 为 6。在二分图中，某个节点 u 的 Girth 是指经过节点 u 的最短圈的圈长，例如，经过节点 u 有长度为 8、10、12 和长度更长的圈，则该节点 u 的 Girth 为 8。在二分图中，某条边 e 的 Girth 是 指经过此边 e 的最短圈的圈长，例如，经过边 e 有长度为 8、10、12 和长度更 长的圈，则此边 e 的短圈为 8。
一个变量节点的短圈是指最短路径的长度，它等同于从这个节点出来的信 息传递回该节点本身的最小迭代次数。在实际迭代次数达到这个最小迭代次数 之前，与这个节点联系的信息可以最优地传递给二分图的剩余部分。如果某个 变量节点的短圈越大，那么该变量节点发出的信息被传递给自身的正反馈信息 将越小，则译码性能也越好。所以，使变量节点的短圈尽量大，从而提高码性能。
二分图中短圈破坏了 LDPC 码的性能。LDPC 码校验矩阵的图形表示形式 是二分图，二分图和校验矩阵之间具有一一对应的关系，一个 M×N 的奇偶校 验矩阵 H 定义了每个具有 N 比特的码字满足 M 个奇偶校验集的约束。一个二 分图包括 N 个变量节点，每个节点对应 H 中的一个比特位；还包括 M 个奇偶 校验节点，每个节点对应一个 H 中的奇偶校验。校验节点连到将要进行校验的 变量节点上；具体地，当第 m 个校验涉及第 n 个比特位，即 Hm,n=1 的时候，将 有一根连线连接校验节点 m 和比特节点 n。二分图名称的由来就是它包括两类 节点，即变量节点和校验节点。二分图中的总边数和校验矩阵中非零元素的个数相等。
图 2-19 说明了 x1、x2 通过长度为 4 的短圈相互联系。图 2-20 说明了 x1、 x2、x3 通过长度为 6 的短圈相互联系，而 LDPC 码的信息传递译码算法假定变 量节点是相互独立的，短圈的存在必然破坏了独立性的假设，使得译码性能明 显下降。事实上，长度为 4、6 的短圈的存在使得变量节点在迭代译码的过程 中频繁地给自身传递正反馈信息，这对于迭代译码而言是不希望出现的。例如， Turbo 码也是迭代译码的，它正是使用交织器来减少这种正反馈效应。对于没 有圈（Cycle Free）的 Tanner 图，信息传递算法会导致最优解码，而短圈的 存在使得信息传递算法是一种次优（Sub-optimality）的迭代译码算法，事实上，最短圈长度越长，信息传递算法越接近最优算法。
图 2-21 为奇偶校验矩阵中长度为 4 短圈在 LDPC 码奇偶校验矩阵中出现 的一般形式的示意图。
图 2-22 为校验矩阵中长度为 6 短圈在 LDPC 码奇偶校验矩阵中出现的一 般形式的示意图。

可见，LDPC 码二分图中的短圈将恶化 LDPC 码的性能，所以无论对于正 则码，还是对于非正则码，找到消除短圈的算法是至关重要的。
综上所述，构造短圈尽量少的 LDPC 码原则如下：首先，被选择的码的最 短圈的长度 Girth 应该尽量大；其次，对于具有同样大小短圈的码，被选择的 码的最短圈的数目应该尽量少。

2.3.8　QC-LDPC 码的短圈特性

图 2-23 为 4 个单位矩阵的基础矩阵在 H 中构成长度为 4 的短圈的示意图。
根据 QC-LDPC 码的基础矩阵定义，其基础矩阵和对应的奇偶校验矩阵在 本质上是一样的。基础矩阵仅仅是奇偶校验矩阵的压缩形式，在给定提升值的 条件下定义 QC-LDPC 码的基础矩阵的短圈就是它的扩展矩阵的短圈，基础矩 阵的短圈是一个省略的说法。



在实际应用中，扩展矩阵是由基本矩阵扩展得到的，标准置换矩阵的维数z一般都是偶数。通过分析校验矩阵的拓扑可知， 扩展矩阵中zxz的分块矩阵和基础矩阵的元素是唯一对应的。如果基础矩阵中某些元素不构成短圈，那么这些元素对应的分块矩阵在扩展矩阵中也将不构成短圈。所以，为了研究扩展矩阵的短圈，仅需要考虑当基础矩阵中出现短圈的情况。
根据上述结构， 可以得到不同短圈条件下LDPC校验矩阵H应具有的矩阵结构。设提升值z为偶数，则有以下结论。
(1) LDPC奇偶校验矩阵Girth≥6的充分必要条件为：在基础矩阵中，对于所有按逆时针(顺时针效果等同)方向构成了长度为4的短圈的任意元素i，j， k， l， 总有mod(i-j+k-1， z) ±0。
(2) LDPC奇偶校验矩阵Girth≥8的充分必要条件为：在基础矩阵中，对于所有按逆时针方向构成了长度为4的短圈的任意元素i，j，k，l，总有mod(i-j+k-l， z) ±0； 且对于所有按逆时针方向构成了长度为6的短圈的任意元素i， j， k， l， m， n， 总有mod(i-j+k-l+m-n， 2) ±0。
(3) LDPC奇偶校验矩阵Girth≥10的充分必要条件为：在基础矩阵中，对于所有按逆时针构成了长度为4的短圈的任意元素i， j， k， l， 总有mod(i-j+k-l，z/2)车0；对于所有按逆时针构成了长度为6的短圈的任意元素i，j，k，l，m， n， 总有mod(i-j+k-l+m-n， 2) 车0； 且对于所有按逆时针构成了长度为8的短圈的任意元素i， j， k， l， m， n， s， t， 总有mod(i-j+k-l+m-n+s-t， 2) ±0。(4) 当Girth≥10时， 提高Girth对译码器的性能， 所以只需要考虑消除长度为4、6和8的短圈。
满足以上特性的LDPC码被称为高Girth的LDPC码， 文献[42] 的3/4码率的高Girth的LDPC码矩阵和文献[43] 的5/6码率的高Girth的LDPC码在WiMAX标准中得到应用。