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ì)角線(xiàn)上的元素全部為GF(q)域上的非“0”元素,，并且剩余的非“0”元素全部對(duì)應(yīng)于對(duì)角線(xiàn)左邊。若構(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ì)角線(xiàn)上元素設(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ì)角線(xiàn)右側(cè)下三角部分

    首先采用后項(xiàng)迭代算法從最后一列變量節(jié)點(diǎn)構(gòu)造，根據(jù)變量節(jié)點(diǎn)度分布^[14]向前連接校驗(yàn)節(jié)點(diǎn),。每列中第一個(gè)非“0”元素位置必須與對(duì)角線(xiàn)上校驗(yàn)節(jié)點(diǎn)連接,，其余非“0”元素需添加在對(duì)角線(xiàn)左側(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ì)角線(xiàn)上元素均為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ì)角線(xiàn)上系數(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碼的線(xiàn)性復(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)