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

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

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

0 引言

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

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

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

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

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

1.1 EMS算法

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

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

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

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

(1)

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

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

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

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

(2)

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

② 校驗(yàn)節(jié)點(diǎn)的運(yùn)算(水平運(yùn)算)

第l次迭代，校驗(yàn)節(jié)點(diǎn)更新如下：

(3)

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

(4)

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

③ 變量節(jié)點(diǎn)的運(yùn)算(垂直運(yùn)算)

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

(5)

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

④ 判決輸出

(6)

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

(7)

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

1.2 復(fù)雜度分析

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

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

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

2.1 資源優(yōu)化

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

2.1.1 置信長(zhǎng)度

因?yàn)樽罱K判決是選擇每個(gè)符號(hào)位取值最小的概率信息對(duì)應(yīng)的域元素，在進(jìn)行校驗(yàn)節(jié)點(diǎn)更新運(yùn)算時(shí)，可以將取值較大的概率信息舍去，每個(gè)符號(hào)位只傳遞概率信息值最小的nm個(gè)變量及其對(duì)應(yīng)的域元素。nm即置信長(zhǎng)度。可將式(4)改寫為：

sort(Lqij′(l-1))

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

(8)

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

2.1.2 變量存儲(chǔ)機(jī)制

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

第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)

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

2.2 FB-BC流水線處理

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

前向計(jì)算：

(15)

后向計(jì)算：

(16)

校驗(yàn)節(jié)點(diǎn)信息更新：

(17)

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

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

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

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

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

(18)

步驟如下：

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

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

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

④ 返回步驟②。

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

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

3.1 四合一譯碼模塊

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

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

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

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

3.2 參數(shù)仿真分析

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

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

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

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

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

④ 硬件模塊運(yùn)行的時(shí)鐘為60 MHz。

⑤ 在誤碼率為10-5時(shí)計(jì)算譯碼增益。

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

3.2.1 量化位數(shù)仿真

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

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

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

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

3.2.2 迭代次數(shù)仿真

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

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

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

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

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

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

3.2.3 置信長(zhǎng)度仿真

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

圖3 置信長(zhǎng)度仿真

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

置信長(zhǎng)度可直接影響譯碼時(shí)延，建議選擇32。

3.2.4 小結(jié)

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

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

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

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

3.3 綜合仿真分析

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

圖4 性能綜合分析

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

表3 譯碼增益對(duì)比

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

4 結(jié)束語(yǔ)

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