基于FMS算法的多元LDPC碼的譯碼器設計

盧泳兵，袁瑞敏，朱 敏

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.西安電子科技大學ISN國家重點實驗室，陜西 西安 710075)

0 引言

多元LDPC碼定義在有限域GF(q=2r)上。相比于二元LDPC碼，多元LDPC碼在中短碼長上具有更高的編碼增益和更強的抗突發錯誤能力，并且非常適宜與高階調制方案結合。因此，多元LDPC碼可應用于空間通信等功率受限系統以及高階調制、MIMO等高吞吐量傳輸系統。北斗三號衛星導航系統就采用了定義在GF(64)上的LDPC碼[1-2]。多元LDPC碼的經典譯碼算法是多元和積算法(QSPA)[3]。QSPA算法具有近似最優的譯碼性能，它的譯碼復雜度為O(ρq2)，其中ρ為校驗節點的度。但是，過高的譯碼復雜度阻礙了多元LDPC碼在實際系統中的應用。如何在糾錯性能損失可忽略的前提下降低譯碼復雜度成為一個研究難點。

QSPA的復雜度主要由校驗節點的更新過程決定。簡化譯碼算法根據校驗節點的更新方式大致可以分為兩類。第一類譯碼算法采用了前向后向更新策略，如擴展最小和算法[4]。EMS算法在因子圖上傳遞消息時只保留前nm(nm?q)個最可靠的消息，其譯碼復雜度為O(ρnmlog2nm)。文獻[5-8]針對EMS算法給出了簡化策略。對于EMS算法，前向后向策略由于其串行本質而使譯碼器的吞吐量受限，同時存儲中間結果又需要占用存儲空間。因此在ρ較大時，EMS算法的表現不是很好。第二類譯碼算法基于網格圖進行譯碼，如基于網格圖的EMS(Trellis Based EMS，T-EMS)[9]算法。T-EMS算法在網格圖上選取部分節點用于構造可靠路徑，能夠并行更新消息。T-EMS算法在高吞吐量方面具有潛力，同時由于只需要存儲部分節點，降低了存儲需求。文獻[10]對T-EMS算法進行改進，提出了FMS算法。FMS算法不僅保留了T-EMS高并行度的優勢，而且具有很低的計算復雜度以及良好的糾錯性能。文獻[11]針對多元LDPC碼提出了分層譯碼算法。在分層譯碼算法中，校驗節點被劃分成幾層。層與層之間的校驗節點串行更新，層內的校驗節點采用簡化算法并行更新。分層譯碼的好處是能夠加快收斂速度。

本文將FMS譯碼算法和分層譯碼算法結合來設計多元LDPC譯碼器。譯碼器使用的是北斗三號衛星導航系統的GF(64)LDPC(88,44)碼。

1 多元LDPC碼的譯碼

1.1 基本概念

多元LDPC碼由定義在GF(q)上的M×N的奇偶校驗矩陣H的零空間給出。H每一行的非零元個數稱為行重，用ρ表示。H每一列的非零元個數稱為列重，用v表示。對于規則LDPC碼，ρ和v都是常數。用c=[c0,c1,c2,…,cN-1]表示多元LDPC碼的一個碼字。碼字經過BPSK調制在AWGN信道上傳輸，在接收端得到y=[y0,y1,y2,…,yN-1]，其中yj是一個r元向量，j=0,1,2,…,N-1。用al，l=0,1,2,…,q-1表示GF(q)上的一個元素。假設碼字等概發送，對于碼字的第j個符號，可以得到對數似然比(Log-Likelihood-Ratio，LLR)形式的消息向量Lj。式(1)給出了每個消息的計算方式。

(1)

式中，amax為cj最可能的有限域元素。這種度量方式確保了消息的度量值是非負數，而且值越小，消息越可靠。

1.2 FMS譯碼算法

FMS算法和EMS算法具有相似性，它們只傳遞前nm個最可靠的消息。消息向量中的元素按照可靠度由高到低的順序排列。消息采用了分布存儲，一方面存儲消息的可靠度，另一方面存儲相應的有限域元素。在多元LDPC碼的因子圖中，變量節點和校驗節點之間有置換節點。置換節點將變量節點消息的有限域元素和H中相應的非零元相乘(置換過程)，將校驗節點消息的有限域元素和H中相應的非零元相除(逆置換過程)。對某個度為ρ的校驗節點，用Rl,c和Yc,l(0≤l<ρ)分別表示置換后的輸入可靠度向量和逆置換前的輸出可靠度向量，相應的有限域元素向量記為Rsl,c和Ysc,l。將Rl,c(0≤l<ρ)按照向量中第2個LLR值由小到大的順序重新排列。假設排列后的結果為：

R0,c[1]≤R1,c[1]≤R2,c[1],…,Rρ-1,c[1]。

(2)

圖1 度為5的校驗節點的網格圖Fig.1 Trellis for a check node of degree 5

① 第一類只有1條路徑，為最可靠路徑，記作Ⅰ類路徑。

② 第二類有ρ條路徑，每條路徑僅有1個偏移節點，來自網格圖的第2行，記作Ⅱ類路徑。

③ 第三類有2ρ-3條路徑，這類路徑分為兩個小類：第一小類包含ρ-1條路徑，每條路徑的第1個偏移節點是網格圖的第2行第1列節點，第2個偏移節點來自網格圖第2行的其余列，記作Ⅲ類路徑；第二小類包含ρ-2條路徑，每條路徑的第1個偏移節點是網格圖的第2行第2列節點，第2個偏移節點來自網格圖第2行的第3到第ρ列，記作Ⅳ類路徑。

④ 第四類有ρ(nnum-2)條路徑，每條路徑僅有1個偏移節點，偏移節點來自網格圖第3行到第nnum行的節點，記作V類路徑。

⑤ 第五類有2(nm-nnum)條路徑，每條路徑僅有一個偏移節點，這類路徑分為2個小類：第一小類的偏移節點來自Si1，記作VI類路徑；第二小類的偏移節點來自Si2，記作VII類路徑。

定義ΔRs和ΔR，分別存儲路徑校驗值和可靠度。可根據文獻[10]中的式(16)和式(17)對ΔRs和ΔR進行更新，輸出向量Yc,l和Ysc,l(0≤l<ρ)可根據文獻[10]中的式(18)和式(19)對進行更新。

1.3 分層譯碼算法

在傳統的泛洪式調度策略中，所有的校驗節點更新結束后才進行變量節點的更新。實際上，考慮到硬件資源消耗的問題，LDPC譯碼器一般不會設計成全并行結構。為了能夠在部分并行結構下加快譯碼器的收斂速度，有學者提出了分層譯碼的調度策略[11-12]。分層策略對CPM-QC-LDPC(Circulant-Permutation-Matrix Quasi-Cyclic LDPC)碼最為合適。一個CPM內的校驗節點為一層，層內的校驗節點并行更新。但本文使用的多元LDPC碼非零元呈現隨機分布，因此以單個校驗節點為一層。下面介紹下分層譯碼算法。

② 檢驗節點和變量節點更新：

第一步：對于第m層的校驗節點i，根據式(3)更新變量節點消息(或者叫先驗信息)，其中j∈Ni。

(3)

第三步：根據式(4)計算變量節點j∈Ni的后驗消息。

(4)

③ 判決得到碼字。如果碼字滿足校驗方程，則停止迭代，輸出碼字，否則m=m+1。

④ 如果m>T，則l=l+1，m=1。如果l>Imax，則宣告譯碼失敗，終止迭代；否則轉至步驟②。

分層譯碼的算法框圖如圖2所示。從圖中可以看出，校驗節點在上一次迭代中產生的消息需要存起來，直到在下一次迭代對本層進行更新時才會用到。每個校驗節點都需要一個RAM來存儲在本層產生的校驗節點消息。

圖2 分層譯碼的算法框圖Fig.2 Block diagram of layer decoding algorithm

1.4 性能比較與復雜度分析

圖3針對LDPC(88,44)碼給出了譯碼算法的性能。圖例中“EMS”和“FMS”的下標表示nm，“FMS”的上標表示nnum。如圖3所示，當nm=16時，EMS算法相比于QSPA算法約有0.1 dB的性能損失；當nm=16，nnum=3時，FMS算法相比于QSPA算法約有0.35 dB的性能損失；當nm=16，nnum=6時，FMS算法相比于QSPA算法約有0.3 dB的性能損失。對于FMS算法，分層策略下最大15次迭代的性能和泛洪策略下最大50次迭代的性能幾乎相同。

圖3 GF(64) LDPC (88,44)碼采用多種譯碼算法的BER性能Fig.3 BER performance of a (88,44) LDPC code over GF(64) using various decoding algorithms

譯碼算法的復雜度主要體現在實數加法(Real Addition,RA)、實數比較(Real Comparison,RC)以及有限域加法(Galois field Addition,GA)上。由于對于FPGA實現來說，實數加法和實數比較的復雜度相當，所以本文將這兩個復雜度結合在一起分析。圖4比較了EMS和FMS兩種譯碼算法在泛洪策略和分層策略下的復雜度，仿真參數為nm=16，nnum=6，泛洪策略的最大迭代次數為50，分層策略的最大迭代次數為15。可以看出，FMS算法的復雜度明顯低于EMS算法，并且對于同樣的校驗節點更新算法，使用分層策略相比于使用泛洪策略，計算量降低約一半。

圖4 EMS算法和FMS算法的復雜度比較Fig.4 Comparison of complexity between the EMS algorithm and the FMS algorithm

相較于EMS算法，FMS算法雖然在BER性能方面略有不及，但是在復雜度方面的增益卻非常高。為保證良好的性能同時又要有很低的復雜度，本文采用FMS算法結合分層策略設計譯碼器，FMS算法參數為：nm=16，nnum=6。

2 多元LDPC譯碼器的結構

2.1 FMS算法的量化

譯碼算法的量化性能是譯碼器所能實現的性能。量化的動態范圍會影響譯碼器性能的好壞和資源占用的高低。圖5給出了分層結構的FMS算法的量化性能。量化方案用(bi,bf)表示，其中bi表示整數部分的量化比特數，bf表示小數部分的量化比特數。為了兼顧性能和復雜度，本文對LLR進行5 bit量化，其中整數部分用4 bit表示，小數部分用1 bit表示。

圖5 GF(64) LDPC (88,44)碼在分層FMS算法下采用不同量化方案的BER性能Fig.5 BER of a (88,44) LDPC code over GF(64), using layered FMS algorithm with different fixed-point implementations

2.2 譯碼器總體結構

譯碼器主要由校驗節點單元、變量節點單元及奇偶校驗單元組成。本文使用的多元LDPC碼，它的奇偶校驗矩陣H的非零元呈現隨機分布。因此分層結構以H的一行作為一層，僅使用一個校驗節點單元。將H從中間分為左右兩塊，即H=[H1|H2]。對于任意一行的4個非零元素，前兩個位于H1中，后兩個位于H2中。因此譯碼器使用兩個變量節點單元，每個變量節點單元串行處理兩個變量節點。下面分別對這幾個模塊進行介紹。

2.3 校驗節點單元

圖6 映射器的結構Fig.6 Structure of the mapper

變量節點傳來的消息需要經過一個交換網絡來產生網格圖。交換網絡的本質就是一組數據選擇器。為獲得網格圖的前兩列和后兩列，需要四選一的數據選擇器。下面通過分析來說明，對于網格圖第3～ρ列，可使用輸入更少的數據選擇器來降低硬件的復雜度。對于網格圖第k列，k∈{3,…,ρ}，如果滿足P(k)lmin1且P(k)>lmin2，那么它對應第k個變量節點。所以為獲得網格圖第3～ρ列，需要ρ-2個三選一的數據選擇器。可以采用查表獲取網格圖第k∈{3,…,ρ}列的數據選擇器的控制信號，查找表的輸入為lmin1和lmin2。校驗節點輸出的消息也需要經過一個交換網絡，以恢復成變量節點的順序。這實際上就是要分析，變量節點可能和網格圖前ρ列中的哪些列對應。首先，對于變量節點k∈{1,2,3,…,ρ}，它可能對應網格圖第1列和第2列。其次，根據前面的分析，還可能對應網格圖第k、k+1或k+2列。這5個位置可能有重復的，因為要滿足k+1≤ρ，k+2≤ρ。所以，輸出端的交換網絡由ρ個數據選擇器組成，每個數據選擇器的輸入端最多有5個。

圖7給出了路徑構造器的結構。交換網絡Π用于生成網格圖，Π-1用于恢復校驗節點消息的順序，配置方法如前文所述。用αsum表示最可靠路徑的校驗和。對于某一條路徑，記路徑節點的列號為e(0),e(1), …,e(ρ-1)，用z={z(k)}表示路徑的零節點的有限域元素，用α={α(k)}表示偏移節點的有限域元素，用x={x(k)}表示偏移節點的LLR，0≤k<ρ，用Szero表示零節點的列號集合，用Snon-zero表示偏移節點的列號集合。那么任一條路徑的可靠度L以及校驗值α可以根據式(5)～式(7)計算。當ρ較大時，如果直接計算路徑的可靠度會有ρ-1個域元素加法。而在FMS譯碼算法中，每條路徑的偏移節點最多有兩個，因而采用式(7)的計算方法，每條路徑最多有4個域元素加法。

圖7 路徑構造器的結構Fig.7 Architecture of the path builder

(5)

(6)

(7)

2.4 變量節點單元

本文所用的LDPC碼具有列重為2的特征。基于這一特點，本文使用了一種改進的分層策略，能夠降低存儲需求。對于列重為2的變量節點，接收到的消息可以分為三類，分別是兩個校驗節點的消息和信道的消息。對于當前校驗節點，圖2通過減操作得到的變量節點消息可以由信道消息和另一個校驗節點消息相加得到。那么其中一個校驗節點更新結束后，校驗節點消息可以寫到一個C2V(Check Nodes to Variable Nodes)存儲單元中。當更新另一個校驗節點時，通過訪問這個C2V存儲單元和信道消息存儲單元來計算先驗信息。在校驗節點輸出端，輸出消息一方面將被寫到C2V存儲單元，另一方面和先驗信息求和，計算后驗信息。通過以上描述，連接到同一個變量節點的兩個校驗節點，可以共用同一個C2V存儲單元。因此相比于圖2給出的結構，針對列重為2的改進可以節省一半校驗節點消息的存儲。變量節點單元的基本操作是完成兩個輸入消息的求和，這個硬件結構可以參考文獻[14]。

2.5 奇偶校驗單元

在完成每層的更新后，變量節點單元會將本層變量節點的判決結果傳遞給奇偶校驗單元。如果當前得到的判決結果能夠滿足所有的奇偶校驗方程，譯碼過程就可以停止了。計算所有的校驗方程需要M×ρ次有限域乘法和M×(ρ-1)次有限域加法，復雜度比較高。本文給出了一種低復雜度的實現方式，每完成一層的更新，能夠得到ρ個變量節點的判決結果。對于每個變量節點，最多影響v個奇偶校驗方程。因此，每完成一層更新，最多需要計算ρ×(v-1)+1個奇偶校驗方程。本文使用的LDPC(88,44)碼，ρ=4，v=2，每完成一層更新，需要計算5個校驗方程。

3 多元LDPC譯碼器的FPGA實現

本文基于Xilinx ZYNQ-7 ZC706評估板(xc7z045ffg900芯片)對多元LDPC譯碼器進行實現。表1給出了多元LDPC譯碼器的實現結果。譯碼器需要7 904個查找表、3 967個寄存器和73.5個塊存儲單元。在100 MHz譯碼時鐘下，吞吐量為0.06 Mbit/s。

表1 譯碼器實現結果Tab.1 Implementation results of the decoder

4 結束語

本文設計了一種基于FMS譯碼算法的具有分層結構的多元LDPC譯碼器。譯碼器在吞吐量方面仍有很大提升空間，后續的工作就是對吞吐量進行優化。優化可以從以下兩方面進行：一是采用流水線結構，將流水線每一級的處理時延設計成nm個時鐘周期；二是充分利用空閑時間。這是因為分層譯碼器只有在前一層更新結束后才能更新下一層[15]，這會導致流水線結構存在大量的空閑時間。針對這個問題，可以采用文獻[16]的幀間流水結構，利用當前幀的空閑時間來處理其他幀。通過上述優化方式，譯碼器的吞吐量預期可達2.5 Mbit/s。除以上所述，另一個限制譯碼器吞吐量的因素是本文使用的多元LDPC碼的并行度很低。如果采用具有準循環結構的LDPC碼，譯碼器的吞吐量和CPM的大小成正比，但代價是資源占用也和CPM的大小成正比。