楊偉 李慧 張鵬 韓星

摘要：針對(duì)低密度奇偶校驗(yàn)碼（Low Density Parity Check Code，LDPC）碼長長、碼率多、校驗(yàn)矩陣復(fù)雜，導(dǎo)致 FPGA 開發(fā)難度大、開發(fā)周期長等問題。在對(duì) LDPC 校驗(yàn)矩陣和譯碼算法深入分析基礎(chǔ)上，提出了一種基于 HLS 的 LDPC 設(shè)計(jì)與實(shí)現(xiàn)方案?；?HLS 開發(fā)流程完成了 LDPC 譯碼的 RTL 實(shí)現(xiàn)，詳細(xì)說明了開發(fā)過程的關(guān)鍵問題及優(yōu)化辦法。與常規(guī) HDL 開發(fā)流程相比，基于 HLS 開發(fā)的 LDPC 譯碼吞吐率更高，時(shí)序更好，且便于后期移植和升級(jí)。

關(guān)鍵詞：LDPC;譯碼算法;FPGA;HLS

中圖分類號(hào)：TN911 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1008-1739（2021）13-66-4

Design and Implementation of LDPC Decoder Based on HLS

YANG Wei1， LI Hui2， ZHANG Peng1， HAN Xing1

（1.Hebei Key Laboratory of Electromagnetic Spectrum Cognition and Control， Shijiazhuang 050081， China;2. Unit 75775， PLA， Kunming 650000， China）

Abstract： Aiming at the problem of long code length， different code rate and complex check matrix of low density parity check code（LDPC） codes， which lead to the difficulty of FPGA development and long development cycle， a LDPC design and implementationscheme based on HLS is proposed based on the in-depth analysis of LDPC check matrix and decoding algorithm. Based on the HLSdevelopment process， the RTL implementation of LDPC decoder is completed， and the key problems and optimization methods in thedevelopment process are described in detail. Compared with the conventional HDL development process， the LDPC decoder based onHLS has higher throughput， higher timing， and is convenient for later transplantation and upgrade.

Keywords：LDPC; decoding algorithm; FPGA; HLS

0 引言

低密度奇偶校驗(yàn)碼（Low Density Parity Check Code，LDPC）由 Gallager 博士于 1962 年首次提出[1]，LDPC 碼具有接近香農(nóng)極限的譯碼性能，而且譯碼復(fù)雜度低，適合并行處理。經(jīng)過近幾十年發(fā)展，LDPC 碼已廣泛應(yīng)用于衛(wèi)星傳輸、深空通信及數(shù)據(jù)存儲(chǔ)等領(lǐng)域。第 2 代數(shù)字視頻廣播（DVB-S2）標(biāo)準(zhǔn)采用 BCH 碼與 LDPC 碼級(jí)聯(lián)的前向糾錯(cuò)（FEC）方式，其性能接近理論極限[2]，支持 64800 和 16200 兩種碼長以及多達(dá) 11 種碼率[3]。由于 LDPC 碼碼長較長、碼率較多，F(xiàn)PGA 開發(fā)過程較為復(fù)雜。

與傳統(tǒng)處理器相比，基于并行結(jié)構(gòu)的 FPGA 在性能、成本、靈活性和功耗等方面有較大優(yōu)勢，因此在通信、電子及數(shù)據(jù)處理等領(lǐng)域得到廣泛應(yīng)用[4]。但是隨著算法復(fù)雜度不斷提高，F(xiàn)PGA 器件不斷升級(jí)，基于 HDL 輸入的常規(guī)開發(fā)方法開始面臨開發(fā)難度大、開發(fā)周期長等問題。針對(duì)這個(gè)問題，Xilinx 公司推出了新一代的開發(fā)工具：高層次綜合（High-Level Synthesis，HLS）。HLS 允許開發(fā)者直接使用 C/C++/System C 進(jìn)行設(shè)計(jì)建模，并自動(dòng)將其轉(zhuǎn)換成 RTL 級(jí)的實(shí)現(xiàn)[5]。HLS 使開發(fā)者有更多精力進(jìn)行系統(tǒng)級(jí)設(shè)計(jì)，不必關(guān)注具體時(shí)序細(xì)節(jié)，從而極大提高設(shè)計(jì)效率。

針對(duì) LDPC 碼譯碼過程時(shí)序復(fù)雜、開發(fā)周期長等問題，基于 HLS 開發(fā)工具進(jìn)行了 LDPC 碼的譯碼設(shè)計(jì)與實(shí)現(xiàn)。HLS 能夠自動(dòng)實(shí)現(xiàn)底層的時(shí)序設(shè)計(jì)、資源綁定及指標(biāo)分析等功能。與常規(guī)開發(fā)流程相比，減小了開發(fā)難度，提高了設(shè)計(jì)效率。

1 LDPC 譯碼算法

1.1 校驗(yàn)矩陣分析

由 DVB-S2 標(biāo)準(zhǔn)可知，LDPC 碼支持 1/4，1/3，2/5，1/2，3/5，2/3，3/4，4/5，5/6，8/9，9/10 共 11 種碼率，64800 和 16200 兩種碼長[6]。

LDPC 碼是非規(guī)則累積碼[7]，校驗(yàn)矩陣可表示為，其中，是m×k的稀疏矩陣，m是校驗(yàn)比特個(gè)數(shù)，k是信息比特個(gè)數(shù)。是滿秩矩陣[8]，如下：

。（1）

矩陣的行重和列重具有一定規(guī)律。矩陣可表示成如下形式[8]：

，（2）

式中，均為q×k的子矩陣，q的取值和碼長及碼率有關(guān)。每個(gè)子矩陣又可分成如下形式：

（3）

式中，均為q×360 的子矩陣，它們分別向右循環(huán)移 1 位，可得到即可得到，以此類推。利用矩陣的周期規(guī)律，可以在譯碼實(shí)現(xiàn)過程中，減少存儲(chǔ)資源。

1.2 LDPC 譯碼算法

LDPC 碼一般采用迭代譯碼，譯碼算法的基本思想是通過使概率信息在變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間來回傳遞，得到信息的獨(dú)立統(tǒng)計(jì)，從而找到正確的碼字。常用的有基于概率的 BP算法（Belief Propagation Algorithm）。基于對(duì)數(shù)域的 BP 算法，最小和算法以及歸一化最小和算法等[9]。考慮不同算法的譯碼性能和實(shí)現(xiàn)過程復(fù)雜度，本文采用歸一化最小和算法。

該譯碼算法的具體步驟為：

（1）初始化似然比信息

（4）

式中，（）表示接收端接收到的初始化似然比信息。

（2）迭代處理，包括校驗(yàn)節(jié)點(diǎn)信息更新和變量節(jié)點(diǎn)信息更新。對(duì)于第k次迭代，有校驗(yàn)節(jié)點(diǎn)信息更新：

，（5）

式中，表示校驗(yàn)節(jié)點(diǎn)j向變量節(jié)點(diǎn)i傳輸?shù)耐獠扛怕市畔?R（j）表示與校驗(yàn)節(jié)點(diǎn)相連的所有變量節(jié)點(diǎn)集合，R（j）＼i則表示除變量節(jié)點(diǎn)i之外所有與校驗(yàn)節(jié)點(diǎn)j相連的變量節(jié)點(diǎn)集合。

變量節(jié)點(diǎn)信息更新：

，（6）

式中，表示變量節(jié)點(diǎn)i向校驗(yàn)節(jié)點(diǎn)j傳輸?shù)乃迫槐刃畔ⅰ?/p>

（3）譯碼判決

計(jì)算所有變量節(jié)點(diǎn)的后驗(yàn)信息，并進(jìn)行判決，如式（7）所示：

，（7）

式中，C（i）表示與校驗(yàn)節(jié)點(diǎn)i相連的所有變量節(jié)點(diǎn)集合，C（i）＼j則表示除變量節(jié)點(diǎn)j之外所有與校驗(yàn)節(jié)點(diǎn)i相連的變量節(jié)點(diǎn)集合;表示比例因子，取值范圍表示 LDPC 譯碼后的碼字，H表示對(duì)應(yīng)的校驗(yàn)矩陣。若，則，否則。

經(jīng)過判決得到 LDPC 譯碼后的碼字，如果滿足或者達(dá)到設(shè)定的最大迭代次數(shù)，則輸出譯碼結(jié)果，結(jié)束譯碼。否則從步驟（2）繼續(xù)迭代處理。

2 HLS 功能及設(shè)計(jì)流程

HLS 可以實(shí)現(xiàn)直接使用 C/C++/System C 規(guī)范對(duì) FPGA 進(jìn)行編程，而無需手動(dòng)創(chuàng)建等效的 RTL 設(shè)計(jì)，從而加速設(shè)計(jì)開發(fā)[11]。相比傳統(tǒng)的開發(fā)過程，HLS 允許設(shè)計(jì)人員在 C 語言級(jí)進(jìn)行開發(fā)設(shè)計(jì)，從而大幅縮短開發(fā)和驗(yàn)證時(shí)間。設(shè)計(jì)人員可以通過不同的優(yōu)化指令控制 C 綜合過程，以探索最優(yōu)的 RTL 實(shí)現(xiàn)，同時(shí)基于 C 的源代碼容易移植和適配不同的器件。

在使用 HLS 工具之前，要首先理解 HLS 功能，設(shè)計(jì)流程以及開發(fā)過程的相關(guān)約束和限制。HLS 的主要功能包括[12：①從 C 源代碼中創(chuàng)建一個(gè) RTL 級(jí)實(shí)現(xiàn);②從 C 源代碼提取出控制信息和數(shù)據(jù)流;③基于默認(rèn)的和用戶定義的命令，實(shí)現(xiàn)設(shè)計(jì);④從相同源代碼描述中，探索實(shí)現(xiàn)更多的設(shè)計(jì)。

HLS 設(shè)計(jì)流程步驟如下：

①編譯、仿真和調(diào)試 C 語言算法;

②將 C 語言程序綜合為 RTL 實(shí)現(xiàn)，期間用戶可根據(jù)實(shí)際情況添加優(yōu)化指令;

③生成詳細(xì)報(bào)告并分析設(shè)計(jì);

④使用按鈕式流程驗(yàn)證 RTL 實(shí)現(xiàn);

⑤將 RTL 實(shí)現(xiàn)封裝為一套選定的 IP 格式。

需要說明的是，HLS 工具并不能處理所有代碼，對(duì)輸入程序有一定的限制：不支持使用動(dòng)態(tài)內(nèi)存分配;減少使用指針對(duì)指針的操作;不使用系統(tǒng)調(diào)用，否則在綜合時(shí)這些指令會(huì)被無視或直接刪掉;減少使用其他標(biāo)準(zhǔn)庫的內(nèi)容;減少使用 C++ 中的函數(shù)指針和虛擬函數(shù);不使用遞歸方程;精準(zhǔn)表達(dá)交互接口等。

3 LDPC 譯碼實(shí)現(xiàn)過程

3.1 譯碼器結(jié)構(gòu)框圖

結(jié)合譯碼算法流程、校驗(yàn)矩陣特點(diǎn)及 FPGA 并行實(shí)現(xiàn)原理，設(shè)計(jì)的譯碼器結(jié)構(gòu)如圖 1 所示。

由圖 1 可知，譯碼處理過程主要包括輸入似然比信息的緩存與重排、變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)的計(jì)算，以及中間計(jì)算結(jié)果的緩存以及譯碼判決輸出等。譯碼過程需要大量的計(jì)算和數(shù)據(jù)緩存。在后續(xù)的 HLS 開發(fā)過程中，以該結(jié)構(gòu)為依據(jù)進(jìn)行優(yōu)化與調(diào)整。

3.2 原有 C 算法程序的限制及處理方法

在使用 HLS 進(jìn)行開發(fā)時(shí)，首先需要對(duì)原有 C 算法程序進(jìn)行修改，主要有以下幾點(diǎn)：

①動(dòng)態(tài)分配內(nèi)存問題：利用固定長度的數(shù)組，只要保證數(shù)組長度滿足最大碼長的需求即可。

②浮點(diǎn)數(shù)問題：轉(zhuǎn)為定點(diǎn)數(shù)計(jì)算，HLS 支持定義任意位寬的變量，打破 C 語言中 short，int，long 等類型的限制。針對(duì)定點(diǎn)小數(shù)，還支持對(duì)截位和溢出的處理。

③頂層函數(shù)的接口問題：最終的 RTL 輸出會(huì)與其他 HDL代碼交互，因此頂層函數(shù)的接口定義也需要進(jìn)行修改。其中，數(shù)據(jù)的輸入和輸出采用 hls：：stream，對(duì)應(yīng) ap_fifo，綜合后為FIFO 接口;參數(shù)的輸入采用標(biāo)量數(shù)據(jù)默認(rèn)的 ap_none，直接輸入，沒有交互;其余的時(shí)鐘、復(fù)位、啟動(dòng)的控制為 HLS 默認(rèn)。

將 C 算法程序中的這些限制修改后，理論上該代碼就可以被綜合為 RTL 代碼，但實(shí)際上，還要根據(jù) HLS 和代碼的特性進(jìn)行優(yōu)化，否則綜合結(jié)果的 FPGA 資源占用和時(shí)序不可控。

3.3 數(shù)組的優(yōu)化

LDPC 的譯碼過程從以下 2 個(gè)方面開展數(shù)組優(yōu)化，提高并行處理能力。在 C 程序中，輸入的似然比信息存儲(chǔ)在一個(gè)數(shù)組中。HLS 會(huì)將數(shù)組映射為 BlockRAM，而 BlockRAM 最多有 2個(gè)讀接口，會(huì)限制程序的并行性。需添加 ARRAY_PARTITION指令，將一個(gè)數(shù)組拆分為多個(gè)小數(shù)組，增加讀寫接口、提升并行性。

在 C 程序中，需要多個(gè)數(shù)組存儲(chǔ)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)更新后的中間信息。這些數(shù)組讀寫地址相同，且讀寫同時(shí)，可以通過 ARRAY_MAP 指令將這些數(shù)組按照位寬進(jìn)行合并。如180 個(gè) 6 bit 位寬的數(shù)組，可以合并為 1 個(gè) 1 080 bit 位寬的數(shù)組，從而充分利用 FPGA 中的 36 bit 位寬的 BlockRAM，減少資源的使用。

3.4 流水線優(yōu)化

流水線設(shè)計(jì)通過將一個(gè)復(fù)雜的計(jì)算分解為多個(gè)簡單計(jì)算，通過流水處理的方式以提高吞吐率。如在校驗(yàn)節(jié)點(diǎn)更新過程中，需要依次執(zhí)行計(jì)算輸入數(shù)據(jù)的絕對(duì)值、最小值以及數(shù)據(jù)符號(hào)乘積 3 個(gè)步驟。通過 PIPELINE 參數(shù)，可以對(duì)該段代碼進(jìn)行流水線設(shè)置，流水優(yōu)化示意圖如圖 2 所示。

圖 2（a）和圖 2（b）分別為流水線優(yōu)化前后的處理時(shí)序。其中，圖中的數(shù)字 1，2，3 分別代表計(jì)算輸入數(shù)據(jù)的絕對(duì)值，最小值以及數(shù)據(jù)符號(hào)乘積 3 個(gè)步驟。前者需要 3 個(gè)時(shí)鐘才能輸入新的數(shù)據(jù)，而后者只需 1 個(gè)時(shí)鐘即可輸入新的數(shù)據(jù)，吞吐率提高了 3 倍。

在 C 程序中存在很多這樣的循環(huán)函數(shù)，如果將循環(huán)進(jìn)行流水處理，會(huì)增加部分邏輯資源，但大大提升循環(huán)的執(zhí)行效率，因?yàn)榇藭r(shí)無需等待本次循環(huán)執(zhí)行完成即可輸入下一次循環(huán)的數(shù)據(jù)進(jìn)行流水處理。

3.5 綜合結(jié)果分析與迭代優(yōu)化

C 綜合完成之后，HLS 會(huì)自動(dòng)生成對(duì)應(yīng)的時(shí)序和資源的報(bào)告，可在分析界面中查看。分析結(jié)果可以針對(duì)具體的函數(shù)或循環(huán)進(jìn)行查看，便于查找性能限制的節(jié)點(diǎn)。需要說明的是，HLS開發(fā)過程往往需要不斷對(duì)綜合結(jié)果分析，進(jìn)行多次參數(shù)及代碼的優(yōu)化，才能得到滿足要求的 RTL 實(shí)現(xiàn)。

經(jīng)過仿真與綜合，最終確定譯碼實(shí)現(xiàn)參數(shù)為：并行度 180;迭代次數(shù) 20;比例因子 =0.75;工作時(shí)鐘不低于 200 MHz;吞吐率不低于 200 Mb/s。

4 測試驗(yàn)證及總結(jié)

在進(jìn)行 C/RTL 聯(lián)合仿真驗(yàn)證后，可以將生成的 RTL 代碼添加至工程中，進(jìn)行功能與指標(biāo)的實(shí)際測試。測試流程包括PN 序列產(chǎn)生、LDPC 編碼、BPSK 調(diào)制、AWGN 信道、LDPC 譯碼、PN 序列驗(yàn)證及誤碼率統(tǒng)計(jì)等。測試流程如圖 3 所示。

經(jīng)過測試，在不同碼長及碼率參數(shù)下，LDPC 譯碼器均能正常譯碼，且譯碼性能滿足工程需求。圖 4 所示為幀長 64 800，碼率 2/3 時(shí)，測試得到的誤碼率曲線。

與已有的 FPGA 譯碼程序相比，基于 HLS 開發(fā)的 LDPC譯碼器工作時(shí)鐘更高，吞吐率更大，這是以增加了少量 LUT和 BlockRAM 資源為代價(jià)得到的。

HLS 以 C 程序作為設(shè)計(jì)輸入，加快了仿真和驗(yàn)證速度。在HLS 工具的支持下，F(xiàn)PGA 開發(fā)人員可以有更多精力關(guān)注系統(tǒng)級(jí)性能，而不必關(guān)心具體的時(shí)序設(shè)計(jì)。同時(shí)在面對(duì)目標(biāo)器件升級(jí)、校驗(yàn)矩陣更改、關(guān)注指標(biāo)側(cè)重不同等問題時(shí)，可以幫助開發(fā)人員更快地進(jìn)行修改、移植和驗(yàn)證，極大提升效率?；贖LS 的設(shè)計(jì)流程，需要設(shè)計(jì)人員對(duì) FPGA 的資源和時(shí)序等有一定了解，以保證最終 RTL 設(shè)計(jì)的可靠。

5 結(jié)束語

針對(duì) LDPC 碼長較長、碼率較多，導(dǎo)致 FPGA 開發(fā)難度大，開發(fā)周期長，不方便移植和升級(jí)等問題，在對(duì) LDPC 譯碼算法深入分析的基礎(chǔ)上，提出了基于 HLS 開發(fā)流程的 LDPC譯碼設(shè)計(jì)思路。對(duì) LDPC 譯碼功能指標(biāo)進(jìn)行了全面的驗(yàn)證測試，能夠滿足設(shè)計(jì)需求。同時(shí)，經(jīng)過對(duì)比，基于 HLS 的設(shè)計(jì)更加易于移植和升級(jí)，縮短開發(fā)周期、提高設(shè)計(jì)效率。

參考文獻(xiàn)

[1] GALLAGER R G. Low-density Parity-checks Codes [J].IEEETransactions on Information Theory，1962，1： 21-28.

[2] 李志勇，李文鐸.一種高速 LDPC 編譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].無線電工程，2009，39（7）：17-19，61.

[3] 王延鵬，潘申富，楊宏偉.基于 FPGA 的 DVB-S2 LDPC 編碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].無線電工程，2015，45（3）：30-33.

[4] 田耘，徐文波，張延偉.無線通信 FPGA 設(shè)計(jì)[M].北京：電子工業(yè)出版社，2009.

[5]黨宏社，王黎，王曉倩.基于 Vivado HLS 的 FPGA 開發(fā)與應(yīng)用研究[J].陜西科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，33（1）：155-159.

[6] ETSIEN 302 307 V1.3.1.Digital Video Broadcasting（ DVB）;Second Generation Framing Structure，Channel Coding andModulation Systems for Broadcasting，Interactive Services，News Gathering and Other Broadband Satellite Applications[S].2013.

[7] 江桂芳，彭克榮.基于 FPGA 的高速并行 DVB-S2 標(biāo)準(zhǔn)LDPC 譯碼[J].空間電子技術(shù)，2013，10（1）：58-61，95.

[8] 賀鶴云.LDPC 碼基礎(chǔ)與應(yīng)用[M].北京：人民郵電出版社，2009.

[9] 袁云云.DVB_S2 標(biāo)準(zhǔn)中多模級(jí)聯(lián)糾錯(cuò)碼研究及其高速FPGA 實(shí)現(xiàn)[D].西安：西安電子科技大學(xué)，2014.

[10] 袁東風(fēng)，張海剛.LDPC 碼理論與應(yīng)用[M].北京：人民郵電出版社，2008.

[11] 符曉，張國斌.朱洪順.Xilinx ZYNQ-7000 AP SoC 開發(fā)實(shí)戰(zhàn)指南[M].北京：清華大學(xué)出版社，2016.

[12] 何賓.Xilinx FPGA 設(shè)計(jì)權(quán)威指南：Vivado 集成設(shè)計(jì)環(huán)境[M].北京：清華大學(xué)出版社，2014.