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

1 引言

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

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

2 LDPC碼的通用編碼方法

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

2.1 傳統算法

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

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

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

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

2.2 基于RU算法的編碼方法

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

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

2.3 準循環LDPC碼及其編碼方法

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

3 準循環LDPC碼的快速編碼方法

對準循環LDPC的編碼實現可分為如下3個步驟：

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

2） 計算校驗位

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

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

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

3.1 快速編碼方法

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

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

2） 進行第二步運算時，依據Ibrahim N.Imam等人提出的采用舒爾分解求解大矩陣逆矩陣的算法求解H2的逆矩陣H2-1可得：若用字符a表示32×32循環矩陣塊為單位矩陣，字符b表示32×32單位矩陣各行分別循環右移一位所得的矩陣，字符c表示32×32單位矩陣各行分別循環右移兩位所得的矩陣，則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個符號或其加法之和組成，而二進制加法可簡單地用異或門實現。這樣H2-1DT的運算就可由最簡單的移位寄存器和異或門構成，最后再用組合邏輯實現除以公因子u的運算，完成了準循環LDPC碼的編碼過程。整個編碼算法的數據流程如圖3所示。

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

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

3.2 快速編碼方法的優點

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

4 小結

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

責任編輯：gt