低秩循环矩阵的构造方法及其关联的多元LDPC码

徐恒舟 朱 海* 冯 丹 张 博 周慢杰

①(周口师范学院网络工程学院 周口 466001)

②(西安邮电大学通信与信息工程学院 西安 710121)

1 引言

5G标准化的基础功能阶段已经完成，而标准化的下一阶段主要面向物联网/垂直行业应用场景，提供支撑未来10年信息社会的无线通信传输方案[1]。这里，标准化主要包括两方面：高可靠低时延通信业务(Ultra Reliable &Low Latency Communication, URLLC)和大规模机器通信(massive Machine Type Communication, mMTC)[2]。与5G不同的是，6G的“万物随心”愿景需要同时满足实时性、可靠性、吞吐量和海量连接的需求，这将对新一代无线通信网络提出全新的挑战[1]。本文主要讨论低时延高可靠通信的信道编码技术。这些通信业务主要面向以机器通信为代表的物联网，具有小数据包、低功耗、海量连接、强突发性等特点，需要编译码速度快、抗突发能力强和码长较短的信道编码方案。时延和可靠性指标通常一起考虑，指的是在一定正确传输概率下通信系统的最大传输时延。对信道编码而言，就是要求编译码处理时延较低，并消除译码算法所产生的错误平层。结合软输出迭代译码，LDPC码是一种有竞争力的实用信道编码技术。研究表明[3]，在中短码长下，与相同比特长度下的二元LDPC码相比，多元LDPC码有以下优势：(1)有更多(1～1.3 dB)的编码增益；(2)有更强的抗突发错误能力；(3)更易于与高阶调制相结合。近年来，在迭代译码框架下，多元LDPC码译码复杂度高的问题也得到了有效的解决[4-8]，这为多元LDPC码的应用奠定了坚实的基础。而在迭代译码中，LDPC码校验矩阵的冗余行可以加快译码收敛速度[9]，从而有效地减少译码时延。此外，在图像处理中，自然图像的数据矩阵通常都是低秩或者近似低秩的[10]。也就是说，这些矩阵的每行(或列)均可由其他的行(或列)线性表示，从而包含了大量的冗余信息。基于这些冗余信息可以去除图像的噪声信息，并恢复出正确的图像信息，还可以恢复错误的图像信息[11]。然而，关于低秩矩阵构造的研究相对较少。综上，研究低秩矩阵(或者冗余行较多的矩阵[12])的构造方法是十分有意义的。

循环矩阵具有循环移位性质，很容易基于线性移位寄存器进行硬件实现。因此，本文主要研究低秩循环矩阵的构造方法。这里的循环矩阵指的是一个大小为 L×L的方阵，它的每一行是上一行的右(或左)循环移位，第1行是最后一行的右(或左)循环移位；它的每一列是它左边一列的向下(或上)循环移位，第1列是最后一列的向下(或上)循环移位。显然，循环矩阵的行重和列重是相同的。分别基于欧氏几何和Reed-Solomon码，文献[13]给出了这类循环矩阵的构造方法；文献[14]则利用2维的最大距离可分(Maximum Distance Separable, MDS)码构造了一些循环矩阵，但这些代数方法所得到的循环矩阵数量有限。基于循环码和同构理论，文献[15]给出了循环矩阵的计算机穷搜索方法。但是，随着矩阵大小和行(或列)重的增大，搜索空间会急剧增大，寻找和确定不同构类将变得异常困难。此外，文献[16]研究了循环矩阵的秩性质，并基于本原多项式给出了满秩循环矩阵的构造方法。

本文首先利用同构理论降低了循环矩阵的搜索空间，然后利用求秩算法搜索得到不同秩的循环矩阵。与文献[15]不同的是，本文利用计算秩的方式直接寻找不同秩的循环矩阵，而不再寻找并划分循环矩阵的同构类。进一步地，本文研究了循环矩阵Tanner图中长度为4的环(简记为4-环)结构，并提出确定4-环的算法，还给出了非零元赋值方法，从而提出了围长至少为6的多元LDPC码构造方法。数值仿真结果表明，在加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道中，所构造的多元LDPC码有很好的迭代译码性能，并且在迭代5次与50次下的性能曲线几乎重叠。

2 基于同构理论的低秩循环矩阵构造方法

2.1 循环矩阵及其同构理论

2.2 基于同构理论的低秩循环矩阵构造方法

这样可以进一步降低位置集合S的搜索空间。由于实际的需求，我们只需构造具有特定秩的循环矩阵。由循环矩阵的大小可知，循环矩阵秩的最小值为1，最大值为L。由于本文主要关注低秩矩阵，为了减少搜索空间，这里设置一个阈值R，只需寻找秩小于R的循环矩阵。

由上可知，循环矩阵的穷搜索等价于位置集合S的穷搜索，而位置集合可以简化为一个包含零元素且共有m个元素的集合。因此，循环矩阵搜索其实就是如何产出组合序列的问题。目前，比特移位方法是一种产生组合序列的有效算法。下面给出一个构造低秩循环矩阵的搜索算法，即表1中的算法1。

为了证明算法1的有效性，表2给出部分低秩循环矩阵的搜索结果。

3 基于低秩循环矩阵的多元LDPC码构造

3.1 循环矩阵的4-环结构

表1 算法1：秩小于R的循环矩阵搜索算法

表2 基于算法1搜索的部分循环矩阵

图1 循环矩阵C中的4-环结构

3.2 多元LDPC码的构造方法

本文主要研究多元LDPC码的构造方法。基于算法1和算法2，可以得到一个大小为 L×L的二元循环矩阵C，其Tanner图的围长至少为6。为了构造多元矩阵，还需要将循环矩阵C中的非零元素1替换为有限域GF(q)上的非零域元素。值得注意的是，在替换过程中，还得保证所得到的多元矩阵不是满秩的。通常情况下，直接将矩阵C中的非零元素1随机替换成非零域元素，那么所得到的多元矩阵基本上全是满秩的。因此，本文采用文献[19]的非零域元素赋值方法，基于一个二元循环矩阵，可以得到一套域阶数、码率均灵活可变的多元LDPC码。不妨假设二元循环矩阵C的秩为R，那么，本文所提出的多元L D P C 码的可选择码率为1 − R,1 − R − 1/L,1 − R − 2/L,1 − R − 3/L,···,0。下面简单介绍两种非零域元素的赋值方法。

表3 算法2：检验循环矩阵C中是否存在4-环的算法

表4 不包含4-环的循环矩阵位置集合

方法1 将二元循环矩阵C中每一列的所有非零元素1替换为有限域GF(q)上的同一个非零域元素，这里的非零域元素是随机选取的。这样，就可以得到一个GF(q)上的矩阵Cq。由文献[19]的定理1可知，二元循环矩阵C与多元矩阵Cq有相同的秩。因此，矩阵Cq的零空间给出了一组码率为(1-R)、码长为L的q元LDPC码。

方法2 将二元循环矩阵C中某一列(或一些列)的非零元素1替换为有限域GF(q)上的不相同非零域元素(要求不相同)，而剩余的每一列的非零元素1替换为有限域GF(q)上的同一个非零域元素，这里的非零域元素是随机选取的。这样，就可以得到一个GF(q)上的矩阵Cq。通常，随着矩阵Cq列中有不同非零域元素的列数逐渐增加，矩阵Cq的秩会逐一增加，直到满秩。因此，矩阵Cq的零空间可以定义一组码率可变的q元LDPC码。

3.3 仿真结果

下面的仿真参数为AWGN信道和BPSK调制。二元LDPC码的译码算法为和积算法(SPA)，而多元LDPC码的译码算法为基于快速傅里叶变换(Fast Fourier Transform, FFT) 的多元和积算法(Q-ary Sum-Product Algorithm, QSPA)。选用的高阶调制为QPSK, 8PSK和64-QAM调制。

考虑一个行(或列)数为31、行(或列)重为5的循环矩阵。根据表4，可以找到一个没有4-环的循环矩阵，它的位置集合为{0, 1, 3, 7, 15}、秩为16。根据3.2节的方法1，可以构造一组码长为31、码率为15/31的q元LDPC码。根据方法2，可以得到一组码长为31、码率可变的q元LDPC码，其可选择的码率有{15/31, 14/31, 13/31, 12/31, 11/31, 10/31, 9/31,8/31, 7/31, 6/31, 5/31, 4/31, 3/31, 2/31, 1/31}。根据方法1，选择有限域GF(64)，可以得到一个64元(31, 15)LDPC码。图2给出了该码在采用迭代1次、3次和50次的QSPA下的误码字率(Word Error Rate, WER)性能。为了在相同码参数(等效比特码长和码率)下比较，这里基于PEG算法构造了一个二元(186, 90)LDPC码[20]。图2也给出了该码在采用迭代50次的SPA下的误码字率性能和码长为186 bit、码率为15/31的有限长性能限(PPV Bound)[21]。可以看出，当迭代次数为50和误码字率等于10-5时，所构造的64元(31, 15)LDPC码比二元(186, 90)LDPC码约有0.9 dB的编码增益。此外，还可以看出所构造的64元(31, 15)LDPC码在迭代3次和50次之间的性能差距很小；当误码字率等于10-5时，所构造的64元(31, 15)LDPC码离有限长性能限约1 dB。图3给出了所构造的64元(31, 15)LDPC码和二元(186, 90)LDPC码在高阶调制下的误码字率性能。可以看出，随着调制阶数的增大，所构造的多元码与二元码的性能差距也变大，而且所构造的多元码在迭代5次和50次的性能曲线几乎重叠。根据方法1，选择有限域GF(4), GF(32)和GF(128)，可以得到3个(31, 15)多元LDPC码。图4给出了这3个码在迭代5次和50次的QSPA下的误码字率性能。由图4可知，所构造的多元LDPC码有较好的译码性能，并且在误码字率10-6处没有出现错误平层。此外，所提出的多元LDPC码只需迭代5次就可以达到迭代50次的译码性能。

图2 GF(64)上的(31, 15)LDPC码和基于PEG算法构造的二元(186,90)LDPC码在不同迭代次数下的误码字率性能比较

图3 GF(64)上的(31, 15)LDPC码和基于PEG算法构造的二元(186,90)LDPC码在高阶调制下的误码字率性能比较

图4 GF(4), GF(32)和GF(128)上的(31, 15)LDPC码在迭代5次和50次下的误码字率性能

4 结束语

本文研究了一类低秩循环矩阵的构造方法。首先将循环矩阵的构造转化为非零元素位置集合的设计，并基于位置集合的同构理论提出了低秩循环矩阵的搜索算法。进一步地，分析了循环矩阵的4-环结构，得到了围长至少为6的循环矩阵。基于此，利用非零域元素的两种赋值方法，提出了多元LDPC码的构造方法。AWGN信道上的数值仿真结果表明，所构造的多元LDPC码有较好的译码性能，并且只需迭代5次就能达到迭代50次的译码性能。这为低时延高可靠无线通信提供了一种有效的候选编码方案。为了进一步提升这类码的性能，如何优化它们的非零域元素是值得研究的。