面向硬件實現(xiàn)的64進制LDPC譯碼算法研究與性能評估

樹玉泉，章林鋒，胡志蕊，劉軼龍，貢冀鑫

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.中國人民解放軍32021部隊，北京 100094)

0 引言

北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)于2020年7月正式開通投入運行，向全球用戶提供位置服務(wù)、應(yīng)急搜救和精密單點定位等多種特色服務(wù)。根據(jù)北斗系統(tǒng)空間信號接口控制文件B1C，B2b和B2a，北斗系統(tǒng)下行信號電文使用了(200,100)(162,81)(96,48)(88,44)四種長度的六十四進制低密度奇偶校驗碼(Low Density Parity Check，LDPC)作為主要信道編碼形式。與二進制LDPC相比，多進制LDPC具有更低的誤碼平層和更高的增益[1-2]，但是由于其譯碼復(fù)雜度較高，對硬件資源較為緊張的接收機設(shè)計帶來了挑戰(zhàn)[3]。

Gallager[4]于1963年提出了二進制LDPC，并得到了廣泛應(yīng)用[5-7]。1998年，Davey和Mackay[8]研究了基于有限域的多進制LDPC，并給出了多進制LDPC的和積譯碼算法(Q-ary Sum-Product Algorithm，QSPA)，多進制LDPC的性能要優(yōu)于二進制LDPC碼，但這是以更大的編譯碼復(fù)雜度換取的。對于定義在GF(q)域的LDPC碼，其中q=2p，標(biāo)準的和積譯碼算法復(fù)雜度會隨著p的增加而迅速增加。而另一方面，隨著進制數(shù)的提升，其抗突發(fā)錯誤能力越強。因此，對于多進制LDPC的研究集中在如何降低譯碼算法復(fù)雜度。

本文面向接收機硬件實現(xiàn)，將基于FB算法的BC方案應(yīng)用到校驗節(jié)點更新中，并通過優(yōu)化變量存儲機制，減少不必要過程變量的存儲，進一步優(yōu)化了資源消耗。在此基礎(chǔ)上，基于Xilinx的XC7K325T FPGA開發(fā)了(200,100)(162,81)(96,48)(88,44)四合一譯碼模塊，開展了性能驗證和分析，在性能、譯碼時延等方面找到了適應(yīng)北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)接收機的參數(shù)配置方案。

1 傳統(tǒng)譯碼算法

T-EMS算法雖然譯碼速率快，但需要存儲較多路徑，不利于資源優(yōu)化，且該算法性能相比于EMS算法略有降低。由于北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)下行電文速率較低，對于地面接收來說譯碼速率不是第一訴求。而且一般的導(dǎo)航接收機硬件資源有限，極大限度地壓縮譯碼模塊的資源占用是更有意義的。因此，本文選擇EMS系列算法進行研究，分析其復(fù)雜度的核心因素，并面向硬件實現(xiàn)，從資源優(yōu)化、流水線處理等方面進行了針對性的設(shè)計。

1.1 EMS算法

對于GF(q),q=2p域上的多進制LDPC，假設(shè)其碼長為n，信息長度為m，校驗矩陣為H，行重為dc，EMS譯碼算法描述如下：

① 初始化數(shù)據(jù)

將接收到的數(shù)據(jù)進行處理，獲得每個符號位取值的概率信息：

j=0,1,…,n-1,ak=0,1,…,q-1，

(1)

式中，Lj(ak)表示第j個符號位取值為ak的概率信息；zj為相對于yj而言通過信道信息估算出來的最有可能的符號，因此，有Lj(ak)≥0，且Lj(ak)的取值越小代表該符號位取值為ak的概率越大。

利用初始信息Lj(ak)建立變量節(jié)點更新矩陣：

Lqij(0)(ak)=Lj(ak)

i,j∈{N(i),C(j)}={Hi,j≠0}，

(2)

式中，Lqij(0)(ak)為變量節(jié)點的初始化矩陣；N(i)為校驗矩陣H的行重集合；C(j)為H矩陣的列重集合。

② 校驗節(jié)點的運算(水平運算)

第l次迭代，校驗節(jié)點更新如下：

(3)

Ψ(i|aj=ak)={(aj′)j′∈N(i){j}|Hijak+

(4)

式中，Lr(l)ij為第l次迭代時的校驗節(jié)點矩陣；Ψ(i|aj=ak)為變量節(jié)點參與更新運算的集合。

③ 變量節(jié)點的運算(垂直運算)

第l次迭代變量節(jié)點更新如下：

(5)

式中，Lqij(l)為第l次迭代時的變量節(jié)點矩陣。

④ 判決輸出

(6)

yj=argmin(Lqj(l)(ak))，

(7)

式中，yj為最終判決輸出的譯碼結(jié)果。

1.2 復(fù)雜度分析

可以看出，校驗節(jié)點的更新是制約多進制LDPC譯碼復(fù)雜度的核心因素。式(4)是校驗節(jié)點更新時用到的集合，該集合的大小隨q和dc的變大而急劇增加。對于北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)使用的六十四進制LDPC而言，q=64，dc=4，每次迭代更新1個有效位置需要計算643次，共有m×dc個有效位置。如此高的運算量對于硬件實現(xiàn)來說是不可承受的。

為了降低譯碼算法的運算量，將從算法層面的資源優(yōu)化方案和實現(xiàn)層面的流水線處理方案兩方面入手,降低硬件實現(xiàn)的復(fù)雜度。

2 面向硬件實現(xiàn)的譯碼方案

2.1 資源優(yōu)化

資源優(yōu)化將從兩方面入手。引入置信長度的概念主要為降低運算量，變量存儲機制主要優(yōu)化運算過程中變量所需的存儲資源。

2.1.1 置信長度

因為最終判決是選擇每個符號位取值最小的概率信息對應(yīng)的域元素，在進行校驗節(jié)點更新運算時，可以將取值較大的概率信息舍去，每個符號位只傳遞概率信息值最小的nm個變量及其對應(yīng)的域元素。nm即置信長度。可將式(4)改寫為：

sort(Lqij′(l-1))

aj′∈conf(Lqij′(l-1),nm)

(8)

首先對Lqij′(l-1)進行從小到大排序，域元素也對應(yīng)調(diào)整，conf(Lqij′(l-1),nm)為前nm個概率信息對應(yīng)的域元素的集合。可以看出，通過運算復(fù)雜度與nm呈正相關(guān)，但是nm取值過小會影響譯碼增益。一般來說，nm≥0.5×q時，將不會對譯碼增益產(chǎn)生明顯影響。下面將對nm的取值做進一步的仿真分析。

2.1.2 變量存儲機制

傳統(tǒng)的EMS算法中，核心的處理為校驗節(jié)點Lr(l)ij(ak)的更新運算和變量節(jié)點Lq(l)ij(ak)的更新運算，需要存儲Lr(l)ij(ak)和Lq(l)ij(ak)。2個變量均為三維矩陣，大小為m×dc×q。由式(5)和式(6)可以看出，最終譯碼結(jié)果的判決只和Lr(l)ij(ak)有關(guān)，Lq(l)ij(ak)僅作為中間變量參與存儲。因此，可以考慮將第2步校驗節(jié)點的運算和第3步變量節(jié)點的運算進行整合。

第1步：初始化數(shù)據(jù)

Lrij(0)(ak)=0，

(9)

Lqj(0)(ak)=Lj(ak)。

(10)

第2步：迭代更新

第l次迭代：

For:i=1:m

Lqij(l)(ak)=Lqj(l-1)(ak)-Lrij(l-1)(ak)，

(11)

(12)

(13)

End

第3步：判決輸出

yj=argmin(Lqj(l)(ak))。

(14)

可以看出，整個譯碼過程精簡為3步，整合后的運算過程將變量節(jié)點更新和校驗節(jié)點更新耦合在一起，使得整個譯碼過程更為緊湊。Lqij(l)(ak)的維度由m×dc×q減小為dc×q，且僅需臨時存儲。通過上述設(shè)計，可以進一步節(jié)省存儲資源并降低時延。

2.2 FB-BC流水線處理

將校驗節(jié)點的運算拆解成兩兩運算。以校驗節(jié)點第m行為例，行度為dc，ni表示第m行第i個有效位置，0≤i

前向計算：

(15)

后向計算：

(16)

校驗節(jié)點信息更新：

(17)

可以看出，上述操作中均有一步相同的運算，命名為基本運算(2個輸入、1個輸出)。建立基本運算模塊，校驗節(jié)點更新重復(fù)調(diào)用該模塊，可流水線操作并減小資源占用。

關(guān)于基本運算模塊有如下簡單算法：

該模塊設(shè)置有2個輸入和1個輸出，輸入為V和I以及對應(yīng)的索引Vq和Iq，輸出為U和Uq。V和I均是按從小到大排序好的序列。建立一個虛擬矩陣M(該矩陣在實際實現(xiàn)時無需存儲，僅僅是便于理解)和排序器S，S的作用是找最小值。

M中的元素為V和I的對應(yīng)操作：

M(i,j)=max(V(i),I(j)),i,j∈[0,nm]。

(18)

步驟如下：

① 將M的第1列及其對應(yīng)的域元素送入排序器S；

② S找出最小值，并將結(jié)果輸出至U，如果該結(jié)果對應(yīng)的域元素已經(jīng)存在于U中，則不做操作；否則將結(jié)果放入U，對應(yīng)域元素放入Uq；

③ 將該結(jié)果在虛擬矩陣中的右鄰居放入S；

④ 返回步驟②。

3 硬件實現(xiàn)及仿真分析

基于第2章的資源優(yōu)化方案和FB-BC流水線處理方案，開發(fā)了四合一仿真譯碼模塊，并對譯碼模塊的量化位數(shù)、迭代次數(shù)和置信長度等參數(shù)配置進行仿真分析，得到了推薦的參數(shù)配置。最終對北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)應(yīng)用的4種六十四進制LDPC進行了綜合性能分析。

3.1 四合一譯碼模塊

為了驗證算法的可實現(xiàn)性，對北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)六十四進制LDPC性能在量化位數(shù)、迭代次數(shù)和置信長度等方面進行了較為全面的仿真分析，基于Xilinx的XC7K325T FPGA開發(fā)了(200,100)(162,81)(96,48)(88,44)四合一譯碼模塊，譯碼模塊的資源占用如表1所示。

表1 四合一譯碼模塊FPGA資源占用

由表1可以看出，該譯碼模塊的硬件資源占用XC7K325T芯片資源較少，可滿足工程的使用需求。

此外，還開發(fā)了測試評估軟件，與四合一譯碼模塊構(gòu)成了半實物仿真系統(tǒng)。測試評估軟件產(chǎn)生電文并進行編碼、加噪聲和量化處理，并傳輸至四合一譯碼模塊，譯碼模塊完成譯碼后，將譯碼后的電文傳輸至上位機軟件，上位機軟件完成譯碼時延和誤碼率的統(tǒng)計，并借助Matlab的繪圖功能繪制誤碼率曲線。該譯碼模塊的迭代次數(shù)、量化位數(shù)和置信長度等均可配置。

3.2 參數(shù)仿真分析

不同的譯碼模塊參數(shù)配置會對資源占用、譯碼時延和譯碼增益等產(chǎn)生影響，對于接收機設(shè)計，應(yīng)根據(jù)需求選取合適的參數(shù)配置，不應(yīng)一味地求全，進而造成不必要的資源浪費。本節(jié)主要基于(96,48)六十四進制LDPC對譯碼模塊的量化位數(shù)、迭代次數(shù)和置信長度等參數(shù)配置進行仿真分析，并得到推薦的參數(shù)配置。

由于3個參數(shù)相互獨立，因此仿真過程采用控制變量法，即在進行某一項參數(shù)仿真時固定另2個仿真參數(shù)。基本仿真參數(shù)設(shè)置如下：

① 噪聲添加方式：加性高斯白噪聲(Additive White Gaussian Noise，AWGN)。

② 調(diào)制方式：二進制相移鍵控(Binary Phase Shift Keying，BPSK)調(diào)制。

③ 電文：隨機產(chǎn)生0，1。

④ 硬件模塊運行的時鐘為60 MHz。

⑤ 在誤碼率為10-5時計算譯碼增益。

其中，運行時鐘是影響硬件模塊運行速率的主要因素之一，本文對于譯碼模塊吞吐率的結(jié)論是在60 MHz時鐘頻率下得到的。

3.2.1 量化位數(shù)仿真

量化位數(shù)仿真中，迭代次數(shù)設(shè)置為10次，置信長度nm為32。量化位數(shù)遍歷了1～8，并繪制了誤碼率曲線，如圖1所示。

圖1 量化位數(shù)仿真

由仿真結(jié)果可以看出，隨著量化位數(shù)在1～4增加，譯碼增益提升明顯，4 bit量化比1 bit量化譯碼增益增加了2 dB。但是繼續(xù)增加量化位數(shù)譯碼增益幾乎不再發(fā)生變化。因此，可以看出，在4 bit及以上量化時，由量化引起的信道信息已不明顯。

量化位數(shù)是直接影響譯碼模塊資源消耗的因素之一，為了避免不必要的資源開銷，可選擇4～5 bit量化。

3.2.2 迭代次數(shù)仿真

迭代次數(shù)仿真中，量化位數(shù)設(shè)置為5 bit，置信長度nm為32。分別對3，5，7，10，15和20次迭代進行了仿真，并繪制了誤碼率曲線，如圖2所示。

圖2 迭代次數(shù)仿真

由仿真結(jié)果可以看出，迭代次數(shù)3，5，7，10之間譯碼增益差異明顯，10次迭代比3次迭代增加了1.5 dB。但10次迭代與15次迭代之間僅相差0.1 dB，15次迭代和20次迭代幾乎重合，增益不再增加。10次迭代時獲得6.7 dB的增益，即可充分發(fā)揮多進制LDPC的優(yōu)勢。

不同迭代次數(shù)的吞吐率對比結(jié)果如表2所示。

表2 不同迭代次數(shù)的吞吐率對比

由表2可以看出，迭代次數(shù)是直接影響譯碼模塊吞吐率的因素，隨著迭代次數(shù)增加，吞吐率呈等比例下降趨勢。北斗下行電文速率最快不超過1 ks/s，相比之下，在10次迭代時可獲得50.41 ks/s的吞吐率，可滿足接收機的使用需求。考慮到迭代次數(shù)的變化并不涉及譯碼模塊內(nèi)部的調(diào)整，可靈活進行配置，因此建議迭代次數(shù)可設(shè)置為5次和10次兩檔，根據(jù)實際接收信號的載噪比進行動態(tài)調(diào)整。

3.2.3 置信長度仿真

置信長度仿真中，量化位數(shù)設(shè)置為5 bit，迭代次數(shù)設(shè)置為10次，置信長度nm分別取值為8，16，32和64，并繪制了誤碼率曲線，如圖3所示。

圖3 置信長度仿真

由仿真結(jié)果可以看出，nm=16時譯碼增益比nm=8時增加約0.6 dB，nm=32時譯碼增益比nm=16時增加約0.1 dB，nm取值為32，64時增益變化不再明顯。

置信長度可直接影響譯碼時延，建議選擇32。

3.2.4 小結(jié)

從量化位數(shù)、迭代次數(shù)和置信長度仿真可以看出，為了保障接收機獲得高可靠的電文信息，可選擇如下參數(shù)資源配置：

① 量化位數(shù)5，迭代次數(shù)5，置信長度32。

② 量化位數(shù)5，迭代次數(shù)10，置信長度32。

配置①可用于接收載噪比較高的通道，配置②可用于接收載噪比較低的通道。

3.3 綜合仿真分析

選擇上節(jié)推薦的2種參數(shù)組合對(200,100)(162,81)(96,48)(88,44)四種長度的六十四進制LDPC性能進行綜合仿真分析，并與同等長度的二進制LDPC進行了對比分析。二進制LDPC使用NMSA算法，5 bit量化，10次迭代，如圖4所示。

圖4 性能綜合分析

根據(jù)仿真圖，可以得到北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)使用的4種六十四進制LDPC的增益，以及和二進制LDPC的增益對比，如表3所示。

表3 譯碼增益對比

由表3可以看出，基于本文的譯碼硬件實現(xiàn)方案，同等長度下北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)六十四進制LDPC比二進制LDPC約有0.2～0.3 dB的性能增益。同等長度下，10次迭代比5次迭代性能可提升0.7～0.8 dB。

4 結(jié)束語

對傳統(tǒng)的EMS算法進行了描述和復(fù)雜度分析，得出了制約北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)六十四進制LDPC譯碼實現(xiàn)的主要因素。從譯碼過程和資源存儲兩方面進行了針對性設(shè)計，提出了校驗節(jié)點和變量節(jié)點深度耦合的實現(xiàn)方案，優(yōu)化了譯碼過程和存儲資源占用。并引入FB-BC流水線處理機制，最終形成了面向硬件實現(xiàn)的譯碼方案。基于該方案開發(fā)了四合一譯碼模塊，并開展了參數(shù)仿真分析和綜合仿真分析。參數(shù)仿真分析表明，量化位數(shù)5、迭代次數(shù)5或10、置信長度32時是資源、時延和增益三方面綜合最優(yōu)的搭配，其中10次迭代即可基本發(fā)揮出多進制LDPC的譯碼增益優(yōu)勢。綜合仿真分析表明，基于本文提出的方案，可獲得6.7～7.1 dB的譯碼增益，并比同等長度的二進制LDPC獲得約0.2～0.3 dB的性能增益。本文的研究成果可為北斗三號全球衛(wèi)星導(dǎo)航系統(tǒng)接收機的設(shè)計提供參考。