一種低錯誤平層LDPC碼構(gòu)造方法

袁建國，汪 哲，高文春，吳英冬，郭 喬，胡瀟月

(重慶郵電大學(xué) 光通信與網(wǎng)絡(luò)重點實驗室，重慶 400065)

一種低錯誤平層LDPC碼構(gòu)造方法

袁建國，汪 哲，高文春，吳英冬，郭 喬，胡瀟月

(重慶郵電大學(xué) 光通信與網(wǎng)絡(luò)重點實驗室，重慶 400065)

針對低密度奇偶校驗 (low-density parity-check, LDPC)碼在高信噪比區(qū)域可能存在錯誤平層的缺點，提出一種具有低錯誤平層LDPC碼的新穎構(gòu)造方法。在該方法中，基本矩陣由漸進(jìn)邊增長(progressive edge growth, PEG)算法搜索構(gòu)造，通過在基本矩陣相應(yīng)的Tanner圖中增加校驗節(jié)點，并將其與擁有最小額外信息度(extrinsic message degree, EMD) 短環(huán)的變量節(jié)點相連來增大短環(huán)的連通性。另外，提出了一種基于伽羅華域的循環(huán)移位系數(shù)矩陣設(shè)計方案，無需計算機搜索即可完全避免4環(huán)的出現(xiàn)，降低算法復(fù)雜度。為了對該方法的可行性進(jìn)行驗證，分別對變量節(jié)點的度分布是規(guī)則和非規(guī)則的基本矩陣進(jìn)行改進(jìn)，在高斯白噪聲(additive white gaussian noise, AWGN)信道下，采用置信傳播(belief propagation, BP)迭代譯碼算法對改進(jìn)后的碼型進(jìn)行仿真分析，仿真結(jié)果表明，利用該法所構(gòu)造的碼型可有效改善在高信噪比區(qū)域的錯誤平層。

漸進(jìn)邊增長(PEG)算法；額外信息度(EMD)；低密度奇偶校驗(LDPC)碼；錯誤平層

0 引 言

低密度奇偶校驗碼(low density parity check，LDPC)在數(shù)字存儲系統(tǒng)和無線通信系統(tǒng)等領(lǐng)域有著廣泛的應(yīng)用前景，因其具有靈活的構(gòu)造方法、逼近Shannon極限的優(yōu)秀性能而成為信道編碼領(lǐng)域研究的熱點[1-3]。絕大多數(shù)中等碼長的LDPC碼都存在錯誤平層問題，即到了一定的高信噪比區(qū)域，誤碼率性能曲線突然變得平坦起來[2-3]。近年來，很多改善錯誤平層的方法被提出，其中包括對已有校驗矩陣進(jìn)行環(huán)提升、消除陷阱集/停止集，或用額外信息度(extrinsic message degree，EMD)/近似外信息度(approximate cycle EMD，ACE)為度量直接構(gòu)造校驗矩陣[4-5]。

針對LDPC碼的錯誤平層問題，并考慮到參數(shù)的靈活設(shè)置和硬件的易實現(xiàn)性，將隨機構(gòu)造法與結(jié)構(gòu)化構(gòu)造法相結(jié)合，提出一種具有低錯誤平層的準(zhǔn)循環(huán)LDPC碼構(gòu)造方法。首先，利用漸進(jìn)邊增長(progressive edge growth，PEG)算法構(gòu)造基本矩陣，并對基本矩陣中短環(huán)的連通性進(jìn)行改進(jìn)。然后，基于伽羅華域設(shè)計循環(huán)移位系數(shù)，用此移位系數(shù)矩陣對改進(jìn)后的基本矩陣進(jìn)行循環(huán)擴展，最終得到校驗矩陣H。仿真結(jié)果表明，本文所構(gòu)造的LDPC碼型可有效降低錯誤平層。

1 經(jīng)典PEG算法

PEG算法是一種經(jīng)典隨機構(gòu)造法[5]。其構(gòu)造的核心思想是在滿足度分布的條件下，利用貪心算法不斷添加校驗節(jié)點與變量節(jié)點之間的邊。在構(gòu)造校驗矩陣的過程中，采用密度進(jìn)化算法，選取合適的度分布，可生成任意碼長和碼率的LDPC碼，其節(jié)點的度分布如(1)式所示。

(1)

(1)式中：dv表示與變量節(jié)點相連的最大邊數(shù)；dc表示與校驗節(jié)點相連的最大邊數(shù)。雖然PEG算法在添加新邊時能夠保證最大圍長，但是其不能從全局的角度對Tanner圖中的環(huán)結(jié)構(gòu)進(jìn)行優(yōu)化，所以會導(dǎo)致環(huán)結(jié)構(gòu)比較復(fù)雜，特別是在長碼長時，環(huán)存在嚴(yán)重的交織問題，有大量公共節(jié)點，在一定程度上會降低迭代譯碼性能。

2 一種低錯誤平層LDPC碼的新穎構(gòu)造方法

2.1 對基本矩陣短環(huán)EMD值的提升

在迭代譯碼算法中，信息傳遞的路徑就是環(huán)，單純地追求消環(huán)并不能有效改進(jìn)LDPC碼的性能，并不是環(huán)長越小對譯碼性能的影響就越大，反而環(huán)長較大但與剩余圖連通性很差的環(huán)對譯碼性能的影響要遠(yuǎn)大于環(huán)長較小但與剩余圖連通性較好的環(huán)。因此，剩余Tanner圖中校驗節(jié)點的連通性是影響譯碼性能的重要因素[6]。TIAN Tao在文獻(xiàn)[7]中也指出并不是Tanner圖中所有環(huán)都會對迭代譯碼收斂有影響，其主要取決于環(huán)的連通性。對于環(huán)的連通性可用EMD度量，有如下定理。

定理1 若一個校驗節(jié)點僅與某變量節(jié)點集合連接一次，則這個校驗節(jié)點稱為該變量節(jié)點集合的外節(jié)點。變量節(jié)點集合的外節(jié)點個數(shù)稱為該變量節(jié)點集合的EMD值[8]。

在分析短環(huán)的EMD時，可以把與構(gòu)成短環(huán)的變量節(jié)點集合相連的校驗節(jié)點分為3個部分：①構(gòu)成短環(huán)校驗節(jié)點；②與變量節(jié)點集合相連一次的校驗節(jié)點；③剩余與變量節(jié)點集合相連的校驗節(jié)點。其中與變量節(jié)點集合相連一次的校驗節(jié)點的個數(shù)即為短環(huán)的EMD值。

另外，增大環(huán)的外部信息節(jié)點，可以有效減少小陷阱集/停止集，從而改善在高信噪比區(qū)域譯碼所出現(xiàn)的錯誤平層。針對PEG算法所構(gòu)造的基本矩陣，為了提升其短環(huán)的EMD值，增大環(huán)的連通性，本文提出了如下算法。

初始化：根據(jù)對碼長、碼率的要求，設(shè)定基本矩陣的大小為(m,n)，新增一個校驗節(jié)點c1。

步驟1 對基本矩陣進(jìn)行全局搜索，找出其中所有的短環(huán)并計算出EMD值，每搜索到一個短環(huán)，將該短環(huán)的所有變量節(jié)點及其EMD值記錄到列表φ中。

步驟2 找出φ中擁有最小EMD值的所有行，記錄為φ，并找出φ中出現(xiàn)次數(shù)最多的變量節(jié)點νi。

步驟3 將變量節(jié)點νi與新增的校驗節(jié)點c1相連，并進(jìn)行判斷，如果構(gòu)成4環(huán)，則選擇φ中的次優(yōu)變量節(jié)點。

步驟4 置空φ和φ，重復(fù)步驟1-步驟3，終止條件即新增校驗節(jié)點與變量節(jié)點相連的邊數(shù)接近校驗節(jié)點的平均度分布，或者沒有滿足條件的變量節(jié)點。

對改進(jìn)后的基本矩陣進(jìn)行搜索分析，雖然圍長大于4的短環(huán)數(shù)量有少量的增加，但與新增校驗節(jié)點相連的變量節(jié)點所構(gòu)成短環(huán)的EMD值有顯著的提升，且其包括新增的短環(huán)。因此，基本矩陣中短環(huán)的連通性得到了顯著的改善。在算法復(fù)雜度上，計算環(huán)EMD值比計算環(huán)的ACE要復(fù)雜，但循環(huán)擴展的基本矩陣選取的都為短碼長，因此不會存在過高復(fù)雜度。

2.2 循環(huán)移位系數(shù)和校驗矩陣的設(shè)計

在構(gòu)造準(zhǔn)循環(huán)LDPC碼時，基本矩陣決定了整體的度分布，但索引矩陣P的合理設(shè)計也是構(gòu)造校驗矩陣的關(guān)鍵，索引矩陣的設(shè)計直接影響校驗矩陣的環(huán)長以及稀疏性。下面給出了一種基于伽羅華域的循環(huán)移位系數(shù)矩陣構(gòu)造方法。

GF(q)即二元伽羅華域，其中令q=2p，p為正整數(shù)，α為伽羅華域GF(q)的本原元[9]，對于αi∈GF(q)，0≤i≤q-2，GF(q)的乘群可由集合{α0,α1,…,αq-2}構(gòu)成?；谫ち_華乘群的循環(huán)移位系數(shù)矩陣P的構(gòu)造如下。

1)在P的構(gòu)造中，其列單元可用乘群{(α0)-1,(α1)-1,…,(αi)-1}表示，其行單元可用乘群{α0,α1,…,αj}表示，其中0≤i,j

2)將上述行與列在二元伽羅華域中對應(yīng)相乘，得到移位系數(shù)矩陣P中的每個元素為wi,j=(αi)-1αj。

3)并對P中的每個元素wi,j都對應(yīng)減去α0，得到移位系數(shù)矩陣中的每個元素為wi,j=(αi)-1αj-1。

P矩陣可以保證每行(列)中的所有元素均是GF(q)中的不同元素，且不同的2行(列)的每個對應(yīng)位置元素均不同。

根據(jù)要求從移位系數(shù)矩陣P中取出大小為m×n的索引矩陣，對于矩陣P中包含的-Inf元素用1替換，包含的0元素用q替換。用基本矩陣與索引矩陣相與后得到循環(huán)移位矩陣為

(2)

將循環(huán)移位矩陣中的0元素，擴展成q-1階零矩陣，將非零元素擴展成q-1階單位矩陣，并按其對應(yīng)的移位系數(shù)進(jìn)行循環(huán)移位，最終得到((m×(q-1)),(n×(q-1)))維校驗矩陣H。

3 性能仿真分析

初始構(gòu)造的原始基本矩陣(m,n)和待改進(jìn)基本矩陣(m,n-1)的變量節(jié)點的度分布規(guī)則，令dv=3，m=24,n=48，q=24和q=26，利用移位系數(shù)矩陣對基本矩陣進(jìn)行循環(huán)擴展，得到2個碼率為0.5的準(zhǔn)循環(huán)LDPC(QC-LDPC)碼，即QC-LDPC(720,360)碼和QC-LDPC(3 024,1 512)碼。在高斯白噪聲(additive white gaussian noise, AWGN)信道下，經(jīng)過二進(jìn)制相移鍵控 (binary phase shift keying，BPSK)調(diào)制，采用置信傳播譯碼算法進(jìn)行30次迭代[10]，得到其仿真性能曲線如圖1所示。

圖1 QC-LDPC(720,360)碼與QC-LDPC(3 024,1 512)碼改進(jìn)前后的誤碼性能比較Fig.1 Comparison of the error-correction performance for QC-LDPC(720,360) and QC-LDPC(3 024,1 512) before and after improved

將圖1中的仿真性能曲線進(jìn)行對比分析可知，對基本矩陣改進(jìn)前后所構(gòu)造的QC-LDPC(720,360)碼在信噪比為3.2 dB時，其糾錯性能有接近一個數(shù)量級的提升。由于碼長越長其糾錯性能越好，改進(jìn)后的QC-LDPC(3 024,1 512)碼在信噪比為2.2 dB時，其糾錯性能提升超過一個數(shù)量級。因此，可以驗證本文所提出的方法能夠有效改善LDPC碼在高信噪比區(qū)域所出現(xiàn)的錯誤平層現(xiàn)象。

為進(jìn)一步對上述提出的方法進(jìn)行論證，本文對非規(guī)則的基本矩陣進(jìn)行改進(jìn)，設(shè)定其度分布λ(x)=0.383 54x+0.042 37x2+0.574 09x3，大小為m=31,n=64，q=25，利用本文提出的算法對基本矩陣進(jìn)行改進(jìn)，選取16×16的移位矩陣進(jìn)行循環(huán)置換后得到EMD QC-LDPC(1 024,512)碼型，在與文獻(xiàn)[11]相同的仿真環(huán)境下，得到其糾錯性能曲線如圖2所示。

在碼長相近和碼率相同的情況下，對圖2中的仿真性能曲線進(jìn)行對比，會發(fā)現(xiàn)在信噪比為3 dB時，文獻(xiàn)[11]構(gòu)造的QC-LDPC(1 008,504)碼的誤碼率為8.84×10-7，而本文構(gòu)造的EMD QC-LDPC(1 024,512)碼的誤碼率為2.03×10-7。因此，利用本文方法所構(gòu)造的碼型能夠有效降低其錯誤平層。

4 結(jié) 論

本文針對LDPC碼在高信噪比區(qū)域所存在錯誤平層的缺陷，提出了一種增大校驗矩陣中短環(huán)EMD值的算法，通過提升短環(huán)的連通性來改善其糾錯性能。另外，還設(shè)計出一種基于伽羅華域的循環(huán)移位系數(shù)的選擇方案，無需計算機搜索即可有效避免4環(huán)的出現(xiàn)，降低其算法復(fù)雜度。仿真結(jié)果表明，利用本文提出的構(gòu)造方法所構(gòu)造的LDPC碼型，可有效降低其在高信噪比區(qū)域的錯誤平層。

圖2 EMD QC-LDPC(1 024,512)碼與QC-LDPC(1 008,504)碼的糾錯性能對比圖Fig.2 Comparison of the error-correction performance for EMD QC-LDPC(1 024,512) and QC-LDPC(1 008,504)

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

[2] LI Juan, LIU Keke, LIN Shu, et al. Algebraic Quasi-Cyclic LDPC Codes: Construction, Low Error-Floor, Large Girth and a Reduced-Complexity Decoding Scheme[J]. IEEE Transactions on Communications, 2014, 62(8): 2626-2637.

[3] 袁建國,周光香.光通信中基于有限域的一種QC-LDPC碼構(gòu)造方法分析[J].半導(dǎo)體光電，2015,36(4):615-617. YUAN Jianguo, ZHOU Guangxiang. Analysis on a Construction Method of QC-LDPC Codes Based on the Finite Field for Optical Communications[J]. Semiconductor Optoelectronics, 2015, 36(4):615-617,656.

[4] KHAZRAIE S, ASVADI R, BANIHASHEMI A. A PEG construction of finite-length LDPC codes with low error floor[J]. IEEE Communications Letters, 2012, 16(8): 1288-1291.

[5] HU Xiaoyun, ELEFTHERIUS E, ARNOLD D M. Regular and irregular progressive edge-growth tanner graphs[J]. IEEE Transactions on Information Theory, 2005, 51(1): 386-398.

[6] HAN Guojun, GUAN Yongliang, KONG Lingjun. Construction of Irregular QC-LDPC Codes via Masking with ACE Optimization[J]. IEEE Communications Letters, 2014, 18(2): 348-351.

[7] TIAN Tao, JONES C R, VILLASENOR J D, et al. Selective avoidance of cycles in irregular LDPC code construction[J]. IEEE Transactions on Communications, 2004, 52(8): 1242-1247.

[8] VUKOBRATOVIC D, SENK V. Transactions papers evaluation and design of irregular LDPC codes using ACE spectrum[J]. IEEE Transactions on Communications, 2009, 57(8): 2272-2279.

[9] YUAN Jianguo, XU Liang, TONG Qingzhen. A Novel QC-LDPC Code Based on the Finite Field Multiplicative Group for Optical Communications[J]. Optoelectronics Letters, 2013, 9(5): 378-380.

[10] MENG Jin, YANG Enhui. Interactive Encoding and Decoding Based on Binary LDPC Codes With Syndrome Accumulation[J]. IEEE Transactions on Information Theory, 2013, 59(5): 3068-3103.

[11] 張軼,達(dá)新宇,蘇一棟.利用等差數(shù)列構(gòu)造大圍長準(zhǔn)循環(huán)低密度奇偶校驗碼[J].電子與信息學(xué)報, 2015, 37(2): 394-398. ZHANG Yi, DA Xinyu, SU Yidong. Construction of Quasi-cyclic Low-density Parity-check Codes with a Large Girth Based on Arithmetic Progression[J].Journal of Electronics & Information Technology,2015,37(2):394-398.

(編輯：田海江)

A construction method of LDPC codes with the low error floor

YUAN Jianguo, WANG Zhe, GAO Wenchun, WU Yingdong, GUO Qiao, HU Xiaoyue

(Key Laboratory of Optical Communication and Networks, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R.China)

Considering that low density parity check (LDPC) codes may exist the fault of the error floor in the high signal noise ratio (SNR) region, a construction method of LDPC codes with the low error floor was proposed. In the proposed method, a basic matrix is constructed and searched by the progressive edge growth (PEG) algorithm, and the connectivity of the short cycle can be effectively increased by way of adding the new check nodes of the corresponding Tanner diagram in the basic matrix and connecting them with the variable nodes of the short cycle which has the minimum extrinsic message degree (EMD) value. In addition, a novel cyclic shift coefficient matrix scheme based on the Galois field method was presented, which can avoid the phenomenon of the girth-4 without the computer search, thus the algorithm complexity is reduced. In order to verify the feasibility of this construction method, the basic matrixes with the regular and irregular degree distributions of the variable nodes are improved respectively. The improved codes are simulated and analyzed under the addictive white gaussian noise(AWGN) channel and the belief propagation(BP) decoding algorithm. The simulation result shows that the LDPC codes constructed by the proposed method can effectively reduce the error floor in the high signal noise ratio region.

progressive edge growth(PEG) algorithm; extrinsic message degree(EMD); low-density parity-check(LDPC) codes; error floor

10.3979/j.issn.1673-825X.2017.01.003

2015-11-10

2016-12-20 通訊作者：袁建國 yyyyjg@126.com

國家自然科學(xué)基金項目(61472464)；重慶市基礎(chǔ)與前沿研究計劃項目(cstc2015jcyjA0554)；2016年重慶郵電大學(xué)大學(xué)生科研訓(xùn)練計劃項目(A2016-61)

Foundation Items：The National Natural Science Foundation of China (61472464); The Natural Science Foundation of Chongqing Science and Technology Commission (cstc2015jcyjA0554); The Undergraduate Science Research Training Project for Chongqing University of Posts and Telecommunications (A2016-61)

TN911.22

A

1673-825X(2017)01-0015-04

袁建國(1968-)，男，重慶人，教授，博士，碩士生導(dǎo)師，主要研究方向為通信技術(shù)與信道編碼技術(shù)。E-mail: yyyyjg@126.com。

汪 哲(1992-)，女，重慶人，碩士研究生，主要研究方向為通信系統(tǒng)中FEC編譯碼技術(shù)。 E-mail: 578091834@qq.com。

高文春(1989-)，男，內(nèi)蒙古赤峰人，碩士研究生，研究方向為通信技術(shù)與信道編碼技術(shù)。E-mail: gaowencun@ict.ac.cn。