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

陳為剛 曹 艷 夏曉曉 楊晉生

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

陳為剛 曹 艷 夏曉曉 楊晉生

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

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

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

0 引 言

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

LDPC碼校驗(yàn)矩陣的構(gòu)造直接影響LDPC碼的實(shí)現(xiàn)復(fù)雜度和糾錯(cuò)性能。LDPC碼校驗(yàn)矩陣的構(gòu)造方法主要分為：隨機(jī)構(gòu)造方法、結(jié)構(gòu)化構(gòu)造方法以及半隨機(jī)構(gòu)造方法等。隨機(jī)構(gòu)造的LDPC碼的優(yōu)點(diǎn)是碼長(zhǎng)和碼率設(shè)計(jì)靈活，可很好地匹配由密度演化等方法得到的最優(yōu)度分布，但其編碼復(fù)雜度往往較高，不利于硬件實(shí)現(xiàn)。而結(jié)構(gòu)化的校驗(yàn)矩陣可有效降低編碼復(fù)雜度，但這種構(gòu)造方法一般難于根據(jù)優(yōu)化的度分布設(shè)計(jì)非規(guī)則碼，譯碼門限性能較差。半隨機(jī)構(gòu)造方法結(jié)合了隨機(jī)構(gòu)造和結(jié)構(gòu)化構(gòu)造的優(yōu)點(diǎn)，是比較實(shí)用的LDPC碼構(gòu)造方法，比較常見(jiàn)的半隨機(jī)構(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ú)線城域網(wǎng)等。

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

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

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

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

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

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

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

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

圖1 以變量節(jié)點(diǎn)sj為根進(jìn)行深度為l的擴(kuò)展

步驟3：非零元素的配置

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

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

2 多進(jìn)制LDPC碼的編碼方案

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

考慮到RA碼的編碼器較為簡(jiǎn)單，可實(shí)現(xiàn)線性時(shí)間編碼[10]，本文設(shè)計(jì)的LDPC碼的校驗(yàn)矩陣經(jīng)線性變換并略微調(diào)整后轉(zhuǎn)換為多進(jìn)制RA碼的校驗(yàn)矩陣結(jié)構(gòu)，因此可直接采用RA編碼器進(jìn)行編碼。具體地，對(duì)校驗(yàn)矩陣H=[HmHc〗的右側(cè)矩陣Hc(行重和列重都為2)進(jìn)行行交織和列交織，使非零元素位于雙對(duì)角線和矩陣的最右上角上，并刪除最右上角的元素。在對(duì)Hc進(jìn)行行列交織時(shí)，為保證變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間的校驗(yàn)關(guān)系不變，Hm也要進(jìn)行相同的行交織。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]表示一個(gè)碼字，其中m和p分別表示信息符號(hào)向量和校驗(yàn)符號(hào)向量。為方便，修改后的校驗(yàn)矩陣仍記為H=[HmHc]，則有:

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

=Hm·mT+Hc·pT=0T

(2)

因此，編碼后的校驗(yàn)位向量為:

(3)

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

圖2 多進(jìn)制QC-LDPC碼的編碼器框圖

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

在本文中，結(jié)合PEG算法與準(zhǔn)隨機(jī)擴(kuò)展的半隨機(jī)方法，并對(duì)非零元素進(jìn)行優(yōu)化，構(gòu)造了適用于衛(wèi)星導(dǎo)航系統(tǒng)的多進(jìn)制LDPC碼，給出其高效編碼方案。仿真結(jié)果表明，相較于衛(wèi)星導(dǎo)航系統(tǒng)IS-GPS-800接口標(biāo)準(zhǔn)中的二進(jìn)制LDPC碼，設(shè)計(jì)的多進(jìn)制LDPC碼有明顯的性能增益，且編碼復(fù)雜度較低。由于優(yōu)化時(shí)間的原因，本文中仿真所采用的多進(jìn)制LDPC碼仍存在進(jìn)一步參數(shù)優(yōu)化的空間，為設(shè)計(jì)實(shí)現(xiàn)適合衛(wèi)星導(dǎo)航系統(tǒng)應(yīng)用的多進(jìn)制LDPC碼提供了新的選項(xiàng)。下一步將設(shè)計(jì)更為高效的優(yōu)化方法優(yōu)化多進(jìn)制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].計(jì)算機(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。國(guó)家自然科學(xué)基金項(xiàng)目(61101114)；教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃項(xiàng)目(NCET-12-0401)；天津市科技興海項(xiàng)目(KJXp011-2);天津大學(xué)自主創(chuàng)新基金項(xiàng)目(60301002,60301014)。陳為剛，副教授，主研領(lǐng)域：高效編碼調(diào)制，無(wú)線網(wǎng)絡(luò)及應(yīng)用。曹艷，碩士生。夏曉曉，碩士生。楊晉生，副教授。

TP911.2

A

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