基于線段投影的ADMM-LP譯碼算法硬件實現

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

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

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

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

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

1 改進的ADMM-LP譯碼算法

1.1 ADMM-LP譯碼算法

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

ADMM-LP譯碼的基本模型為

(1)

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

(2)

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

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

(3)

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

(4)

(5)

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

(6)

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

(7)

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

1.2 改進的ADMM-LP算法

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

(8)

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

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

1.3 簡化的LSA算法

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

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

算法2 簡化的中心對稱LSA算法輸入:待投影向量v′∈Rdj1:βv,i=1, v′i>00, v′i≤0{2:if 集合{i|βv,i=1}的元素個數為偶數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:偶數頂點:A=βv,i, 如果 i≠a1-βv,i, 如果 i=a{,偶數頂點:B=βv,i, 如果 i≠b1-βv,i, 如果 i=b{8:輸出:投影向量s=ΠAB(v′)9:return s

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

2 ADMM-LP譯碼算法的硬件實現

2.1 譯碼器總體框架

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

圖1 硬件結構框圖Fig.1 Block diagram of hardware structure

2.2 并行度設計

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

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

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

2.3 變量節點計算模塊

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

圖2 VN模塊硬件結構圖Fig.2 Hardware structure diagram of VN module

變量節點計算模塊經過Vivado HLS生成的模塊IP如圖3所示。

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

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

為了對裝配式建筑工程施工在進行招標評標時出現的各種問題加以解決，可以采取兩段式評標方法來對工程項目進行招標評標工作。實際操作時，在第一階段主要評審資質標和技術標，并以第一階段的評審結果為基礎確定具備進入商務標的第二階段評審的資格。同時可以根據招標方的實際需要，對兩個階段的評標得分權重進行適當的調整，并計算出最終的評標結果，確定中標單位。

2.4 校驗節點計算模塊

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

圖4 CN模塊硬件結構圖Fig.4 Hardware structure diagram of CN module

其中,投影模塊是校驗節點計算模塊中最復雜的算法模塊,也是本實驗實現過程的關鍵所在,將采用1.3節提出的算法2。

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

圖5 LSA模塊硬件結構圖Fig.5 Hardware structure diagram of LSA module

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

2.5 定點位寬設計

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

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

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

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

3 實驗結果

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

如圖6所示,數據c經過BPSK(binary phase shift keying)調制,然后經過高斯白噪聲并求出對數似然比,經過雙緩存后,ADMM-LP譯碼器對γ進行譯碼,譯碼結果x經過校驗模塊與數據c進行對比校驗,若譯碼失敗,則統計錯誤碼字個數,最后求得誤碼率。

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

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

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

圖7 ADMM-LP譯碼器狀態機Fig.7 State machine of ADMM-LP decoder

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

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

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

圖9展示了在不同迭代次數下,各信噪比的誤碼率,由實驗數據可以得出,迭代次數的增加,使得各信噪比下的誤碼率不斷降低,但在迭代次數為64以后,迭代次數對譯碼性能影響很小,誤碼率不再明顯降低。因此,將選取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譯碼器性能相差無幾。但本文實現的ADMM-LSA譯碼器的譯碼效率更高,且在譯碼器資源占用方面,有較大提高。

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

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

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

4 結論

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