基于 HLS 的 LDPC 譯碼設計與實現

楊偉 李慧 張鵬 韓星

摘要：針對低密度奇偶校驗碼（Low Density Parity Check Code，LDPC）碼長長、碼率多、校驗矩陣復雜，導致 FPGA 開發難度大、開發周期長等問題。在對 LDPC 校驗矩陣和譯碼算法深入分析基礎上，提出了一種基于 HLS 的 LDPC 設計與實現方案。基于 HLS 開發流程完成了 LDPC 譯碼的 RTL 實現，詳細說明了開發過程的關鍵問題及優化辦法。與常規 HDL 開發流程相比，基于 HLS 開發的 LDPC 譯碼吞吐率更高，時序更好，且便于后期移植和升級。

關鍵詞：LDPC;譯碼算法;FPGA;HLS

中圖分類號：TN911 文獻標志碼：A 文章編號：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 引言

低密度奇偶校驗碼（Low Density Parity Check Code，LDPC）由 Gallager 博士于 1962 年首次提出[1]，LDPC 碼具有接近香農極限的譯碼性能，而且譯碼復雜度低，適合并行處理。經過近幾十年發展，LDPC 碼已廣泛應用于衛星傳輸、深空通信及數據存儲等領域。第 2 代數字視頻廣播（DVB-S2）標準采用 BCH 碼與 LDPC 碼級聯的前向糾錯（FEC）方式，其性能接近理論極限[2]，支持 64800 和 16200 兩種碼長以及多達 11 種碼率[3]。由于 LDPC 碼碼長較長、碼率較多，FPGA 開發過程較為復雜。

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

針對 LDPC 碼譯碼過程時序復雜、開發周期長等問題，基于 HLS 開發工具進行了 LDPC 碼的譯碼設計與實現。HLS 能夠自動實現底層的時序設計、資源綁定及指標分析等功能。與常規開發流程相比，減小了開發難度，提高了設計效率。

1 LDPC 譯碼算法

1.1 校驗矩陣分析

由 DVB-S2 標準可知，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 碼是非規則累積碼[7]，校驗矩陣可表示為，其中，是m×k的稀疏矩陣，m是校驗比特個數，k是信息比特個數。是滿秩矩陣[8]，如下：

。（1）

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

，（2）

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

（3）

式中，均為q×360 的子矩陣，它們分別向右循環移 1 位，可得到即可得到，以此類推。利用矩陣的周期規律，可以在譯碼實現過程中，減少存儲資源。

1.2 LDPC 譯碼算法

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

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

（1）初始化似然比信息

（4）

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

（2）迭代處理，包括校驗節點信息更新和變量節點信息更新。對于第k次迭代，有校驗節點信息更新：

，（5）

式中，表示校驗節點j向變量節點i傳輸的外部概率信息;R（j）表示與校驗節點相連的所有變量節點集合，R（j）＼i則表示除變量節點i之外所有與校驗節點j相連的變量節點集合。

變量節點信息更新：

，（6）

式中，表示變量節點i向校驗節點j傳輸的似然比信息。

（3）譯碼判決

計算所有變量節點的后驗信息，并進行判決，如式（7）所示：

，（7）

式中，C（i）表示與校驗節點i相連的所有變量節點集合，C（i）＼j則表示除變量節點j之外所有與校驗節點i相連的變量節點集合;表示比例因子，取值范圍表示 LDPC 譯碼后的碼字，H表示對應的校驗矩陣。若，則，否則。

經過判決得到 LDPC 譯碼后的碼字，如果滿足或者達到設定的最大迭代次數，則輸出譯碼結果，結束譯碼。否則從步驟（2）繼續迭代處理。

2 HLS 功能及設計流程

HLS 可以實現直接使用 C/C++/System C 規范對 FPGA 進行編程，而無需手動創建等效的 RTL 設計，從而加速設計開發[11]。相比傳統的開發過程，HLS 允許設計人員在 C 語言級進行開發設計，從而大幅縮短開發和驗證時間。設計人員可以通過不同的優化指令控制 C 綜合過程，以探索最優的 RTL 實現，同時基于 C 的源代碼容易移植和適配不同的器件。

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

HLS 設計流程步驟如下：

①編譯、仿真和調試 C 語言算法;

②將 C 語言程序綜合為 RTL 實現，期間用戶可根據實際情況添加優化指令;

③生成詳細報告并分析設計;

④使用按鈕式流程驗證 RTL 實現;

⑤將 RTL 實現封裝為一套選定的 IP 格式。

需要說明的是，HLS 工具并不能處理所有代碼，對輸入程序有一定的限制：不支持使用動態內存分配;減少使用指針對指針的操作;不使用系統調用，否則在綜合時這些指令會被無視或直接刪掉;減少使用其他標準庫的內容;減少使用 C++ 中的函數指針和虛擬函數;不使用遞歸方程;精準表達交互接口等。

3 LDPC 譯碼實現過程

3.1 譯碼器結構框圖

結合譯碼算法流程、校驗矩陣特點及 FPGA 并行實現原理，設計的譯碼器結構如圖 1 所示。

由圖 1 可知，譯碼處理過程主要包括輸入似然比信息的緩存與重排、變量節點與校驗節點的計算，以及中間計算結果的緩存以及譯碼判決輸出等。譯碼過程需要大量的計算和數據緩存。在后續的 HLS 開發過程中，以該結構為依據進行優化與調整。

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

在使用 HLS 進行開發時，首先需要對原有 C 算法程序進行修改，主要有以下幾點：

①動態分配內存問題：利用固定長度的數組，只要保證數組長度滿足最大碼長的需求即可。

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

③頂層函數的接口問題：最終的 RTL 輸出會與其他 HDL代碼交互，因此頂層函數的接口定義也需要進行修改。其中，數據的輸入和輸出采用 hls：：stream，對應 ap_fifo，綜合后為FIFO 接口;參數的輸入采用標量數據默認的 ap_none，直接輸入，沒有交互;其余的時鐘、復位、啟動的控制為 HLS 默認。

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

3.3 數組的優化

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

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

3.4 流水線優化

流水線設計通過將一個復雜的計算分解為多個簡單計算，通過流水處理的方式以提高吞吐率。如在校驗節點更新過程中，需要依次執行計算輸入數據的絕對值、最小值以及數據符號乘積 3 個步驟。通過 PIPELINE 參數，可以對該段代碼進行流水線設置，流水優化示意圖如圖 2 所示。

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

在 C 程序中存在很多這樣的循環函數，如果將循環進行流水處理，會增加部分邏輯資源，但大大提升循環的執行效率，因為此時無需等待本次循環執行完成即可輸入下一次循環的數據進行流水處理。

3.5 綜合結果分析與迭代優化

C 綜合完成之后，HLS 會自動生成對應的時序和資源的報告，可在分析界面中查看。分析結果可以針對具體的函數或循環進行查看，便于查找性能限制的節點。需要說明的是，HLS開發過程往往需要不斷對綜合結果分析，進行多次參數及代碼的優化，才能得到滿足要求的 RTL 實現。

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

4 測試驗證及總結

在進行 C/RTL 聯合仿真驗證后，可以將生成的 RTL 代碼添加至工程中，進行功能與指標的實際測試。測試流程包括PN 序列產生、LDPC 編碼、BPSK 調制、AWGN 信道、LDPC 譯碼、PN 序列驗證及誤碼率統計等。測試流程如圖 3 所示。

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

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

HLS 以 C 程序作為設計輸入，加快了仿真和驗證速度。在HLS 工具的支持下，FPGA 開發人員可以有更多精力關注系統級性能，而不必關心具體的時序設計。同時在面對目標器件升級、校驗矩陣更改、關注指標側重不同等問題時，可以幫助開發人員更快地進行修改、移植和驗證，極大提升效率。基于HLS 的設計流程，需要設計人員對 FPGA 的資源和時序等有一定了解，以保證最終 RTL 設計的可靠。

5 結束語

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

參考文獻

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

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

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

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

[5]黨宏社，王黎，王曉倩.基于 Vivado HLS 的 FPGA 開發與應用研究[J].陜西科技大學學報（自然科學版），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 標準LDPC 譯碼[J].空間電子技術，2013，10（1）：58-61，95.

[8] 賀鶴云.LDPC 碼基礎與應用[M].北京：人民郵電出版社，2009.

[9] 袁云云.DVB_S2 標準中多模級聯糾錯碼研究及其高速FPGA 實現[D].西安：西安電子科技大學，2014.

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

[11] 符曉，張國斌.朱洪順.Xilinx ZYNQ-7000 AP SoC 開發實戰指南[M].北京：清華大學出版社，2016.

[12] 何賓.Xilinx FPGA 設計權威指南：Vivado 集成設計環境[M].北京：清華大學出版社，2014.