面向衛(wèi)星導(dǎo)航系統(tǒng)的多進制LDPC碼的構(gòu)造

陳為剛 曹 艷 夏曉曉 楊晉生

面向衛(wèi)星導(dǎo)航系統(tǒng)的多進制LDPC碼的構(gòu)造

陳為剛 曹 艷 夏曉曉 楊晉生

(天津大學(xué)電子信息工程學(xué)院 天津 300072)

面向衛(wèi)星導(dǎo)航系統(tǒng)應(yīng)用，設(shè)計一種性能優(yōu)越且編碼復(fù)雜度低的多進制低密度奇偶校驗(LDPC)碼。結(jié)合漸進邊增長(PEG)算法與準(zhǔn)循環(huán)擴展的半隨機構(gòu)造法，并優(yōu)化非零元素的選擇，構(gòu)造與新一代衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口標(biāo)準(zhǔn)中參數(shù)一致的多進制LDPC碼。進一步，通過將校驗矩陣轉(zhuǎn)換為重復(fù)累加碼(RA)碼的校驗矩陣結(jié)構(gòu)，實現(xiàn)低復(fù)雜度編碼。仿真結(jié)果表明，與衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口標(biāo)準(zhǔn)中碼長碼率相同的二進制LDPC碼相比，多進制LDPC碼有明顯的編碼增益，且其編碼復(fù)雜度較低。

衛(wèi)星導(dǎo)航系統(tǒng) 多進制低密度奇偶校驗碼 半隨機構(gòu)造法

0 引 言

衛(wèi)星導(dǎo)航系統(tǒng)具有全球性、實時性、全天候和高精度的特點，可提供導(dǎo)航、定位與授時服務(wù)，在國家安全與人們?nèi)粘Ｉ钪邪l(fā)揮著越來越重要的作用。早期的GPS L1 C/A采用漢明碼作為信道編碼方案，但僅可以檢錯并不能糾錯。隨著前向糾錯技術(shù)的發(fā)展，大多數(shù)的現(xiàn)代導(dǎo)航系統(tǒng)采用卷積碼作為信道編碼，與漢明碼相比，卷積碼獲得了大約5 dB的性能增益。2013年，新一代衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口規(guī)范中采用了低密度奇偶校驗(LDPC)碼作為信道編碼[1]。LDPC碼可獲得逼近香農(nóng)極限的性能，并且復(fù)雜度適中。因此，LDPC碼將有望取代卷積碼而成為未來導(dǎo)航系統(tǒng)中的信道編碼方案。

LDPC碼校驗矩陣的構(gòu)造直接影響LDPC碼的實現(xiàn)復(fù)雜度和糾錯性能。LDPC碼校驗矩陣的構(gòu)造方法主要分為：隨機構(gòu)造方法、結(jié)構(gòu)化構(gòu)造方法以及半隨機構(gòu)造方法等。隨機構(gòu)造的LDPC碼的優(yōu)點是碼長和碼率設(shè)計靈活，可很好地匹配由密度演化等方法得到的最優(yōu)度分布，但其編碼復(fù)雜度往往較高，不利于硬件實現(xiàn)。而結(jié)構(gòu)化的校驗矩陣可有效降低編碼復(fù)雜度，但這種構(gòu)造方法一般難于根據(jù)優(yōu)化的度分布設(shè)計非規(guī)則碼，譯碼門限性能較差。半隨機構(gòu)造方法結(jié)合了隨機構(gòu)造和結(jié)構(gòu)化構(gòu)造的優(yōu)點，是比較實用的LDPC碼構(gòu)造方法，比較常見的半隨機構(gòu)造方法有重復(fù)累加(RA)碼的構(gòu)造方法[2]，準(zhǔn)循環(huán)構(gòu)造方法[3]等。這些方法，一方面可較好地適合由密度演化等方法得到的度分布，另一方面也具有比較好的結(jié)構(gòu)，編譯碼復(fù)雜度低。因此這類LDPC碼已被多種標(biāo)準(zhǔn)采用，例如歐洲第二代衛(wèi)星數(shù)字廣播、無線城域網(wǎng)等。

與二進制LDPC碼相比，中短碼長的多進制LDPC碼[4,5]糾錯能力更強，且可以有效糾正突發(fā)錯誤，因此受到廣泛關(guān)注。本文采用基于漸進邊增長(PEG)算法結(jié)合準(zhǔn)循環(huán)擴展，并通過優(yōu)化非零元素選擇，構(gòu)造了一種與新一代衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口標(biāo)準(zhǔn)中參數(shù)一致的多進制LDPC碼。由于構(gòu)造的多進制LDPC碼的校驗矩陣可通過行列交織、簡單調(diào)整后轉(zhuǎn)換為多進制RA碼的校驗矩陣結(jié)構(gòu)，編碼復(fù)雜度較低。仿真表明，相較于IS-GPS-800接口標(biāo)準(zhǔn)中的LDPC碼，本文所構(gòu)造的多進制LDPC碼有明顯編碼增益，且其編碼復(fù)雜度較低。

1 多進制LDPC碼的構(gòu)造

在本文中，設(shè)計的多進制LDPC碼采用一種多步生成的半隨機構(gòu)造方法，即首先構(gòu)造一個MB×NB的基矩陣；然后將基矩陣的每個元素擴展為B×B的子矩陣，進而得到M×N的二進制校驗矩陣Hb，其中M=MB×B，N=NB×B；最后利用GF(q)上的非零元素替代二進制矩陣Hb中的“1”，得到多進制LDPC碼的校驗矩陣H。下面詳細(xì)介紹本設(shè)計中多進制LDPC碼的構(gòu)造方法。

步驟1：基矩陣的設(shè)計

根據(jù)碼長和碼率，確定基矩陣的大小。然后根據(jù)節(jié)點的度數(shù)和圍長的設(shè)定要求，依次對每個變量節(jié)點選擇合適的校驗節(jié)點進行連邊。在本設(shè)計中，基矩陣的大小是2×4，行重和列重分別為2和4，即基矩陣是大小為2×4的全1矩陣。

步驟2：采用PEG算法的基矩陣準(zhǔn)循環(huán)擴展

完成大小為MB×NB的基矩陣的構(gòu)造后，將基矩陣的每個元素擴展為B×B的子矩陣。在本實現(xiàn)中，采用循環(huán)置換矩陣替代基矩陣中的“1”元素，以全零陣替代基矩陣中的“0”元素，并采用PEG算法[6]確保在用B×B的子矩陣替換基矩陣中的元素后校驗矩陣仍滿足設(shè)定的圍長要求。

由于置換矩陣的循環(huán)性，PEG算法不再是以單個變量節(jié)點逐個向Tanner圖中添加邊，而是以一組變量節(jié)點(B個)的形式添加。對于每個變量節(jié)點組，只需以第一個變量節(jié)點為根進行深度為l的擴展，而其它變量節(jié)點所連接的校驗節(jié)點自動確定[7]。

圖1 以變量節(jié)點sj為根進行深度為l的擴展

步驟3：非零元素的配置

在采用PEG算法得到擴展的二進制矩陣后，需要對非零元素進行配置。非零元素的配置對多進制LDPC碼的性能影響很大，可隨機取自集合{α0,α1,…,αq-2}，也可進行優(yōu)化。Davey和Mackay通過蒙特卡洛法，搜索GF(q)上行重為dc時的最優(yōu)非零值[4]。而Poulliat C等人利用非零元素的二進制矩陣替代非零元素，得到一個等價的二進制校驗矩陣，然后再進行優(yōu)化分析，該優(yōu)化方法的基本思想是搜索可使最小碼字距離dmin最大的非零值，從而使得校驗節(jié)點傳遞給變量節(jié)點的消息更可靠[8]。本文采用的優(yōu)化方法是通過優(yōu)化非零元素的位置，盡量消除短環(huán)上可能形成的低重碼字，因此可有效減少低重碼字的數(shù)量，改善多進制碼的性能，尤其是高信噪比下的性能。具體地，對定義在有限域GF(64)上行重dc=4的多進制LDPC碼，每一行選擇的最優(yōu)值均為α0、α9、α22和α37。

此外，通過以上方法構(gòu)造的多進制LDPC碼可通過縮短和刪余操作對碼長和碼率進行小的調(diào)整。其中，對縮短碼，發(fā)送端將被縮短的比特設(shè)定為一個確定的序列，如全0序列，然后再進行編碼，接收端在被縮短比特對應(yīng)的位置按照確定的序列進行譯碼。而刪余則是有選擇地刪除編碼后碼字序列中的若干校驗位比特，接收端在刪余比特對應(yīng)位置的信道先驗信息為0。

2 多進制LDPC碼的編碼方案

多進制LDPC碼的編碼一般有兩種方法：基于生成矩陣的編碼方法和基于校驗矩陣的編碼方法。基于生成矩陣的編碼方法的運算量和存儲量較大，不利于硬件實現(xiàn)，因此多采用基于校驗矩陣的編碼方法[9]。

考慮到RA碼的編碼器較為簡單，可實現(xiàn)線性時間編碼[10]，本文設(shè)計的LDPC碼的校驗矩陣經(jīng)線性變換并略微調(diào)整后轉(zhuǎn)換為多進制RA碼的校驗矩陣結(jié)構(gòu)，因此可直接采用RA編碼器進行編碼。具體地，對校驗矩陣H=[HmHc〗的右側(cè)矩陣Hc(行重和列重都為2)進行行交織和列交織，使非零元素位于雙對角線和矩陣的最右上角上，并刪除最右上角的元素。在對Hc進行行列交織時，為保證變量節(jié)點和校驗節(jié)點之間的校驗關(guān)系不變，Hm也要進行相同的行交織。Hc經(jīng)行列交織和修改后的矩陣結(jié)構(gòu)如下式所示，

(1)

其中αki,j∈GF(q)，i=0，j=1或1≤i≤(M?1)，j=0,1。

假定c=[m p]表示一個碼字，其中m和p分別表示信息符號向量和校驗符號向量。為方便，修改后的校驗矩陣仍記為H=[HmHc]，則有:

H·cT=[Hm,Hc]·[m,p]T

=Hm·mT+Hc·pT=0T

(2)

因此，編碼后的校驗位向量為:

(3)

由于Hc為雙對角線矩陣，則上式中Hc-1為下三角矩陣，因此可采用累加器實現(xiàn)，構(gòu)造的多進制LDPC碼的編碼器結(jié)構(gòu)如圖2所示，其中αk由矩陣Hc的次對角線與主對角線上的非零值決定。

圖2 多進制QC-LDPC碼的編碼器框圖

在編碼后，將得到的校驗位向量p與信息位向量m一起，構(gòu)成最終的碼字向量c=[m p]。

為設(shè)計與IS-GPS-800接口標(biāo)準(zhǔn)中LDPC碼的碼長和碼率一致的多進制LDPC碼，本文采用了截短和刪余方法微調(diào)有關(guān)參數(shù)。其中，針對IS-GPS-800標(biāo)準(zhǔn)中碼長為548，碼率為0.5的LDPC碼，具體參數(shù)設(shè)計如下，采用半隨機構(gòu)造法構(gòu)造了一個定義在有限域GF(64)上的多進制LDPC碼，其基矩陣是大小為2×4的全1矩陣，擴展因子為23?；谶@些參數(shù)，構(gòu)造的多進制LDPC碼的碼長為552，碼率為0.5。去掉兩個信息比特，即在274位信息比特前補充兩個0比特，然后再進行編碼。編碼后，刪余兩個校驗比特。因此傳輸長度成為548個比特。在譯碼端，在被縮短比特的對應(yīng)位置按照確定的0序列進行譯碼。

3 優(yōu)化設(shè)計與仿真結(jié)果

以IS-GPS-800標(biāo)準(zhǔn)中規(guī)定的兩種碼長的LDPC碼為參照，本文采用基于PEG算法與準(zhǔn)循環(huán)擴展的半隨機構(gòu)造法設(shè)計了定義在有限域GF(64)上的LDPC碼。為與IS-GPS-800標(biāo)準(zhǔn)中碼長為1200，碼率為0.5的LDPC碼進行對比，設(shè)計了參數(shù)完全相同的多進制LDPC碼，其校驗矩陣的基矩陣是大小為2×4的全1矩陣，擴展因子為50。同樣，為與IS-GPS-800標(biāo)準(zhǔn)中碼長548，碼率0.5的LDPC碼進行對比，構(gòu)造出的多進制LDPC碼的基矩陣也是大小為2×4的全1矩陣，擴展因子為23。兩個多進制LDPC碼的校驗矩陣每一行的非零值均為α0，α9，α22和α37。基于這樣的參數(shù)構(gòu)造的LDPC碼碼長為552。為與標(biāo)準(zhǔn)中LDPC碼的碼長相同，采用截短和刪余操作，使傳輸碼長變?yōu)?48。

為降低構(gòu)造的多進制LDPC碼的誤碼平層，采用全局優(yōu)化方法[8]來避免產(chǎn)生低重碼字的環(huán)。對于環(huán)長為l的環(huán)，如果其等價的二進制矩陣是滿秩的，則該環(huán)不會產(chǎn)生碼字，因此該環(huán)的存在不會影響LDPC碼的性能。為避免環(huán)長為l的環(huán)產(chǎn)生低重碼字，可通過改變校驗矩陣對應(yīng)行的非零元素的值，來確保環(huán)長為l的環(huán)滿足滿秩條件。表1和表2分別給出了構(gòu)造的兩種LDPC碼的優(yōu)化結(jié)果，包括Tanner圖優(yōu)化后的環(huán)個數(shù)和非零元素優(yōu)化后產(chǎn)生低重碼字的環(huán)個數(shù)。

表1 定義在GF(64)上的(274,548)碼的優(yōu)化結(jié)果

表2 定義在GF(64)上的(600,1200)碼的優(yōu)化結(jié)果

圖3和圖4分別為構(gòu)造的多進制LDPC碼與IS-GPS-800接口標(biāo)準(zhǔn)中的兩種二進制LDPC碼采用置信傳播(BP)算法時的誤比特率和誤幀率的性能比較，其中迭代次數(shù)為40。從圖中可看出，與IS-GPS-800接口標(biāo)準(zhǔn)中碼長為1200，碼率為0.5的二進制LDPC碼相比，在BER為10-7或FER為10-5時，設(shè)計的多進制LDPC碼可獲得約0.25 dB的性能增益。而相較于IS-GPS-800接口標(biāo)準(zhǔn)中碼長為548，碼率為0.5的二進制LDPC碼，在BER為10-7或FER為10-5時，設(shè)計的多進制LDPC碼可獲得約0.6 dB的性能增益。

圖3 設(shè)計的多進制LDPC碼與IS-GPS-800標(biāo)準(zhǔn)中兩種二進制LDPC碼的誤比特率比較

圖4 設(shè)計的多進制LDPC碼與IS-GPS-800標(biāo)準(zhǔn)中兩種二進制LDPC碼的誤幀率比較

4 結(jié) 語

在本文中，結(jié)合PEG算法與準(zhǔn)隨機擴展的半隨機方法，并對非零元素進行優(yōu)化，構(gòu)造了適用于衛(wèi)星導(dǎo)航系統(tǒng)的多進制LDPC碼，給出其高效編碼方案。仿真結(jié)果表明，相較于衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口標(biāo)準(zhǔn)中的二進制LDPC碼，設(shè)計的多進制LDPC碼有明顯的性能增益，且編碼復(fù)雜度較低。由于優(yōu)化時間的原因，本文中仿真所采用的多進制LDPC碼仍存在進一步參數(shù)優(yōu)化的空間，為設(shè)計實現(xiàn)適合衛(wèi)星導(dǎo)航系統(tǒng)應(yīng)用的多進制LDPC碼提供了新的選項。下一步將設(shè)計更為高效的優(yōu)化方法優(yōu)化多進制LDPC碼。

[1] GPS Navstar Joint Program Office.Navstar GPS space segment/user segment L1C interface [S].IS-GPS-800C,2013.

[2] Jin H,Khandekar A.Irregular repeat-accunulate codes [C]// Proc.the 2nd International Smposium on Turbo Codes & Related Topics.Best,France:IEEE Press,2000:1-8.

[3] Li Z,Kumar B.A class of good quasi-cyclic low-densigy parity check codes based on progressive edge growth graph [C]// Proc.Conference Record of the Thirty-Eighth Asilomar Conference on Signals,Systems and Computers.CA,USA:IEEE Press,2004:1990-1994.

[4] Davey M C,MacKay D.Low-density parity-check codes over GF(q) [C]// Proc.IEEE Information Theory Workshop.Killarney,Ireland:IEEE Press,1998:70-71.

[5] Zhang L,Tan L,Zeng F.A novel family of nonbinary LDPC codes over finite fields [C]// Proc.International Conference on Information Science and Control Engineering.Shenzhen,China:IEEE Press,2012:1-5.

[6] Hu X Y,Eleftheriou E,Amold D M.Progressive edge-growth tanner graphs [C]// Proc.IEEE Global Telecommunications Conference.San Antonio,USA:IEEE Press,2001:995-1001.

[7] Healy C T,de Lamare R C.Quasi-cyclic low-desity parity-check codes based on decoder optimised progressive edge growth for short blocks [C]// Proc.IEEE International Conference on Acoustics,Speech and Signal Processing.Kyoto,Japan:IEEE Press,2012:2889- 2992.

[8] Poulliat C,Fossorier M,Declercq D.Design of regular (2,dc)-LDPC codes over GF(q) using their binary images [J].IEEE Transactions on Communications,2008,56(10):1626-1635.

[9] 詹偉,梁俊杰.低編碼復(fù)雜度不規(guī)則LDPC碼的構(gòu)造方法[J].計算機工程與應(yīng)用,2010,46(28):102-104.

[10] Chen W,Liang C,Guo T,et al.Encoder implementation with FPGA for non-binary LDPC codes [C]// Proc.18th Asia Pacific Conference on Communications.Jeju,Korea:IEEE Press,2012:980-984.

CONSTRUCTING NON-BINARY LDPC CODES FOR SATELLITE NAVIGATION SYSTEMS

Chen Weigang Cao Yan Xia Xiaoxiao Yang Jinsheng

(SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China)

We designed a kind of non-binary low-density parity-check (NB-LDPC) codes with superior performance and low encoding complexity for the application of satellite navigation systems.In our design,we constructed the NB-LDPC codes with same parameters as the binary LDPC codes in IS-GPS-800 interface standard of new generation satellite navigation system by combining the semi-random construction method based on progressive-edge-growth (PEG) algorithm and quasi-cyclic expansion and optimising the non-zero elements selection.Furthermore,by converting parity-check matrix to the check matrix structure of repeat-accumulate (RA) codes,we implemented the low complexity encoding.Simulation results demonstrated that,the designed NB-LDPC codes has noticeable encoding gain and lower encoding complexity compared with the binary LDPC codes in same code length and code rate in IS-GPS-800 interface standard of satellite navigation system.

Satellite navigation system Non-binary LDPC codes Semi-random construction method

2014-10-27。國家自然科學(xué)基金項目(61101114)；教育部新世紀(jì)優(yōu)秀人才支持計劃項目(NCET-12-0401)；天津市科技興海項目(KJXp011-2);天津大學(xué)自主創(chuàng)新基金項目(60301002,60301014)。陳為剛，副教授，主研領(lǐng)域：高效編碼調(diào)制，無線網(wǎng)絡(luò)及應(yīng)用。曹艷，碩士生。夏曉曉，碩士生。楊晉生，副教授。

TP911.2

A

10.3969/j.issn.1000-386x.2016.04.026