陳全坤 楊奇 李二保 雷菁

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

高斯消元清除E，同時(shí)將碼字C寫成，其中為前個(gè)校驗(yàn)位，為后個(gè)校驗(yàn)位，則有：

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

2.3 基于QC-LDPC碼的編碼

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

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

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

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

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

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

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

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

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

3.1邏輯運(yùn)算電路設(shè)計(jì)

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

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

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

3.2 校驗(yàn)矩陣的分層存儲(chǔ)

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

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

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

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

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

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

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

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

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

3.4 控制模塊設(shè)計(jì)

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)

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

[2]肖揚(yáng).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.