朱宏鵬 程 磊 張 劍

(解放軍理工大學通信工程學院，南京，210007)

?

可變碼長LDPC碼的GAU構(gòu)造算法*

朱宏鵬 程 磊 張 劍

(解放軍理工大學通信工程學院，南京，210007)

考慮度分布、最小環(huán)長和環(huán)近似外信息度等因素，從減少短環(huán)和增加外信息度入手，提出了可變碼長LDPC碼的GAU(Girth-ACE union)構(gòu)造算法。該算法構(gòu)造的校驗矩陣能適應較大范圍的碼長變化，其短碼的糾錯性能與802.16e中的LDPC碼相當，中長碼的性能較后者略優(yōu)。不同碼長的碼字具有結(jié)構(gòu)相同的校驗矩陣，便于編譯碼器對所有碼長采用同一架構(gòu)設計，能有效降低編譯碼器的實現(xiàn)復雜度。GAU算法適用于支持可變長度數(shù)據(jù)傳輸?shù)母黝愅ㄐ畔到y(tǒng)的LDPC碼設計，具有重要的理論意義和實用價值。

低密度奇偶校驗;最小環(huán)長;環(huán)近似外信息度

引 言

低密度奇偶校驗(Long low density parity check, LDPC)碼[1]是一類性能優(yōu)越的前向糾錯編碼技術(shù)，其糾錯性能逼近香農(nóng)極限，具有較低的實現(xiàn)復雜度，被廣泛應用于各類通信系統(tǒng)，如嫦娥探月工程的數(shù)據(jù)傳輸、GPS導航電文的播發(fā)等[2]。同一碼率的LDPC碼，碼長越長，糾錯性能越好。對于支持可變長度數(shù)據(jù)傳輸?shù)耐ㄐ艖?，如果選用固定碼長的LDPC碼來進行差錯控制，并非最佳選擇。對于較短的數(shù)據(jù)，需要補充空字符以達到編碼需要的信息長度，影響了通信的有效性；而對于較長的數(shù)據(jù)，采用較短的碼長無法達到最佳的糾錯能力，降低了通信的可靠性。如果采用碼長可變的LDPC碼，則有效性和可靠性兩個方面都能較好地兼顧。構(gòu)造碼長可變的LDPC碼，有兩種方法：(1)對不同長度的碼字分別進行設計，不同碼長對應的校驗矩陣不同；(2)對所有長度的碼字基于同一個校驗矩陣統(tǒng)一設計。方法1能夠確保每種碼字都具有很好的糾錯性能，缺點是碼型較多，實現(xiàn)復雜度高。方法2的優(yōu)點是能夠采用同一編譯碼架構(gòu)，大大降低實現(xiàn)復雜度，缺點是部分碼字性能無法達到最優(yōu)。綜合考慮糾錯性能和工程可實現(xiàn)性，本文針對方法2，重點研究如何采用同一架構(gòu)設計可變碼長的LDPC碼。QC-LDPC(準循環(huán)LDPC)[3]是一類非常重要的LDPC碼，其校驗矩陣具有準循環(huán)結(jié)構(gòu)，存在線性復雜度的快速編碼算法，且適合支持可變碼長的統(tǒng)一架構(gòu)設計。目前，QC-LDPC已被多個通信系統(tǒng)標準采用，如IEEE 802.16e，DVB-S2和802.11等。對于QC-LDPC構(gòu)造的研究很多，有基于有限幾何的構(gòu)造算法，也有基于循環(huán)移位矩陣的構(gòu)造算法。Fossorier等提出的構(gòu)造算法[3]主要考慮了短環(huán)對譯碼性能的影響，而且針對的是規(guī)則LDPC碼。相對于規(guī)則LDPC碼而言，不規(guī)則LDPC碼具有更好的糾錯性能。本文將針對不規(guī)則QC-LDPC碼，綜合考慮最短環(huán)長、最短環(huán)數(shù)目和外信息度等多個因素，對QC-LDPC碼進行構(gòu)造，并針對不同碼長對其進行適應改造，提出支持可變碼長的QC-LDPC碼構(gòu)造算法。

1 QC-LDPC碼

QC-LDPC碼是一類校驗矩陣具有準循環(huán)結(jié)構(gòu)的LDPC碼。設信息長度為k，碼長為n，校驗位的長度為m，m=n-k。校驗矩陣定義為H，大小為m×n，其形式如下

(1)

式中：Pi,j是z×z的單位循環(huán)移位矩陣或者零矩陣。定義mb×nb的基礎(chǔ)矩陣Hb，m=mb×z，n=nb×z,矩陣形式如式(2)所示，其中，si,j為-1～(z-1)之間的整數(shù)，稱為循環(huán)移位因子。

(2)

(3)

2 GAU構(gòu)造算法

基于統(tǒng)一架構(gòu)設計可變碼長的LDPC碼，重點是研究如何構(gòu)造基礎(chǔ)矩陣。設QC-LDPC碼的基礎(chǔ)校驗矩陣Hb的行數(shù)為mb，列數(shù)為nb。nb決定了碼長的變化步徑。nb越小，碼長的變化分辨率越高，對可變長度的數(shù)據(jù)業(yè)務適應能力也就越好。但是，隨著nb的減小，校驗矩陣設計過程中可控的參數(shù)也就變少，導致碼字在很多碼長上糾錯性能較差。nb的增加能提升碼字在各個碼長的糾錯性能，但會減小碼長的變化分辨率，同時還會增加編譯碼器的實現(xiàn)復雜度。綜合考慮糾錯性能、業(yè)務適應性和實現(xiàn)復雜度，基礎(chǔ)矩陣的尺寸需要確定一個適中的數(shù)值?；A(chǔ)矩陣的構(gòu)造采用半隨機、半結(jié)構(gòu)化的構(gòu)造方法，右半部分采用第1節(jié)介紹的雙對角結(jié)構(gòu)，左半部分采用隨機構(gòu)造法。構(gòu)造分為3步:度分布設計、母矩陣設計和循環(huán)移位因子構(gòu)造。

2.1 度分布設計

基礎(chǔ)矩陣的右半部分采用近似雙對角結(jié)構(gòu)，引入近半數(shù)度數(shù)為2的變量節(jié)點。度數(shù)較低的節(jié)點容易導致LDPC碼停止集的產(chǎn)生[6]，從而引起糾錯性能的下降。因此，需要在隨機構(gòu)造的校驗矩陣左半部分提升度數(shù)較高的變量節(jié)點比例。根據(jù)給定的碼率，結(jié)合右半部分結(jié)構(gòu)化構(gòu)造的度分布，在此基礎(chǔ)上采用密度演化算法[7-8]產(chǎn)生最優(yōu)的度分布。

2.2 母矩陣設計

母矩陣的尺寸與基礎(chǔ)校驗矩陣相同，設為mb×nb。母矩陣中的元素只有0和-1兩種，0對應于基礎(chǔ)矩陣中非負的循環(huán)移位因子，-1對應于基礎(chǔ)矩陣中的-1。母矩陣的設計主要是確定基礎(chǔ)矩陣中非負元素的位置。短環(huán)是導致LDPC碼糾錯性能惡化的關(guān)鍵因素之一。母矩陣的設計要盡量避免短環(huán)的產(chǎn)生或者減少短環(huán)的數(shù)目。根據(jù)前文介紹的度分布設計算法，可以確定母矩陣各列的度。定義母矩陣各列的度構(gòu)成的集合為

(4)

式中dci為第i列的度。此外，矩陣的右半部分采用結(jié)構(gòu)化設計，具有近似雙對角結(jié)構(gòu)，因此右半部分非負元素的位置可以直接根據(jù)雙對角結(jié)構(gòu)確定。本文采用PEG算法[9-11]確定母矩陣左半部分非負元素的位置。母矩陣定義為HM，行數(shù)為mb，左半部分需要構(gòu)造的列數(shù)為kb=nb-mb，第i列的度數(shù)為dci，算法描述如下。

(1)初始化：母矩陣的左半部分全部初始化為-1。

for(i=0;i

for(j=0;j

HM(i,j)=-1;}}

(2)確定非負元素位置。

for(i=0;i

for(j=0;j

①以母矩陣當前列對應的變量節(jié)點為根節(jié)點構(gòu)建擴展樹；

②if(樹的當前層尚未涉及到所有的校驗節(jié)點而下一層擴展到所有的校驗節(jié)點 or當前層和下一層均未擴展到所有的校驗節(jié)點，但兩層涉及到的校驗節(jié)點不再變化) do{

從當前層未涉及到的校驗節(jié)點中尋找度數(shù)最小的節(jié)點，若存在多個度數(shù)最小的節(jié)點，則隨機選取一個，設其對應的母矩陣的行號為Chk_Sel;

③HM[Chk_Sel][i]=0; }}}

2.3 循環(huán)移位因子構(gòu)造算法

基礎(chǔ)校驗矩陣在母矩陣的基礎(chǔ)之上產(chǎn)生，將母矩陣中的0替換為相應的循環(huán)移位因子，-1保持不變，就得到基礎(chǔ)校驗矩陣。循環(huán)移位因子的設計需要避免短環(huán)的產(chǎn)生。環(huán)長和循環(huán)移位因子的關(guān)系如定理1所示。

定理1[3]對于mb×nb的基礎(chǔ)校驗矩陣Hb，si,j表示第i行第j列的循環(huán)移位因子，si,j≠-1。

定義Δmx,my(nk)=smx,nk-smy,nk。當且僅當

(5)

基礎(chǔ)校驗矩陣Hb擴展得到的校驗矩陣H存在長度為2i的環(huán)，其中z為擴展單位陣的大小。校驗矩陣H的最小環(huán)長與循環(huán)移位因子的關(guān)系如定理2所示。

定理2[3]基礎(chǔ)校驗矩陣Hb擴展得到的校驗矩陣H的最小環(huán)長不小于2(i+1)的充要條件是

(6)

式(6)滿足所有的j(2≤j≤i)，所有的mk(0≤mk≤mb-1)，所有的mk+1(0≤mk+1≤mb-1)和所有的nk，其中m0=mj，mk≠mk+1，nk≠nk+1。定理1，2介紹了校驗矩陣的環(huán)長與基礎(chǔ)校驗矩陣中循環(huán)移位因子之間的關(guān)系。根據(jù)定理1，遍歷不同循環(huán)移位因子的過程中需要進行環(huán)長和環(huán)分布的大量統(tǒng)計，Mehdi Karimi等人提出了高效環(huán)長統(tǒng)計方法[12]，可以有效降低循環(huán)移位因子搜索過程中環(huán)長和環(huán)分布的統(tǒng)計復雜度。環(huán)的近似外信息度(Approximate cycle extrinsic, ACE)是影響譯碼性能的另一重要因素。環(huán)的ACE越大，對譯碼性能的改善越顯著。定理3給出了環(huán)的ACE與變量節(jié)點度的關(guān)系。

定理3[13]一個長度為2i的環(huán)，其ACE如下式所示

(7)

式中：dk是環(huán)中第k個變量節(jié)點的度。

循環(huán)移位因子采用GAU構(gòu)造算法，聯(lián)合考慮最小環(huán)長和近似外信息度，將母矩陣左半部分kb列非負元素“0”替換為具體的循環(huán)移位因子。對于每一個非負元素，具體構(gòu)造算法如下。

(1)初始化：循環(huán)移位因子初始化為0；

(2)計算校驗矩陣對應的Girth，ACE和最短環(huán)數(shù)目；

(3)循環(huán)移位因子從1到z-1遍歷；如果當前循環(huán)移位因子的Girth大于已選因子Girth；或者Girth相等，當前ACE大于已選因子ACE；或者Girth和ACE相等，當前最短環(huán)數(shù)目小于已選因子最短環(huán)數(shù)目；將已選因子更新為當前循環(huán)移位因子。繼續(xù)遍歷下一個循環(huán)移位因子。

(4)遍歷完成后，已選因子即為GAU算法選取的循環(huán)移位因子。

基礎(chǔ)校驗矩陣中的循環(huán)移位因子針對可變碼長中的最長碼字進行設計，其他碼長的基礎(chǔ)校驗矩陣與最長碼的基礎(chǔ)校驗矩陣結(jié)構(gòu)相同，但循環(huán)移位因子在最長碼的基礎(chǔ)上進行修改。假設最長碼的基礎(chǔ)校驗矩陣第i行第j列的循環(huán)移位因子為si,j,maxlen，最長碼對應的擴展單位陣的大小為zmax×zmax，當前需要構(gòu)造的碼字第i行第j列的循環(huán)移位因子為si,j，對應的擴展單位陣的大小為z×z，則si,j和si,j,maxlen滿足如下關(guān)系式[4]

(8)

在找出最長碼的循環(huán)移位因子的基礎(chǔ)上，可以對任意擴展因子z對應的碼長按照式(8)確定相應的循環(huán)移位因子，從而使設計出的基礎(chǔ)校驗矩陣適應可變碼長。

3 性能仿真

設可變碼長QC-LDPC碼需要支持的最大碼長為3 200，碼率為1/2。綜合考慮復雜度和糾錯性能，基礎(chǔ)校驗矩陣的尺寸定為16×32。首先基于上述算法設計出碼長為3 200的LDPC碼基礎(chǔ)校驗矩陣，在此基礎(chǔ)上對循環(huán)移位因子進行修改，得到碼長小于3 200且變化步徑長度為32的所有LDPC碼的基礎(chǔ)校驗矩陣。信道選取加性白噪聲高斯信道，采用BPSK調(diào)制方式，譯碼使用歸一化最小和算法，分別對384,1 024,2 048,3 200等幾個典型碼長的糾錯性能進行了仿真。每個碼長仿真100 000次，然后統(tǒng)計誤比特率。仿真結(jié)果如圖1 所示， 五角星標記的曲線對應于 384 碼長的誤碼性能， 圓圈標記的曲線對應于1 024碼長的誤碼性能，正方形標記的曲線對應于2 048碼長的誤碼性能，星號標記的曲線對應于3 200碼長的誤碼性能。仿真結(jié)果表明，BER為10-5時，碼長384的LDPC碼編碼增益為6.4 dB，1 024對應的編碼增益為7.2 dB，2 048對應的編碼增益為7.7 dB，3 200碼長的編碼增益為7.9 dB。碼長越長，編碼增益越大。IEEE 802.16e標準也支持可變碼長的LDPC碼，1/2碼率的碼長變化范圍為576至2 304，圖2給出了本文構(gòu)造的LDPC與802.16e給出的LDPC的性能對比。選取2種典型碼長，576和2 016，譯碼仍選用歸一化最小和算法，仿真100 000次，統(tǒng)計誤碼率，仿真結(jié)果如圖2所示。圖中五角星標記的曲線對應于GAU算法576碼長的誤碼性能，圓圈標記的曲線對應于IEEE 802.16e標準中576碼長的誤碼性能，正方形標記的曲線對應于GAU算法2 016碼長的誤碼性能，星號標記的曲線對應于802.16e標準中2 016碼長的誤碼性能?？梢钥闯?，GAU算法構(gòu)造的LDPC碼與802.16e標準中的LDPC碼在576碼長時誤碼性能相當，碼長為2 016時，GAU算法性能略優(yōu)，且仿真中GAU算法構(gòu)造的校驗矩陣比802.16e適應更大范圍的碼長變化。綜合來看，GAU算法構(gòu)造的碼字性能更優(yōu)。

圖1 幾種典型碼長的LDPC碼誤碼性能 圖2 GAU算法和802.16e構(gòu)造的LDPC碼誤碼性能比較Fig.1 BER of LDPC codes for several typical code lengths Fig.2 BER comparison between GAU and 802.16e

4 結(jié)束語

隨著通信技術(shù)與應用的發(fā)展，越來越多的通信系統(tǒng)需要支持可變長度的數(shù)據(jù)傳輸。前向糾錯編碼是提高數(shù)據(jù)傳輸可靠性的一項有效措施，而LDPC碼是近幾年被深入研究和廣泛應用的一類前向糾錯編碼。本文對可變碼長LDPC碼的構(gòu)造算法進行了研究，綜合考慮度分布、最小環(huán)長、環(huán)近似外信息度和最小環(huán)數(shù)目等因素，提出了可變碼長LDPC碼的統(tǒng)一構(gòu)造方法——GAU算法。仿真結(jié)果表明，GAU算法構(gòu)造的LDPC支持較大范圍的碼長變化，且短碼和中長碼都有很好的糾錯性能。GAU算法對不同碼長的LDPC碼采用同一架構(gòu)進行設計，有利于編譯碼器使用同一實現(xiàn)框架，能有效降低實現(xiàn)復雜度。研究成果具有重要的理論意義和實用價值。

[1] Gallager R G. Low-density parity-check codes[D]. Cambridge, MA: MIT Press, 1963.

[2] GPS Joint Program Office. Navstar global positioning system interface specification: Draft IS-GPS-800[R]. [S．l．]：Global Positioning System Directorate, 2006:26-27.

[3] Marc P, Fossorier C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Transactions on Information Theory, 2004,50(8):1788-1793.

[4] LAN/MAN Standards Committee of the IEEE Computer Society and the IEEE Microwave Theory and Techniques Society. IEEE standard 802.16e 2005 amendment 2 and corrigendum 1 to IEEE standard 802.16 2004[R]. [S．l．]： IEEE， 2005:626-630.

[5] Seho M, Kyeongcheol Y, Jaeyoel K. Quasi-cyclic LDPC codes for fast encoding[J]. IEEE Transactions on Information Theory, 2005,51(8):2894-2901.

[6] Orlitsky A, Viswanathan K, Zhang J. Stopping set distribution of LDPC code ensembles[J]. IEEE Transactions on Information Theory, 2005,51(3):929-953.

[7] Wei X, AKansu A N. Density evolution for low-density parity-check codes under Max-Log-MAP decoding[J]. IEE Electron Letters, 2001,37:1225-1226.

[8] Chen Jinghu, Marc P, Fossorier C. Density evolution for two improved BP-based decoding algorithms of LDPC codes[J]. IEEE Communications Letters, 2002,6(5):208-210.

[9] Hu X Y, Eleftheriou E, Arnold D M. Progressive edge-growth tanner graphs[C]∥Proceedings of IEEE GLOBECOM 2001. San Antonio: IEEE, 2001:995-1001.

[10]Xiao H, Amir H B. Improved progressive-edge-growth (PEG) construction of irregular LDPC codes[J]. IEEE Communications Letters, 2004,8(12):715-717.

[11]傅婷婷，吳湛擊,王文博.基于PEG算法的準循環(huán)LDPC碼的編碼構(gòu)造方法[J]. 數(shù)據(jù)采集與處理，2009,24(Z1)：182-186.

Fu Tingting, Wu Zhanji, Wang Wenbo. Construction algorithm of QC-LDPC codes based on PEG algorithm[J]. Journals of Data Acquisition and Processing, 2009,24(Z1):182-186.

[12]Mehdi K, Amir H B. Counting short cycles of quasi cyclic protograph LDPC codes[J]. IEEE Communication letters, 2012,16(3):400-403.

[13]Tao T, Christopher R J, Villasenor J D, et al. Selective avoidance of cycles in irregular LDPC code construction[J]. IEEE Transactions on Communications, 2004,52(8):1242-1247.

GAU Algorithm for Construction of Variably Long LDPC Codes

Zhu Hongpeng, Cheng Lei, Zhang Jian

(College of Communication Engineering，PLA University of Science and Technology, Nanjing， 210007, China)

A girth-ACE union (GAU) construction algorithm is proposed for variably long LDPC codes considering the degree distribution, girth and approximate cycle extrinsic (ACE) message degree in a unified architecture. Therefore the short cycle number is reduced and the extrinsic message degree is increased. Large range of variable code length is accommodated through parity check matrix constructed by GAU algorithm. For short length codes, the performance of GAU algorithm is similar with that of LDPC codes in IEEE 802.16e. For middle length and long codes, GAU algorithm performs a little better. Variably long LDPC codes are designed using a common parity check matrix. The design of encoder and decoder with the same architecture for variable lengths is facilitated, which reduce the realizing complexity of encoder and decoder. Results show that the algorithm is useful in designing LDPC codes, which support variably long data communication, and the research is meaningful both in theory and practice.

low density parity check (LDPC); girth; approximate cycle extrinsic (ACE)

國家自然科學基金(61032004，91338201)資助項目。

2014-01-10；

2014-05-30

TN911.22

A

朱宏鵬(1982-),男,博士，講師，研究方向：衛(wèi)星通信，信道編碼，E-mail:hongpengzhu@126.com。

程磊(1990-)，男，碩士研究生，研究方向：衛(wèi)星通信。

張劍(1979-)，男，博士，講師，研究方向：衛(wèi)星通信。