面向衛星導航系統的多進制LDPC碼的構造

陳為剛 曹 艷 夏曉曉 楊晉生

面向衛星導航系統的多進制LDPC碼的構造

陳為剛 曹 艷 夏曉曉 楊晉生

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

面向衛星導航系統應用，設計一種性能優越且編碼復雜度低的多進制低密度奇偶校驗(LDPC)碼。結合漸進邊增長(PEG)算法與準循環擴展的半隨機構造法，并優化非零元素的選擇，構造與新一代衛星導航系統IS-GPS-800接口標準中參數一致的多進制LDPC碼。進一步，通過將校驗矩陣轉換為重復累加碼(RA)碼的校驗矩陣結構，實現低復雜度編碼。仿真結果表明，與衛星導航系統IS-GPS-800接口標準中碼長碼率相同的二進制LDPC碼相比，多進制LDPC碼有明顯的編碼增益，且其編碼復雜度較低。

衛星導航系統 多進制低密度奇偶校驗碼 半隨機構造法

0 引 言

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

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

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

1 多進制LDPC碼的構造

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

步驟1：基矩陣的設計

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

步驟2：采用PEG算法的基矩陣準循環擴展

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

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

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

步驟3：非零元素的配置

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

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

2 多進制LDPC碼的編碼方案

多進制LDPC碼的編碼一般有兩種方法：基于生成矩陣的編碼方法和基于校驗矩陣的編碼方法?；谏删仃嚨木幋a方法的運算量和存儲量較大，不利于硬件實現，因此多采用基于校驗矩陣的編碼方法[9]。

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

(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為下三角矩陣，因此可采用累加器實現，構造的多進制LDPC碼的編碼器結構如圖2所示，其中αk由矩陣Hc的次對角線與主對角線上的非零值決定。

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

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

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

3 優化設計與仿真結果

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

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

表1 定義在GF(64)上的(274,548)碼的優化結果

表2 定義在GF(64)上的(600,1200)碼的優化結果

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

圖3 設計的多進制LDPC碼與IS-GPS-800標準中兩種二進制LDPC碼的誤比特率比較

圖4 設計的多進制LDPC碼與IS-GPS-800標準中兩種二進制LDPC碼的誤幀率比較

4 結 語

在本文中，結合PEG算法與準隨機擴展的半隨機方法，并對非零元素進行優化，構造了適用于衛星導航系統的多進制LDPC碼，給出其高效編碼方案。仿真結果表明，相較于衛星導航系統IS-GPS-800接口標準中的二進制LDPC碼，設計的多進制LDPC碼有明顯的性能增益，且編碼復雜度較低。由于優化時間的原因，本文中仿真所采用的多進制LDPC碼仍存在進一步參數優化的空間，為設計實現適合衛星導航系統應用的多進制LDPC碼提供了新的選項。下一步將設計更為高效的優化方法優化多進制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] 詹偉,梁俊杰.低編碼復雜度不規則LDPC碼的構造方法[J].計算機工程與應用,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。國家自然科學基金項目(61101114)；教育部新世紀優秀人才支持計劃項目(NCET-12-0401)；天津市科技興海項目(KJXp011-2);天津大學自主創新基金項目(60301002,60301014)。陳為剛，副教授，主研領域：高效編碼調制，無線網絡及應用。曹艷，碩士生。夏曉曉，碩士生。楊晉生，副教授。

TP911.2

A

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