0 引言

    隨著移動(dòng)互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的不斷發(fā)展，第五代移動(dòng)通信(Fifth-Generation Mobile Communication Technology，5G)面臨移動(dòng)通信爆發(fā)式增長(zhǎng)^[1-2]。5G技術(shù)不僅需要大幅度提升頻譜利用效率，而且需要具備支持海量設(shè)備連接的能力^[3-6]。由于低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼具有高可靠性、快速收斂性及較強(qiáng)抗突發(fā)錯(cuò)誤能力^[7-8]，可以提高系統(tǒng)有效性^[9-10]，使得3GPP RAN1會(huì)議在2016年確定在5G移動(dòng)通信中使用LDPC碼作為移動(dòng)帶寬eMBB業(yè)務(wù)數(shù)據(jù)的長(zhǎng)碼塊編碼方案。

    本文對(duì)2004年由王鵬提出的LDPC碼迭代編碼算法^[11]進(jìn)行改進(jìn)，轉(zhuǎn)變?yōu)檫m用于多元LDPC碼的編碼算法，稱(chēng)為多元迭代編碼算法；2005年，Hu Xiaoyu提出了漸進(jìn)邊增長(zhǎng)（Progressive Edge Growth，PEG）構(gòu)造算法^[12]，該算法譯碼性能好，但編碼復(fù)雜度較高。本文針對(duì)PEG算法具有高編碼復(fù)雜度這一缺點(diǎn)，提出改進(jìn)的PEG算法，即irPEG算法；結(jié)構(gòu)化構(gòu)造算法，即QC-LDPC構(gòu)造算法^[13]，該算法復(fù)雜，譯碼性能差于隨機(jī)構(gòu)造算法，但復(fù)雜度大幅度下降，硬件實(shí)現(xiàn)性強(qiáng)。本文提出一種改進(jìn)的QC-LDPC算法，使校驗(yàn)矩陣具有下三角結(jié)構(gòu)，降低復(fù)雜度，加快收斂速度，構(gòu)造出無(wú)短環(huán)的校驗(yàn)矩陣。然后，從編碼復(fù)雜度和糾錯(cuò)性能兩方面考慮，基于多元迭代編碼算法，提出混合構(gòu)造算法，即HC構(gòu)造算法，將隨機(jī)構(gòu)造和結(jié)構(gòu)化構(gòu)造算法結(jié)合，irPEG算法構(gòu)造基矩陣，改進(jìn)的QC-LDPC算法生成循環(huán)移位矩陣和有限域系數(shù)矩陣，消除短環(huán)影響，設(shè)置校驗(yàn)矩陣個(gè)數(shù)，從中選取最優(yōu)校驗(yàn)矩陣。該算法既具有隨機(jī)構(gòu)造的隨機(jī)性，又保持結(jié)構(gòu)化構(gòu)造的低復(fù)雜度，降低結(jié)構(gòu)化構(gòu)造對(duì)誤碼性能帶來(lái)的損失，是比較折中的算法。

1 多元迭代編碼算法

    在圖1中對(duì)角線上的元素全部為GF(q)域上的非“0”元素，并且剩余的非“0”元素全部對(duì)應(yīng)于對(duì)角線左邊。若構(gòu)造出的多元LDPC校驗(yàn)矩陣具有圖1的結(jié)構(gòu)，則在編碼過(guò)程中可直接采用迭代編碼算法編碼。

其中，l∈[0，n-k-1]，h_i，j表示校驗(yàn)矩陣H中第i行j列上的元素，且k=n-m。由式(1)知，多元迭代編碼算法過(guò)程為利用校驗(yàn)矩陣H中各行約束關(guān)系，采用后項(xiàng)迭代算法，逐次計(jì)算每個(gè)校驗(yàn)位符號(hào)值。

    對(duì)迭代編碼算法改進(jìn)，將二元迭代編碼時(shí)采用的與(AND)和異或(XOR)運(yùn)算，改進(jìn)為GF(q)域上乘法和加法運(yùn)算。同時(shí)多元迭代編碼算法的運(yùn)算過(guò)程中引入了GF(q)域上除法運(yùn)算。對(duì)運(yùn)算量簡(jiǎn)化，將對(duì)角線上元素設(shè)置為1，式(1)改為式(2)。

2 混合構(gòu)造算法

2.1 irPEG構(gòu)造算法

    針對(duì)PEG算法具有較高編碼復(fù)雜度的缺點(diǎn)，提出一種具有下三角結(jié)構(gòu)非規(guī)則的PEG算法，即irPEG算法。該算法從編碼方案、構(gòu)造校驗(yàn)矩陣方面改進(jìn)，以降低編碼復(fù)雜度，提升糾錯(cuò)性能。具體步驟如下：

    (1)確定基矩陣中各參數(shù)

    行列數(shù)、變量節(jié)點(diǎn)度分布序列，并且初始化基矩陣的信息，包括與變量節(jié)點(diǎn)相互連接的校驗(yàn)節(jié)點(diǎn)的集合以及它的補(bǔ)集。

    (2)構(gòu)造基矩陣對(duì)角線右側(cè)下三角部分

    首先采用后項(xiàng)迭代算法從最后一列變量節(jié)點(diǎn)構(gòu)造，根據(jù)變量節(jié)點(diǎn)度分布^[14]向前連接校驗(yàn)節(jié)點(diǎn)。每列中第一個(gè)非“0”元素位置必須與對(duì)角線上校驗(yàn)節(jié)點(diǎn)連接，其余非“0”元素需添加在對(duì)角線左側(cè)。尋找所有與該變量節(jié)點(diǎn)連接的校驗(yàn)節(jié)點(diǎn)集合，從中篩選度數(shù)最小的校驗(yàn)節(jié)點(diǎn)集合。若該集合含有多元素，則從中刪除構(gòu)成短環(huán)的校驗(yàn)節(jié)點(diǎn)，隨機(jī)連接剩余某校驗(yàn)節(jié)點(diǎn)，若只有一個(gè)元素，則直接連接該校驗(yàn)節(jié)點(diǎn)。

    (3)構(gòu)造基矩陣的前n-m列

    從第n-m個(gè)變量節(jié)點(diǎn)依次向前構(gòu)造。根據(jù)初始化變量節(jié)點(diǎn)度分布序列選擇度數(shù)最小的校驗(yàn)節(jié)點(diǎn)，保證每行行重相比于平均行重相差不大。刪除構(gòu)成短環(huán)的校驗(yàn)節(jié)點(diǎn)后，從剩余校驗(yàn)節(jié)點(diǎn)中隨機(jī)連接。

    由于構(gòu)造出的矩陣具有下三角結(jié)構(gòu)，構(gòu)造時(shí)在滿(mǎn)足式(4)度分布的基礎(chǔ)上，將矩陣最后一列列重設(shè)置為1，校驗(yàn)部分對(duì)角線上元素均為1，下三角部分均為0元素。由此可見(jiàn)，可以利用式(2)直接采用后多元迭代編碼算法進(jìn)行編碼。

2.2 混合構(gòu)造算法

    雖然irPEG算法結(jié)合多元迭代編碼算法可大大降低編碼復(fù)雜度，但更適用于中短碼硬件實(shí)現(xiàn)，對(duì)于長(zhǎng)碼來(lái)說(shuō)，硬件實(shí)現(xiàn)復(fù)雜度依然較高。此時(shí)犧牲多元LDPC碼一定糾錯(cuò)性能，在改進(jìn)的QC-LDPC算法的基礎(chǔ)上使其具有下三角結(jié)構(gòu)，同時(shí)采用irPEG算法構(gòu)造基矩陣W_J×L，提高多元LDPC碼隨機(jī)性，降低結(jié)構(gòu)化構(gòu)造對(duì)糾錯(cuò)性能帶來(lái)的損失。將改進(jìn)的QC-LDPC構(gòu)造算法與irPEG算法結(jié)合，稱(chēng)為混合構(gòu)造算法，即HC構(gòu)造算法。HC構(gòu)造算法步驟如下：

    (1)irPEG算法構(gòu)造基矩陣W_J×L。

    給定多元LDPC碼度分布，根據(jù)irPEG算法構(gòu)造出具有下三角結(jié)構(gòu)二元基矩陣，大小為J×L。

    (2)確定有限域元素系數(shù)矩陣Gc_J×L，根據(jù)基矩陣非“0”元素位置，在(0，q-1)間隨機(jī)選擇gc_j，l值。

    (3)基矩陣W_J×L確定循環(huán)移位系數(shù)矩陣S_J×L。

    將循環(huán)移位系數(shù)矩陣S_J×L對(duì)角線上系數(shù)設(shè)為0，隨機(jī)選擇移位系數(shù)s_j，l，通過(guò)W_J×L結(jié)合避免長(zhǎng)度為2ⁱ的充分必要條件，如式(5)所示，確定移位系數(shù)矩陣S_J×L中移位系數(shù)s_j，l。

其中，0表示p×p維的零矩陣，P表示p×p維的單位陣，碼長(zhǎng)為n=p×L，碼率為r=(1-J/L)。HC構(gòu)造算法的流程圖如圖2所示。

3 編碼復(fù)雜度分析

    PEG算法、irPEG算法、HC算法的編碼復(fù)雜度如表1所示。其中，w是生成矩陣的平均列重，n是碼長(zhǎng)，k是信息位長(zhǎng)。

    在存儲(chǔ)復(fù)雜度方面，HC算法構(gòu)造的LDPC碼存儲(chǔ)矩陣時(shí)存儲(chǔ)一個(gè)p×p維目標(biāo)方陣P、一個(gè)J×L維多元系數(shù)矩陣GcJ×L及一個(gè)J×L循環(huán)移位系數(shù)矩陣S_J×L。irPEG算法構(gòu)造同樣大小校驗(yàn)矩陣，存儲(chǔ)一個(gè)p×J×p×L大小的校驗(yàn)矩陣?？梢?jiàn)，HC算法與irPEG算法相比具有更簡(jiǎn)單的矩陣存儲(chǔ)結(jié)構(gòu)。

    在編碼復(fù)雜度方面，PEG算法采用高斯消去編碼算法，irPEG算法和HC算法采用多元迭代編碼算法。高斯消去編碼復(fù)雜度包含預(yù)處理，運(yùn)算復(fù)雜度為o(n³)，編碼復(fù)雜度為o(n²)，整個(gè)編碼過(guò)程需wn次乘法，(w-1)n次加法。多元迭代編碼算法整個(gè)編碼過(guò)程用到(w-1)(n-k)次加法，w(n-k)次乘法。

    irPEG算法和HC算法能直接構(gòu)造出下三角校驗(yàn)矩陣，避免了校驗(yàn)矩陣預(yù)處理的同時(shí)保證了校驗(yàn)矩陣的稀疏性。因此，w相對(duì)于n可以看成非常小的常數(shù)，實(shí)現(xiàn)多元LDPC碼的線性復(fù)雜度編碼，與傳統(tǒng)的構(gòu)造算法相比，大幅度地降低了編碼的復(fù)雜度。

4 仿真結(jié)果及分析

    仿真參數(shù)設(shè)置：度分布服從式(4)的多元LDPC碼，矩陣通過(guò)PEG算法和irPEG算法生成，在十六進(jìn)制1/2碼率（Code1）和3/4碼率（Code2）下進(jìn)行仿真，Code1時(shí)，信息位長(zhǎng)為512 bit；Code2時(shí)，信息位長(zhǎng)為176 bit。譯碼采用Mixed Log-FFT-BP譯碼算法^[15]，迭代次數(shù)25，BPSK調(diào)制，AWGN信道。

    圖3和圖4分別為Code1和Code2時(shí)不同碼率下的糾錯(cuò)性能。由圖3和圖4可知，irPEG算法與PEG算法誤碼率相比，性能相差不大，表明irPEG算法構(gòu)造具有下三角結(jié)構(gòu)的多元LDPC碼在大幅度降低硬件實(shí)現(xiàn)復(fù)雜度的同時(shí)，具有較強(qiáng)的糾錯(cuò)能力。

    對(duì)Code1和Code2譯碼時(shí)間進(jìn)行測(cè)量，保持仿真環(huán)境一致性，如表2和表3所示。由表2可知，irPEG算法時(shí)間明顯比PEG算法少，當(dāng)誤比特?cái)?shù)較少時(shí)，時(shí)間節(jié)省量少于50%，隨著誤比特?cái)?shù)增加，時(shí)間節(jié)省量穩(wěn)定在50%，因此，irPEG算法耗費(fèi)時(shí)間僅為PEG算法50%。Code2在信噪比為4 dB時(shí)的仿真測(cè)試結(jié)果如表3所示，同樣表明譯碼所需時(shí)間減少一半。

    參數(shù)設(shè)置如下：碼率1/2、2/3、3/4、4/5、6/7，矩陣通過(guò)PEG和HC生成，十六進(jìn)制(Code3)下仿真，1/2碼率時(shí)，基矩陣16列，目標(biāo)矩陣P為24×24單位陣；2/3碼率時(shí)，基矩陣18列，P為16×16單位陣；3/4碼率時(shí)，基矩陣16列，P為16×16單位陣；4/5碼率時(shí)，基矩陣20列，P為12×12單位陣；6/7碼率時(shí)，基矩陣14列，P為16×16單位陣，固定信息位長(zhǎng)768 bit。圖5為Code3情況時(shí)，PEG算法與HC算法在不同碼率下的誤比特率性能。

    由圖5可知，HC算法與PEG算法構(gòu)造的多元LDPC碼在低信噪比時(shí)沒(méi)有明顯差別；在高信噪比下HC算法性能略差于PEG算法構(gòu)造的多元LDPC碼，因此兩種算法具有一致的編碼增益。

5 結(jié)論

    本文提出基于多元LDPC碼迭代編碼算法的混合校驗(yàn)矩陣構(gòu)造算法，首先對(duì)迭代編碼算法改進(jìn)，使其適用于多元LDPC碼；然后采用后項(xiàng)迭代法使PEG算法具有下三角結(jié)構(gòu)，并將其作為混合構(gòu)造算法基矩陣；最后采用改進(jìn)后具有下三角的QC-LDPC碼算法生成循環(huán)移位矩陣和有限域系數(shù)矩陣，設(shè)置校驗(yàn)矩陣的個(gè)數(shù)，從中選取最優(yōu)的校驗(yàn)矩陣，該校驗(yàn)矩陣消除了短環(huán)影響，形成混合構(gòu)造算法。仿真結(jié)果表明，本文提出的算法可以更好地適用于5G移動(dòng)通信系統(tǒng)且滿(mǎn)足譯碼算法的需求，對(duì)于高速通信設(shè)備來(lái)說(shuō)是一種很好的候選校驗(yàn)矩陣構(gòu)造算法。

參考文獻(xiàn)

[1] TANG B，YANG S H.An LDPC approach for chunked network codes[J].IEEE-ACM Transactions on Networking，2018，26(1)：605-617.

[2] MENG J H，ZHAO D F，TIAN H，et al.Sum of the Magnitude for hard decision decoding algorithm based on loop update detection[J].Sensors，2018，18(1)：236.

[3] ZHANG C，HUANG Y H，SHEIKH F.Advanced baseband processing algorithm[J].Circuits, and Implementations for 5G Communication.IEEE Journal on Emerging and Selected Topics in Circuits and Systems，2017，7(4)：477-490.

[4] DJORDJEVIC I B.Multidimensional OAM-Based secure high-speed wireless communications[J].IEEE Access，2017，5(4)：16416-16428.

[5] MALANDRINO F，CHIASSERINI C F，KIRKPATRICK C.Cellular network traces towards 5G：using，analysis and generation[J].IEEE Transactions on Mobile Computing，2018，17(3)：529-542.

[6] SOTELO M，MARCO A，MAESTRE V，et al.Reasoning and knowledge acquisition framework for 5G network analytics[J].Sensors，2017，17(10)：2405.

[7] YU Y，CHEN W.Design of low complexity non-binary LDPC codes with an approximated performance-complexity tradeoff[J].IEEE Communications Letters，2012，16(4)：514-517.

[8] SONG L Y，HUANG Q，WANG Z L.Two enhanced reliability-based decoding algorithm for nonbinary LDPC codes[J].IEEE Transactions on Communications，2016，64(2)：479-489.

[9] ZHAO S C，MA X.Construction of high-performance array-based non-binary LDPC codes with moderate rates[J].IEEE Communications Letters，2016，20(1)：13-16.

[10] XIA T，WU H C.Blind identification of nonbianry LDPC codes using average LLR of syndrome a posteriori proba-bility[J].IEEE Communications Letters，2013，17(7)：1301-1304.

[11] 王鵬，王新梅.LDPC碼的快速編碼研究[J].西安電子科技大學(xué)學(xué)報(bào)，2004，6(31)：934-938.

[12] Hu Xiaoyu，EVANGELOS E，DIETER M A.Progressive edge growth tanner graphs[J].IEEE Transactions on Information Theory，2005，51(1)：995-1001.

[13] DRAGOI V，KALACHI H T.Cryptanalysis of a public key encryption scheme based on QC-LDPC and QC-MDPC codes[J].IEEE Transactions on Information Theory，2018，22(2)：264-267.

[14] TONG N N.Research of encode and decode algorithm optimization and application for non-binary LDPC codes[D].Harbi：Harbin Engineering University，2014.

[15] SONG H，CRUZ J R.Reduced-complexity decoding of Qary LDPC codes for magnetic recording[J].IEEE Transactions on Magnetics，2003，39(2)：1081-1087.

作者信息:

孟嘉慧，趙旦峰，張  良

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱150001)