基于線段投影的ADMM-LP譯碼算法硬件實現(xiàn)

張俊偉, 鄭昱津, 劉惠陽, 夏巧橋*

(1.華中師范大學(xué)物理科學(xué)與技術(shù)學(xué)院, 武漢 430079; 2.武漢大學(xué)計算機學(xué)院, 武漢 430072)

低密度奇偶校驗(low density parity check, LDPC)碼[1]有糾錯能力強、結(jié)構(gòu)簡單、錯誤平臺低、便于硬件實現(xiàn)等優(yōu)點,因此被廣泛地應(yīng)用于光纖通信、5G通信以及衛(wèi)星通信等領(lǐng)域[2-4]。研究者針對LDPC碼提出了各種譯碼算法,當前應(yīng)用最廣泛的為BP譯碼算法,且一直是當前硬件實現(xiàn)的重點[5]。但該算法在高性噪比下存在錯誤平臺問題。Barman等[6]提出了一種基于交替方向乘子法(alternating direction method of multipliers,ADMM)的線性規(guī)劃(linear programming,LP)譯碼算法,該算法可有效解決錯誤平臺問題,且與傳統(tǒng)LP譯碼算法相比,有效地降低了算法的復(fù)雜度,并具有最大似然特性。在此基礎(chǔ)上,研究者針對ADMM譯碼算法提出了各種改進算法[7]。

硬件實現(xiàn)是ADMM譯碼算法落地于實際的關(guān)鍵,而硬件實現(xiàn)的難點在于其中涉及的奇偶校驗多胞體投影算法[8]。Barman等[6]對此提出了求解歐幾里得投影的“two-slice”法。但是,“two-slice”法涉及排序和反排序操作,復(fù)雜度較高。對此,Zhang等[9]提出了一種割查找(cut search algorithm, CSA)算法,CSA算法與原始投影算法相比,擁有更低的復(fù)雜度,但仍然涉及排序操作。Zhang等[10]提出在奇偶多面體上的投影可以轉(zhuǎn)化為在單純形上的投影,但單純形投影方法仍然涉及部分排序操作。Wasson等[11]提出在奇偶多胞體和概率單純形上投影的硬件實現(xiàn),并在現(xiàn)場可編程邏輯門陣列(field programmable logic gate array,FPGA)平臺上實現(xiàn)了ADMM譯碼器[12]。但以上投影算法都是精確投影,復(fù)雜度較高,降低了ADMM-LP譯碼器的吞吐率,增加了硬件資源的消耗。Jiao等[13]提出了一種基于查找表(look up table,LUT)的投影方法,進一步簡化了投影算法。Samhan[14]在Wasson的ADMM-LP譯碼器的基礎(chǔ)上結(jié)合LUT投影方法做了進一步改進,在FPGA上實現(xiàn)了約50%的位寬縮減。最近,Xia等[15]提出了一種不需要排序和迭代操作的線段投影算法(line segment projection algorithm,LSA),并在此算法的基礎(chǔ)上進行了改進研究[16-18]。LSA是一種近似投影,復(fù)雜度低,且比CSA更節(jié)省投影時間。

結(jié)合LSA的硬件友好特性,現(xiàn)開展ADMM-LP譯碼算法的硬件實現(xiàn)研究。首先針對硬件實現(xiàn)對線段投影算法進行簡化,并設(shè)計完整的ADMM譯碼硬件實現(xiàn)方案,最后在FPGA上搭建完整的譯碼測試平臺。本文所實現(xiàn)的譯碼器使得譯碼速率更高,且譯碼器的資源消耗更低,得以更好地應(yīng)用于實際。

1 改進的ADMM-LP譯碼算法

1.1 ADMM-LP譯碼算法

對于一個m×n階的校驗矩陣H,其行下標索引可用J={1,2,…,m}表示,其列下標索引可用I={1,2,…,n}表示。vi表示第i個變量節(jié)點,cj表示第j個校驗節(jié)點。與vi關(guān)聯(lián)的校驗節(jié)點用Nv(i)表示,與cj關(guān)聯(lián)的變量節(jié)點用Nc(j)表示。dcj=|Nc(j)|和dvi=|Nv(i)|則分別表示校驗節(jié)點的度以及變量節(jié)點的度。

ADMM-LP譯碼的基本模型為

(1)

式(1)中:x為待求解的發(fā)送碼字;γi為對數(shù)似然比;Pj為選擇矩陣;zj為校驗節(jié)點cj對應(yīng)的輔助變量;PPdj為第j個校驗節(jié)點對應(yīng)的校驗多胞體。增廣拉格朗日函數(shù)為

(2)

式(2)中:λ為對偶變量或拉格朗日乘子;μ為懲罰系數(shù)且為正數(shù)。式(2)可以通過式(3)迭代求解。

xk+1=argminLμ(x,zk,λk)

(3)

zk+1=argminLμ(xk+1,z,λk)

(4)

(5)

在對式(3)中xk+1求解時,將zk和λk當作常量,并對x求偏導(dǎo),由式(6)表示。

(6)

式(6)中:Π[0,1]為在區(qū)間[0,1]上的投影。同理,在更新z時,將x和λ看作常數(shù),對z求偏導(dǎo),得到zj的解為

(7)

式(7)中:ΠPPdj為在校驗多胞體PPdj上做歐幾里得投影操作,此操作是ADMM-LP譯碼算法中最復(fù)雜的部分,也是本文的研究重點所在。

1.2 改進的ADMM-LP算法

改進的ADMM-LP算法合并了原始ADMM-LP算法中的部分參數(shù),使得消息傳遞變量更簡潔。具體地,本文研究將常量μ從變量λj和zj的計算中移除,降低無關(guān)變量的迭代傳遞計算。此外,針對硬件實現(xiàn)中,定點計算可能出現(xiàn)的不對稱性,可以將ADMM譯碼算法改為中心對稱的譯碼模型,即

(8)

與原始ADMM譯碼模型不同的是,超立方體由[0,1]n變換到了[-0.5,0.5]n,通過簡單的加減法計算就能將原始的非對稱模型變化為中心對稱模型。改進后的基于中心對稱的ADMM-LP譯碼算法的具體流程如算法1所示。

算法1 改進的ADMM-LP 譯碼算法輸入:信道接收到的對數(shù)似然比(LLR)向量γ∈Rn輸出:譯碼結(jié)果x∈[-0.5,0.5]n1:for ?j∈J,do2: λj←0 //對參數(shù)λj進行初始化3: for ?i∈I, do4: mj→i←0 //對mj→i做初始化5: end for6:end for 7:repeat8: for ?i∈I,do //變量節(jié)點更新9: ti=1TmNv(i)←i-γi10: si=ti+α, 如果ti≥0ti-α, 如果ti<0{11: xi=Π-12,12[]siNv(i) //變量節(jié)點的計算12: end for13: for ?j∈J, do //校驗節(jié)點更新14: vj=xNc(j)+λj15: zj=ΠPP|Nc(j)|-12(vj) //對zj進行投影計算16: λj=vj-zj //參數(shù)λj的更新17: mj→Nc(j)=2zj-vj //校驗節(jié)點計算18:end for19:直到達到最大迭代次數(shù)

1.3 簡化的LSA算法

投影算法是ADMM-LP譯碼算法中最復(fù)雜且最耗時的部分,為了使ADMM譯碼算法在硬件上更容易實現(xiàn),尋求一種簡單的投影算法至關(guān)重要。LSA算法是一種近似投影算法,原始的LSA算法需要判斷待投影向量是否在超立方體上,如果待投影向量在超立方體上,則此待投影向量為投影結(jié)果,此過程為精確投影。反之,若待投影向量不在超立方體上,則需進行近似投影操作。為消除分支在硬件實現(xiàn)中對流水線的影響,本文去除超立方體投影判斷該步驟,將統(tǒng)一采用近似投影作為投影結(jié)果,實驗結(jié)果表明,該簡化操作對譯碼器性能并無明顯影響。

為使LSA算法硬件實現(xiàn)更為簡便,本文將原始LSA算法中的可合并變量進行合并,進一步簡化了算法流程以及變量的傳遞。簡化后的LSA算法如算法2所示。其中,βv表示待投影向量v的二值化向量,它是將指示向量與奇數(shù)頂點向量合并后的變量。相較于傳統(tǒng)的LSA算法,簡化后的中心對稱LSA算法的步驟1、步驟3和步驟6中的比較閾值

算法2 簡化的中心對稱LSA算法輸入:待投影向量v′∈Rdj1:βv,i=1, v′i>00, v′i≤0{2:if 集合{i|βv,i=1}的元素個數(shù)為偶數(shù)3: i?=argmaxi||v′i-0||4: βv,i?=1-βv,i?5: end if6: 位置索引a=argmini(|v′i-0|),位置索引b=argmini≠a(|v′i-0|)7:偶數(shù)頂點:A=βv,i, 如果 i≠a1-βv,i, 如果 i=a{,偶數(shù)頂點:B=βv,i, 如果 i≠b1-βv,i, 如果 i=b{8:輸出:投影向量s=ΠAB(v′)9:return s

由原始的0.5變?yōu)?,中心對稱可消除硬件實現(xiàn)中定點數(shù)計算帶來的不利影響。然后對索引a和b位置上的元素進行翻轉(zhuǎn)得到其相對應(yīng)的偶數(shù)頂點A和B。最后,計算待投影向量v在線段AB上的投影s=ΠAB(v′)。

2 ADMM-LP譯碼算法的硬件實現(xiàn)

2.1 譯碼器總體框架

在ADMM-LP譯碼器進行譯碼過程中,首先輸入對數(shù)似然比(likelihood rate,LLR)向量數(shù)據(jù),將數(shù)據(jù)寫入輸入緩存中,變量節(jié)點計算模塊從輸入緩存中讀取數(shù)據(jù)并進行計算。若譯碼未通過且迭代次數(shù)未達到最大值,則將變量節(jié)點信息通過變量節(jié)點信息緩存(VN-To-CN)傳遞到校驗節(jié)點計算模塊進行計算。校驗節(jié)點計算完畢后將計算結(jié)果寫入到校驗節(jié)點信息緩存(CN-To-VN),中間變量寫入校驗節(jié)點變量緩存供下次迭代使用。信息在變量節(jié)點計算模塊與校驗節(jié)點計算模塊之間來回迭代,在譯碼成功或達到最大迭代次數(shù)之后將譯碼結(jié)果輸出。

圖1 硬件結(jié)構(gòu)框圖Fig.1 Block diagram of hardware structure

2.2 并行度設(shè)計

采用準循環(huán)低密度奇偶校驗(QC-LDPC)碼作為實驗碼字,由于QC-LDPC碼特殊的矩陣結(jié)構(gòu),在硬件實現(xiàn)中,可以通過移位寄存器來完成存儲和尋址,從而降低了硬件譯碼器的部署難度。

本次實驗采用c1(155,64)碼字進行實驗,該碼字是一個校驗節(jié)點度為5,變量節(jié)點度為3的碼字,該碼字的校驗矩陣可以由5×3個31×31的單位矩陣的循環(huán)位移矩陣組成。從譯碼效率的角度考慮,可以實例化5個VN模塊和3個CN模塊并行計算。

在本實驗中,所有的數(shù)據(jù)存儲模塊都將使用RAM模塊實現(xiàn)。具體地,結(jié)合本實驗所使用的QC-LDPC碼字,輸入緩存采用5個深度為31的RAM存儲。但由于VN模塊和CN模塊之間串行工作,在VN-To-CN模塊和CN-To-VN模塊之間只需2個深度為31的RAM來進行數(shù)據(jù)交互。

2.3 變量節(jié)點計算模塊

變量節(jié)點計算模塊主要完成1.2節(jié)中算法1的變量節(jié)點的更新計算部分。首先對所有校驗節(jié)點傳遞給變量節(jié)點的信息求和,并減去LLR向量γ。然后對ti的值進行判斷,若ti>0則加上懲罰系數(shù)α,反之則減去懲罰系數(shù)α。算法1中步驟11用步驟10的計算結(jié)果除以變量節(jié)點的度,最后將結(jié)果投影到區(qū)間[-0.5,0.5]。VN模塊硬件結(jié)構(gòu)圖如圖2所示。

圖2 VN模塊硬件結(jié)構(gòu)圖Fig.2 Hardware structure diagram of VN module

變量節(jié)點計算模塊經(jīng)過Vivado HLS生成的模塊IP如圖3所示。

圖3 變量節(jié)點計算模塊IPFig.3 Compute module IP of variable node

度為3的變量節(jié)點計算模塊生成的intellectual property IP包含時鐘接口ap_clk、復(fù)位接口ap_rst、控制接口ap_ctrl、LLR向量輸入接口llr_V_V、懲罰系數(shù)輸入接口p_V_V、三個變量節(jié)點輸入datain_V_V以及一個輸出數(shù)據(jù)dataout_V_V。變量節(jié)點計算模塊采用1個時鐘周期間隔的流水線設(shè)計,每次并行的輸入LLR向量、懲罰系數(shù)以及3個輸入數(shù)據(jù),經(jīng)過6個時鐘周期的計算,輸出結(jié)果數(shù)據(jù)。

為了對裝配式建筑工程施工在進行招標評標時出現(xiàn)的各種問題加以解決，可以采取兩段式評標方法來對工程項目進行招標評標工作。實際操作時，在第一階段主要評審資質(zhì)標和技術(shù)標，并以第一階段的評審結(jié)果為基礎(chǔ)確定具備進入商務(wù)標的第二階段評審的資格。同時可以根據(jù)招標方的實際需要，對兩個階段的評標得分權(quán)重進行適當?shù)恼{(diào)整，并計算出最終的評標結(jié)果，確定中標單位。

2.4 校驗節(jié)點計算模塊

校驗節(jié)點計算模塊主要完成1.2節(jié)算法1中的校驗節(jié)點更新計算部分,根據(jù)算法結(jié)構(gòu),校驗節(jié)點計算模塊由3個向量加法運算以及投影模塊組成。如圖4所示,首先,從變量節(jié)點計算模塊傳來的數(shù)據(jù)與參數(shù)λj求和,然后經(jīng)過投影模塊進行計算,將計算結(jié)果mj→Nc(j)傳遞給變量節(jié)點計算模塊,并將計算后的中間變量λj存入校驗節(jié)點變量緩存,供下一次校驗節(jié)點計算時使用。

圖4 CN模塊硬件結(jié)構(gòu)圖Fig.4 Hardware structure diagram of CN module

其中,投影模塊是校驗節(jié)點計算模塊中最復(fù)雜的算法模塊,也是本實驗實現(xiàn)過程的關(guān)鍵所在,將采用1.3節(jié)提出的算法2。

基于前述LSA算法給出對應(yīng)的硬件實現(xiàn)框圖如圖5所示,首先對待投影向量v進行二值化操作,使其大于等于0時為1,小于0時為0。然后對向量βv進行奇偶判斷,若元素為偶數(shù)個,則對距離中心點“0”最近的元素取反,反之則無需取反。接下來將距離中心點“0”最近的兩個索引取反,得到A、B兩個偶數(shù)頂點,最后,在線段AB上進行投影操作。

圖5 LSA模塊硬件結(jié)構(gòu)圖Fig.5 Hardware structure diagram of LSA module

整個校驗節(jié)點模塊需要58個時鐘周期完成,其中數(shù)據(jù)流水輸入輸出需要31個時鐘周期,投影模塊需要13個時鐘周期,校驗節(jié)點計算需要10個時鐘周期以及4個時鐘周期的時鐘同步。校驗節(jié)點計算模塊雖然是整個譯碼器中最耗時的模塊,但由于其并行的流水線結(jié)構(gòu)和簡單的投影算法,相較于其他ADMM-LP硬件譯碼器而言,仍然具有優(yōu)勢。

2.5 定點位寬設(shè)計

在投影模塊計算過程中涉及較多定點數(shù)的計算,而定點數(shù)的位寬將影響譯碼的精度以及資源的占用。因此,為達到譯碼準確度與資源占用之間的最佳平衡,本文研究需選取合適的定點量化方案,采用Q(S,I,D)來表示,其中,S、I、D分別為符號位、整數(shù)位寬和小數(shù)位寬。例如,Q(1,2,3)表示符號位為1位,整數(shù)部分位寬為2,小數(shù)部分位寬為3。

為達到譯碼速度與資源的平衡,結(jié)合文獻[11]給出各模塊的量化方案,具體量化方案如表1所示。

其中,變量節(jié)點計算模塊VN中的LLR向量輸入采用Q(1,0,7)的量化方案,即1位符號位,7位小數(shù)位,校驗節(jié)點傳遞給變量節(jié)點信息CN-To-VN采用Q(1,3,7)的量化方案。VN模塊輸出數(shù)據(jù),即變量節(jié)點傳遞給校驗節(jié)點信息VN-To-CN的數(shù)據(jù)采用Q(1,0,10)的量化方案。校驗節(jié)點計算模塊CN的中間數(shù)據(jù)以及輸出數(shù)據(jù)均采用Q(1,3,7)的量化方案。最后LSA模塊的輸入量化方案為Q(1,4,10),輸出數(shù)據(jù)量化方案為Q(1,0,14)。

表1 ADMM-LSA各個模塊量化方案

3 實驗結(jié)果

為了能夠驗證譯碼器的譯碼性能,在 FPGA 平臺中搭建了完整的測試平臺。本文的ADMM-LP譯碼器采用改進后的ADMM-LP譯碼算法,投影算法采用基于中心對稱的LSA 算法,信道選取AWGN(additive white gaussian noise)信道,并采用BPSK調(diào)制。實驗平臺為Xilinx 公司的型號為ZCU102評估板。軟件則采用Xilinx 公司的Vivado、Vivado HLS等工具。實驗使用HLS生成測試碼流的IP,其他部分使用Vivado進行開發(fā)。測試平臺上的測試過程如圖6所示。

如圖6所示,數(shù)據(jù)c經(jīng)過BPSK(binary phase shift keying)調(diào)制,然后經(jīng)過高斯白噪聲并求出對數(shù)似然比,經(jīng)過雙緩存后,ADMM-LP譯碼器對γ進行譯碼,譯碼結(jié)果x經(jīng)過校驗?zāi)K與數(shù)據(jù)c進行對比校驗,若譯碼失敗,則統(tǒng)計錯誤碼字個數(shù),最后求得誤碼率。

譯碼器整個流程可以簡單地用圖7所示狀態(tài)機進行調(diào)度。ADMM-LP譯碼器的狀態(tài)機主要設(shè)計了4種狀態(tài)來完成調(diào)度,數(shù)據(jù)載入完成后進行變量節(jié)點的計算,在變量節(jié)點計算完畢后進入校驗節(jié)點計算的狀態(tài),然后進行判決和信息的來回迭代,直到滿足譯碼成功條件或達到最大迭代次數(shù)之后,進入狀態(tài)3,譯碼完成。

圖8展示了ADMM-LP譯碼器的時序仿真圖。其中最大錯誤幀ERROR_FRAME_MAX設(shè)置為100,信噪比(signal noise ratio,SNR)設(shè)置為3 db,最大迭代次數(shù)MAX_ITER設(shè)置為64,狀態(tài)機decoderState包含4種狀態(tài),狀態(tài)0表示載入數(shù)據(jù),狀態(tài)1表示變量節(jié)點的計算,狀態(tài)2表示校驗節(jié)點的計算,狀態(tài)3表示譯碼完成狀態(tài)。如圖8所示,狀態(tài)機在數(shù)據(jù)載入后,在狀態(tài)1和狀態(tài)2之間反復(fù)迭代計算。即消息在變量節(jié)點和校驗節(jié)點之間來回迭代計算,直到譯碼通過或迭代次數(shù)達到最大值,狀態(tài)機進入狀態(tài)3譯碼完成。若未成功譯出該幀數(shù)據(jù),則錯誤幀error_frame_cnt數(shù)值加1,直到達到最大錯誤幀100,完成數(shù)據(jù)統(tǒng)計,求出在該信噪比下,該碼字的誤碼率。

圖6 ADMM-LP譯碼器測試平臺Fig.6 Test platform for ADMM-LP decoder

圖7 ADMM-LP譯碼器狀態(tài)機Fig.7 State machine of ADMM-LP decoder

圖8 ADMM-LP譯碼器時序仿真圖Fig.8 Timing simulation diagram of ADMM-LP decoder

譯碼器的整體時序仿真后,在硬件平臺上進行譯碼器的性能測試。針對在不同信噪比下,迭代次數(shù)對譯碼性能的影響情況,進行了相關(guān)實驗對此進行驗證。

圖9 不同迭代次數(shù)的誤碼率Fig.9 Frame error rate for different iterations

圖9展示了在不同迭代次數(shù)下,各信噪比的誤碼率,由實驗數(shù)據(jù)可以得出,迭代次數(shù)的增加,使得各信噪比下的誤碼率不斷降低,但在迭代次數(shù)為64以后,迭代次數(shù)對譯碼性能影響很小,誤碼率不再明顯降低。因此,將選取64次迭代來達到資源與性能的最佳平衡。

圖10 ADMM-LSA譯碼器與ADMM-CSA譯碼器譯碼性能對比Fig.10 Comparison of decoding performance between ADMM-LSA decoder and ADMM-CSA decoder

圖10展示了在硬件平臺FPGA以及軟件平臺下的譯碼器性能比較,并將本文提出的ADMM-LSA譯碼器性能與Wasson等[11]提出的ADMM-CSA譯碼器進行比較。從圖10中可以看出,在相同定點量化位寬條件下,本次實驗的ADMM-LSA譯碼器在硬件平臺與軟件平臺的譯碼性能基本一致,且與ADMM-CSA譯碼器性能相差無幾。但本文實現(xiàn)的ADMM-LSA譯碼器的譯碼效率更高,且在譯碼器資源占用方面,有較大提高。

表2展示了本文提出的ADMM-LSA譯碼器與已有的ADMM-CSA譯碼器的譯碼效率以及資源消耗情況。

表2 ADMM-LP譯碼器資源占用情況對比

從計算效率情況來看,在250 M時鐘下,相較于ADMM-CSA譯碼器,本文提出的ADMM-LSA譯碼器,無論變量節(jié)點模塊還是校驗節(jié)點模塊的計算效率都有所提升,但由于本文所提出的改進投影算法計算復(fù)雜度大大降低,校驗節(jié)點模塊的計算效率提高顯著,資源占用情況大幅下降。整體而言,本文提出的譯碼器譯碼速率相較已有方法的4.7 Mbps提升至6.14 Mbps,提升了30%以上。而查找表(LUT)資源占用量由13 262降為7 914,觸發(fā)器(FF)資源占用量由30 178降為9 748,而DSP資源由11降為5。

4 結(jié)論

在ADMM-LSA算法的基礎(chǔ)上,進行了一系列算法優(yōu)化,使其利于在硬件平臺上實現(xiàn),并給出了對應(yīng)的硬件實現(xiàn)方案,在FPGA上成功搭建實驗平臺。實驗結(jié)果表明:相較于ADMM-CSA譯碼器,本實驗所實現(xiàn)的ADMM-LSA譯碼器在譯碼性能上與之相當,但在譯碼效率與資源消耗上改善顯著。具體地,譯碼速率提升了約30.6%,LUT資源占用減少了40.3%,FF資源占用減少了約67.6%,DSP資源占用減少了約54.5%。