一種低復(fù)雜度LDPC譯碼器的計與實現(xiàn)

摘要：利用切比雪夫多項式良好的逼近性，提出了基于切比雪夫多項式擬合的BP譯碼算法，并將該算法在FPGA上進行了實現(xiàn).該算法利用切比雪夫多項式擬合算法對傳統(tǒng)BP算法中的復(fù)雜函數(shù)進行擬合，用少量的乘法和加法運算代替?zhèn)鹘y(tǒng)BP算法中的復(fù)雜函數(shù).此外，調(diào)整得到的多項式系數(shù)，使其便于硬件實現(xiàn).同時，提出一種基于移位運算的切比雪夫結(jié)構(gòu)，減小因乘法器的實現(xiàn)帶來的復(fù)雜度；并提出基于流水線設(shè)計的半并行結(jié)構(gòu)，設(shè)計并實現(xiàn)了低復(fù)雜度的BP譯碼器.實驗結(jié)果表明，相比于相關(guān)工作，這種結(jié)構(gòu)能有效減少硬件資源.

關(guān)鍵詞：FPGA；LDPC（Low Density Parity Check）碼；BP譯碼

中圖分類號：TN47 文獻標(biāo)識碼：A

A FPGA Design and Implementation

of Low-complexity Decoder for LDPC Code

SHI Shao-bo， QI Yue， WANG Qin

（School of Computer Communication Engineering， Univ of Science Technology Beijing， Beijing 100083， China）

Abstract： Taking advantage of the good approximation performance of Chebyshev polynomial， this paper proposed a BP algorithm based on Chebyshev polynomial fitting. And this method can transform the complicated index formula into polynomial， which can reduce the consumption of memory resources. At the same time， a Chebyshev structure with shift operation was proposed to reduce the complexity brought by multiplier； also a semi-parallel architecture with pipeline design was proposed to reduce the complexity of BP decoder. The experimental results show that such a structure can effectively reduce the hardware resources.

Key words： FPGA； LDPC code； BP decoding

1963年，Gallager提出了低密度奇偶校驗（Low Density Parity Check， LDPC）碼及其相應(yīng)的譯碼算法^[1].根據(jù)文獻[2]中所述，在無記憶的高斯白噪聲信道下，LDPC碼的性能與香農(nóng)極限僅有不到0.1 dB的差.由于其較高的譯碼性能，LDPC碼被廣泛應(yīng)用于當(dāng)前各種通信系統(tǒng)中.如DVB-S， WLAN以及WiMAX^[3]等流行的無線通信系統(tǒng).

置信傳播（Belief Propagation， BP）譯碼算法被認為是最優(yōu)的迭代譯碼算法^[1].然而，BP算法中，大量使用了乘法和指數(shù)的運算，從而導(dǎo)致了LDPC碼的實現(xiàn)復(fù)雜度較高，無法適用于高速通信系統(tǒng)中.目前，主要有兩類方法來降低LDPC碼的譯碼實現(xiàn)復(fù)雜度.第一類是通過對原始BP算法中的復(fù)雜公式進行變形，從而降低其實現(xiàn)復(fù)雜度.如文獻[4]提出了最小和（Min-Sum）迭代譯碼算法.該算法利用簡單的符號函數(shù)和加法運算來代替?zhèn)鹘y(tǒng)BP算法中的指數(shù)運算和乘法運算.最小和算法雖然使得LDPC碼的譯碼實現(xiàn)復(fù)雜度得到了降低，但其性能與傳統(tǒng)BP算法相比，降低了1 dB左右^[5]；另一類是基于ROM查表方法^[6].ROM查表法的實現(xiàn)結(jié)構(gòu)簡單，準確度較高，應(yīng)用較廣泛.但是，受到ROM容量的限制，性能的提高很有限.因此，需要尋找一種在不影響譯碼性能的前提下，能夠有效地降低實現(xiàn)復(fù)雜度的譯碼算法.

本文提出了一種適合于VLSI實現(xiàn)的LDPC碼譯碼算法.首先，使用切比雪夫多項式擬合的方法，對傳統(tǒng)BP算法中的復(fù)雜函數(shù)進行擬合，使用少量的乘法運算和加法運算來代替?zhèn)鹘y(tǒng)BP算法中的復(fù)雜函數(shù)的運算.其次，對文獻[7]中的半并行譯碼結(jié)構(gòu)進行了改進，提出了對基于切比雪夫多項式擬合的LDPC譯碼算法的基于流水線半并行譯碼器結(jié)構(gòu)設(shè)計，進一步提高了LDPC碼的譯碼速度，從而提高了整個通信系統(tǒng)的實時性.

本文的結(jié)構(gòu)安排如下：第1部分簡要描述LDPC碼的基本概念以及傳統(tǒng)的BP算法.第2部分描述基于切比雪夫多項式擬合的LDPC譯碼算法.第3部分介紹基于切比雪夫多項式擬合的LDPC譯碼算法的硬件結(jié)構(gòu)設(shè)計.第4部分給出基于切比雪夫多項式擬合的LDPC譯碼算法的性能分析與驗證.第5部分給出本文的總結(jié).

1 LDPC碼及其BP譯碼算法

1.1 LDPC碼簡介

LDPC碼是一種線性分組碼，可以用Tanner圖或校驗矩陣H來表示.由于校驗矩陣中的元素絕大部分為“0”，“1”的個數(shù)很少，因此LDPC碼又稱為稀疏圖碼，并且Tanner圖與校驗矩陣是相對應(yīng)的，如圖1所示.

1.2 BP譯碼算法

LDPC碼的BP譯碼算法是基于Tanner圖的消息迭代譯碼算法.該算法的理論依據(jù)是：1）貝葉斯準則，即：P（X|Y） = P（Y|X）P（X） / P（Y）；2）判決準則：如果 P（X=0|Y） >= P（X=1|Y） => X = 0；如果 P（X=0|Y） < P（X=1|Y） => X = 1.

假設(shè)接收到的向量為y，其長度為N，H矩陣的大小為M×N，定義集合：

〖HL（1：1，Z〗M（n）={m：Hm，n=1}，

N（m）={n：Hm，n=1}，

N（m）＼i={n：Hm，n=1，n≠i}，

M（n）＼j={m：Hm，n=1，m≠j}.

BP譯碼算法分以下幾個步驟 ：

初始化（Initialization）：計算每個變量節(jié)點的初始信道先驗概率值.即對于n∈{1，2，…，N}，計算概率：

若迭代次數(shù)沒有達到預(yù)設(shè)的最大次數(shù)，則重復(fù)（2）～（4）步驟，反復(fù)迭代，直到得出譯碼結(jié)果.

BP譯碼算法充分利用了變量節(jié)點和校驗節(jié)點之間的關(guān)系，從而可以得到逼近香農(nóng)極限的譯碼性能，且其迭代過程中的收斂也比較快.同時由于采用了并行的迭代譯碼算法，譯碼復(fù)雜度和譯碼延時都很低.

1.3 算法分析

由上述算法描述可知，在譯碼過程中，除了大量的加法和乘法運算外，在式（1）的計算中還要用到ex.一般地，在FPGA設(shè)計中，對此公式的實現(xiàn)方法主要有：ROM（Read Only Memory）查表法、泰勒級數(shù)求值法.其中ROM查表法結(jié)構(gòu)簡單、準確度高，應(yīng)用廣泛，但受ROM容量限制，性能提高很有限，且數(shù)據(jù)精度也會受影響；泰勒級數(shù)求值法運算復(fù)雜，在硬件實現(xiàn)的復(fù)雜度和速度上受到一定限制.為了在不影響譯碼性能的前提下，最大程度地減少所占內(nèi)存資源，同時降低復(fù)雜度，本文利用切比雪夫多項式擬合算法的優(yōu)良的逼近性能，提出采用切比雪夫多項式擬合的方法，對式（1）進行簡化，方便其硬件實現(xiàn).

2 切比雪夫多項式

2.1 切比雪夫多項式理論

由上述結(jié)論可知，可以通過式（6）對一些復(fù)雜度的表達式進行切比雪夫多項式擬合，從而進行簡化.

2.2 改進的概率初始化公式

在通信系統(tǒng)模型中，當(dāng)信噪比SNR屬于某區(qū)間時，經(jīng)過該信道加噪后的傳輸信號，即譯碼器輸入數(shù)據(jù)也是屬于特定范圍的.因此，若對區(qū)間進行劃分，則可以利用基于截斷切比雪夫級數(shù)的多項式來擬合式（1）.

3 BP譯碼算法的設(shè)計與實現(xiàn)

本文在對BP譯碼算法進行實現(xiàn)的過程中，將節(jié)點實現(xiàn)分為校驗節(jié)點單元（Check Node Unit ， CNU）和變量節(jié)點單元（Variable Node Unit ，VNU），對應(yīng)于譯碼算法中的橫向處理和縱向處理，分別用來處理校驗節(jié)點和變量節(jié)點的概率更新.同時，本文還利用切比雪夫多項式來進行初始化處理.

本文中譯碼器的總體結(jié)構(gòu)如圖2所示.

3.1 切比雪夫單元

由上節(jié)可知，當(dāng)用Pn=C0+C1x+C2x2來擬合式（1）時，該公式的實現(xiàn)由3個乘法和3個加法組成.實際上，當(dāng)x的范圍確定時，切比雪夫多項式的系數(shù)C0， C1和C2是定值，為了進一步降低電路設(shè)計的復(fù)雜度，將式中系數(shù)進一步簡化為2的指數(shù)和的形式.即Pn=C0+（2-a+2-b）*x+（2-c+2-d）*x2，在二進制域中，式中與2-n的乘法可以轉(zhuǎn)化為移位運算.因此，在本文中利用移位運算對切比雪夫多項式的實現(xiàn)進行了簡化.

由圖3可知，改進后的切比雪夫多項式的實現(xiàn)可轉(zhuǎn)化為1個乘法、3個加法和4個移位運算.與原式相比，所占資源明顯減少，且降低了復(fù)雜度.

3.2 改進式半并行結(jié)構(gòu)

一般地，由于BP譯碼算法的特性，采用全并行結(jié)構(gòu)的譯碼器，可以達到很高的譯碼速率.全并行結(jié)構(gòu)的譯碼器是指在概率更新過程中，多個CNU單元或VNU單元并行執(zhí)行，數(shù)據(jù)在CNU模塊和VNU模塊之間直接傳遞.這種方法能夠很快地得到輸出結(jié)果.但是對于傳輸信息位超過1 000 bit的碼字，在全并行結(jié)構(gòu)下，由于各執(zhí)行單元的并行性，不僅會要求較多的資源，同時還會要求很大的存儲量來存儲中間值.因此，本文中采用了半并行結(jié)構(gòu).

半并行結(jié)構(gòu)是一種并串結(jié)合的結(jié)構(gòu).其主要思路是通過串行地完成原本可以由多個節(jié)點并行完成的計算，僅實現(xiàn)數(shù)目遠遠少于二分圖節(jié)點數(shù)目的計算單元，從而簡化譯碼器節(jié)點之間錯綜復(fù)雜的數(shù)據(jù)線網(wǎng)絡(luò)布線問題并降低譯碼器對邏輯資源的需求.與全并行結(jié)構(gòu)相同，半并行譯碼器的譯碼算法的計算由節(jié)點完成，并增加緩存來對計算數(shù)據(jù)進行存儲，其具體框圖如圖4所示.

由圖4可知，傳統(tǒng)半并行譯碼器在每次迭代中的工作流程按照以下幾步進行：

1）VNU根據(jù)H矩陣，順序從與之連接的RAM中讀取數(shù)據(jù).

2）VNU將計算結(jié)果輸出到RAM的寫端口，并將數(shù)據(jù)寫回到RAM的原先位置.

3）步驟1）～2）循環(huán)n次，直到RAM中的所有數(shù)據(jù)都被讀寫一次之后， CNU開始工作.

4）CNU根據(jù)H矩陣，順序從與之連接的RAM中讀取數(shù)據(jù).

5）CNU將計算結(jié)果輸出到RAM的寫端口，并將數(shù)據(jù)寫回到RAM的原先位置.

6）步驟3）～4）循環(huán)m次，直到RAM中的所有數(shù)據(jù)都被讀寫一次之后，一次迭代結(jié)束.

同時，為了減少由于半并行結(jié)構(gòu)中的串行計算帶來的速率延遲，每一個節(jié)點單元的計算須采用流水線結(jié)構(gòu).然而，對于非規(guī)則LDPC碼來說，因其校驗矩陣的行重與列重不相同，故對于VNU和CNU執(zhí)行單元來說，每一次參與運算的數(shù)據(jù)個數(shù)是不相同的，這必會引起流水線結(jié)構(gòu)中復(fù)雜的控制信號.為了減少控制部件的復(fù)雜度，本文中取行計算和列計算的最大時序周期，作為流水結(jié)構(gòu)中的固定周期，用在CNU模塊和VNU模塊中，對這兩個模塊進行了流水線的設(shè)計.其模塊流水設(shè)計如圖5所示.

由表1可知，與文獻[7]的實現(xiàn)結(jié)果對比，可以發(fā)現(xiàn)使用切比雪夫多項式的BP譯碼算法省去了因查表法而占用的存儲資源，同時采用的半并行結(jié)構(gòu)使得系統(tǒng)在邏輯資源消耗上較相關(guān)工作更少.

5 結(jié) 論

本文針對LDPC的BP譯碼算法提出了一種低復(fù)雜度的實現(xiàn)方法，通過基于切比雪夫不等式的優(yōu)化，可以有效降低譯碼算法的計算量，并將BP算法在FPGA上進行了驗證，實驗結(jié)果表明該方法可以有效簡化硬件結(jié)構(gòu)設(shè)計，降低硬件資源開銷.

參考文獻

[1] GALLAGER R G. Low density parity check codes[M]. Cambridge，Mass：MIT Press， 1963.

[2] RICHARDSON T J， SHOKROLLAHI A， URBANKE R. Design of provably good low-density parity check codes[C]//Proceedings of IEEE International Symposium on Information Theory， 2000：199.

[3] GB 206002—2006 數(shù)字電視地面廣播系統(tǒng)幀結(jié)構(gòu)、信道編碼和調(diào)制[S]. 北京：中國標(biāo)準出版社，2006.

GB 206002—2006 Framing structure， channel coding and modulation for digital television terrestrial broadcasting system[S]. Beijing： Chinese Standard Press， 2006.（In Chinese）

[4] ELEFTHERIOU E， MITTELHOLZER T， DHOLAKIA A. Reduced-complexity decoding algorithm for low-density parity-check codes[J]. Electronics Letters， 2001，37（2）：102-104.

[5] ANASTASOPOULOS A. A comparison between the sum-product and the min-sum iterative detection algorithms based on density evolution[C]//Proceedings of Global Telecommunications Conference. New York： IEEE， 2001， 2：1021-1025.

[6] THEOCHARIDES T， LINK G. Implementing LDPC decoding on network-on-chip[C]//Proceedings of 18th International Conference on VLSI Design. New York： IEEE， 2005：134-137.

[7] ZHANG T， PARHI K K. An FPGA implementation of （3， 6）-regular low-density parity-check code decoder[J]. EURASIP Journal on Applied Signal Processing， 2003， 6： 530-542.

[8] PRESS W H， TEUKOLSKY S A. Numerical recipes in C： the art of scientific computing[M]. 2nd ed. Cambridge，UK： Cambridge University Press， 1992.