LDPC譯碼器中SISO模塊的高層次綜合實(shí)現(xiàn)

段倩妮++吳迪

摘要：日益增長(zhǎng)的硬件設(shè)計(jì)復(fù)雜度和越來越短的芯片研發(fā)周期給集成電路設(shè)計(jì)帶來了極大的挑戰(zhàn)。通過更高抽象層實(shí)現(xiàn)硬件設(shè)計(jì)自動(dòng)化的方法是解決問題的關(guān)鍵。 VivadoTM High-Level Synthesis（HLS）是Xilinx公司發(fā)布的高層次綜合工具。針對(duì)信道編解碼LDPC譯碼器芯片的核心模塊—軟輸入軟輸出（Soft-Input Soft-Output， SISO）模塊，采用HLS設(shè)計(jì)方法進(jìn)行了基于C語言模型的實(shí)現(xiàn)。HLS的綜合結(jié)果能與手工使用Verilog實(shí)現(xiàn)的性能接近，但明顯縮短了設(shè)計(jì)時(shí)間。

關(guān)鍵詞：High-Level Synthesis； SISO； Log-Map； IEEE 802.11ac； LDPC

中圖分類號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）17-0183-04

Implementation of SISO Module in LDPC Decoder with High-Level Synthesis Tool

DUAN Qian-ni1，WU Di2

（1. Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China；2. Soochow University， Suzhou 215006， China）

Abstract：The increasing complexity of hardware and decreasing time of development brings challenges to integrated circuit design. High-level synthesis-based design automation is the key to solve the problem. VivadoTM High-Level Synthesis is a high-level synthesis tool from Xilinx Inc. Targeting the Soft-Input Soft-Output （SISO） module which is the core unit of LDPC decoder， HLS methodology is applied by programming the SISO module in C. The synthesis result shows that HLS based design achieves similar hardware efficiency as compared to the manually coded design using Verilog， while significantly reducing the design effort.

Key words：High-Level Synthesis； SISO； Log-Map； IEEE 802.11ac； LDPC

1 概述

低密度奇偶校驗(yàn)Low Density Parity Check（LDPC）碼最早于1962年由R.Gallager第一次提出[1]，是一類校驗(yàn)矩陣為稀疏矩陣的線性分組碼，在1996年被再次發(fā)現(xiàn)[2]。非規(guī)則LDPC碼的構(gòu)造使得數(shù)據(jù)傳輸速率能夠接近香農(nóng)容限，無線通信標(biāo)準(zhǔn)如DVB-T2，WLAN（802.11n，802.11ac）都考慮了LDPC碼的使用。

由于LDPC譯碼器的高處理要求，通常用硬件來實(shí)現(xiàn)。在軟件無線電系統(tǒng)中，可編程邏輯陣列（FPGA）的靈活性和高處理能力使得LDPC譯碼器的硬件設(shè)計(jì)成為可能[3-5]?；赗TL級(jí)的HDL設(shè)計(jì)是目前最為廣泛的數(shù)字電路實(shí)現(xiàn)方法。但是，隨著時(shí)間的推移，各類產(chǎn)品應(yīng)用中使用的信號(hào)處理算法比以往更加復(fù)雜，傳統(tǒng)基于RTL設(shè)計(jì)FPGA的實(shí)現(xiàn)需要更多的時(shí)間來分析設(shè)計(jì)，迭代仿真和優(yōu)化性能。為了擺脫這個(gè)困境，Xilinx公司發(fā)布了VivadoTM HLS工具，可由高層次抽象層（如C語言）直接綜合出硬件設(shè)計(jì)。因此，設(shè)計(jì)者可將關(guān)注點(diǎn)集中在抽象層而不是執(zhí)行細(xì)節(jié)。設(shè)計(jì)者只需在抽象層驗(yàn)證函數(shù)功能的正確性即可，驗(yàn)證的速度將比基于HDL的設(shè)計(jì)流程快得多。再加之LDPC譯碼器的很多設(shè)計(jì)架構(gòu)在抽象層次上就具有很高的并行性[6]，很容易通過約束條件來實(shí)現(xiàn)高性能的硬件。更高的設(shè)計(jì)層次帶來更大的設(shè)計(jì)空間，也增加了尋找到最佳設(shè)計(jì)的可能性。

本文將展示如何通過Xilinx VivadoTM HLS工具實(shí)現(xiàn)LDPC譯碼器中用于更新校驗(yàn)節(jié)點(diǎn)的SISO模塊。首先，根據(jù)算法所采用的架構(gòu)寫成C代碼；其次，利用Xilinx VivadoTM HLS工具對(duì)C代碼進(jìn)行綜合，實(shí)現(xiàn)SISO模塊；最后驗(yàn)證了SISO的性能是否滿足設(shè)計(jì)需求。

2 VivadoTM HLS的開發(fā)流程

圖1是VivadoTM HLS工具的設(shè)計(jì)流程。設(shè)計(jì)的輸入是C、C++或者SystermC代碼，約束條件和Test Bench。

1）C、C++或者Systerm C代碼。C代碼根據(jù)算法的硬件架構(gòu)來實(shí)現(xiàn)，并完成算法應(yīng)有的功能。

2）約束條件。添加的約束條件用來指導(dǎo)C代碼綜合的流程，循環(huán)、接口、數(shù)組都可以添加約束條件，設(shè)計(jì)者通過優(yōu)化C代碼和添加適當(dāng)?shù)募s束條件來獲得最大吞吐率。

3）Test Bench。Test Bench用來在綜合前驗(yàn)證C代碼功能的正確性，并可以在之后的C/RTL聯(lián)合仿真時(shí)比對(duì)RTL的輸出結(jié)果。

VivadoTM HLS的輸出結(jié)果是可綜合的Verilog、VHDL或SystemC代碼，可以在FPGA硬件上執(zhí)行[7]。

以下是設(shè)計(jì)的流程。

1）在使用VivadoTM HLS工具進(jìn)行設(shè)計(jì)前，首先應(yīng)該對(duì)算法實(shí)現(xiàn)的硬件架構(gòu)有初步的框架，根據(jù)這個(gè)架構(gòu)來寫出實(shí)現(xiàn)算法功能的C代碼。再編譯、執(zhí)行和調(diào)試C代碼，并驗(yàn)證代碼功能的正確性。

2）根據(jù)實(shí)現(xiàn)需求添加適當(dāng)?shù)募s束條件，綜合C代碼生成相應(yīng)的RTL設(shè)計(jì)，同時(shí)產(chǎn)生綜合報(bào)告和設(shè)計(jì)分析。分析生成的報(bào)告是否符合要求，如果不符合要求，繼續(xù)優(yōu)化C代碼并修改約束條件。

3）C/RTL聯(lián)合仿真，利用Test Bench來驗(yàn)證RTL實(shí)現(xiàn)的正確性。

4）如果需要，可以將實(shí)現(xiàn)的RTL設(shè)計(jì)封裝成IP核。

在高層次具有較高并行度的算法用VivadoTM HLS軟件實(shí)現(xiàn)，容易通過添加適當(dāng)?shù)募s束條件，綜合出高效的處理流水線。

3 SISO模塊的Log-Map算法

在LDPC譯碼器的分層迭代譯碼算法中，復(fù)雜度最高的是更新校驗(yàn)節(jié)點(diǎn)信息[Λ（xi）]的計(jì)算，文獻(xiàn)[8]提出了一種代替雙邊圖來表示LDPC碼的方法，來簡(jiǎn)化[Λ（xi）]的計(jì)算過程。

一個(gè)LDPC碼完整的網(wǎng)格結(jié)構(gòu)非常大，會(huì)使得和—積算法難以實(shí)現(xiàn)。然而，一個(gè)[M×N]的LDPC碼可以看成[M]個(gè)并行級(jí)聯(lián)的單校驗(yàn)碼，每個(gè)單校驗(yàn)碼對(duì)應(yīng)一個(gè)校驗(yàn)節(jié)點(diǎn)。如圖2所示，一個(gè)單校驗(yàn)碼可以表示成兩個(gè)狀態(tài)的有限長(zhǎng)卷積碼。每一個(gè)單校驗(yàn)碼都可以通過Log-Map的算法來譯碼，即更新校驗(yàn)節(jié)點(diǎn)信息[Λ（xi）]的計(jì)算可以利用Log-Map算法。

Log-MAP的譯碼算法同樣也在文獻(xiàn)[9]中提出。具體內(nèi)容如下考慮到[H]矩陣第[j]行有[n]個(gè)1，位置為{[j1，j2，???，jn]}，則對(duì)應(yīng)的碼字[x]中的{[xj1，xj2，....，xjn]}滿足校驗(yàn)矩陣每行的偶校驗(yàn)約束，如果是[LLR]值，我們使用一種boxplus（）的操作來表示校驗(yàn)節(jié)點(diǎn)[xi]收到變量節(jié)點(diǎn)的更新信息

IEEE 802.11ac中LDPC碼是準(zhǔn)循環(huán)碼（QC-LDPC），協(xié)議中定義了三種碼長(zhǎng)（648、1296、1944）和四種碼率（1/2、2/3、3/4、5/6），總共12個(gè)矩陣。觀察協(xié)議中的矩陣發(fā)現(xiàn)，矩陣每一行中1的個(gè)數(shù)最多為8個(gè)[11]。為了支持IEEE 802.11ac，輸入數(shù)組[γ]和存儲(chǔ)[γ]的數(shù)組[γ_stack]設(shè)為最大值8。因?yàn)樵谟蒀代碼綜合的過程中需要分配硬件資源，如果寫成動(dòng)態(tài)的參數(shù)，則綜合不出結(jié)果，所以在數(shù)組定義時(shí)大小需設(shè)置具體的數(shù)值。根據(jù)算法，數(shù)組[α]、數(shù)組[β]、數(shù)組[α_temp]的最大長(zhǎng)度為7。

兩個(gè)循環(huán)的內(nèi)部主要執(zhí)行的都是條件分支。條件分支可以在并行中以分離的路徑來執(zhí)行，允許數(shù)據(jù)從一個(gè)任務(wù)流進(jìn)里面有狀態(tài)執(zhí)行的下一個(gè)任務(wù)，導(dǎo)致系統(tǒng)有更高的性能。

下面是SISO主體部分的偽代碼。

γ_stack、α_stack

LOOP1：

for k=0 to iter do

if k

γ_stack[k] ← γ[k]

end if

if k==0 then

α[0] ← γ[0]

α_stack[0] ← α[0]

end if

if 0

α[k] DFU（α[k-1]，γ[k]）

α_stack[k] ← α[k]

end if

if k==iter-1 then

Λ[indexlast] ← α[k]

end if

end for

LOOP2：

for k=iter to iter2 then

if k==iter then

β[indexlast] ← γ[k]

end if

if iter

β[index] ← DFU（γ_temp[index+1]，β[index+1]）

end if

if iter

Λ[index] ←DFU（α_temp[index-1]，β[index-1]）

end if

if k==iter2-1 then

Λ[0] β[0]

end if

end for

實(shí)現(xiàn)算法之后的C代碼經(jīng)過調(diào)試和仿真，如果功能正確將顯示：

4.3 約束條件

在SISO模塊中，當(dāng)最大值為8時(shí)，LOOP1執(zhí)行次數(shù)為7次，LOOP2執(zhí)行次數(shù)也為7次，每次根據(jù)判斷條件來執(zhí)行相應(yīng)的操作。根據(jù)偽代碼，LOOP1本身沒有并行性，因?yàn)閇α]一次迭代的計(jì)算需要用到上一個(gè)迭代的值。但是LOOP1和LOOP2之間，一旦[α]的最后一個(gè)值有效就可以輸出給[Λ]，并同時(shí)開始[β]和后續(xù)[Λ]值的計(jì)算。根據(jù)偽代碼，[β、Λ]的值可以并行計(jì)算。因此對(duì)兩個(gè)循環(huán)分別添加約束條件UNROLL，能使數(shù)據(jù)一有效就被執(zhí)行使用，并可以并行執(zhí)行循環(huán)內(nèi)的操作。這個(gè)約束條件大大增加了吞吐率。

VivadoTM HLS工具在綜合C代碼時(shí)，有時(shí)會(huì)犧牲資源來?yè)Q取算法并行度的增加，因而浪費(fèi)了部分資源并增加了硬件延遲。根據(jù)偽代碼，總共有3個(gè)DFU的函數(shù)調(diào)用，分別用來計(jì)算[α、β、Λ]的值。因此整個(gè)設(shè)計(jì)就只需要給[α、β、Λ]分別實(shí)例一個(gè)DFU。為了將資源的利用控制在一定的范圍內(nèi)，對(duì)SISO主函數(shù)添加約束條件ALLOCATION，規(guī)定設(shè)計(jì)中只有3個(gè)DFU函數(shù)的實(shí)例。

根據(jù)偽代碼，輸入?yún)?shù)是數(shù)組形式。在VivadoTM HLS中默認(rèn)將數(shù)組參數(shù)綜合成ap_memory類型的接口。這是一個(gè)標(biāo)準(zhǔn)塊RAM接口，一般只使用雙端口中的一個(gè)接口。根據(jù)SISO模塊的硬件設(shè)計(jì)，外部連接的塊RAM只需要使用單接口。為了防止VivadoTM HLS工具在綜合C代碼時(shí)增加并行度而使用雙端口。對(duì)SISO主函數(shù)添加約束條件RESOURCE，規(guī)定數(shù)組使用的是一個(gè)單接口的塊RAM。

對(duì)字長(zhǎng)的優(yōu)化能進(jìn)一步提高設(shè)計(jì)的性能。根據(jù)SISO的設(shè)計(jì)要求，字長(zhǎng)設(shè)定為8bit定點(diǎn)數(shù)。C代碼的數(shù)據(jù)類型只支持8的整數(shù)倍字長(zhǎng)，可RTL的總線支持任意字長(zhǎng)。VivadoTM HLS中提供了一種支持任意精度字長(zhǎng)的規(guī)范，可以在C代碼的設(shè)計(jì)中使用盡可能小的位寬來減少硬件資源，但實(shí)現(xiàn)同樣的功能。將數(shù)據(jù)設(shè)置為8bit定點(diǎn)數(shù)（7bit整數(shù)和1bit小數(shù)）比浮點(diǎn)數(shù)利用更少的資源。

下面是本次設(shè)計(jì)的字長(zhǎng)配置。

4.4 C/RTL聯(lián)合仿真

添加好約束條件后可以對(duì)C代碼進(jìn)行綜合，根據(jù)綜合后的結(jié)果和期望的要求進(jìn)行迭代優(yōu)化，最終實(shí)現(xiàn)最后的RTL設(shè)計(jì)。

為了驗(yàn)證RTL設(shè)計(jì)的正確性，綜合完成后，利用VivadoTM HLS提供的C/RTL聯(lián)合仿真功能，在選擇Verilog進(jìn)行仿真的情況下，HLS工具利用Test Bench給RTL代碼提供激勵(lì)，并將RTL的輸出結(jié)果與正確結(jié)果進(jìn)行比對(duì)，如果正確，顯示如下。說明RTL的輸出結(jié)果正確，SISO模塊的延遲為16個(gè)時(shí)鐘周期。

5 結(jié)果與性能

通過上述C代碼綜合出的硬件，當(dāng)設(shè)為最大值8時(shí)，SISO的延遲是16個(gè)時(shí)鐘周期，如果連續(xù)進(jìn)數(shù)，之后每8個(gè)時(shí)鐘周期計(jì)算輸出8個(gè)數(shù)。產(chǎn)生的設(shè)計(jì)文件是基于FPGA器件xc7z020clg484-1。仿真結(jié)果最小時(shí)鐘周期為10.65ns，也就是頻率為93MHz，VivadoTM HLS生成的SISO模塊資源利用情況如圖5所示，共使用了129個(gè)寄存器，484個(gè)LUT。

文獻(xiàn)[2]中更新校驗(yàn)節(jié)點(diǎn)的模塊穩(wěn)定工作在100MHz時(shí)，如果連續(xù)進(jìn)數(shù)，更新12個(gè)數(shù)據(jù)需要12個(gè)cycle。與本文的設(shè)計(jì)一樣，都平均一個(gè)時(shí)間周期計(jì)算輸出一個(gè)數(shù)，只是本次設(shè)計(jì)的頻率略低于文獻(xiàn)[2]，但是本次設(shè)計(jì)直接通過C代碼綜合成硬件設(shè)計(jì)，周期短，開發(fā)簡(jiǎn)單，說明利用VivadoTM HLS軟件進(jìn)行硬件設(shè)計(jì)開發(fā)是可行的。

浮點(diǎn)和定點(diǎn)的LDPC譯碼器性能如圖6所示。其中，LDPC譯碼器使用了Log-Map算法來更新校驗(yàn)節(jié)點(diǎn)信息?？梢钥闯鲈?0～20dB范圍內(nèi)，浮點(diǎn)和定點(diǎn)的性能是差不多的，只有當(dāng)信噪比更高的情況下定點(diǎn)才比浮點(diǎn)差一些。

6 結(jié)論

本文采用Xilinx VivadoTM HLS設(shè)計(jì)方法完成了LDPC譯碼器中SISO模塊設(shè)計(jì)。生成的硬件結(jié)構(gòu)性能與手工Verilog完成的設(shè)計(jì)性能接近，但基于C語言的HLS設(shè)計(jì)和手工RTL設(shè)計(jì)相比，顯著縮短了開發(fā)周期，減少了設(shè)計(jì)的復(fù)雜度。證明了具有較高復(fù)雜度的數(shù)字電路是可以通過HLS來進(jìn)行高效實(shí)現(xiàn)的[12]。

參考文獻(xiàn)：

[1] R. G. Gallager. Low Density Parity Check Code [M]. America： M.I.T. Press， 1963.

[2] 江濤. QC-LDPC碼設(shè)計(jì)和分層譯碼器的FPGA實(shí)現(xiàn)[D]. 南京：南京航空航天大學(xué)，2011.

[3] 張玉凱. 準(zhǔn)循環(huán)LDPC碼的編譯碼器設(shè)計(jì)及FPGA 實(shí)現(xiàn)[D]. 西安：西安電子科技大學(xué)，2009.

[4] 徐歡，雷菁，文磊. 準(zhǔn)循環(huán)LDPC碼低存儲(chǔ)量譯碼器設(shè)計(jì)與實(shí)現(xiàn)[J]. 重慶郵電大學(xué)學(xué)報(bào)，2010.22（6）： 771-774.

[5] 雷瑾亮，陳洪美，王愛華. 基于FPGA的準(zhǔn)循環(huán)LDPC碼低時(shí)延譯碼器設(shè)計(jì)[J]. 北京理工大學(xué)學(xué)報(bào)， 2013， 33（7）： 732-735.

[6] 姚遠(yuǎn)，葉凡，任俊彥. 采用并行分層譯碼的LDPC譯碼器設(shè)計(jì)研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2012， 48（4）：57-60.

[7] Xilinx. Vivado Design Suite User Guide High-Level Synthesis[Z]. 2014.

[8] Yang Sun， Joseph R. Cavallaro. Unified Decoder Architecture for LDPC/Turbo Codes[J]. Signal Processing Systems.2008， 13-18.

[9] Miquel Esteve Martin. Design of a Configurable LDPC Decoder for High-speed Wireless[D]. Spain： Universitat Politècnica de Catalunya， 2012.

[10] Xiao-Yu Hu， Evangelos Eleftheriou， Dieter-Michael Arnold， Ajay Dholakia. Efficient implementations of the SPA for decoding LDPC Codes[J]. IBM Research， Zurich Research Laboratory/IEEE GLOBECOM， 2001. 2：1036-1036E

[11] IEEE P802.11acTM/D4.0， Draft STANDARD for

Information Technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements

Part 11： Wireless LAN Medium Access Control

（MAC） and Physical Layer （PHY） specifications[S]， 2012.

[12] Peyic M， Baba H， Guleyuboglu E， et al. A low power multi-rate decoder hardware for IEEE 802.11n LDPC codes[J]. Microprocessors and Microsystems， 2012，36（3）：159-166