一類準(zhǔn)循環(huán)LDPC碼的快速編碼方法-設(shè)計(jì)應(yīng)用

精品文檔-下載后可編輯一類準(zhǔn)循環(huán)LDPC碼的快速編碼方法-設(shè)計(jì)應(yīng)用1引言低密度奇偶校驗(yàn)(LowDensitvParitvCheck，LDPC)碼已成為當(dāng)今信道編碼領(lǐng)域的研究熱點(diǎn)之一。LDPC碼屬于線性分組碼，根據(jù)其構(gòu)造方法和相應(yīng)的編碼算法，主要分為兩類：一類是隨機(jī)構(gòu)造的LDPC碼，該類碼在長碼時(shí)具有很好的糾錯能力，然而由于碼組過長，以及生成矩陣與校驗(yàn)矩陣的不規(guī)則性，使編碼過于復(fù)雜而難以用硬件實(shí)現(xiàn)，編碼時(shí)間過長也不利于硬件的實(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)的糾錯能力，性能接近隨機(jī)構(gòu)造的LDPC碼，又因其硬件實(shí)現(xiàn)極其簡單，只需用反饋移位寄存器連接就可實(shí)現(xiàn)，因此具有很好的應(yīng)用前景。

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

2LDPC碼的通用編碼方法

作為信道編碼中糾錯能力強(qiáng)的碼型之一，LDPC碼由于其譯碼器結(jié)構(gòu)實(shí)現(xiàn)簡單，可以用較少的資源消耗獲得很高的吞吐量，但編碼器的復(fù)雜度問題作為不利因素制約著LDPC碼的應(yīng)用。傳統(tǒng)的編碼方法是通過生成矩陣生成碼字，其復(fù)雜度和碼長的平方成正比，這使得LDPC碼在編碼上需要大量的硬件資源和很長的延時(shí)。Richardson在文獻(xiàn)[4]中引入了一種新穎的算法在很大程度上解決了該問題，之后，Dong-ULee等人利用這種新算法設(shè)計(jì)了相應(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=[H1H2]，其中H2是一個(gè)(n-k)×(n-k)的稀疏方陣，并且在二元域上是非奇異陣，那么G就可用式(1)給出

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

該編碼算法可簡單概括為：若LDPC編碼器將長度為k的信息比特m=(m0，m1，…，mk-1)編碼為一個(gè)長度為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指出通過對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來計(jì)算p1和p2。RU算法主要包括預(yù)處理和實(shí)際編碼兩個(gè)步驟。預(yù)編碼通過行列變換把校驗(yàn)矩陣H轉(zhuǎn)化為近似的下三角陣形式H′,預(yù)編碼只需執(zhí)行，可以在軟件中預(yù)先處理。然后把H′分成6個(gè)稀疏矩陣，通過分步計(jì)算求得p1和p2，其中p1復(fù)雜度為O(N+g2)，p2的計(jì)算復(fù)雜度為O(N)。圖1為H經(jīng)預(yù)編碼后的近似下三角陣形式H′。

但如何得到這個(gè)近似下三角矩陣仍沒有令人滿意的方法，T.J.Rrichdson等人通過貪心算法重排校驗(yàn)矩陣過于復(fù)雜，且這樣的預(yù)處理需要很長時(shí)間。尤其當(dāng)碼長較長時(shí)，這種編碼方法不是一種理想的實(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)移位單元在每個(gè)時(shí)鐘周期循環(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個(gè)步驟：

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

2)計(jì)算校驗(yàn)位，這一步是整個(gè)編碼算法中復(fù)雜度也是耗費(fèi)資源的部分。

3)獲得編碼后的碼字C=(m，p)。

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

3.1快速編碼方法

基于FPGA平臺，在對一類碼長為15360，行重為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)算過程，用FPGA實(shí)現(xiàn)時(shí)只要一個(gè)時(shí)鐘的時(shí)間。

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

其具體運(yùn)算過程為：將日H2-1矩陣分成a，b，c3部分獨(dú)立存儲，若H2-1矩陣相應(yīng)位置含有元素a，則將a存儲區(qū)相應(yīng)位置1，否則置0，同理完成對b和c存儲區(qū)的初始化，完成步運(yùn)算的中間結(jié)果參與第二步運(yùn)算時(shí)，若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個(gè)時(shí)鐘周期內(nèi)完成，終除以常數(shù)公因子u的運(yùn)算可用組合邏輯實(shí)現(xiàn)，不占用時(shí)鐘周期。

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

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

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

4小結(jié)

隨著集成電路技術(shù)和加工工藝的不斷發(fā)展