一种可节约RAM资源的准循环LDPC码的编码装置

汪毅峰，潘 涛

（上海诺基亚贝尔股份有限公司，江苏 南京 210037）

0 引言

通信系统设计的核心问题是如何克服通信信道中随机噪声的干扰，在尽可能少地影响信息传输效率的同时，减少信息的传输误差，这种在传输的信息码元后附加其他传输信息编码方式叫作纠错编码。纠错编码按照实现方式可以分为非线性分组编码和线性分组编码，其中线性分组编码根据校验矩阵的类型可以细分为非循环码和循环码两种方式。[1]

低密度奇偶校验码（Low-Density Parity-Check，LDPC）属于线性分组纠错码，早在20世纪60年代，Gallager就在他的博士论文中提出了LDPC码理论，但受限于当时的硬件计算能力，一直被人们所忽略。直到1995年MacKay和Neal等人提出了可行的译码算法后，人们发现LDPC码具有极佳的性能，是一种接近香农容量限的纠错码。随着硬件计算能力的日渐提升，LDPC码技术逐渐成为当前最炙手可热的信道编码技术。LDPC码纠错能力强、编码效率高，而且码率可从1/2至15/16中选择，十分灵活。目前，LDPC码的相关理论技术也日趋成熟，并且出现了很多成熟的研究成果，并逐渐进入了多项无线通信技术标准，例如数字广播电视、WiMax和新无线（New Radio，NR）的物理层数据信道等标准都支持LDPC编码，尤其是NR在标准讨论之初，就明确了凡是物理层数据信道，编码方案都使用LDPC码[2-5]。

1 一种基于准循环LDPC编码装置

NR在物理数据信道，选择使用LDPC编解码方案，并且写入了标准《3GPP TS 38.212 物理层复用和信道编码协议》[6-8]。LDPC码作为最具发展潜力和应用前景的一类分组纠错码，其挑战在于编码复杂，且并行译码算法的硬件资源的开销大。为充分发挥LDPC码的性能优势，并合理控制硬件复杂度，通常寻求码字校验矩阵具有一定规律的LDPC编码。然而，使用规则LDPC编码方式时，其编码性能明显低于不规则LDPC编码，特别是采用和积译码算法时性能损失大。此外，虽然循环码具有简单的编码器，但遗憾的是，相比于其他性能优异的编解码方案，循环码性能同样有损失，而准循环码却具有更良好的性能。准循环码可以用在规则LDPC编码上，也可以用在非规则LDPC编码上，同时具有相对较低复杂度的编码结构，所以应用更广泛，例如，WiMax标准中就支持非规则的LDPC准循环码的编码方案。FPGA是目前通用的逻辑器件，可以有效实现QC-LDPC码的编码以及相对应的译码算法[6,8]。

假设QC-LDPC选择的校验矩阵H1是一个m行n列的矩阵，QC-LDPC步骤简单阐述如下：

（1）对选择的校验矩阵H1进行线性变化得到一个如图1所示的矩阵，可以看到原来的校验矩阵H1被拆成A,B,T,C,D,E6个子矩阵。行列重排存在切分后，存在某个子矩阵列的维数和码元比特输出行的维数均为N-M，满足矩阵相乘，这样的矩阵切分可以大大减少运算量，其中N是校验矩阵总行数，M是校验矩阵全0行数，g是校验矩阵除掉全0行数和对角矩阵后的剩余行数。

图1 行列变换后的校验矩阵

（2）对分解后的校验矩阵H1进行矩阵变换，构造矩阵如式（1），得到新的校验矩阵H如式（2）所示。构造的矩阵要避免生成的新校验矩阵短环的问题，这是从LDPC角度考虑的，因为要保证LDPC迭代译码时，能充分利用码字内各比特的相关性，构造矩阵：

式中：I为单位矩阵。

（3）设进入编码器分为有效信息S和校验信息P1和P2两部分，有效信息的编码长度为g，校验信息的编码长度为M-g，则得到：

（4）通过式（3）进行线性变换，找到校验信息和有效信息之间的关系如式（4），注意到 -ET-1B+D要为一个非奇异矩阵，这是因为在约束校验信息和有效信息之间需要对这个矩阵求逆，如果不能满足非奇异特性，就不存在逆矩阵，所以在校验矩阵分块的时候也需要考虑到这一点。根据式（3）可以推导出：

基于如上分析和推导，假设在NR的物理层数据信道[9,10]采用QC-LDPC对数据进行编码，编码速率R=5/6，码长为576 bits，即72 Bytes，公共因子Zf=24。设码字校验矩阵为H，如式（5）；H是96行576列的稀疏矩阵，并设其基矩阵为Hb，如式（6）。

式中：A为72行480列的矩阵；B为72行24列的矩阵；T为72行72列的矩阵；C为24行480列的矩阵；D为24行24列的矩阵；E为24行72列的矩阵。

基于矩阵Hb生成校验矩阵H的规则为：

式中：p(i,j)为Hb的第i行第j列的元素；为向下取整运算；p(f,i,j)为运算结果。设I24为24阶单位阵，当p(f,i,j)小于0时，相对的元素以24行24列0矩阵代替，当p(f,i,j)等于0时，相对的元素以I24代替，当p(f,i,j)大于0时，相对的元素以I24的向右循环移位矩阵代替，移位位数为p(f,i,j)。

LDPC码也属于分组码的范畴，以组为单位对码元进行编码[4,5]，设码元信息bit为uT，其中u为480列的行向量。设v为编码的码字，LDPC编码结果v可以表示为：

简便起见做如下约定：

令α=ET-1A+C，β=T-1(A+BET-1A+BC)，则α为24行480列的矩阵，β为72行480列的矩阵，式（8）可以简写为：

式中：I480为480阶单位阵；α和β都是常数矩阵。

式（11）即可作为LDPC的编码校验矩阵。

2 简化准循环LDPC编码方法

由于α，β和u都是维数较大的矩阵或向量，如果直接这样实现则需要较多的逻辑资源。为进一步简化准循环LDPC码的编码复杂度，在编码装置设计中，充分发挥LDPC码的最大特点，即校验矩阵的稀疏特性，并且为了合理有效地利用FPGA资源，特别是减少FPGA硬件逻辑资源和RAM存储资源，提出一种简易的准循环码编码装置。该装置采取流水线的方式，利用移位寄存器来实现，即u以比特逐个进入，依次进行与运算并进行模2求和，一组信息全部完毕后再逐个输出编码码字。编码电路如图2所示。

图2 QC-LDPC编码方案硬件电路

这样的编码方式仍然会耗费很多的FPGA的RAM资源，非常不经济，对此本文充分利用LDPC校验矩阵的稀疏特性来简化编码装置。经计算，发现α和β同样为稀疏矩阵，其中α的每行中有61个1，其余为0，而β的每行中，只可能是36个1或51个1或81个1，都远小于其列数480。

以4字节（32 bits）表示α，β和u的行，则α变为24行15列的矩阵，β为72行15列的矩阵，u变为长为15的行向量。这样共需15次移位可完成整个运算。设α，β和u分别表示为：

式中：xij表示矩阵x的第i行32(j-1)+1位至第32j位bit中1所在的位置，有几个1就有几个值需要被表示。这样u以32 bits为单位逐个表示，依次与ai，j和bi，j进行按位与运算，并对结果模2求和，一组信息全部完毕后再逐个输出，得到编码的码字。编码电路可改变为图3。

图3 基于QC-LDPC的简化编码装置结构

由于每个元素ai，j和bi，j的位数均为32位，因此最多只需5 bits就能表示32位中任意一个bit的位置。例如，α1.1，即α第一行的前32列元素可表示为{10000 00000 00100 00100 00000 10000 10}，共有5个1，分别位于第0，12，17，25，30位，其余均为0。为节省存储空间忽略元素0，只将元素1所在的位置表示出来，则α1.1=(0,12,17,15,30)，即α1.1可表示为{0 1100 10001 11001 11110}，共 20 bits，便可表示原来的32 bits校验矩阵所要表示的信息。类似地，可得到其他ai，j和bi，j的位置表示。

经计算，采用新的基于存储有效信息地址的方式，最后可用22 234 bits表示α和β，而本来共需96×480=46 080 bits来表示，可见本编码方案大大缩小了对RAM的需求，可节约一半左右的RAM的存储空间资源。

3 结语

本文对QC-LDPC编码提出的改进方式，可以使得LDPC编码装置更加合理有效地利用FPGA资源。本文方法以移位寄存器方式实现LDPC码的编码，采取流水线结构来减少FPGA硬件逻辑资源，并通过矩阵变换，以非0元素的位置代替原稀疏矩阵的矩阵表示，从而大大降低了RAM存储资源，节省了编码器的硬件资源。