低秩循環(huán)矩陣的構(gòu)造方法及其關(guān)聯(lián)的多元LDPC碼

徐恒舟 朱 海* 馮 丹 張 博 周慢杰

①(周口師范學(xué)院網(wǎng)絡(luò)工程學(xué)院 周口 466001)

②(西安郵電大學(xué)通信與信息工程學(xué)院 西安 710121)

1 引言

5G標(biāo)準(zhǔn)化的基礎(chǔ)功能階段已經(jīng)完成，而標(biāo)準(zhǔn)化的下一階段主要面向物聯(lián)網(wǎng)/垂直行業(yè)應(yīng)用場(chǎng)景，提供支撐未來10年信息社會(huì)的無線通信傳輸方案[1]。這里，標(biāo)準(zhǔn)化主要包括兩方面：高可靠低時(shí)延通信業(yè)務(wù)(Ultra Reliable &Low Latency Communication, URLLC)和大規(guī)模機(jī)器通信(massive Machine Type Communication, mMTC)[2]。與5G不同的是，6G的“萬物隨心”愿景需要同時(shí)滿足實(shí)時(shí)性、可靠性、吞吐量和海量連接的需求，這將對(duì)新一代無線通信網(wǎng)絡(luò)提出全新的挑戰(zhàn)[1]。本文主要討論低時(shí)延高可靠通信的信道編碼技術(shù)。這些通信業(yè)務(wù)主要面向以機(jī)器通信為代表的物聯(lián)網(wǎng)，具有小數(shù)據(jù)包、低功耗、海量連接、強(qiáng)突發(fā)性等特點(diǎn)，需要編譯碼速度快、抗突發(fā)能力強(qiáng)和碼長(zhǎng)較短的信道編碼方案。時(shí)延和可靠性指標(biāo)通常一起考慮，指的是在一定正確傳輸概率下通信系統(tǒng)的最大傳輸時(shí)延。對(duì)信道編碼而言，就是要求編譯碼處理時(shí)延較低，并消除譯碼算法所產(chǎn)生的錯(cuò)誤平層。結(jié)合軟輸出迭代譯碼，LDPC碼是一種有競(jìng)爭(zhēng)力的實(shí)用信道編碼技術(shù)。研究表明[3]，在中短碼長(zhǎng)下，與相同比特長(zhǎng)度下的二元LDPC碼相比，多元LDPC碼有以下優(yōu)勢(shì)：(1)有更多(1～1.3 dB)的編碼增益；(2)有更強(qiáng)的抗突發(fā)錯(cuò)誤能力；(3)更易于與高階調(diào)制相結(jié)合。近年來，在迭代譯碼框架下，多元LDPC碼譯碼復(fù)雜度高的問題也得到了有效的解決[4-8]，這為多元LDPC碼的應(yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)。而在迭代譯碼中，LDPC碼校驗(yàn)矩陣的冗余行可以加快譯碼收斂速度[9]，從而有效地減少譯碼時(shí)延。此外，在圖像處理中，自然圖像的數(shù)據(jù)矩陣通常都是低秩或者近似低秩的[10]。也就是說，這些矩陣的每行(或列)均可由其他的行(或列)線性表示，從而包含了大量的冗余信息。基于這些冗余信息可以去除圖像的噪聲信息，并恢復(fù)出正確的圖像信息，還可以恢復(fù)錯(cuò)誤的圖像信息[11]。然而，關(guān)于低秩矩陣構(gòu)造的研究相對(duì)較少。綜上，研究低秩矩陣(或者冗余行較多的矩陣[12])的構(gòu)造方法是十分有意義的。

循環(huán)矩陣具有循環(huán)移位性質(zhì)，很容易基于線性移位寄存器進(jìn)行硬件實(shí)現(xiàn)。因此，本文主要研究低秩循環(huán)矩陣的構(gòu)造方法。這里的循環(huán)矩陣指的是一個(gè)大小為 L×L的方陣，它的每一行是上一行的右(或左)循環(huán)移位，第1行是最后一行的右(或左)循環(huán)移位；它的每一列是它左邊一列的向下(或上)循環(huán)移位，第1列是最后一列的向下(或上)循環(huán)移位。顯然，循環(huán)矩陣的行重和列重是相同的。分別基于歐氏幾何和Reed-Solomon碼，文獻(xiàn)[13]給出了這類循環(huán)矩陣的構(gòu)造方法；文獻(xiàn)[14]則利用2維的最大距離可分(Maximum Distance Separable, MDS)碼構(gòu)造了一些循環(huán)矩陣，但這些代數(shù)方法所得到的循環(huán)矩陣數(shù)量有限。基于循環(huán)碼和同構(gòu)理論，文獻(xiàn)[15]給出了循環(huán)矩陣的計(jì)算機(jī)窮搜索方法。但是，隨著矩陣大小和行(或列)重的增大，搜索空間會(huì)急劇增大，尋找和確定不同構(gòu)類將變得異常困難。此外，文獻(xiàn)[16]研究了循環(huán)矩陣的秩性質(zhì)，并基于本原多項(xiàng)式給出了滿秩循環(huán)矩陣的構(gòu)造方法。

本文首先利用同構(gòu)理論降低了循環(huán)矩陣的搜索空間，然后利用求秩算法搜索得到不同秩的循環(huán)矩陣。與文獻(xiàn)[15]不同的是，本文利用計(jì)算秩的方式直接尋找不同秩的循環(huán)矩陣，而不再尋找并劃分循環(huán)矩陣的同構(gòu)類。進(jìn)一步地，本文研究了循環(huán)矩陣Tanner圖中長(zhǎng)度為4的環(huán)(簡(jiǎn)記為4-環(huán))結(jié)構(gòu)，并提出確定4-環(huán)的算法，還給出了非零元賦值方法，從而提出了圍長(zhǎng)至少為6的多元LDPC碼構(gòu)造方法。數(shù)值仿真結(jié)果表明，在加性高斯白噪聲(Additive White Gaussian Noise, AWGN)信道中，所構(gòu)造的多元LDPC碼有很好的迭代譯碼性能，并且在迭代5次與50次下的性能曲線幾乎重疊。

2 基于同構(gòu)理論的低秩循環(huán)矩陣構(gòu)造方法

2.1 循環(huán)矩陣及其同構(gòu)理論

2.2 基于同構(gòu)理論的低秩循環(huán)矩陣構(gòu)造方法

這樣可以進(jìn)一步降低位置集合S的搜索空間。由于實(shí)際的需求，我們只需構(gòu)造具有特定秩的循環(huán)矩陣。由循環(huán)矩陣的大小可知，循環(huán)矩陣秩的最小值為1，最大值為L(zhǎng)。由于本文主要關(guān)注低秩矩陣，為了減少搜索空間，這里設(shè)置一個(gè)閾值R，只需尋找秩小于R的循環(huán)矩陣。

由上可知，循環(huán)矩陣的窮搜索等價(jià)于位置集合S的窮搜索，而位置集合可以簡(jiǎn)化為一個(gè)包含零元素且共有m個(gè)元素的集合。因此，循環(huán)矩陣搜索其實(shí)就是如何產(chǎn)出組合序列的問題。目前，比特移位方法是一種產(chǎn)生組合序列的有效算法。下面給出一個(gè)構(gòu)造低秩循環(huán)矩陣的搜索算法，即表1中的算法1。

為了證明算法1的有效性，表2給出部分低秩循環(huán)矩陣的搜索結(jié)果。

3 基于低秩循環(huán)矩陣的多元LDPC碼構(gòu)造

3.1 循環(huán)矩陣的4-環(huán)結(jié)構(gòu)

表1 算法1：秩小于R的循環(huán)矩陣搜索算法

表2 基于算法1搜索的部分循環(huán)矩陣

圖1 循環(huán)矩陣C中的4-環(huán)結(jié)構(gòu)

3.2 多元LDPC碼的構(gòu)造方法

本文主要研究多元LDPC碼的構(gòu)造方法。基于算法1和算法2，可以得到一個(gè)大小為 L×L的二元循環(huán)矩陣C，其Tanner圖的圍長(zhǎng)至少為6。為了構(gòu)造多元矩陣，還需要將循環(huán)矩陣C中的非零元素1替換為有限域GF(q)上的非零域元素。值得注意的是，在替換過程中，還得保證所得到的多元矩陣不是滿秩的。通常情況下，直接將矩陣C中的非零元素1隨機(jī)替換成非零域元素，那么所得到的多元矩陣基本上全是滿秩的。因此，本文采用文獻(xiàn)[19]的非零域元素賦值方法，基于一個(gè)二元循環(huán)矩陣，可以得到一套域階數(shù)、碼率均靈活可變的多元LDPC碼。不妨假設(shè)二元循環(huán)矩陣C的秩為R，那么，本文所提出的多元L D P C 碼的可選擇碼率為1 ? R,1 ? R ? 1/L,1 ? R ? 2/L,1 ? R ? 3/L,···,0。下面簡(jiǎn)單介紹兩種非零域元素的賦值方法。

表3 算法2：檢驗(yàn)循環(huán)矩陣C中是否存在4-環(huán)的算法

表4 不包含4-環(huán)的循環(huán)矩陣位置集合

方法1 將二元循環(huán)矩陣C中每一列的所有非零元素1替換為有限域GF(q)上的同一個(gè)非零域元素，這里的非零域元素是隨機(jī)選取的。這樣，就可以得到一個(gè)GF(q)上的矩陣Cq。由文獻(xiàn)[19]的定理1可知，二元循環(huán)矩陣C與多元矩陣Cq有相同的秩。因此，矩陣Cq的零空間給出了一組碼率為(1-R)、碼長(zhǎng)為L(zhǎng)的q元LDPC碼。

方法2 將二元循環(huán)矩陣C中某一列(或一些列)的非零元素1替換為有限域GF(q)上的不相同非零域元素(要求不相同)，而剩余的每一列的非零元素1替換為有限域GF(q)上的同一個(gè)非零域元素，這里的非零域元素是隨機(jī)選取的。這樣，就可以得到一個(gè)GF(q)上的矩陣Cq。通常，隨著矩陣Cq列中有不同非零域元素的列數(shù)逐漸增加，矩陣Cq的秩會(huì)逐一增加，直到滿秩。因此，矩陣Cq的零空間可以定義一組碼率可變的q元LDPC碼。

3.3 仿真結(jié)果

下面的仿真參數(shù)為AWGN信道和BPSK調(diào)制。二元LDPC碼的譯碼算法為和積算法(SPA)，而多元LDPC碼的譯碼算法為基于快速傅里葉變換(Fast Fourier Transform, FFT) 的多元和積算法(Q-ary Sum-Product Algorithm, QSPA)。選用的高階調(diào)制為QPSK, 8PSK和64-QAM調(diào)制。

考慮一個(gè)行(或列)數(shù)為31、行(或列)重為5的循環(huán)矩陣。根據(jù)表4，可以找到一個(gè)沒有4-環(huán)的循環(huán)矩陣，它的位置集合為{0, 1, 3, 7, 15}、秩為16。根據(jù)3.2節(jié)的方法1，可以構(gòu)造一組碼長(zhǎng)為31、碼率為15/31的q元LDPC碼。根據(jù)方法2，可以得到一組碼長(zhǎng)為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}。根據(jù)方法1，選擇有限域GF(64)，可以得到一個(gè)64元(31, 15)LDPC碼。圖2給出了該碼在采用迭代1次、3次和50次的QSPA下的誤碼字率(Word Error Rate, WER)性能。為了在相同碼參數(shù)(等效比特碼長(zhǎng)和碼率)下比較，這里基于PEG算法構(gòu)造了一個(gè)二元(186, 90)LDPC碼[20]。圖2也給出了該碼在采用迭代50次的SPA下的誤碼字率性能和碼長(zhǎng)為186 bit、碼率為15/31的有限長(zhǎng)性能限(PPV Bound)[21]?？梢钥闯?，當(dāng)?shù)螖?shù)為50和誤碼字率等于10-5時(shí)，所構(gòu)造的64元(31, 15)LDPC碼比二元(186, 90)LDPC碼約有0.9 dB的編碼增益。此外，還可以看出所構(gòu)造的64元(31, 15)LDPC碼在迭代3次和50次之間的性能差距很?。划?dāng)誤碼字率等于10-5時(shí)，所構(gòu)造的64元(31, 15)LDPC碼離有限長(zhǎng)性能限約1 dB。圖3給出了所構(gòu)造的64元(31, 15)LDPC碼和二元(186, 90)LDPC碼在高階調(diào)制下的誤碼字率性能?？梢钥闯?，隨著調(diào)制階數(shù)的增大，所構(gòu)造的多元碼與二元碼的性能差距也變大，而且所構(gòu)造的多元碼在迭代5次和50次的性能曲線幾乎重疊。根據(jù)方法1，選擇有限域GF(4), GF(32)和GF(128)，可以得到3個(gè)(31, 15)多元LDPC碼。圖4給出了這3個(gè)碼在迭代5次和50次的QSPA下的誤碼字率性能。由圖4可知，所構(gòu)造的多元LDPC碼有較好的譯碼性能，并且在誤碼字率10-6處沒有出現(xiàn)錯(cuò)誤平層。此外，所提出的多元LDPC碼只需迭代5次就可以達(dá)到迭代50次的譯碼性能。

圖2 GF(64)上的(31, 15)LDPC碼和基于PEG算法構(gòu)造的二元(186,90)LDPC碼在不同迭代次數(shù)下的誤碼字率性能比較

圖3 GF(64)上的(31, 15)LDPC碼和基于PEG算法構(gòu)造的二元(186,90)LDPC碼在高階調(diào)制下的誤碼字率性能比較

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

4 結(jié)束語

本文研究了一類低秩循環(huán)矩陣的構(gòu)造方法。首先將循環(huán)矩陣的構(gòu)造轉(zhuǎn)化為非零元素位置集合的設(shè)計(jì)，并基于位置集合的同構(gòu)理論提出了低秩循環(huán)矩陣的搜索算法。進(jìn)一步地，分析了循環(huán)矩陣的4-環(huán)結(jié)構(gòu)，得到了圍長(zhǎng)至少為6的循環(huán)矩陣?；诖耍梅橇阌蛟氐膬煞N賦值方法，提出了多元LDPC碼的構(gòu)造方法。AWGN信道上的數(shù)值仿真結(jié)果表明，所構(gòu)造的多元LDPC碼有較好的譯碼性能，并且只需迭代5次就能達(dá)到迭代50次的譯碼性能。這為低時(shí)延高可靠無線通信提供了一種有效的候選編碼方案。為了進(jìn)一步提升這類碼的性能，如何優(yōu)化它們的非零域元素是值得研究的。