陳全坤 楊奇 李二保 雷菁

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

關(guān)鍵詞：通用型 LDPC碼 高速編碼器

中圖分類號：TP3 TN4 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）05-0000-00

1 引言

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

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

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

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

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

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

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

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

只對校驗矩陣H進(jìn)行行列置換，轉(zhuǎn)化為具有近似下三角的結(jié)構(gòu)[4]（圖1），其中H中剩下的行稱為近似表示的間隙。

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

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

2.3 基于QC-LDPC碼的編碼

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

此外，在準(zhǔn)循環(huán) LDPC 碼的基礎(chǔ)上附加約束，使其具有更加方便進(jìn)行處理的結(jié)構(gòu)，也可以實現(xiàn)有效編碼。這些方法的優(yōu)點是編碼復(fù)雜度進(jìn)一步降低，不足之處是對校驗矩陣具有更加特殊的要求，對一般LDPC碼、特別是隨機構(gòu)造的LDPC碼不具備通用性。

2.4 基于優(yōu)化的高斯消元編碼算法

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

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

3 編碼器硬件結(jié)構(gòu)設(shè)計

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

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

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

3.1邏輯運算電路設(shè)計

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

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

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

3.2 校驗矩陣的分層存儲

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

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

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

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

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

3.3 輸入輸出緩存設(shè)計

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

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

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

3.4 控制模塊設(shè)計

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

4 實現(xiàn)結(jié)果及分析

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

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

5 結(jié)語

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

參考文獻(xiàn)

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

[2]肖揚.Turbo與LDPC編解碼與應(yīng)用[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.