一種低復雜度LDPC譯碼器的計與實現

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

關鍵詞：FPGA；LDPC（Low Density Parity Check）碼；BP譯碼

中圖分類號：TN47 文獻標識碼：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）碼及其相應的譯碼算法^[1].根據文獻[2]中所述，在無記憶的高斯白噪聲信道下，LDPC碼的性能與香農極限僅有不到0.1 dB的差.由于其較高的譯碼性能，LDPC碼被廣泛應用于當前各種通信系統中.如DVB-S， WLAN以及WiMAX^[3]等流行的無線通信系統.

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

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

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

1 LDPC碼及其BP譯碼算法

1.1 LDPC碼簡介

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

1.2 BP譯碼算法

LDPC碼的BP譯碼算法是基于Tanner圖的消息迭代譯碼算法.該算法的理論依據是：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.

假設接收到的向量為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）：計算每個變量節點的初始信道先驗概率值.即對于n∈{1，2，…，N}，計算概率：

若迭代次數沒有達到預設的最大次數，則重復（2）～（4）步驟，反復迭代，直到得出譯碼結果.

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

1.3 算法分析

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

2 切比雪夫多項式

2.1 切比雪夫多項式理論

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

2.2 改進的概率初始化公式

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

3 BP譯碼算法的設計與實現

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

本文中譯碼器的總體結構如圖2所示.

3.1 切比雪夫單元

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

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

3.2 改進式半并行結構

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

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

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

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

2）VNU將計算結果輸出到RAM的寫端口，并將數據寫回到RAM的原先位置.

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

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

5）CNU將計算結果輸出到RAM的寫端口，并將數據寫回到RAM的原先位置.

6）步驟3）～4）循環m次，直到RAM中的所有數據都被讀寫一次之后，一次迭代結束.

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

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

5 結 論

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

參考文獻

[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 數字電視地面廣播系統幀結構、信道編碼和調制[S]. 北京：中國標準出版社，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.