高性能時(shí)不變LDPC卷積碼構(gòu)造算法研究

穆麗偉 劉星成 張 涵

?

高性能時(shí)不變LDPC卷積碼構(gòu)造算法研究

穆麗偉*①②劉星成③張 涵①②

①(華南師范大學(xué)物理與電信工程學(xué)院 廣州 510006)②(華南師范大學(xué)廣東省量子調(diào)控工程與材料重點(diǎn)實(shí)驗(yàn)室 廣州 510006)③(中山大學(xué)電子與通信工程系 廣州 510006)

該文基于由QC-LDPC碼獲得時(shí)不變LDPC卷積碼的環(huán)同構(gòu)方法，設(shè)計(jì)了用有限域上元素直接獲得時(shí)不變LDPC卷積碼多項(xiàng)式矩陣的新算法。以MDS卷積碼為例，給出了一個(gè)具體的構(gòu)造過程。所提構(gòu)造算法可確保所獲得的時(shí)不變LDPC卷積碼具有快速編碼特性、最大可達(dá)編碼記憶以及設(shè)計(jì)碼率。基于滑動(dòng)窗口的BP譯碼算法在AWGN信道上的仿真結(jié)果表明，該碼具有較低的誤碼平臺(tái)和較好的糾錯(cuò)性能。

LDPC卷積碼；有限域；快速編碼；時(shí)不變；最大編碼記憶

1 引言

眾所周知，卷積碼主要用于實(shí)時(shí)通信系統(tǒng)，然而，由于Viterbi譯碼算法的高復(fù)雜性，一般情況下僅使用具有較小約束長(zhǎng)度的卷積碼。近年來，LDPC卷積碼[1,2]引起了研究人員的關(guān)注。與LDPC分組碼一樣，LDPC卷積碼也由稀疏奇偶校驗(yàn)矩陣定義；但與LDPC分組碼不同的是，它們可對(duì)輸入碼流進(jìn)行連續(xù)編譯碼。在發(fā)送端，可用基于移位寄存器的編碼器對(duì)輸入信息流進(jìn)行連續(xù)編碼；在接收端，可用基于置信傳播(Belief Propagation, BP)譯碼算法的滑動(dòng)窗口譯碼器對(duì)從信道接收的碼流進(jìn)行連續(xù)譯碼[3]。而且，與LDPC分組碼相比，它們還具有更好的譯碼性能[1]。LDPC卷積碼，因具有比LDPC分組碼更好的譯碼性能[1]，比Viterbi更簡(jiǎn)單的BP譯碼算法，以及能對(duì)輸入碼流進(jìn)行連續(xù)編譯碼的特性，而有更好的應(yīng)用價(jià)值，比如，適用于Ethernet。除此之外，印度空間研究組織(Indian Space Research Organization, ISRO)已經(jīng)開發(fā)出了用于全球?qū)Ш叫l(wèi)星系統(tǒng)(Global Navigation Satellite System, GNSS) 的LDPC 卷積碼的MATLAB 和C++模塊。美國、俄羅斯、歐盟、中國、日本、印度、尼日利亞及許多其他國家正在頻帶1559~1610 MHz(L1頻帶)、1215~1300 MHz(L2頻帶)以及1164~1215 MHz(L5頻帶)上計(jì)劃/開發(fā)GNSS。每個(gè)系統(tǒng)的信息和數(shù)據(jù)結(jié)構(gòu)都各不相同，數(shù)據(jù)率變化范圍為25 bit/s到500 bit/s。碼率=1/2，信息長(zhǎng)度=7 的卷積碼已被推薦用于不同信息的前向糾錯(cuò)技術(shù)(Forward Error Correction, FEC)中。利用該編碼方案的FEC 技術(shù)可用于深空通信、光纖通信以及計(jì)算機(jī)間的通信等。

LDPC卷積碼主要有兩種結(jié)構(gòu)：具有隨機(jī)結(jié)構(gòu)的碼[4]和具有固定結(jié)構(gòu)的碼。后者又稱為時(shí)不變LDPC卷積碼，因具有規(guī)則結(jié)構(gòu)并能減少系統(tǒng)實(shí)現(xiàn)復(fù)雜度而受到學(xué)者的廣泛關(guān)注，其奇偶校驗(yàn)矩陣可由單項(xiàng)式或多項(xiàng)式構(gòu)成。文獻(xiàn)[5]介紹了一種獲得時(shí)不變LDPC卷積碼奇偶校驗(yàn)矩陣的方法。然而，根據(jù)文獻(xiàn)[5]的分析，由單項(xiàng)式構(gòu)成的具有更好的環(huán)特性，這種結(jié)構(gòu)可由準(zhǔn)循環(huán)LDPC(Quasi-Cyclic LDPC, QC-LDPC)分組碼或隨機(jī)搜索算法[11,12]獲得，顯然，由QC-LDPC分組碼獲得的構(gòu)造算法更簡(jiǎn)單。

本文根據(jù)由QC-LDPC分組碼獲得LDPC卷積碼的方法，提出用有限域元素直接獲得LDPC卷積碼的由單項(xiàng)式組成的奇偶校驗(yàn)矩陣的算法，并舉例給出了一種用截短的最大距離可分(Maximum- Distance Separable, MDS)卷積碼獲得的具體構(gòu)造。到目前為止，幾乎所有時(shí)不變LDPC卷積碼的構(gòu)造算法主要考慮其譯碼性能上的優(yōu)異性，而忽視了其實(shí)現(xiàn)上的便利性，更沒有考慮LDPC卷積碼本身的一個(gè)特有優(yōu)勢(shì)：快速編碼特性。本文算法旨在獲得兼具快速編碼特性與優(yōu)異譯碼性能的時(shí)不變LDPC卷積碼。該構(gòu)造算法還具有任意時(shí)刻上的最大可達(dá)編碼記憶以及結(jié)果碼率與設(shè)計(jì)碼率相等的特性。仿真結(jié)果表明，本文提出的時(shí)不變LDPC卷積碼在小的約束長(zhǎng)度下就具有很好的譯碼性能。

2 時(shí)不變LDPC卷積碼的奇偶校驗(yàn)矩陣

2.1具有快速編碼的LDPC卷積碼的二元矩陣

2.2具有快速編碼的時(shí)不變LDPC卷積碼的多項(xiàng)式矩陣

3 構(gòu)造前準(zhǔn)備：在有限域上構(gòu)造時(shí)不變LDPC卷積碼的多項(xiàng)式矩陣

本節(jié)回顧文獻(xiàn)[13]用QC-LDPC分組碼獲得時(shí)不變LDPC卷積碼的構(gòu)造過程，提出在有限域上直接獲得時(shí)不變LDPC卷積碼多項(xiàng)式矩陣的方法。

(4)

根據(jù)環(huán)同構(gòu)，由式(4)可獲得時(shí)不變LDPC卷積碼多項(xiàng)式矩陣：

4 構(gòu)造具有快速編碼的時(shí)不變LDPC卷積碼多項(xiàng)式矩陣

本節(jié)根據(jù)LDPC卷積碼的兩個(gè)獨(dú)有特性：(1)快速編碼特性，(2)譯碼性能與編碼記憶成正比的特性[1]；設(shè)計(jì)具有快速編碼特性及最大可達(dá)編碼記憶的LDPC卷積碼多項(xiàng)式矩陣模型，并以MDS卷積碼為例，給出獲得該矩陣模型的具體構(gòu)造方法。

4.1建立矩陣模型

根據(jù)二元矩陣與多項(xiàng)式矩陣之間的關(guān)系，由式(6)可知令矩陣()最后列對(duì)角線上元素為，可確?？焖倬幋a特性；令矩陣()前列對(duì)角線上元素為，可確保每個(gè)編碼時(shí)刻都有最大編碼記憶(具體取值見4.2節(jié))，此時(shí)，校驗(yàn)?zāi)Ｐ陀洃洠囗?xiàng)式矩陣()可表示為

該矩陣可確保時(shí)不變LDPC卷積碼具有快速編碼特性和每個(gè)編碼時(shí)刻上的最大可達(dá)編碼記憶。

4.2構(gòu)造算法

(5)所有碼字重量(碼字中非零碼元個(gè)數(shù))為。

該矩陣具有下列特性：

因?yàn)橛蒑DS碼生成的QC-LDPC分組碼具有更好的性能[15]，本節(jié)考慮用碼率為1/的截短MDS卷積碼[15]的部分碼字作為L(zhǎng)DPC卷積碼基矩陣的行元素，并給出一個(gè)具體的構(gòu)造例子。

其中，滿足約束條件：

5 數(shù)值結(jié)果

本節(jié)用4.3節(jié)的方法構(gòu)造生成LDPC卷積碼及其對(duì)應(yīng)的QC-LDPC分組碼并進(jìn)行性能仿真。用符號(hào)()表示碼率為的LDPC卷積碼，-校驗(yàn)?zāi)Ｐ陀洃洠?多項(xiàng)式矩陣行數(shù)，-多項(xiàng)式矩陣列數(shù)。用符號(hào)表示QC-LDPC分組碼，-變量節(jié)點(diǎn)數(shù)，-校驗(yàn)節(jié)點(diǎn)數(shù)。為了進(jìn)行性能比較，本文假設(shè)LDPC卷積碼和QC-LDPC分組碼的譯碼算法具有相同的處理器復(fù)雜度，即，分組碼的分組長(zhǎng)度和卷積碼的約束長(zhǎng)度相同：。仿真在AWGN信道下進(jìn)行，最大迭代次數(shù)為50，采用文獻(xiàn)[1]介紹的BP譯碼算法對(duì)LDPC卷積碼及其相應(yīng)的QC-LDPC分組碼進(jìn)行仿真。

圖1 有限域GF(24), GF(25), GF(26)和GF(27)上的LDPC卷積碼性能

圖2 QC-LDPC分組碼與LDPC卷積碼的BER性能

表1 碼率3/6LDPC卷積碼及其對(duì)應(yīng)的QC-LDPC碼環(huán)數(shù)

6 結(jié)束語

本文由QC-LDPC分組碼獲得LDPC卷積碼的方法提出了用有限域上的元素構(gòu)造時(shí)不變LDPC卷積碼的新方法，并確保所獲得的碼具有快速編碼特性、最大可達(dá)編碼記憶以及設(shè)計(jì)碼率。本文以碼率為的MDS卷積碼為例，給出了具體的構(gòu)造方法及其仿真結(jié)果。在AWGN信道下的仿真結(jié)果表明，與具有類似結(jié)構(gòu)的碼相比，該構(gòu)造方法所獲得的LDPC卷積碼在小的約束長(zhǎng)度下就具有較低的誤碼平臺(tái)和良好的譯碼性能。該碼可用移位寄存器實(shí)現(xiàn)的快速編碼算法以及可用滑動(dòng)窗口譯碼器實(shí)現(xiàn)的BP譯碼算法使其適合于硬件實(shí)現(xiàn)。

[1] FELTSTROM A and ZIGANGIROV K. Time-varying periodic convolutional codes with low-density parity-check matrix[J]., 1999, 45(6): 2181-2191.

[2] BOCHAROVA I, KUDRYASHOV B, and JOHANNESSON R. Searching for binary and nonbinary block and

convolutional LDPC codes[J]., 2016, 62(1): 163-183.

[3] ZHAO Yue and LAU F. Implementation of decoders for LDPC block codes and LDPC convolutional codes based on GPUs[J]., 2015, 25(3): 663-672.

[4] ZHOU Hua and GOERTZ N. Recoverability of variable nodes in periodically punctured LDPC convolutional code[J]., 2015, 19(4): 521-524.

[5] BALDI M, CANCELLIERI G, and CHIARALUCE F. Array convolutional low-density parity-check codes[J]., 2014, 18(2): 336-339.

[6] GIOULEKAS F, PETROU C, VGENIS A,. On the construction of LDPC convolutional code ensembles based on permuted circulant unit matrices[C]. IEEE International Conference on Electronics, Circuits and Systems, Marseille, 2014: 407-410.

[7] JUNHO C and SCHMALEN L. Construction of protographs for large-girth structured LDPC convolutional codes[C]. IEEE International Conference on Communications, London, 2015: 4412-4417.

[8] SRIDHARAN A and COSTELLO D. A new construction for low density parity check convolutional codes[C]. Proceedings of the IEEE Information Theory Workshop, Bangalore, India, 2002: 212.

[9] ZHOU Hua and GOERTZ N. Girth analysis of polynomial- based time-invariant LDPC convolutional codes[C]. International Conference on Systems, Signals and Image Processing, Vienna, 2012: 104-108.

[10] TANNER R, SRIDHARA D, SRIDHARAN A,. LDPC block and convolutional codes based on circulant matrices[J]., 2004, 50(12): 2966-2984.

[11] ESMAEILI M and GHOLAMI M. Geometrically-structured maximum-girth LDPC block and convolutional codes[J]., 2009, 27(6): 831-845.

[12] PUSANE A, SMARANDACHE R, VONTOBEL P,. Deriving good LDPC convolutional codes from LDPC block codes[J]., 16(6): 897-900.

[13] MU Liwei, LIU Xingcheng, and LIANG Chulong. Construction of binary LDPC convolutional codes based on finite fields[J]., 2012, 16(6): 897-900.

[14] CHEN Chao, BAI Baoming, and WANG Xingmei. Construction of quasi-cyclic LDPC codes based on a two-dimensional MDS code[J]., 2010, 14(5): 447-449.

[15] JUSTESEN J. An algebraic construction of rate 1/convolutional codes[J]., 1975, 21(5): 577-580.

New Ensemble of Time-invariant LDPC Convolutional Codes with High Performance

MU Liwei①②LIU Xingcheng③ZHANG Han①②

①(School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China)②(Guangdong Provincial Key Laboratory of Quantum Engineering and Quantum Materials, South China Normal University,Guangzhou 510006, China)③(Department of Electronic and Communications Engineering, Sun Yat-sen University, Guangzhou 510006, China)

In this paper, a new ensemble of the polynomial matrix of a time-invariant LDPC convolutional code is proposed. Based on the method of deriving time-invariant LDPC convolutional codes from QC (Quasi-Cyclic)- LDPC block codes, the elements over finite fields are used to generate directly the polynomial parity-check matrices of LDPC convolutional codes. A concrete example of using MDS (Maximum-Distance Separable) convolutional codes to derive the polynomial matrices is given. The proposed method ensures the fast encoding property, maximum encoding memory and designed rate. Simulation results show that the proposed LDPC convolutional codes exhibit low error floor and good decoding performance under BP (Belief Propagation) decoding algorithm over AWGN (Additive White Gaussian Noise) channel.

LDPC convolutional codes; Finite fields; Fast encoding; Time-invariant; Maximum encoding memory

TN911.22

A

1009-5896(2016)09-2274-06

10.11999/JEIT151376

2015-12-08；

2016-05-06；

2016-07-04

國家自然科學(xué)基金(61401164, 61572534, 60141176, 61002012, 61501126)，廣東省自然科學(xué)基金(2014A030310308, S2013010016297)，廣東省優(yōu)秀青年教師培養(yǎng)計(jì)劃(YQ2015046)

The National Natural Science Foundation of China(61401164, 61572534, 60141176, 61002012, 61501126), The Natural Science Foundation of Guangdong Province of China (2014A030310308, S2013010016297), The High Education Excellent Young Teacher Program of Guangdong Province (YQ2015046)

穆麗偉 liweimu@m.scnu.edu.cn

穆麗偉： 女，1980年生，博士，講師，研究方向?yàn)闊o線通信、信道編碼.

劉星成： 男，1968年生，教授，博士生導(dǎo)師，研究方向?yàn)闊o線通信、信道編碼.

張 涵： 男，1981年生，教授，碩士生導(dǎo)師，研究方向?yàn)樾盘?hào)處理、無線通信.