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

1 引言

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

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

2 LDPC碼的通用編碼方法

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

2.1 傳統(tǒng)算法

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

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

該編碼算法可簡(jiǎn)單概括為：若LDPC編碼器將長(zhǎng)度為k的信息比特m=（m0，m1，…，mk-1）編碼為一個(gè)長(zhǎng)度為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不是稀疏矩陣，因此在編碼時(shí)所用到的矩陣乘法的運(yùn)算量階數(shù)是O（N2）。

2.2 基于RU算法的編碼方法

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

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

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

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

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

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

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

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

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

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

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

3.1 快速編碼方法

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

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

2） 進(jìn)行第二步運(yùn)算時(shí)，依據(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。顯而易見(jiàn)：將公因子u提取出來(lái)以后，H2-1矩陣中的所有元素都可由a，b，c這3個(gè)符號(hào)或其加法之和組成，而二進(jìn)制加法可簡(jiǎn)單地用異或門(mén)實(shí)現(xiàn)。這樣H2-1DT的運(yùn)算就可由最簡(jiǎn)單的移位寄存器和異或門(mén)構(gòu)成，最后再用組合邏輯實(shí)現(xiàn)除以公因子u的運(yùn)算，完成了準(zhǔn)循環(huán)LDPC碼的編碼過(guò)程。整個(gè)編碼算法的數(shù)據(jù)流程如圖3所示。

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

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

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

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

4 小結(jié)

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

責(zé)任編輯：gt