LDPC介绍与OAI模块实现

bigbing

###  简单介绍

LDPC中文全称为低密度奇偶校验码，是线性分组码的一种。LDPC的校验矩阵H是一个稀疏矩阵，这也是LDPC中低密度一说的由来。得益于校验矩阵H的稀疏特性，LDPC的H矩阵可以按照稀疏特性存储以减少存储空间。稀疏的校验矩阵H使得LDPC的译码具有线性的复杂度，即当编码长度增加时译码复杂度会线性的增加。

LDPC编码由校验矩阵H获得 ，这与我们所了解的线性分组码有所不同，例如循环码。校验矩阵H是设计LDPC编码的关键所在。校验矩阵H的设计方式有多种，诸如QC-LDPC、 Gallager构造法(下图)等等。LDPC校验矩阵H的性能以及特征关系到LDPC编码的效率以及解码的情况。

![image-20230622163419004]()

根据校验矩阵获得LDPC码序列同样也有多种方法。传统的高斯消元得到码生成矩阵G生成LDPC码序列的方式计算量大但非常的便捷，类似的方法还有上三角矩阵法以及准上三角矩阵法。LDPC还有一种迭代式的编码方式，这里不再赘述。综上，LDPC的编码可分解为两步：①构造校验矩阵H；②选择适当的方法生产LDPC码序列。

LDPC的解码是LDPC编码形式的灵魂所在。与传统的线性分组码所不同的是，LDPC不再采用基于校验矩阵与纠错图样的方式来解码，而是使用迭代的译码方式进行译码（这部分将在LDPC解码原理部分介绍）。软迭代的方式使得LDPC的译码复杂度降低译码速度大大增加且译码准确度极高。

###  LDPC编码

3GPP 38.212中规定NR中所使用的LDPC为QC-LDPC。QC-LDPC中文全称为准循环低密度奇偶校验码。按照前文所述，我们先讨论QC-LDPC的校验矩阵生成。

QC-LDPC的校验矩阵由38.212中的基本图形规定（Base Graph, BG），并由BG扩展成大校验矩阵H。在38.212中定义了许多BG矩阵![img]()，![img]()矩阵中的非稀疏元素均为非负整数。![img]()的部分元素如下图所示：

![img]()

Zc中的每一个元素将由一个方阵替换得到最终的校验矩阵H。38.212使用单位矩阵的移位所得到的矩阵对Zc进行填充。首先选定单位矩阵的宽度Zc，其中Zc的值在标准中也有所规定。我们根据如下公式选择![img]()的值：

![img]()

其中B表示输入序列的长度，M为BG的列向量个数。

根据得到的Zc值即可扩充BG矩阵得到校验矩阵H。首先，我们将BG矩阵中的稀疏元素全部用宽为Zc的全零矩阵替换；其次，我们将BG中的所有其他非稀疏元素对Zc取模得到循环位移值；最后，我们将宽为Zc的单位矩阵根据上一步得到的位移值进行循环移位然后填入BG相应的位置得到最终的校验矩阵H。

得到校验矩阵后根据**Hc**=**0**计算出LDPC码序列。在OAI中，LDPC的编码使用高斯消元法得到的生产矩阵G进行计算。需要注意的是OAI中目前只支持BG1与BG2以及部分Zc的QC-LDPC编码。

在目录ran/openair1/PHY/CODING/nrLDPC_encoder下，Gen_shift_value.h中存有BG1与BG2的多种准循环位移值矩阵。其余的nrLDPC头文件均为一些LDPC编码的宏定义信息。time_meas依赖为LDPC编解码中统计时间信息的函数结构体与宏。ldpc_generate_coefficient.c与ldpc_encode_parity_check.c均为LDPC奇偶校验部分编码的链接文件，所不同的是前者是单纯的LDPC编码而后者加入了CPU指令集优化。同样的是，ldpc_encoder.c、ldpc_encoder2.c、ldpc_encoder_optim.c、ldpc_encoder_optim8seg.c与ldpc_encoder_optim8segmulti.c均为LDPC的编码文件，所不同的地方在于是否使用优化或者优化方式是否相同。

与38.212中相同的是，OAI同样将LDPC码序列的生产过程分为两步：①块序列c（对比38.212）的移位填入；②奇偶检验比特序列d的生成并与c合并。在这两个过程中我们重点介绍第二步中检验比特序列d的产生。



![img]()

在encode_parity_check_part_orig函数中，函数调用choose_generator_matrix函数用来选择偏移值矩阵并将矩阵指针传给encode_parity_check_part_orig函数。最后encode_parity_check_part_orig函数根据输入参数返回序列d。

接下来我们将介绍优化后编码的实现。在ldpc_encoder2.c源文件中提供了基于SSE与AVX2以及多向量运算优化的编码函数。这些函数大同小异，因此我们主要介绍ldpc_encoder_optim编码函数的实现流程。

![img]()

Ldpc_encoder_optim函数的输入输出与ldpc_encoder_orig函数相同，所不同的定在与优化函数输入中由编码样式impp结构体（impp中包含gen_code代码）。我们重点介绍优化部分，即d序列产生部分。

![img]()

LDPC_BG_ZC库中定义了部分BG1与BG2部分Zc的奇偶校验码生成函数。这些函数输入块序列c以及检验比特序列d的指针，返回计算后的d指针。函数中用到了SSE与AVX2的向量优化运算，可以提高编码速度。当encode_parity_check_part_optim函数接收到参数时会相应的从LDPC_BG_ZC库中调用相应的函数完成d序列输出。



###  LDPC解码

LDPC目前有比特翻转硬解码、软迭代和积算法以及最小和积算法等解码方式。LDPC最大的优势在软解码上，接下来简单介绍软解码原理（具体公式请参照Gallager’s paper）。无论是和积算法还是最小和积算法均采用置信传播的软迭代方式。首先根据Tanner图，我们把码节点分为比特节点与检验节点两方进行迭代。在每次比特节点与码节点迭代时会产生两个似然概率，这两个似然概率之间会不断的迭代更新以最终适应检验节点的校验。

![img]()

OAI中使用的时对数域的最小和积算法进行解码。解码模块的文件结构简洁，在目录ran/openair1/PHY/CODING/nrLDPC_decoder下。

该解码实现实现流程如下：

![img]()

各种Buf用作缓冲空间防止迭代时的数据错误也可以用来优化程序。主要的处理在cnProc（检验位处理计算）与bnProc（比特位处理计算）。检验位处理主要用于计算最小积概率以得到比特位处理所计算的和概率。而和概率则在不满足检验位时继续送往检验位用于计算新的和概率并循环此过程。

最小积概率：

![img]()

和概率：

![img]()