北斗導航系統中的信道編碼研究

蔡建平，樹玉泉，何巍巍

(1.北京衛星導航中心，北京 100094； 2.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊 050081)

北斗導航系統中的信道編碼研究

蔡建平1，樹玉泉2，何巍巍2

(1.北京衛星導航中心，北京 100094； 2.衛星導航系統與裝備技術國家重點實驗室，河北 石家莊 050081)

針對衛星導航系統現代化的需求，采用高效的編譯碼技術有利于提高導航系統的工作性能與可靠性。研究了BCH碼、卷積碼和低密度奇偶校驗碼(LDPC)這3種常見的信道編碼，對其編譯碼方案進行了簡要介紹，仿真比較了其編碼增益，對不同參數配置下編碼性能進行了分析與比對。依據仿真結果，綜合編譯碼復雜度、電文設計等需求，提出了適用于北斗RDSS系統現代化發展的信道編碼的方案，為北斗系統信號體制設計提供了分析思路和設計參考。

衛星導航；信道編碼；LDPC碼；卷積碼； BCH碼

0 引言

北斗導航系統RNSS和RDSS體制的集成應用是我國衛星導航系統的獨特優勢和核心競爭力，廣泛應用于軍事和經濟社會發展的各個領域。為提高北斗RDSS系統服務性能和用戶容量，需要研究新的信號體制，提升用戶的易用性，降低用戶發射功率。目前用戶設備發射信號的功率較大，需采用的功放是10 W左右[1]。為了降低用戶設備的發射功率，使用戶設備發射信號功率降低到1～2 W，中心站的接收信號的信噪比將大幅度降低，對于RDSS系統中心站接收將是一個巨大的挑戰，因此系統采用高增益的編碼方案是必要的手段。

在衛星導航系統中BCH碼、卷積碼和LDPC碼是常用的3種編碼。BCH碼由Hocquenghem于1959年、Bose和Ray-Chaudhuri于1960年分別提出的、糾正多個隨機錯誤的循環碼；卷積碼由Elias等人于1955年提出的[2]，在編碼過程中，使前后的碼元之間產生相關性，通過相關性對各碼元進行檢驗。尤其是l967年Viterbi提出了Viterbi譯碼算法后，卷積碼逐漸得到廣泛的應用，而后出現的網格編碼調制(TCM)技術，使得卷積碼可以應用于帶寬受限的通信系統中。1962年，Gallage就提出了低密度奇偶校驗碼(Low Density Parity Check Codes，LDPC)，并提出相應的迭代譯碼概念[3]。本文將依次對這3種編碼方案進行技術分析，對其性能進行仿真并且對比它們之間的性能差異，為北斗RDSS系統新的信號體制設計中的高增益編碼方案選取提供參考。

1 BCH碼技術分析

BCH碼是迄今為止所發現的一類很好的線性糾錯碼類[4]。它建立在嚴格的數學基礎上，具有很強的糾錯能力，特別是在中等碼長的情況下，其性能接近理論值，構造方便，編碼簡單，是目前應用的最為廣泛的碼類之一。

BCH碼是循環碼的一個特殊的子集。因此BCH編碼的核心問題在于生成多項式的選取，譯碼的核心問題在于求錯誤位置多項式。下面針對這兩方面進行分析。

1.1 編碼特性之生成多項式的選取

在計算生成多項式之前需要確定碼長n和糾錯能力t。當碼長n確定后，BCH碼糾錯能力t的選擇并不是任意的，需要受到一定限制。對于q元BCH碼2t個根對應2t個最小多項式，每個最小多項式的次數不應超過m，那么2t個最小多項式的最小公倍式g(x)的次數為deg[g(x)]=n-k≤2tm。對于二元BCH碼，t個根對應于t個最小多項式，則它們的最小公倍式g(x)的次數為deg[g(x)]=n-k≤tm。因為xn-1共有n個根，連續冪次根不能超過根的總數，即2t≤n。

設定碼長n和糾錯能力t后，構造BCH碼生成多項式的方法如下：

① 由關系式n=qm-1算出m，查表找到m次本原多項式P(x)，產生一個GF(2m)擴域；

② 在GF(2m)上找一個本原元α，一般情況下，先利用本原多項式P(x)的根，然后分別計算2t個連續冪次根αα2．．．α2t所對應的GF(2m)域中最小多項式m1(x)m2(x)…m2t(x)；

③ 計算這些最小多項式的最小公倍式，得到生成多項式：

g(x)=LCM(m1(x),m2(x),…,m2t(x))。

對于二元BCH碼，由于在GF(2)域上，連續2t個冪次根有一半是另一半的共軛元，在求最大公倍式時不起作用，因此上述第②步可簡化，只需列出t個連續奇次冪的根即可。

當確定好g(x)后，將信息組c(x)乘以xn-k變成xn-kc(x)，乘以xn-k的目的是將信息位放在碼字的最左側，用以生成系統碼。用生成多項式g(x)除以xn-kc(x)，得到商q(x)和余式r(x)，最終編碼結果為xn-kc(x)+r(x)。

1.2 譯碼算法分析

BCH碼有BM、無逆BM和Euclid等譯碼算法。BM算法是由Berlekamp[5]和Masseey[6]提出的。該算法計算較為簡單，適合微處理機和軟件實現，但是在計算過程中需要求逆，在硬件實現中較為困難。為此Burton提出了無逆BM算法[7]。Euclid算法[8]與BM算法的區別主要在迭代過程。BM是基于自回歸濾波器原理來求解最短反饋鏈接多項式，而Euclid迭代式基于多項式分解原理來求解多項式最大公因式，后者需要進行除法運算，其譯碼速度要比BM算法慢。ME算法[9]是一種對Euclid算法的改進，避免了求逆運算。無逆BM算法在實際應用中較為常用。

1.3BCH碼性能分析

影響BCH碼性能的因素主要有：編碼效率、糾錯個數和編碼長度等。下面利用計算機仿真來對比分析上述因素對BCH碼性能的影響。

對糾錯能力相同但是編碼效率不同的BCH碼進行了對比，如圖1所示。對碼長相同但是糾錯個數不同的BCH碼進行了對比，如圖2所示。對碼長相同但是編碼效率不同的BCH碼進行了對比，如圖3所示。對碼率相近但是碼長不同的BCH碼進行了對比，如圖4所示。

圖1 糾錯能力為3 bit的BCH碼誤比特性能對比

圖2 碼長均為15糾錯個數不同的BCH碼誤比特性能對比

圖3 糾錯能力不同碼率不同的BCH碼誤比特性能對比

圖4 碼率相近糾錯能力不同的BCH碼誤比特性能對比

由圖1、圖2、圖3和圖4可以得到如下結論：

① 當糾錯能力相同的時候，碼率越高的BCH碼性能越好(圖1)；

② 移動信道以突發錯誤為主，故糾1個或2個錯誤對信息的傳輸并沒有多少改進(圖2)，而糾錯個數多的譯碼器對性能的改善較大(圖3)；

③ 當碼率相近的時候，糾錯能力越強的BCH碼性能越好(圖4)；

④ 如圖3所示，當信噪比低于3.5dB時，(31，11，5)的性能比(31，26，1)要差，在高信噪比時性能逐漸超過。從理論上分析這是因為在低信噪比時信道容量交叉，碼率高的編碼性能更好，當信道容量提升之后，糾錯能力強的碼的優勢才開始顯露出來；

⑤ 當糾錯個數增加到一定程度時，由于碼的冗余元達到了一定的長度，致使糾錯能力停止增長，反而由于碼率的降低性能會變差(圖3)。

2 卷積碼技術分析

卷積碼(n,k,N)的編碼器是在任一段規定的時間內輸入k個碼元產生n個碼元，它不僅僅取決于這段時間內的N個信息位，還取決于前(N-1)段規定時間內的信息位，參數N即為卷積碼的約束長度，移位寄存器的數目m=N-1。

卷積碼的譯碼器一般情況下使用維特比譯碼并配合軟判決。在這個條件下，隨著約束長度的提升，卷積碼的性能也有一定的提升，但是考慮到接收端在采用維特比軟判決譯碼的時候要求在進行每次迭代時都必須遍歷2k(N-1)個狀態，并存儲2k(N-1)個幸存路徑。約束長度N每增加1，接收端的運算復雜度就會增加1倍。因此卷積碼的約束長度并不是越長越好，在留有一定系統余量的情況下應該選擇適當的約束長度。

在約束條件確定的情況下，影響卷積碼性能的因素還有譯碼時的軟判決量化比特數以及譯碼時的回溯深度。下面從這2個方面對卷積碼進行分析。

2.1 譯碼特性之軟判決量化比特的選擇

卷積碼譯碼的判決方式分為軟判決和硬判決，軟判決的性能要比硬判決好1～1.5dB。因此在實際應用中卷積碼的譯碼方式幾乎全部使用軟判決。在做軟判決時模擬信號難以在數字信號系統中處理，為了實現軟判決，要采用多bit量化來逼近模擬信號作為譯碼器的輸入。然而量化會帶來量化噪聲，因此量化比特數會影響最終的性能。

以(2，1，11)卷積碼為例，如圖5所示。譯碼時選擇的回溯深度均為7N也就是70，采用3、4和5bit量化的軟判決性能要遠遠好于2bit量化。同時4bit量化相對于5bit量化性能幾乎沒有區別，而都要明顯好于3bit量化。軟判決需要用A/D轉換來實現，隨著bit數的增加，A/D轉換器的復雜度明顯增大。綜合考慮，建議在實際應用中選用3bit量化。

圖5 不同量化比特下卷積碼誤比特性能對比

2.2 譯碼特性之回溯深度的選擇

編碼后的信息長度很大，接收機不能等到所有的信息都接收完了之后再去譯碼，而是接收一段譯一段。此接收長度即為回溯深度。

不同回溯深度下卷積碼誤比特性能對比如圖6所示，仍然以(2，1，11)卷積碼為例，當回溯深度為50～100的時候性能變化并不大，但是都要明顯好于回溯深度為30的時候。一般選擇回溯深度為5N～10N，N為編碼器寄存器數。

圖6 不同回溯深度下卷積碼誤比特性能對比

采用硬件實現維特比譯碼時必須要考慮儲存器容量的問題。假設回溯深度為L，每一級由2k(N-1)個狀態，每個狀態由kbit的分支取值，那么總的儲存量為L×k×2k(N-1)bit，相應的路長和路徑值在最小距離譯碼下每個分支最多要求log(n)bit。所以最終需要的存儲容量為L×(k+log(n))×2k(N-1)。所以深度越大性能越好，但是延時越大，并且接收端需要的儲存器容量也越大。最終綜合考慮性能和實現難度，卷積碼譯碼時的回溯深度應選擇為5N左右比較合適。

3 LDPC碼技術分析

LDPC碼是一種碼長非常大的線性分組碼，碼長一般是成百上千，甚至更長。其校驗矩陣也很大，并且具有一個重要特征是矩陣中的非零元素非常少，即為稀疏矩陣，也就是非零元素的個數占總元素個數的比率非常小，故稱之為低密度奇偶校驗碼。

LDPC碼具有以下優點：具有非常接近香農理論界限的性能；能夠實現快速編碼；在不同信道上都表現出良好的性能；不需要深度交織就能獲得好的誤碼性能，所以系統的時延比Turbo碼短；錯誤平層大大降低。

影響LDPC編碼性能的因素有以下2種：校驗矩陣的構造以及譯碼方式的選取。

3.1 編碼特性之校驗矩陣的選擇

因為LDPC碼是基于稀疏校驗矩陣的線性分組碼，并且在實際應用中普遍使用校驗矩陣H直接進行編碼。因此構造LDPC碼實際上就是構造校驗矩陣H。H的結構決定了LDPC碼的性能。構造H的方法大致可以分為2類：隨機構造法和結構化構造法。

在實際應用中，出于對編碼復雜度以及譯碼速度等方面的考慮，一般都采用結構化構造校驗矩陣H。為了便于在實際應用中儲存和編碼，普遍的做法是選用準循環LDPC碼(QC_LDPC)以及雙對角結構。在這方面最具有代表性的是802.16E標準中的LDPC碼。符合802.16E標準的LDPC碼在硬件實現上較為容易。802.16E標準的LDPC碼碼長均為24的倍數，通過改變循環矩陣的維度來改變碼長。該標準在實際中有廣泛的應用。

準循環校驗矩陣H的設計思路在于首先設計出基校驗矩陣Hb，然后將基校驗矩陣Hb的每個元素替換為L階單位矩陣的循環右移矩陣。

以802.16E中規定的(2304，1152)LDPC碼為例，其校驗矩陣表達式為：

式中，子矩陣Hb1的維數為12×12；子矩陣Hb2的維數為12×1；子矩陣Hb3的維數為12×11。循環矩陣的階數L=96。Hb中的每個元素代表循環右移的次數，其中-1代表全0矩陣，0代表單位矩陣。

矩陣Hb1通過相應的算法得到，而Hb3和Hb2具有固定的結構。

矩陣Hb3的結構如下式所示，為雙條對角矩陣，每個非零子矩陣均為單位矩陣。

矩陣Hb2的表達式為

802.16E標準中對不同長度的LDPC碼做了比較，對于LDPC碼，編碼長度越長，性能越好。LDPC碼的優異性能如圖7所示。

當碼長超過2 000時，滿足誤比特率低于10-5僅僅需要不到2 dB。圖中還體現出來在編碼長度相近的情況下LDPC碼的誤比特性能是相近的。在實際應用中選取LDPC編碼長度時，其性能可以參考802.16E標準中碼長相近的LDPC碼的性能。

圖7 不同長度LDPC碼性能比較

當LDPC碼對應的Tanner圖中存在短環時，某一節點發出的信息經過一個環長的傳遞會被傳回本身，從而造成自身信息的疊加，破壞了獨立性的假設，會影響迭代譯碼的效果。另外，在高信噪比的情況下，環的存在使變量節點和校驗節點之間傳遞的信息在經過較少的迭代次數即產生相關性，從而準確性下降形成“錯誤平層”。因此，消除短環是LDPC校驗矩陣設計中優先考慮的問題。由Tanner圖的結構可以知道，環長最小為4。Mackay等指出消除長度為4的環對碼的性能有很大提高，繼續消除其他長度的短環對提高碼的性能的效果越來越不明顯。不包含4環是LDPC校驗矩陣的基本要求。

3.2 譯碼方式的選擇

按照普通線性分組碼的譯碼方式，譯碼的基本思路是先求伴隨式，再根據伴隨式求可糾正的錯誤圖樣。假如碼長n=1 000，信息長度k=500，不同的伴隨式的個數將有2n-k=2500之多，以現有的技術是不能夠實現的。因此LDPC碼的譯碼是基于Tanner圖的迭代譯碼：

① 首先變量節點接收到來自信道的初始概率信息，并將這些信息傳送給與其相連的校驗節點；

② 校驗節點接收到來自與其相連的不同變量節點的信息并進行處理，再將處理后的信息傳送給與其相連的變量節點；

③ 變量節點對校驗節點傳送來的信息處理并進行硬判決。判斷是否達到最大迭代次數或者與校驗矩陣正交，二者滿足其一則停止迭代，輸出判決結果，否則重復執行步驟②和步驟③。

迭代算法主要有置信傳播譯碼(BP)[10]、對數似然比BP譯碼算法(Log-BP)[11]、最小和譯碼算法(Min-Sum)[12]以及歸一化最小和譯碼算法(NormalizedBP-based)[13]等。普通的BP譯碼算法需要大量的乘法運算，運算復雜度較高；對數似然比譯碼算法把大量的乘法運算變為加法運算，減少了運算時間[14]，由于需要對數運算，實現復雜度仍然很大；最小和譯碼算法是將對數似然比算法中的復雜的對數運算簡化成了比較運算，大大降低了譯碼復雜度，但性能有一定的損失；歸一化最小和譯碼算法在最小和譯碼算法的基礎上增加了一些乘法運算，使其性能有了明顯的提升[15]。

不同譯碼方式性能比較如圖8所示，最小和算法雖然運算量小，但是相較于對數似然比算法性能有較大的差距，歸一化最小和的性能比最小和算法有了大約0.5dB的提升，與對數似然比算法的性能非常接近。綜上所述歸一化最小和算法是比較理想的譯碼算法，在誤比特性能，復雜度上都比較合適。

圖8 不同譯碼方式性能比較

4 信道編碼性能對比

不同的信道編碼有各自的特點和適用場景，LDPC碼的性能要優于BCH碼和卷積碼，但是其編譯碼復雜度也會高很多。因此選擇一種合適的信道編碼是非常重要的。

(2，1，N)卷積碼在維特比軟判決譯碼下的性能如圖9所示。在不同碼長下，碼率為1/2下的LDPC編碼的性能如圖10所示。

圖9 不同約束長度的卷積碼性能比較

圖10 不同長度的LDPC碼的性能比較

對比圖9和圖10可知，在誤比特率pe≤10-5的條件下，若采用(2，1，11)的卷積碼，其解調Eb/N0門限約為3.5dB。若采用LDPC編碼，在信息長度小于192bit時，其解調Eb/N0門限高于3.5dB，在信息長度為192bit左右時，其解調Eb/N0門限約為3.5dB。當信息長度達到504bit左右時，其解調Eb/N0門限可降低至2.25dB以下。

BCH碼和LDPC碼的性能比較如圖11所示。可以看出，BCH碼的誤比特性能較低，但與其他2種編碼方式相比，BCH編碼的編譯碼算法都相對簡單，更加容易實現。適用于對誤比特性能要求不高，需要硬件設備簡單的情況。

圖11 BCH碼和LDPC碼的性能比較

在考慮RDSS系統新體制中，當用戶機的發射信號功率為1W(0dBW)時，預估入站接收系統的處理信號的載噪比為35dB-Hz左右。當選擇信息速率Rb=1 kbps時，對應的Eb/N0計算如下：

顯然，此時選擇(2，1，11)卷積編碼便可滿足系統誤碼率需求。但是，當信息長度較大時，選擇LDPC編碼能獲得更大的編碼增益。

綜合考慮糾錯性能、編譯碼復雜度、系統實現成本等因素，建議的編碼方案為：當信息長度小于192 bit時，采用(2，1，11)卷積碼，當信息長度大于等于192 bit時，采用LDPC編碼。

5 結束語

本文從北斗導航RDSS系統提高信號編解碼處理增益的需要出發，分別介紹了BCH碼、卷積碼和LDPC碼等3種常見的信道編碼方案，仿真比較了各編碼方案的解碼性能。仿真結果表明，對于北斗RDSS現代化系統而言，根據電文長度采用自適應卷積碼和LDPC的編碼方案，在電文長度較短時采用卷積碼，電文長度較長時采用LDPC編碼，在提高糾錯能力、增強信號接收的載噪比，優化抗干擾能力的同時，能夠有效減小編碼器復雜度，降低硬件復雜度，是切實可行的衛星導航系統信道編解碼方案。

[1] 鄭晶茹，鄭 萍，馮林剛.北斗衛星導航系統及其應用[J].西部資源，2012(6)：155-157．

[2] 周炯磐，龐沁華，續大我，等.通信原理(第3版)[M].北京：北京郵電大學出版社，2008.

[3] GALLAGER R G.Low-Density Parity-Check Codes[J].IRE Trans.Inform.Theory,1962,8(1):21-28.

[4] WILSON S G.Digital Modulation and Coding[M].Beijing:Publishing House of Electronic Industy,1998.

[5] BERLEKAM E R.Algebraic Coding Theory[J].Trans.Comput,1968(34):393-403.

[6] MASSEY J L.Shift-register Synthesis and BCH Decoding[J].IEEE Trans,1969(15):122-127.

[7] BURTON H O.Inversionless Decoding of Binary BCH Codes[J].IEEE Trans,1971,17(4):464-466.

[8] SUGIYAMA Y,KASAHARA Y,HIRASAWAS M.A Method for Solving Key Equation for Decoding Goppa Codes[J].Inf & Control,1975(27):87-99.

[9] SHAO H M,DEUTSEH L J,YUENANDI J H,et al.A VLSI Design of a Pipeline Reed-Solomon Decoder[J].IEEE Trans,1985(34):393-403.

[10] FORNEY J G D.The Forward-backward Algorithm[C]∥ Proc.34th Allerton Conf.Communication,Control and Computing,1996:432-445.

[11] 張亞林，蔚保國，范廣偉.IEEE802.16e標準下LDPC碼譯碼性能分析[J].無線電工程，2013，43(11)：8-10.

[12] CHEN Jin-hu,MARC P C.Density Evolution for Two Improved BP-based Decoding Algorithms of LDPC Codes[J].IEEE Communications Letters,2002,6(5):256-259.

[13] BRACK T,ALLES M,LEHNIGK-Emden.Low Complexity LDPC Code Decoders for Next Generation Standards Design[C]∥Automation & Test in Europe Conference & Exhibition,2007:1-6.

[14] TANNER R M.A Recursive Approach to Low Complexity Codes[J].IEEE Transactions on Information Theory,1981,27(5):533-547.

[15] 雷 婷,張建志.LDPC編譯碼算法分析[J].無線電工程，2012，42(10)：8-9.

蔡建平 男，(1964—)，碩士，高級工程師。主要研究方向：衛星導航。

何巍巍 女，(1979—)，碩士，高級工程師。主要研究方向：衛星導航。

Research on Channel Coding in Beidou Navigation System

CAI Jian-ping1,SHU Yu-quan2,HE Wei-wei2

(1.BeijingSatelliteNavigationCenter,Beijing100094,China; 2.StateKeyLaboratoryofSatelliteNavigationSystemandEquipmentTechnology,ShijiazhuangHebei050081,China)

In view of the demand of satellite navigation system modernization,the application of high-efficiency codec technology is favourable to improve the operation performance and reliability of navigation system.This paper studies such three common channel coding methods as BCH code,convolutional code and LDPC code.The codec scheme of these three methods is introduced briefly,the coding gain is simulated and the coding performance in different parameter configuration is analyzed and compared.Based on simulation results and combined with codec complexity and message design,this paper proposes a channel coding scheme suitable for Beidou RDSS system modernization and provides analysis idea and design reference for Beidou system signal system design.

satellite navigation;channel coding;LDPC code;convolutional code;BCH code

10.3969/j.issn.1003-3106.2017.05.12

蔡建平,樹玉泉,何巍巍.北斗導航系統中的信道編碼研究[J].無線電工程,2017,47(5):47-53.[CAI Jianping,SHU Yuquan,HE Weiwei.Research on Channel Coding in Beidou Navigation System[J].Radio Engineering,2017,47(5):47-53.]

2017-01-10

地理信息工程國家重點實驗室開放基金資助項目(SKLGIE2014-M-2-4)。

TN911

A

1003-3106(2017)05-0047-07