通用型高速LDPC碼編碼器設計與FPGA實現

陳全坤 楊奇 李二保 雷菁

摘要：隨著高速數據傳輸業務的快速發展，人們對信息傳輸的質量和速率要求越來越高，高速LDPC碼編譯碼器在通信系統中的應用需求更加強烈。在節約硬件資源的前提下，為最大限度的降低編碼時延、提高編碼器速率，本文從編碼算法的通用性出發，將一致校驗矩陣通過行列置換和高斯消元，使每個校驗位的運算只與預處理后矩陣的對應行相關，具備了可以靈活并行處理的結構。在編碼器的硬件設計上，本文提出了一種校驗位并行分步運算的編碼器架構，通過同時計算所有校驗位，分步處理單個校驗位，有效地降低了硬件實現復雜度，縮短了關鍵路徑時延，提高了編碼速率。實現結果表明，本文設計和實現的編碼器工作時鐘頻率可以達到250MHz，相應的吞吐量為14Gbit/s。

關鍵詞：通用型 LDPC碼 高速編碼器

中圖分類號：TP3 TN4 文獻標識碼：A 文章編號：1007-9416（2016）05-0000-00

1 引言

低密度奇偶校驗碼（Low-dentisy Check Codes，LDPC碼）是一種線性分組碼，由Gallager博士于1963年在其博士論文中首次提出[1]。LDPC碼校驗矩陣具有稀疏特性，不僅描述簡單、編譯碼復雜度比較低，而且錯誤平臺較低，編譯碼可以實現硬件并行處理，在現行通信標準中得到了廣泛應用。

人們對LDPC碼的批評主要集中在高編碼復雜度上[2]，如何實現快速編碼一直是LDPC碼的一個研究熱點。現行的編碼方案有基于生成矩陣的編碼算法和基于校驗矩陣的編碼算法兩大類，前者是利用稀疏校驗矩陣的特定結構，對校驗矩陣進行預處理，求出生成矩陣后編碼，而后者是利用校驗矩陣直接進行編碼。

本文立足工程實踐的需求，采取高斯消元編碼算法，設計出了資源占用較少、并行度高且算法靈活、關鍵路徑時延低、布線簡單的編碼器結構，實現了編碼速率的極大提高。

2 常用編碼算法介紹與分析

對于一個LDPC碼，設碼字空間為C，校驗位用P表示，信息位用S表示，則其碼長為n，信息位個數為k，校驗位個數為，由奇偶校驗矩陣H唯一確定。校驗矩陣H的每一行對應一個校驗方程，每一列對應碼字中的一個比特。編碼時，可以先得到生成矩陣，再由生成矩陣與信息序列S的線性關系式求得碼字：

2.1 基于LU分解的編碼[3]

將校驗矩陣H分為兩部分，其中A為m階的方陣。如果A可以通過行列變化和高斯消元，分解成為LU兩部分（L為下三角矩陣，U為上三角矩陣），同時引入中間變量y，即可由L矩陣迭代得到中間向量y，再由U矩陣迭代得到校驗序列P。這種算法的優點是運算復雜度與碼長成線性關系；缺點是預處理時需要尋找優良的分解方法以保持矩陣的稀疏性，前后迭代運算時延較大。

2.2 基于近似下三角矩陣的編碼

只對校驗矩陣H進行行列置換，轉化為具有近似下三角的結構[4]（圖1），其中H中剩下的行稱為近似表示的間隙。

高斯消元清除E，同時將碼字C寫成，其中為前個校驗位，為后個校驗位，則有：

展開后，即可得出、的計算公式。該算法優點是，如果可以將g控制在較小范圍內，復雜度與碼長呈線性關系；缺點是重新排列矩陣實現較為復雜，且矩陣求逆復雜度較高，需要特定結構的校驗矩陣以降低復雜度。

2.3 基于QC-LDPC碼的編碼

有學者提出了校驗矩陣具有一定簡單編碼結構的準循環LDPC碼[5]，其校驗矩陣被分割成若干個小的方陣，每個方陣由循環置換矩陣或全0矩陣構成。該碼校驗矩陣H和生成矩陣G都具有準循環結構，可以釆用移位寄存器進行存儲，節約了硬件資源。

此外，在準循環 LDPC 碼的基礎上附加約束，使其具有更加方便進行處理的結構，也可以實現有效編碼。這些方法的優點是編碼復雜度進一步降低，不足之處是對校驗矩陣具有更加特殊的要求，對一般LDPC碼、特別是隨機構造的LDPC碼不具備通用性。

2.4 基于優化的高斯消元編碼算法

上述編碼算法都對編碼復雜度進行了一定優化，但同時也有很大的局限性，一方面對LDPC碼矩陣結構有特定的要求，通用性不強，另一方面硬件電路的設計也較為復雜，帶來一定延時。因此，本文提出了一種基于優化的高斯消元的編碼算法。

在消元過程中，少數列變換對生成碼字的順序有一定影響，計算出校驗位后，根據變換順序重新調整序列，即可得出正確的碼字。這樣，求解校驗位的過程只與預處理后的校驗矩陣中對應的行相關，便于實現行間高度并行的運算。這種編碼方法的不足是破壞了校驗矩陣的稀疏性；優點是通用性強，對于各種類型的LDPC碼的校驗矩陣都可以處理，并且在硬件實現上并行度高、時延小，布線較為簡單，存儲資源的占用也可以接受。

3 編碼器硬件結構設計

以上分析了幾種常用的編碼方法，并對基于優化的高斯消元編碼算法進行了介紹。本文以（4480，3920）LDPC碼為例，基于優化的高斯消元編碼方案，設計了一種校驗位并行分步運算的編碼器結構，如圖2所示。

圖2中，ROM1至ROM7表示7個ROM存儲塊，用來存儲預處理后的校驗矩陣。

工作流程可以描述為：每個時鐘周期并行輸入56個信息位，分別被傳遞給輸入緩存模塊與邏輯運算模塊；同時，從7個ROM塊中讀取出矩陣的560行、56列元素，并送入邏輯運算模塊；邏輯運算模塊接收到兩類數據后，開始執行校驗位運算。此過程重復執行70個時鐘周期后，邏輯運算模塊計算出560個檢驗位，輸送至輸出緩存模塊；此時，輸入緩存模塊恰好將緩存的3920個信息位傳遞給輸出緩存模塊；560個校驗位和3920個信息位經輸出緩存模塊重新排序后，轉化成 64路并行輸出。

3.1邏輯運算電路設計

每個校驗位的計算只與矩陣中的對應行相關，因此，本文提出了一種校驗位并行分步計算方案，即每個時鐘周期，56個信息位分別在560個邏輯運算電路內，與對應的子矩陣中560行、56列元素進行運算，經過70個時鐘周期，即可同時計算出560個校驗位。

以第k個校驗位的計算為例（如圖3）：第1個時鐘周期，矩陣的第k行1到56個元素與并行輸入的56個信息位一一對應，分別進行邏輯與運算，得出的56個變量與ak（初始值為0）執行異或運算，得出的結果更新到ak，并作為反饋信號參與到下一周期運算；第2個時鐘周期，更新后的56路信息位，與矩陣的第k行中57到112個元素執行相同運算，而后與上一周期得出的ak進行異或運算；依次類推，直到第70個周期運算結束，得出結果即為對應的校驗位pk。

圖3中，Ti表示第1到第70個時鐘周期數，b表示矩陣第k行的元素，S表示信息位，設，則。

3.2 校驗矩陣的分層存儲

由于一幀數據運算需要70個時鐘周期，在存儲時，對矩陣進行如下處理（圖4）：

（1）將矩陣按每80行為1層，共分為7層，每層含個元素；定義7個ROM塊，分別把矩陣的第1層至第7層存儲到ROM1到ROM7中。

（2）矩陣的每層，按每56列分成70個矩陣塊，每個矩陣塊大小為，含4480個元素；對應的，定義每個ROM塊深度為70，寬度為4480比特。7個ROM塊的每一存儲單元，對應存儲一個大小的。

（3）每個矩陣塊中的元素在對應的存儲單元中是按行分布的。以ROM1為例，設矩陣第1層的元素可以用表示（），則對應的存儲單元對的存儲順序如圖5所示。

這樣，7個ROM塊的每個地址，各自對應矩陣中的80行、56列元素。在第k個計算周期上升沿，就可以同時對7個ROM塊的第k個存儲單元進行尋址，將矩陣中第k個56列數據一次性全部讀出，輸送到邏輯運算電路。

3.3 輸入輸出緩存設計

校驗位需要70個時鐘周期才能計算完成，需要對并行輸入的56路信息位進行緩存，待校驗位計算完成后，兩者組成完整的編碼碼字，方可輸出。

為此，本文設計了一個輸入緩存模塊，主要由56個串/并轉換模塊組成，每個串/并轉換模塊對應一路輸入信號，將一幀56路并行、每路串行輸入70個信息位的信息序列，經70個時鐘周期，轉換成3920路并行輸出。此時，560個校驗位計算完成，與3920路并行輸出的信息位組合成完整的編碼碼字，傳遞到輸出緩存模塊。

輸出緩存模塊與輸入緩存原理相似，而功能相逆。組合后的4480路并行輸入的碼字傳遞到輸出緩存模塊后，被轉換成64路并行信號，每路串行輸出70比特數據。

3.4 控制模塊設計

控制模塊是編碼器的核心模塊，作用是：信息序列輸入的同時，輸入一個使能信號Rx_en，使存儲模塊地址Addr和控制模塊中的計數器初始化為零，對7個ROM塊進行尋址，邏輯運算模塊開始工作。隨后，每經過一個時鐘周期，地址Addr和計數器自動加1。當第70個時鐘周期結束，一幀數據運算完成，計數器達到預定值，產生一個使能信號Data_en，啟動輸出緩存模塊輸出編碼碼字。

4 實現結果及分析

本設計采用Xilinx公司的Vivado 14.4版本的硬件開發軟件，以Virtex-7 系列芯片為硬件平臺，進行了綜合和布局布線后，編碼器FPGA資源消耗情況和吞吐量如表1所示。

本文所設計的編碼器LUT資源使用僅占芯片的5.29%，BRAM存儲資源使用也僅占芯片的29.76%，布局布線后的工作時鐘頻率可以達到250MHz，吞吐量可達14Gbps。

5 結語

本文在對現有編碼方案進行分析和對比的基礎上，提出了一種基于優化的高斯消元算法的編碼方案，該算法通用性強，適用于一般的LDPC碼，并且在求校驗位時便于實現行間高度并行的運算。在硬件實現上，設計了并行分步運算的快速編碼結構，優化了矩陣的存儲方法，簡化了布線路徑，降低了關鍵路徑時延，達到了高速編碼的目的。在基于Xilinx公司XC7vx690t FPGA芯片硬件平臺上，本文設計的編碼器工作時鐘可以達到250MHz，吞吐量達到了14Gbps，且消耗資源較少，具有較大的工程應用價值。

參考文獻

[1]Gallager R G.Low-Density Party Check Codes[D].Canbridge，MA：MIT Press，1963.

[2]肖揚.Turbo與LDPC編解碼與應用[M].北京：人民郵電出版社，2010.

[3]R.M.Neal.Sparse matrix methods and probabilistic inference algorithm.IMA Program On Codes，Systems，and Graphic Models，1999.

[4]Richardson T， Urbanke R. Efficient encoding of low-density parity check codes[J]. IEEE Transactions on Information Theory，2001，47（2）：638～656.

[5]M.P.C. Fossorier. Quasi-Cyclic LDPC low-density parity-check codes from circulant permutation matrices[J].IEEE Trans.Inf.Theory，vol.50，pp.1788-1793，Aug.2004.