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

1 引言

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

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

2 LDPC碼的通用編碼方法

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

2.1 傳統(tǒng)算法

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

很容易驗證：這樣的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為校驗位，設(shè)LDPC碼的奇偶校驗矩陣為H=［H1，H2］，其中，H1子矩陣包括H矩陣中的前k列，H2子矩陣包括H矩陣中的后n-k列，則由式（1）及C=mxG可得校驗位

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

2.2 基于RU算法的編碼方法

Richardson和Urbanke指出通過對LDPC的校驗矩陣進行一定規(guī)則的線性操作即預(yù)編碼的算法（RU算法），可以使LDPC編碼器的復(fù)雜度控制在與碼長成線性關(guān)系。設(shè)碼字矢量x=（s，p1，p2），其中s為信息位，p1與p2合起來表示校驗位，利用校驗方程Hx′=0來計算p1和p2。RU算法主要包括預(yù)處理和實際編碼兩個步驟。預(yù)編碼通過行列變換把校驗矩陣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等人通過貪心算法重排校驗矩陣過于復(fù)雜，且這樣的預(yù)處理需要很長時間。尤其當碼長較長時，這種編碼方法不是一種理想的實現(xiàn)方式。

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

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

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

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

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

2） 計算校驗位

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

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

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

3.1 快速編碼方法

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

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

2） 進行第二步運算時，依據(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個符號或其加法之和組成，而二進制加法可簡單地用異或門實現(xiàn)。這樣H2-1DT的運算就可由最簡單的移位寄存器和異或門構(gòu)成，最后再用組合邏輯實現(xiàn)除以公因子u的運算，完成了準循環(huán)LDPC碼的編碼過程。整個編碼算法的數(shù)據(jù)流程如圖3所示。

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

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

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

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

4 小結(jié)

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

責(zé)任編輯：gt