基于FMS算法的多元LDPC碼的譯碼器設(shè)計(jì)
2021-02-26 03:26:44盧泳兵袁瑞敏
無線電通信技術(shù) 2021年1期
盧泳兵，袁瑞敏，朱 敏
(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081；2.西安電子科技大學(xué)ISN國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710075)
0 引言
多元LDPC碼定義在有限域GF(q=2r)上。相比于二元LDPC碼，多元LDPC碼在中短碼長(zhǎng)上具有更高的編碼增益和更強(qiáng)的抗突發(fā)錯(cuò)誤能力，并且非常適宜與高階調(diào)制方案結(jié)合。因此，多元LDPC碼可應(yīng)用于空間通信等功率受限系統(tǒng)以及高階調(diào)制、MIMO等高吞吐量傳輸系統(tǒng)。北斗三號(hào)衛(wèi)星導(dǎo)航系統(tǒng)就采用了定義在GF(64)上的LDPC碼[1-2]。多元LDPC碼的經(jīng)典譯碼算法是多元和積算法(QSPA)[3]。QSPA算法具有近似最優(yōu)的譯碼性能，它的譯碼復(fù)雜度為O(ρq2)，其中ρ為校驗(yàn)節(jié)點(diǎn)的度。但是，過高的譯碼復(fù)雜度阻礙了多元LDPC碼在實(shí)際系統(tǒng)中的應(yīng)用。如何在糾錯(cuò)性能損失可忽略的前提下降低譯碼復(fù)雜度成為一個(gè)研究難點(diǎn)。
QSPA的復(fù)雜度主要由校驗(yàn)節(jié)點(diǎn)的更新過程決定。簡(jiǎn)化譯碼算法根據(jù)校驗(yàn)節(jié)點(diǎn)的更新方式大致可以分為兩類。第一類譯碼算法采用了前向后向更新策略，如擴(kuò)展最小和算法[4]。EMS算法在因子圖上傳遞消息時(shí)只保留前nm(nm?q)個(gè)最可靠的消息，其譯碼復(fù)雜度為O(ρnmlog2nm)。文獻(xiàn)[5-8]針對(duì)EMS算法給出了簡(jiǎn)化策略。對(duì)于EMS算法，前向后向策略由于其串行本質(zhì)而使譯碼器的吞吐量受限，同時(shí)存儲(chǔ)中間結(jié)果又需要占用存儲(chǔ)空間。因此在ρ較大時(shí)，EMS算法的表現(xiàn)不是很好。第二類譯碼算法基于網(wǎng)格圖進(jìn)行譯碼，如基于網(wǎng)格圖的EMS(Trellis Based EMS，T-EMS)[9]算法。T-EMS算法在網(wǎng)格圖上選取部分節(jié)點(diǎn)用于構(gòu)造可靠路徑，能夠并行更新消息。T-EMS算法在高吞吐量方面具有潛力，同時(shí)由于只需要存儲(chǔ)部分節(jié)點(diǎn)，降低了存儲(chǔ)需求。文獻(xiàn)[10]對(duì)T-EMS算法進(jìn)行改進(jìn)，提出了FMS算法。FMS算法不僅保留了T-EMS高并行度的優(yōu)勢(shì)，而且具有很低的計(jì)算復(fù)雜度以及良好的糾錯(cuò)性能。文獻(xiàn)[11]針對(duì)多元LDPC碼提出了分層譯碼算法。在分層譯碼算法中，校驗(yàn)節(jié)點(diǎn)被劃分成幾層。層與層之間的校驗(yàn)節(jié)點(diǎn)串行更新，層內(nèi)的校驗(yàn)節(jié)點(diǎn)采用簡(jiǎn)化算法并行更新。分層譯碼的好處是能夠加快收斂速度。
本文將FMS譯碼算法和分層譯碼算法結(jié)合來設(shè)計(jì)多元LDPC譯碼器。譯碼器使用的是北斗三號(hào)衛(wèi)星導(dǎo)航系統(tǒng)的GF(64)LDPC(88,44)碼。
1 多元LDPC碼的譯碼
1.1 基本概念
多元LDPC碼由定義在GF(q)上的M×N的奇偶校驗(yàn)矩陣H的零空間給出。H每一行的非零元個(gè)數(shù)稱為行重，用ρ表示。H每一列的非零元個(gè)數(shù)稱為列重，用v表示。對(duì)于規(guī)則LDPC碼，ρ和v都是常數(shù)。用c=[c0,c1,c2,…,cN-1]表示多元LDPC碼的一個(gè)碼字。碼字經(jīng)過BPSK調(diào)制在AWGN信道上傳輸，在接收端得到y(tǒng)=[y0,y1,y2,…,yN-1]，其中yj是一個(gè)r元向量，j=0,1,2,…,N-1。用al，l=0,1,2,…,q-1表示GF(q)上的一個(gè)元素。假設(shè)碼字等概發(fā)送，對(duì)于碼字的第j個(gè)符號(hào)，可以得到對(duì)數(shù)似然比(Log-Likelihood-Ratio，LLR)形式的消息向量Lj。式(1)給出了每個(gè)消息的計(jì)算方式。
(1)
式中，amax為cj最可能的有限域元素。這種度量方式確保了消息的度量值是非負(fù)數(shù)，而且值越小，消息越可靠。
1.2 FMS譯碼算法
FMS算法和EMS算法具有相似性，它們只傳遞前nm個(gè)最可靠的消息。消息向量中的元素按照可靠度由高到低的順序排列。消息采用了分布存儲(chǔ)，一方面存儲(chǔ)消息的可靠度，另一方面存儲(chǔ)相應(yīng)的有限域元素。在多元LDPC碼的因子圖中，變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間有置換節(jié)點(diǎn)。置換節(jié)點(diǎn)將變量節(jié)點(diǎn)消息的有限域元素和H中相應(yīng)的非零元相乘(置換過程)，將校驗(yàn)節(jié)點(diǎn)消息的有限域元素和H中相應(yīng)的非零元相除(逆置換過程)。對(duì)某個(gè)度為ρ的校驗(yàn)節(jié)點(diǎn)，用Rl,c和Yc,l(0≤l<ρ)分別表示置換后的輸入可靠度向量和逆置換前的輸出可靠度向量，相應(yīng)的有限域元素向量記為Rsl,c和Ysc,l。將Rl,c(0≤l<ρ)按照向量中第2個(gè)LLR值由小到大的順序重新排列。假設(shè)排列后的結(jié)果為：
R0,c[1]≤R1,c[1]≤R2,c[1],…,Rρ-1,c[1]。
(2)
圖1 度為5的校驗(yàn)節(jié)點(diǎn)的網(wǎng)格圖Fig.1 Trellis for a check node of degree 5
① 第一類只有1條路徑，為最可靠路徑，記作Ⅰ類路徑。
② 第二類有ρ條路徑，每條路徑僅有1個(gè)偏移節(jié)點(diǎn)，來自網(wǎng)格圖的第2行，記作Ⅱ類路徑。
③ 第三類有2ρ-3條路徑，這類路徑分為兩個(gè)小類：第一小類包含ρ-1條路徑，每條路徑的第1個(gè)偏移節(jié)點(diǎn)是網(wǎng)格圖的第2行第1列節(jié)點(diǎn)，第2個(gè)偏移節(jié)點(diǎn)來自網(wǎng)格圖第2行的其余列，記作Ⅲ類路徑；第二小類包含ρ-2條路徑，每條路徑的第1個(gè)偏移節(jié)點(diǎn)是網(wǎng)格圖的第2行第2列節(jié)點(diǎn)，第2個(gè)偏移節(jié)點(diǎn)來自網(wǎng)格圖第2行的第3到第ρ列，記作Ⅳ類路徑。
④ 第四類有ρ(nnum-2)條路徑，每條路徑僅有1個(gè)偏移節(jié)點(diǎn)，偏移節(jié)點(diǎn)來自網(wǎng)格圖第3行到第nnum行的節(jié)點(diǎn)，記作V類路徑。
⑤ 第五類有2(nm-nnum)條路徑，每條路徑僅有一個(gè)偏移節(jié)點(diǎn)，這類路徑分為2個(gè)小類：第一小類的偏移節(jié)點(diǎn)來自Si1，記作VI類路徑；第二小類的偏移節(jié)點(diǎn)來自Si2，記作VII類路徑。
定義ΔRs和ΔR，分別存儲(chǔ)路徑校驗(yàn)值和可靠度?？筛鶕?jù)文獻(xiàn)[10]中的式(16)和式(17)對(duì)ΔRs和ΔR進(jìn)行更新，輸出向量Yc,l和Ysc,l(0≤l<ρ)可根據(jù)文獻(xiàn)[10]中的式(18)和式(19)對(duì)進(jìn)行更新。
1.3 分層譯碼算法
在傳統(tǒng)的泛洪式調(diào)度策略中，所有的校驗(yàn)節(jié)點(diǎn)更新結(jié)束后才進(jìn)行變量節(jié)點(diǎn)的更新。實(shí)際上，考慮到硬件資源消耗的問題，LDPC譯碼器一般不會(huì)設(shè)計(jì)成全并行結(jié)構(gòu)。為了能夠在部分并行結(jié)構(gòu)下加快譯碼器的收斂速度，有學(xué)者提出了分層譯碼的調(diào)度策略[11-12]。分層策略對(duì)CPM-QC-LDPC(Circulant-Permutation-Matrix Quasi-Cyclic LDPC)碼最為合適。一個(gè)CPM內(nèi)的校驗(yàn)節(jié)點(diǎn)為一層，層內(nèi)的校驗(yàn)節(jié)點(diǎn)并行更新。但本文使用的多元LDPC碼非零元呈現(xiàn)隨機(jī)分布，因此以單個(gè)校驗(yàn)節(jié)點(diǎn)為一層。下面介紹下分層譯碼算法。
② 檢驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)更新：
第一步：對(duì)于第m層的校驗(yàn)節(jié)點(diǎn)i，根據(jù)式(3)更新變量節(jié)點(diǎn)消息(或者叫先驗(yàn)信息)，其中j∈Ni。
(3)
第三步：根據(jù)式(4)計(jì)算變量節(jié)點(diǎn)j∈Ni的后驗(yàn)消息。
(4)
③ 判決得到碼字。如果碼字滿足校驗(yàn)方程，則停止迭代，輸出碼字，否則m=m+1。
④ 如果m>T，則l=l+1，m=1。如果l>Imax，則宣告譯碼失敗，終止迭代；否則轉(zhuǎn)至步驟②。
分層譯碼的算法框圖如圖2所示。從圖中可以看出，校驗(yàn)節(jié)點(diǎn)在上一次迭代中產(chǎn)生的消息需要存起來，直到在下一次迭代對(duì)本層進(jìn)行更新時(shí)才會(huì)用到。每個(gè)校驗(yàn)節(jié)點(diǎn)都需要一個(gè)RAM來存儲(chǔ)在本層產(chǎn)生的校驗(yàn)節(jié)點(diǎn)消息。
圖2 分層譯碼的算法框圖Fig.2 Block diagram of layer decoding algorithm
1.4 性能比較與復(fù)雜度分析
圖3針對(duì)LDPC(88,44)碼給出了譯碼算法的性能。圖例中“EMS”和“FMS”的下標(biāo)表示nm，“FMS”的上標(biāo)表示nnum。如圖3所示，當(dāng)nm=16時(shí)，EMS算法相比于QSPA算法約有0.1 dB的性能損失；當(dāng)nm=16，nnum=3時(shí)，F(xiàn)MS算法相比于QSPA算法約有0.35 dB的性能損失；當(dāng)nm=16，nnum=6時(shí)，F(xiàn)MS算法相比于QSPA算法約有0.3 dB的性能損失。對(duì)于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
譯碼算法的復(fù)雜度主要體現(xiàn)在實(shí)數(shù)加法(Real Addition,RA)、實(shí)數(shù)比較(Real Comparison,RC)以及有限域加法(Galois field Addition,GA)上。由于對(duì)于FPGA實(shí)現(xiàn)來說，實(shí)數(shù)加法和實(shí)數(shù)比較的復(fù)雜度相當(dāng)，所以本文將這兩個(gè)復(fù)雜度結(jié)合在一起分析。圖4比較了EMS和FMS兩種譯碼算法在泛洪策略和分層策略下的復(fù)雜度，仿真參數(shù)為nm=16，nnum=6，泛洪策略的最大迭代次數(shù)為50，分層策略的最大迭代次數(shù)為15?？梢钥闯?，F(xiàn)MS算法的復(fù)雜度明顯低于EMS算法，并且對(duì)于同樣的校驗(yàn)節(jié)點(diǎn)更新算法，使用分層策略相比于使用泛洪策略，計(jì)算量降低約一半。
圖4 EMS算法和FMS算法的復(fù)雜度比較Fig.4 Comparison of complexity between the EMS algorithm and the FMS algorithm
相較于EMS算法，F(xiàn)MS算法雖然在BER性能方面略有不及，但是在復(fù)雜度方面的增益卻非常高。為保證良好的性能同時(shí)又要有很低的復(fù)雜度，本文采用FMS算法結(jié)合分層策略設(shè)計(jì)譯碼器，F(xiàn)MS算法參數(shù)為：nm=16，nnum=6。
2 多元LDPC譯碼器的結(jié)構(gòu)
2.1 FMS算法的量化
譯碼算法的量化性能是譯碼器所能實(shí)現(xiàn)的性能。量化的動(dòng)態(tài)范圍會(huì)影響譯碼器性能的好壞和資源占用的高低。圖5給出了分層結(jié)構(gòu)的FMS算法的量化性能。量化方案用(bi,bf)表示，其中bi表示整數(shù)部分的量化比特?cái)?shù)，bf表示小數(shù)部分的量化比特?cái)?shù)。為了兼顧性能和復(fù)雜度，本文對(duì)LLR進(jìn)行5 bit量化，其中整數(shù)部分用4 bit表示，小數(shù)部分用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 譯碼器總體結(jié)構(gòu)
譯碼器主要由校驗(yàn)節(jié)點(diǎn)單元、變量節(jié)點(diǎn)單元及奇偶校驗(yàn)單元組成。本文使用的多元LDPC碼，它的奇偶校驗(yàn)矩陣H的非零元呈現(xiàn)隨機(jī)分布。因此分層結(jié)構(gòu)以H的一行作為一層，僅使用一個(gè)校驗(yàn)節(jié)點(diǎn)單元。將H從中間分為左右兩塊，即H=[H1|H2]。對(duì)于任意一行的4個(gè)非零元素，前兩個(gè)位于H1中，后兩個(gè)位于H2中。因此譯碼器使用兩個(gè)變量節(jié)點(diǎn)單元，每個(gè)變量節(jié)點(diǎn)單元串行處理兩個(gè)變量節(jié)點(diǎn)。下面分別對(duì)這幾個(gè)模塊進(jìn)行介紹。
2.3 校驗(yàn)節(jié)點(diǎn)單元
圖6 映射器的結(jié)構(gòu)Fig.6 Structure of the mapper
變量節(jié)點(diǎn)傳來的消息需要經(jīng)過一個(gè)交換網(wǎng)絡(luò)來產(chǎn)生網(wǎng)格圖。交換網(wǎng)絡(luò)的本質(zhì)就是一組數(shù)據(jù)選擇器。為獲得網(wǎng)格圖的前兩列和后兩列，需要四選一的數(shù)據(jù)選擇器。下面通過分析來說明，對(duì)于網(wǎng)格圖第3～ρ列，可使用輸入更少的數(shù)據(jù)選擇器來降低硬件的復(fù)雜度。對(duì)于網(wǎng)格圖第k列，k∈{3,…,ρ}，如果滿足P(k)
圖7給出了路徑構(gòu)造器的結(jié)構(gòu)。交換網(wǎng)絡(luò)Π用于生成網(wǎng)格圖，Π-1用于恢復(fù)校驗(yàn)節(jié)點(diǎn)消息的順序，配置方法如前文所述。用αsum表示最可靠路徑的校驗(yàn)和。對(duì)于某一條路徑，記路徑節(jié)點(diǎn)的列號(hào)為e(0),e(1), …,e(ρ-1)，用z={z(k)}表示路徑的零節(jié)點(diǎn)的有限域元素，用α={α(k)}表示偏移節(jié)點(diǎn)的有限域元素，用x={x(k)}表示偏移節(jié)點(diǎn)的LLR，0≤k<ρ，用Szero表示零節(jié)點(diǎn)的列號(hào)集合，用Snon-zero表示偏移節(jié)點(diǎn)的列號(hào)集合。那么任一條路徑的可靠度L以及校驗(yàn)值α可以根據(jù)式(5)～式(7)計(jì)算。當(dāng)ρ較大時(shí)，如果直接計(jì)算路徑的可靠度會(huì)有ρ-1個(gè)域元素加法。而在FMS譯碼算法中，每條路徑的偏移節(jié)點(diǎn)最多有兩個(gè)，因而采用式(7)的計(jì)算方法，每條路徑最多有4個(gè)域元素加法。
圖7 路徑構(gòu)造器的結(jié)構(gòu)Fig.7 Architecture of the path builder
(5)
(6)
(7)
2.4 變量節(jié)點(diǎn)單元
本文所用的LDPC碼具有列重為2的特征。基于這一特點(diǎn)，本文使用了一種改進(jìn)的分層策略，能夠降低存儲(chǔ)需求。對(duì)于列重為2的變量節(jié)點(diǎn)，接收到的消息可以分為三類，分別是兩個(gè)校驗(yàn)節(jié)點(diǎn)的消息和信道的消息。對(duì)于當(dāng)前校驗(yàn)節(jié)點(diǎn)，圖2通過減操作得到的變量節(jié)點(diǎn)消息可以由信道消息和另一個(gè)校驗(yàn)節(jié)點(diǎn)消息相加得到。那么其中一個(gè)校驗(yàn)節(jié)點(diǎn)更新結(jié)束后，校驗(yàn)節(jié)點(diǎn)消息可以寫到一個(gè)C2V(Check Nodes to Variable Nodes)存儲(chǔ)單元中。當(dāng)更新另一個(gè)校驗(yàn)節(jié)點(diǎn)時(shí)，通過訪問這個(gè)C2V存儲(chǔ)單元和信道消息存儲(chǔ)單元來計(jì)算先驗(yàn)信息。在校驗(yàn)節(jié)點(diǎn)輸出端，輸出消息一方面將被寫到C2V存儲(chǔ)單元，另一方面和先驗(yàn)信息求和，計(jì)算后驗(yàn)信息。通過以上描述，連接到同一個(gè)變量節(jié)點(diǎn)的兩個(gè)校驗(yàn)節(jié)點(diǎn)，可以共用同一個(gè)C2V存儲(chǔ)單元。因此相比于圖2給出的結(jié)構(gòu)，針對(duì)列重為2的改進(jìn)可以節(jié)省一半校驗(yàn)節(jié)點(diǎn)消息的存儲(chǔ)。變量節(jié)點(diǎn)單元的基本操作是完成兩個(gè)輸入消息的求和，這個(gè)硬件結(jié)構(gòu)可以參考文獻(xiàn)[14]。
2.5 奇偶校驗(yàn)單元
在完成每層的更新后，變量節(jié)點(diǎn)單元會(huì)將本層變量節(jié)點(diǎn)的判決結(jié)果傳遞給奇偶校驗(yàn)單元。如果當(dāng)前得到的判決結(jié)果能夠滿足所有的奇偶校驗(yàn)方程，譯碼過程就可以停止了。計(jì)算所有的校驗(yàn)方程需要M×ρ次有限域乘法和M×(ρ-1)次有限域加法，復(fù)雜度比較高。本文給出了一種低復(fù)雜度的實(shí)現(xiàn)方式，每完成一層的更新，能夠得到ρ個(gè)變量節(jié)點(diǎn)的判決結(jié)果。對(duì)于每個(gè)變量節(jié)點(diǎn)，最多影響v個(gè)奇偶校驗(yàn)方程。因此，每完成一層更新，最多需要計(jì)算ρ×(v-1)+1個(gè)奇偶校驗(yàn)方程。本文使用的LDPC(88,44)碼，ρ=4，v=2，每完成一層更新，需要計(jì)算5個(gè)校驗(yàn)方程。
3 多元LDPC譯碼器的FPGA實(shí)現(xiàn)
本文基于Xilinx ZYNQ-7 ZC706評(píng)估板(xc7z045ffg900芯片)對(duì)多元LDPC譯碼器進(jìn)行實(shí)現(xiàn)。表1給出了多元LDPC譯碼器的實(shí)現(xiàn)結(jié)果。譯碼器需要7 904個(gè)查找表、3 967個(gè)寄存器和73.5個(gè)塊存儲(chǔ)單元。在100 MHz譯碼時(shí)鐘下，吞吐量為0.06 Mbit/s。
表1 譯碼器實(shí)現(xiàn)結(jié)果Tab.1 Implementation results of the decoder
4 結(jié)束語
本文設(shè)計(jì)了一種基于FMS譯碼算法的具有分層結(jié)構(gòu)的多元LDPC譯碼器。譯碼器在吞吐量方面仍有很大提升空間，后續(xù)的工作就是對(duì)吞吐量進(jìn)行優(yōu)化。優(yōu)化可以從以下兩方面進(jìn)行：一是采用流水線結(jié)構(gòu)，將流水線每一級(jí)的處理時(shí)延設(shè)計(jì)成nm個(gè)時(shí)鐘周期；二是充分利用空閑時(shí)間。這是因?yàn)榉謱幼g碼器只有在前一層更新結(jié)束后才能更新下一層[15]，這會(huì)導(dǎo)致流水線結(jié)構(gòu)存在大量的空閑時(shí)間。針對(duì)這個(gè)問題，可以采用文獻(xiàn)[16]的幀間流水結(jié)構(gòu)，利用當(dāng)前幀的空閑時(shí)間來處理其他幀。通過上述優(yōu)化方式，譯碼器的吞吐量預(yù)期可達(dá)2.5 Mbit/s。除以上所述，另一個(gè)限制譯碼器吞吐量的因素是本文使用的多元LDPC碼的并行度很低。如果采用具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼，譯碼器的吞吐量和CPM的大小成正比，但代價(jià)是資源占用也和CPM的大小成正比。
