基于EP2S60型FPGA芯片的LDPC碼快速編碼的實(shí)現(xiàn)設(shè)計

　　作者：劉春江，吳智勇，于新，施玉海

1 引言

低密度奇偶校驗(yàn)（Low Densitv Paritv Check，LDPC）碼已成為當(dāng)今信道編碼領(lǐng)域的研究熱點(diǎn)之一。LDPC碼屬于線性分組碼，根據(jù)其構(gòu)造方法和相應(yīng)的編碼算法，主要分為兩類：一類是隨機(jī)構(gòu)造的LDPC碼，該類碼在長碼時具有很好的糾錯能力，然而由于碼組過長，以及生成矩陣與校驗(yàn)矩陣的不規(guī)則性，使編碼過于復(fù)雜而難以用硬件實(shí)現(xiàn)，編碼時間過長也不利于硬件的實(shí)時應(yīng)用；另一類是結(jié)構(gòu)碼，它由幾何、代數(shù)和組合設(shè)計等方法構(gòu)造。大多數(shù)LDPC結(jié)構(gòu)碼是循環(huán)或準(zhǔn)循環(huán)結(jié)構(gòu)，準(zhǔn)循環(huán)碼在中短碼時具有相當(dāng)強(qiáng)的糾錯能力，性能接近隨機(jī)構(gòu)造的最優(yōu)LDPC碼，又因其硬件實(shí)現(xiàn)極其簡單，只需用反饋移位寄存器連接就可實(shí)現(xiàn)，因此具有很好的應(yīng)用前景。

在LDPC碼的理論和應(yīng)用研究越來越受到人們關(guān)注的同時，探討LDPC碼在DSP，VLSI（超大規(guī)模集成電路）和FPGA（現(xiàn)場可編程門陣列）等上的實(shí)現(xiàn)也成為一個重要研究方向。在科研項(xiàng)目的工作中，發(fā)現(xiàn)一種針對準(zhǔn)循環(huán)LDPC碼的快速編碼實(shí)現(xiàn)方法，對于碼長為15 360的LDPC碼，基于Altera公司的EP2S60型FPGA芯片實(shí)現(xiàn)時可達(dá)到25 Mbit／s以上的編碼速度。

2 LDPC碼的通用編碼方法

作為信道編碼中糾錯能力最強(qiáng)的碼型之一，LDPC碼由于其譯碼器結(jié)構(gòu)實(shí)現(xiàn)簡單，可以用較少的資源消耗獲得很高的吞吐量，但編碼器的復(fù)雜度問題作為不利因素制約著LDPC碼的應(yīng)用。傳統(tǒng)的編碼方法是通過生成矩陣生成碼字，其復(fù)雜度和碼長的平方成正比，這使得LDPC碼在編碼上需要大量的硬件資源和很長的延時。Richardson在文獻(xiàn)［4］中引入了一種新穎的算法在很大程度上解決了該問題，之后，Dong-U Lee等人利用這種新算法設(shè)計了相應(yīng)的編碼方法，這種編碼方法適用于大多數(shù)的LDPC碼；而對于基于有限幾何或其他置換方法等構(gòu)造出的具有循環(huán)或準(zhǔn)循環(huán)特性的LDPC碼，由于其特殊的構(gòu)造，可簡單地用移位寄存器來實(shí)現(xiàn)編碼，編碼算法復(fù)雜度進(jìn)一步降低。

2.1 傳統(tǒng)算法

LDPC碼的傳統(tǒng)編碼算法和一般的線性分組碼十分類似，需要求出生成矩陣。若已知長度為k的輸入信息向量M，以及k×n的生成矩陣G，碼字C就可以得到：C=M×G。在獲得校驗(yàn)矩陣H后，利用H和G之間的正交性可以用高斯消元法來得到生成矩陣G。假設(shè)稀疏矩陣H有如下形式：H=［H1 H2］，其中H2是一個（n-k）×（n-k）的稀疏方陣，并且在二元域上是非奇異陣，那么G就可用式（1）給出

很容易驗(yàn)證：這樣的G滿足HGT=0，其中，Ik是一個k階的單位矩陣，這樣得到的碼字具有系統(tǒng)碼的形式。

該編碼算法可簡單概括為：若LDPC編碼器將長度為k的信息比特m=（m0，m1，…，mk-1）編碼為一個長度為n的LDPC碼字C=（m，p）=（m0，m1，…，mk-1，p0，p1，…，pn-k-1），其中p為校驗(yàn)位，設(shè)LDPC碼的奇偶校驗(yàn)矩陣為H=［H1，H2］，其中，H1子矩陣包括H矩陣中的前k列，H2子矩陣包括H矩陣中的后n-k列，則由式（1）及C=mxG可得校驗(yàn)位

已知校驗(yàn)矩陣H求解生成矩陣G的主要算法是二元域上的高斯消元法，一般而言，這樣得到生成矩陣G不是稀疏矩陣，因此在編碼時所用到的矩陣乘法的運(yùn)算量階數(shù)是O（N2）。

2.2 基于RU算法的編碼方法

Richardson和Urbanke指出通過對LDPC的校驗(yàn)矩陣進(jìn)行一定規(guī)則的線性操作即預(yù)編碼的算法（RU算法），可以使LDPC編碼器的復(fù)雜度控制在與碼長成線性關(guān)系。設(shè)碼字矢量x=（s，p1，p2），其中s為信息位，p1與p2合起來表示校驗(yàn)位，利用校驗(yàn)方程Hx′=0來計算p1和p2。RU算法主要包括預(yù)處理和實(shí)際編碼兩個步驟。預(yù)編碼通過行列變換把校驗(yàn)矩陣H轉(zhuǎn)化為近似的下三角陣形式H′，預(yù)編碼只需執(zhí)行一次，可以在軟件中預(yù)先處理。然后把H′分成6個稀疏矩陣，通過分步計算求得p1和p2，其中p1復(fù)雜度為O（N+g2），p2的計算復(fù)雜度為O（N）。圖1為H經(jīng)預(yù)編碼后的近似下三角陣形式H′。

但如何得到這個近似下三角矩陣仍沒有令人滿意的方法，T.J.Rrichdson等人通過貪心算法重排校驗(yàn)矩陣過于復(fù)雜，且這樣的預(yù)處理需要很長時間。尤其當(dāng)碼長較長時，這種編碼方法不是一種理想的實(shí)現(xiàn)方式。

2.3 準(zhǔn)循環(huán)LDPC碼及其編碼方法

準(zhǔn)循環(huán)LDPC碼是一類構(gòu)造比較特殊且應(yīng)用范圍越來越廣的LDPC碼，其校驗(yàn)矩陣Hqc由一系列的m×m小循環(huán)方陣組成，這些小循環(huán)方陣可以是置換矩陣或是基于有限幾何的矩陣等。由于Hqc的準(zhǔn)循環(huán)特性，可以得到具有系統(tǒng)碼形式和準(zhǔn)循環(huán)特性的生成矩陣，即通過式（1）所得到的生成矩陣具有準(zhǔn)循環(huán)特性，則只需要采用移位寄存器即可實(shí)現(xiàn)輸入信息和生成矩陣的編碼運(yùn)算。針對一些特殊的準(zhǔn)循環(huán)LDPC碼，D.E，Hocevar等人還提出一種僅利用校驗(yàn)矩陣即可用移位寄存器進(jìn)行快速編碼的方法，其結(jié)構(gòu)如圖2所示。B中存儲著用來和信息比特相乘的循環(huán)移位值，循環(huán)移位單元在每個時鐘周期循環(huán)右移或者左移一次。從實(shí)現(xiàn)的低復(fù)雜度考慮，它優(yōu)于基于RU算法的LDPC編碼方案，但它只適用于具有準(zhǔn)循環(huán)特性的LDPC碼。

3 準(zhǔn)循環(huán)LDPC碼的快速編碼方法

對準(zhǔn)循環(huán)LDPC的編碼實(shí)現(xiàn)可分為如下3個步驟：

1） 計算中間變量DT=H1mT，根據(jù)H1矩陣具有準(zhǔn)循環(huán)特性，使用循環(huán)移位寄存器實(shí)現(xiàn)，并對DT加以緩存。

2） 計算校驗(yàn)位

，這一步是整個編碼算法中復(fù)雜度最高也是最耗費(fèi)資源的部分。

3） 獲得編碼后的碼字C=（m，p）。

常用的編碼算法因通過高斯消去法獲得的H2-1既不是稀疏矩陣，又不具備明顯的準(zhǔn)循環(huán)特性，因此造成第二步運(yùn)算過程中運(yùn)算復(fù)雜度較高，降低了運(yùn)算速度，影響了整體編碼速度和效率。此時，本文針對H2列重小于4的準(zhǔn)循環(huán)LDPC碼（通常H2矩陣的列重均較?。榻B了該類碼的快速編碼算法，進(jìn)一步簡化了編碼復(fù)雜度，以適當(dāng)增加資源占用為代價，極大地提高了編碼速度。

3.1 快速編碼方法

基于FPGA平臺，在對一類碼長為15 360，行重為5～25，列重為2～12的準(zhǔn)循環(huán)非正則LDPC碼（其中每個子循環(huán)塊的大小為32×32），按照如下步驟進(jìn)行編碼：

1） 第一步求DT=H1mT的運(yùn)算，由于H1矩陣為準(zhǔn)循環(huán)矩陣，只需將信息序列m以32個bit為單位按照H1矩陣中循環(huán)子矩陣的要求進(jìn)行循環(huán)移位操作就可完成運(yùn)算過程，用FPGA實(shí)現(xiàn)時只要一個時鐘的時間。

2） 進(jìn)行第二步運(yùn)算時，依據(jù)Ibrahim N.Imam等人提出的采用舒爾分解求解大矩陣逆矩陣的算法求解H2的逆矩陣H2-1可得：若用字符a表示32×32循環(huán)矩陣塊為單位矩陣，字符b表示32×32單位矩陣各行分別循環(huán)右移一位所得的矩陣，字符c表示32×32單位矩陣各行分別循環(huán)右移兩位所得的矩陣，則H2-1矩陣所有元素只有a／u，b／u，c／u，（b+c）／u，（a+b）／u，（a+c）／u這6種類型，其中u=a2+ab+b2。顯而易見：將公因子u提取出來以后，H2-1矩陣中的所有元素都可由a，b，c這3個符號或其加法之和組成，而二進(jìn)制加法可簡單地用異或門實(shí)現(xiàn)。這樣H2-1DT的運(yùn)算就可由最簡單的移位寄存器和異或門構(gòu)成，最后再用組合邏輯實(shí)現(xiàn)除以公因子u的運(yùn)算，完成了準(zhǔn)循環(huán)LDPC碼的編碼過程。整個編碼算法的數(shù)據(jù)流程如圖3所示。

其具體運(yùn)算過程為：將日H2-1矩陣分成a，b，c 3部分獨(dú)立存儲，若H2-1矩陣相應(yīng)位置含有元素a，則將a存儲區(qū)相應(yīng)位置1，否則置0，同理完成對b和c存儲區(qū)的初始化，完成第一步運(yùn)算的中間結(jié)果參與第二步運(yùn)算時，若a存儲區(qū)某位置為1，則數(shù)據(jù)保持不變參與后面的三輸入異或運(yùn)算，若該位置為0，則將所有數(shù)據(jù)置為0參與運(yùn)算，同理若b存儲區(qū)某位置為1，則數(shù)據(jù)右移1位后參與后面的三輸入異或運(yùn)算，若c存儲區(qū)某位置為1，則數(shù)據(jù)右移2位后參與后面的三輸入異或運(yùn)算，為0則將數(shù)據(jù)置為0參與異或運(yùn)算，移位和異或運(yùn)算可在1個時鐘周期內(nèi)完成，最終除以常數(shù)公因子u的運(yùn)算可用組合邏輯實(shí)現(xiàn)，不占用時鐘周期。

將H2-1矩陣分成3部分存儲以后，采用流水線結(jié)構(gòu)，將原本需要10個時鐘周期左右的運(yùn)算過程縮短到最多4個時鐘就可以完成，整個運(yùn)算過程中除了存取數(shù)據(jù)外，只有移位操作和異或運(yùn)算，大大提高了運(yùn)算速度，同時也降低了編碼的復(fù)雜度，而且由于采用了恰當(dāng)?shù)拇鎯Ψ绞剑m然分成3部分存儲，但對存儲資源的占用并沒有太大增加，所耗費(fèi)的邏輯運(yùn)算單元僅略有增加。

3.2 快速編碼方法的優(yōu)點(diǎn)

本文介紹的快速編碼方法的本質(zhì)就是根據(jù)式（2）對準(zhǔn)循環(huán)LDPC碼進(jìn)行編碼求取校驗(yàn)位時，將H2-1采取一種最合理有效的方式加以存儲，同時將整個求解過程簡化為只有寄存器移位和異或運(yùn)算。由于準(zhǔn)循環(huán)LDPC碼的校驗(yàn)矩陣Hqc由一系列的m×m小循環(huán)方陣組成，采用舒爾分解法求得的H2的逆矩陣H2-1中只由少數(shù)幾個元素或其加法組合構(gòu)成，因此，對于所有準(zhǔn)循環(huán)LDPC碼均可以采用如圖3所示的快速編碼算法加以實(shí)現(xiàn)。該實(shí)現(xiàn)算法中只有循環(huán)移位和異或運(yùn)算，且每次運(yùn)算可同時對m個信息位進(jìn)行處理。因此，采用快速編碼算法不僅可實(shí)現(xiàn)線性時間內(nèi)編碼，且其運(yùn)算次數(shù)為O（N／m），降低了LDPC編碼的時間復(fù)雜度。

4 小結(jié)

隨著集成電路技術(shù)和加工工藝的不斷發(fā)展，大規(guī)模集成電路的邏輯資源數(shù)量呈幾何級數(shù)增加，尤其是FPGA芯片的邏輯單元數(shù)量已達(dá)到數(shù)百萬數(shù)量級，但運(yùn)算速度雖有很大提高卻受制于物理結(jié)構(gòu)和加工工藝等因素不能呈倍數(shù)的增加。本文提出的準(zhǔn)循環(huán)LDPC快速編碼算法依據(jù)“面積換速度”的設(shè)計準(zhǔn)則，通過適當(dāng)增加對邏輯資源的占用，降低了運(yùn)算復(fù)雜度，極大地提高了運(yùn)算速度，且該方法對于準(zhǔn)循環(huán)LDPC碼具有通用性，對于應(yīng)用越來越廣泛的準(zhǔn)循環(huán)LDPC碼的編碼具有重要的參考價值。

責(zé)任編輯：gt