范文同，馬林華，林志國

（1.空軍工程大學(xué)航空航天工程學(xué)院，西安　710038；2.空軍工程大學(xué)裝備管理與安全工程學(xué)院，西安　710051）

?

一種新穎的并行級聯(lián)LDPC碼譯碼算法*

范文同1，馬林華1，林志國2

（1.空軍工程大學(xué)航空航天工程學(xué)院，西安710038；2.空軍工程大學(xué)裝備管理與安全工程學(xué)院，西安710051）

摘要：針對傳統(tǒng)的并行級聯(lián)低密度奇偶校驗碼（PCGC）譯碼算法采用串行算法導(dǎo)致譯碼延遲大，難以在實時通信系統(tǒng)中應(yīng)用的問題，提出了一種新穎的PCGC碼譯碼算法，該算法通過對各子碼進(jìn)行并行消息迭代，對相同的信息位進(jìn)行變量消息聯(lián)合更新，實現(xiàn)了PCGC碼的并行譯碼。理論分析和仿真結(jié)果表明，提出的PCGC碼譯碼算法相較于傳統(tǒng)譯碼算法譯碼延遲降低，信噪比較低時誤碼率性能弱于后者，信噪比較高時，誤碼率性能優(yōu)于后者。

關(guān)鍵詞：譯碼，延遲，誤碼率，聯(lián)合，并行級聯(lián)低密度奇偶校驗碼

0　引言

LDPC碼［1］是迄今為止發(fā)現(xiàn)的最接近香農(nóng)限的好碼之一［2］。隨著計算機(jī)技術(shù)的飛速發(fā)展和硬件集成技術(shù)的提高，LDPC碼優(yōu)異的糾錯性能吸引了諸多學(xué)者的研究，其工程化應(yīng)用研究也逐漸興起［3-5］。目前，LDPC碼已被WiMAX、DVB-S2等通信標(biāo)準(zhǔn)作為信道糾錯碼字［6-7］。

PCGC碼是一種將LDPC碼運用于并行級聯(lián)編碼結(jié)構(gòu)而得到的編碼方式。文獻(xiàn)［8］首次提出了并行級聯(lián)LDPC碼的概念，并給出了編譯碼結(jié)構(gòu)；文獻(xiàn)［9］在并行級聯(lián)譯碼中引入了最小和譯碼算法，降低了譯碼復(fù)雜度；文獻(xiàn)［10］提出了兩種低復(fù)雜度的并行級聯(lián)碼譯碼迭代終止準(zhǔn)則，降低了譯碼器時延；文獻(xiàn)［11］構(gòu)造了結(jié)構(gòu)化的并行級聯(lián)碼，提高了編譯碼的效率；文獻(xiàn)［12］在傳統(tǒng)并行級聯(lián)碼編碼結(jié)構(gòu)的基礎(chǔ)上，將信息位復(fù)制2份編碼傳輸，高信噪比下性能得到了提高；文獻(xiàn)［13］采用兩個相同的子碼構(gòu)造并行級聯(lián)碼結(jié)構(gòu)。相較于文獻(xiàn)［8］中傳統(tǒng)的PCGC碼，文獻(xiàn)［12-13］都是通過改變或限制PCGC碼結(jié)構(gòu)來獲得更好的譯碼性能。文獻(xiàn)［13］還通過部分并行譯碼，比傳統(tǒng)譯碼算法提高了譯碼收斂速率。傳統(tǒng)的PCGC碼譯碼算法采用的是子碼串行譯碼算法，延遲較大，難以在低延遲應(yīng)用場合如實時通信系統(tǒng)中應(yīng)用，且相較于文獻(xiàn)［12-13］的誤碼率性能也較差。

本文針對PCGC碼傳統(tǒng)譯碼算法中存在的上述問題，提出了一種新的譯碼算法，通過對各子碼進(jìn)行并行的消息迭代，對相同的信息位進(jìn)行變量消息聯(lián)合更新，實現(xiàn)了PCGC碼的并行譯碼，降低了譯碼延遲。仿真結(jié)果表明，本文提出的算法進(jìn)一步提升了較高信噪比下的誤碼率性能。

1并行級聯(lián)LDPC碼

PCGC碼由多個被稱為子碼的LDPC碼級聯(lián)構(gòu)成，文獻(xiàn)［8］提出的PCGC碼編碼結(jié)構(gòu)如圖1所示。其余已知文獻(xiàn)中的PCGC編碼結(jié)構(gòu)都是圖中所示結(jié)構(gòu)或是基于此結(jié)構(gòu)的變體。圖中，s0為信息比特X的直接復(fù)制，s1和s2是信息比特X通過編碼器1和編碼器2分別編碼后產(chǎn)生的校驗比特。s=［s0，s1，s2］即為PCGC編碼后生成的碼字。

圖1　PCGC編碼器結(jié)構(gòu)

令編碼器生成的碼字s經(jīng)過調(diào)制和信道后在接收端接收到的對應(yīng)數(shù)據(jù)為y=［y0，y1，y2］，即y0對應(yīng)的是信息位s0在接收端的信號，y1、y2分別對應(yīng)的是校驗位s1、s2在接收端的信號，則PCGC碼典型譯碼器結(jié)構(gòu)如圖2所示。

圖2　PCGC譯碼器結(jié)構(gòu)

圖2中，譯碼器1和譯碼器2先后進(jìn)行迭代譯碼，譯碼方式采用LDPC碼譯碼算法。譯碼器1迭代后生成傳遞給譯碼器2的外部信息p1e，譯碼器2迭代后生成傳遞給譯碼器1的外部信息p2e，譯碼器1第一次迭代時，p2e值初始化為0。

可以看出，傳統(tǒng)PCGC碼譯碼算法中譯碼器1和譯碼器2為串行關(guān)系，譯碼器2需要譯碼器1計算出外部信息p1e后才能開始消息迭代，在一定程度上相較于單個LDPC碼增加了譯碼延遲。

2本文提出的譯碼算法

定義PCGC碼的兩個LDPC子碼的校驗矩陣分別為H1和H2。不失一般性，隨機(jī)設(shè)置H1和H2如式（1）和式（2）所示，H1和H2的前部分表示系統(tǒng)信息位，后部分表示校驗位。

由文獻(xiàn)［8］中PCGC碼定義可知，校驗矩陣H1和H2的前3個符號對應(yīng)相同的系統(tǒng)信息位，兩個校驗矩陣可聯(lián)合表示如式（3）所示。由基于置信傳播的LDPC碼譯碼算法可知，新構(gòu)成的矩陣H的前3個符號可聯(lián)合更新變量信息。

以H中第一行第一列元素對應(yīng)的變量消息更新為例，除式（3）所示外，也可用Tanner圖表示如下：

圖3　PCGC碼h11處對應(yīng)的變量消息更新

信息位在矩陣H中對應(yīng)的h11處的變量節(jié)點與矩陣H1和H2中共4個校驗節(jié)點連接，變量消息可由這4個校驗節(jié)點聯(lián)合更新。

基于上述思想，本文提出的PCGC碼譯碼器架構(gòu)如下頁圖4所示。

令兩個校驗矩陣的維數(shù)分別為M1×N1和M2× N2，對應(yīng)于其的接收端信息分別為y和y'，子譯碼器采用最小和譯碼算法，本文提出的PCGC譯碼算法具體步驟如下：

圖4　本文提出的PCGC譯碼器結(jié)構(gòu)

①初始化。分別計算由信道獲得的兩個子譯碼器變量節(jié)點的初始概率似然比消息L1（Pi），L2（Pi''），，并對其相鄰的校驗節(jié)點賦值，變量消息分別表示為L1（qij）和L2（q'i'j'），表達(dá)式如下：

②分別對每個子譯碼器進(jìn)行校驗消息更新，校驗消息分別表示為，計算表達(dá)式如下：

式中，Vj和Vj''分別表示H1中與校驗節(jié)點j相連的變量節(jié)點的集合和H2中與校驗節(jié)點j'相連的變量節(jié)點的集合，Vji和Vj''i'分別表示Vj中除i外的變量節(jié)點的集合和Vj''中除i'外的變量節(jié)點的集合。

③分別對每個子譯碼器進(jìn)行變量消息更新，表達(dá)式如下：

式中，Ci和Ci''分別表示H1中與變量節(jié)點i相連的校驗節(jié)點的集合和H2中與校驗節(jié)點i'相連的校驗節(jié)點的集合，Ci j和Ci'' j'分別表示Ci中除j外的校驗節(jié)點的集合和Ci''中除j'外的校驗節(jié)點的集合。

④判決消息更新。

⑤兩個子碼均校驗成功或達(dá)到設(shè)定的最大迭代次數(shù)則輸出譯碼結(jié)果，否則重復(fù)前述步驟。

可以看出，本文提出的PCGC碼譯碼算法每個步驟均可實現(xiàn)兩個子LDPC碼的并行譯碼，即實現(xiàn)了PCGC碼的并行譯碼機(jī)制，相較于傳統(tǒng)譯碼算法的串行譯碼機(jī)制提高了譯碼迭代速率。

3仿真結(jié)果與分析

采用與文獻(xiàn)［8］中相同構(gòu)造的碼長為1 920，碼率為1/3的PCGC碼，子譯碼器均采用最小和譯碼算法，傳統(tǒng)譯碼算法最大迭代次數(shù)設(shè)置為50次，本文提出的譯碼算法最大迭代次數(shù)設(shè)置為25次，分別仿真在傳統(tǒng)PCGC譯碼算法和本文提出的譯碼算法下的性能。仿真結(jié)果如圖5所示。

圖5　碼長1 920，碼率1/3 的PCGC碼譯碼性能

圖6　碼長600，碼率1/3的PCGC碼譯碼性能

采用與文獻(xiàn)［13］中相同構(gòu)造的碼長為600，碼率為1/3的PCGC碼，子譯碼器均采用最小和譯碼算法，其余設(shè)置同上，分別仿真在傳統(tǒng)PCGC譯碼算法和本文提出的譯碼算法下的性能。仿真結(jié)果如圖6所示。

由圖5和圖6可以看出，對于短PCGC碼和中長PCGC碼，本文提出的譯碼算法在信噪比較高時誤碼率性能均好于PCGC碼傳統(tǒng)譯碼算法。本文提出的PCGC碼譯碼算法采用并行譯碼機(jī)制，相較于傳統(tǒng)譯碼算法串行機(jī)制，加快了譯碼迭代速率，提高了收斂速度，正因如此，在低信噪比時，本文提出的譯碼算法要差于傳統(tǒng)譯碼算法，原因是低信噪比下，本文提出的算法加速了錯誤信息的擴(kuò)散。

4　結(jié)論

提出了一種新的并行級聯(lián)LDPC碼譯碼算法，相較于傳統(tǒng)的譯碼算法，本文算法實現(xiàn)了各子碼的并行譯碼，提高了譯碼速率，降低了譯碼延遲，且信噪比較高時誤碼率性能更優(yōu)。本文提出的算法更便于PCGC碼在實際工程應(yīng)用中實現(xiàn)。但是，本文對于PCGC碼各子碼結(jié)構(gòu)對新算法的影響未作分析，有待下一步繼續(xù)研究。

參考文獻(xiàn)：

［1］GALLAGER R G.Low-density parity-check codes［J］.IRE Transactions on Information Theory，1962，8（1）:21-28.

［2］MACKAY D J C，NEAL R M.Near shannon limit performance of low-density parity-check codes［J］.Electronics

Letters，1996，33（6）:457-458.

［3］TAGHAVI M H，SHOKROLLAHI A，SIEGEL P H.Efficient implementation of linear programming decoding［J］.IEEE Transactions on Information Theory，2011，57（9）:5960-5982.

［4］張立軍，劉明華，盧萌.低密度奇偶校驗碼加權(quán)大數(shù)邏輯譯碼研究［J］.西安交通大學(xué)學(xué)報，2013，47（4）:35-38.

［5］TIWARI H D，HUYNH N B，YONG B C.Flexible LDPC decoder using stream data processing for 802.11n and 802.16e ［J］.IEEE Transactions on Consumer Electronics，2011，57 （4）:1505-1512.

［6］YONGMIN J，YUNHO J.Low-complexity multi-way and reconfigurable cyclic shift network of QC-LDPC decoder for Wi-Fi/WIMAX applications［J］.IEEE Transactions on Consumer Electronics，2013，59（3）:467-475.

［7］JENFA H，CHUN M H，CHAO C Y.Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth［J］.IEEE Transactions on Information Theory，2012，58（3）:1825-1836.

［8］BEHAIRY H，CHANG S.Parallel concatenated gallager codes［J］.Electron Letters，2000，36（24）:2025-2026.

［9］LI J，YOU X H，YUN H K.Low complexity decoding algorithm of parallel concatenated LDPC code［J］.Proceedings of the IEEE 6th Circuits and Systems Symposium on Emerging Technologies，2004（1）:289-291.

［10］李晉，滑翰，華驚宇，等.并行級聯(lián)LDPC碼譯碼迭代終止準(zhǔn)則研究［J］.通信學(xué)報，2006，27（4）:95-100.

［11］SERRATO J C，O’FARRELL T.Structured parallel concatenated LDPC codes［C］//In the Annual London Conference on Communications（LCS 2006），2006.

［12］CATHERINE P C.Parallel concatenation of LDPC codes with two sets of source Bits［C］//2011 4th International Conference on Emerging Trends in Engineering and Technology，2011，112-115.

［13］KUMAR，PRAVIN R.An efficient methodology for parallel concatenation of LDPC codes with reduced complexity and decoding delay［C］//2013 National Conference on Rakhesh Singh Communications（NCC），2013.

A Novel Decoding Algorithm for Parallel Concatenation of LDPC Codes

FAN Wen-tong1，MA Lin-hua1，LIN Zhi-guo2
（1.School of Aeronautics and Astronautics Engineering，Air Force Engineering University，Xi’an 710038，China；2.School of Equipment Management and Safety Engineering，Air Force Engineering University，Xi’an 710051，China）

Abstract：A novel decoding algorithm for parallel concatenation of LDPC codes is proposed for solving the problem of the high decoding latency in traditional PCGC decoders which are not suitable for real-time communication applications.Through parallel message passing operations for component LDPC codes in a PCGC code and combination updates for the same systematic message bit，the proposed algorithm realizes a fully parallel decoding manner，replacing the serial manner used in traditional ones.Theory analysis and simulation results show that the proposed algorithm can achieve lower decoding latency and better BER with high SNR but worse BER with low SNR，compared with the traditional PCGC decoding algorithm.

Key words：decoding，latency，bit error rate，combination，Parallel concatenated Gallager codes

作者簡介：范文同（1983-），男，江蘇鹽城人，博士。研究方向：信息編碼。

*基金項目：國家自然科學(xué)基金資助項目（61201209）

收稿日期：2015-03-01修回日期：2015-05-16

文章編號：1002-0640（2016）03-0012-03

中圖分類號：TN911.22

文獻(xiàn)標(biāo)識碼：A