一種高性能低復雜度的ＬＤＰＣ譯碼器的ＦＰＧＡ實現

摘 要：低密度校驗碼（LDPC碼）所具有的優越性能和實用價值使其已經成為編碼領域研究的熱點。然而實際中LDPC碼的應用還有許多具有挑戰性的問題，像如何降低譯碼的復雜度以及如何減少譯碼所需的大量硬件資源等。基于以上原因，研究一種高性能、低復雜度的軟判決譯碼算法。這種譯碼算法較常用的硬判決譯碼算法性能出色，同時較一般的迭代譯碼算法的收斂速度快，并且可以部分并行譯碼，需要的存儲量很小，能夠大幅度降低LDPC譯碼的硬件實現復雜度，具有實際應用價值。

關鍵詞：低密度奇偶校驗碼；圖模型；高斯信道；消息傳遞算法；軟判決譯碼

中圖分類號：TN710 文獻標識碼：B 文章編號：1004373X(2008)1813504

FPGA Implement for High Performance and Low Complex LDPC Decoder

WANG Bo，WAN Lihua

(Chongqing Jinmei Communication Co.Ltd.，Chongqing，400030，China)

Abstract：For high performance and great value，most of scientists on channelcoding have great interested in Low Density ParityCheck Code（LDPC）.But there are many problems unsolved，such as how to reduce the implement complexity，how to cut down the hardware resource and so on.For these reasons，a study on softdecision decoding arithmetic has been carried out.The arithmetic has high performance，high convergence and so on.The sidebyside decoding can be used to implement the decoder，which makes design has low memorystored and low hardware implantation complexity.So the design has great value for practice utility.

Keywords：low density paritycheck code;graph model;Girth channel;message passing algorithm;softdecision decoding

1 引 言

低密度校驗碼(Low Density ParityCheck Code，LDPC碼)是一種基于稀疏校驗矩陣的分組碼。它于1962年由 Gallager發現，故亦稱Gallager碼。近年來，LDPC碼所具有的優越性能和實用價值使其在理論和實踐中都逐漸成為編碼領域最受矚目的熱點。

然而實際中LDPC碼的應用還有許多具有挑戰性的問題:如何降低譯碼和存儲復雜的奇偶校驗矩陣以及如何減少譯碼所需的大量硬件資源等。因此，低復雜度的編譯碼器實現結構也一直是糾錯領域研究的熱點。

本文研究一種非常適合準循環LDPC碼部分并行譯碼的高性能、低復雜度的軟判決譯碼算法，其性能介于比特翻轉算法和一般的消息傳遞算法之間。這種譯碼算法較常用的硬判決譯碼算法性能出色，同時較一般的迭代譯碼算法的收斂速度快，并且可以部分并行譯碼，需要的存儲量很小，能夠大幅度降低1 dpc譯碼的硬件實現復雜度，具有很大的工程實用價值。

2 ldpc碼相關

2.1 ldpc碼

LDPC碼可以用非常稀疏的校驗矩陣或二分圖來描述，也就是說LDPC碼的校驗矩陣的矩陣元除一小部分不為0外，其他絕大多數都為0。一個(n，j，k)LDPC碼其j和k都遠遠小于n，以滿足校驗矩陣的低密度特性。校驗矩陣中列和行的個數即j和k為固定值的LDPC碼稱為規則碼，否則稱為非規則碼。一般來說非規則的性能優于規則碼。Gallager曾給出一個規則(9，2，3)LDPC碼的校驗矩陣，如圖1所示。

圖1 規則(9，2，3)LDPC碼的校驗矩陣2.2 圖模型

設一個(n，λ，ρ) 正則LDPC 碼具有校驗矩陣H，則其相應的Tanner圖模型可以表示為一個二部圖。其中碼字向量X=(x1，x2，…，xn)表示為一組變量節點{ xj，j=1，2，…，n}，分別對應于校驗矩陣的各列;而校驗約束則表示為一組校驗節點{ zi，i=1，2，…，n}，對應于校驗矩陣的各行。對于(n，λ，ρ)正則LDPC碼，每個變量節點與λ個校驗節點相連，稱該變量節點的度為λ；每個校驗節點與ρ個變量節點相連，稱該校驗節點的度為ρ，度表示與節點相連的邊的數目。圖2給出了圖1所示的校驗矩陣對應的Tanner圖結構。

圖2 一個規則(2，3)LDPC碼的Tanner圖

表示及其對應的校驗矩陣3 TDMP算法譯碼

消息傳遞算法是一類通用的LDPC碼的譯碼算法，其本質是 一 種 迭 代 譯 碼 算 法。而TDMP (TurboDecoding MessagePassing)算法即為消息傳遞算法中的一種，非常適合于準循環LDPC碼的部分并行譯碼實現。因其采用軟判決譯碼，因此性能出色。同時比一般的迭代譯碼算法的收斂速度快，譯碼的硬件實現復雜度低。下面來詳細介紹其實現原理和方法。

3.1 消息傳遞

消息傳遞算法是一種迭代譯碼算法，在該算法的每一輪迭代過程中，關于各個節點的置信消息需要在變量節點和校驗節點之間傳遞。一類比較重要的消息傳遞算法被稱作置信傳播算法（Belief Propagation Algorithm）。在置信傳播算法中，各個節點之間傳遞的信息是概率或置信信息，比如由變量節點 傳遞給校驗節點c的信息是v取某些特定值的概率信息，該信息的具體取值依賴于 的觀測值和其他所有與 相連的校驗節點（除c以外）在上一輪迭代中傳遞給v的置信信息。

3.2 LLR

消 息 傳 遞 算 法的迭代公式是在獨立性假設下推導得到的，這里僅考慮碼元為0，1時的情況。設某個二值隨機變量x取值為0，1的概率分別為Pr(x=0)和Pr(x=1)。為了使所傳遞的消息中能夠同時包含2個取值概率信息，通常用兩者的一個函數變量表示該信息，如概率比或者對數似然比：L(x)=Pr(x=0)Pr(x=1)或LLR(x)=lnPr(x=0)Pr(x=1)

由于對數域的譯碼算法不需要做乘積運算，因此在硬件實現時比較簡單，下面介紹的算法均為對數域中的，且是基于AWGN信道。

設x為滿足均勻分布的二值隨機變量，即Pr(x=0)/Pr(x=1)=1/2，為y為x經過信道后的觀測值，根據Bayes規則有：LLR(x/y)=lnP(x=0|y)P(x=1|y)

=lnP(x=0，y)/P(y)P(x=0，y)/P(y)

=lnP(y|x=0)/P(x=0)P(y|x=1)/P(x=1)

=lnP(y|x=0)P(y|x=1)

=LLR(y/x)

根據上面的結論就可以由y得到第i比特的信道信息的對數似然比（LLR）值，Li=lnP(xj=0|y)P(xj=1|y)=lnP(xj~=+1|yj)P(xj~=-1|yj)

=lnP(yj|xj~=+1)P(yj|xj~=-1)=lnP(nj|yj=-1)P(nj|yj~=+1)

=ln12πδe(yj－1)22δ212πδe(yj+1)22δ2=2yjδ23.3 譯碼步驟

Gallager的長n＝pc的規則(r，c)LDPC碼可看成r個超碼（按行分的子矩陣）的交，每個超碼由c個p×p矩陣構成，而每個超碼又可看成由p個相互獨立的單校驗（Single ParityCheck）碼構成，單校驗碼可用BCJR算法譯碼，這就是Mansour提出的TDMP算法的基本思想。

具體譯碼算法如下：

步驟1 初始化：γ=δ; k=0; (λi=0，i=1，…，r。

步驟2 如果k

步驟3 對第i+1個超碼的p個單校驗碼分別譯碼：

對于一個單校驗碼，先取出對應的c個位置（一行中1的位置）的γ-λi+1的值，通過計算相應的Δα，Δβ的值，得到新的λi+1和γ的值，更新這些位置的λi+1和γ的值，γ=δ+∑ri=1λi。具體的計算方法在下文給出。

步驟4 如果i

步驟5 k=k＋1，轉到步驟2。

步驟6 通過γ的值最后判定接收值。

下面介紹步驟3的具體計算過程。設c個γλi+1的值分別為a1，a2，…，ac；新的λi+1和γ的值分別為λ1，λ2，…，λc和γ1，γ2，…，γc;相應的c個Δα，Δβ的值分別為Δα1，Δα2，…，Δβc和Δβ1，Δα2，…，Δβc，Δβ1和Δβc分別賦初值為-∞，則：Δαi+1=q(Δαi，ai)，i=1，2，…，c－1

Δβi－1=q(Δβi，ai)，i=2，3，…，c

λi=q(Δαi，Δβi)，i=1，2，…，c

γi=λi+ai，i=1，2，…，c

q(x，y)=q0(x，y)+δq(x，y)

q0(x，y)=max(x，y)－max(x+y，0)

δq(x，y)=ln(1+e－|x－y|)－ln(1+e－|x+y|)

顯然，q0(x，y)便于硬件實現，而δq(x，y)需要用查表法或下面的便于實現的近似函數來代替:δQ(x，y)=max(58－|x－y|4，0)－

max(58－|x+y|4，0)4 FPGA實現

TDMP算法是3種算法中所需存儲量最低的一種算法，而且TDMP算法的收斂速度比前兩種算法要高，同等性能下需要的量化比特數也比前兩種算法要少，且只需用均勻量化。考慮到量化精度和存儲空間的均衡，本文采用3比特量化。

本文采用部分并行的譯碼方法，通過多個超碼共用存儲空間，在不降低譯碼速度的同時，很好地降低了存儲實現的復雜度，從而大幅地降低了成本。

4.1 單校驗碼譯碼器的實現

單校驗碼譯碼器是整個譯碼器運算部分的核心，在單校驗碼譯碼器的基礎上，加入適當的控制電路，就構成了整個譯碼電路的總體結構。

單校驗碼譯碼器（如圖3所示）內部包含13塊Q函數模塊（如圖4所示），第1行的4塊計算α，第2行的4塊計算β，第3行的5塊計算λ，用流水線結構使得1個時鐘周期就能算出1組（5個）λ和γ（延遲5個時鐘周期）。

γλ的值在輸入Q函數模塊前要有限幅模塊，在算出新的一組λ值（6 b）后將其與對應的γλ值（9 b）相加（注意這里不會產生溢出），將得到的9 b值限幅到8 b后就得到了新的γ值。

由圖可以看出，實現單校驗碼譯碼器比較簡單，主要由限幅和寄存電路、q函數、加法電路組成。限幅實現很簡單，實現代碼如下：

圖3 單校驗碼譯碼器原理框圖

input ［8:0］ din;

output ［7:0］ dout;

wire select;

assign select = din［8］^din［7］;

assign dout = (select) ? {din［8］，{7{din［7］}}}: {din［8］，din［6:0］};

下面主要介紹實現單校驗碼譯碼器中q函數的verilog實現。

4.2 Q函數的實現

Q函數模塊是實現式q(x，y)=q0(x，y)+δq(x，y)的功能；其中delta函數模塊實現式δq(x，y)=ln(1+e－|x－y|)－ln(1+e－|x+y|)的功能，由于其結構比較簡單，這里不列出其實現的原理框圖。需要說明的是譯碼器中所有運算數據均采用補碼的表示形式，而下式:

δQ(x，y)=max(58－|x－y|4，0)－max(58－|x+y|4，0)中的5/8也用量化值3代替。

Q函數的實現文件Q_function.v如下所示:

assign a_minus_b = {dina［5］，dina}-{dinb［5］，dinb};//防止溢出進行位擴展，以下類似

assign a_plus_b = {dina［5］，dina}+{dinb［5］，dinb};

assign select1 = a_minus_b［6］^a_plus_b［6］;

assign c = (select1)? dina : dinb;

assign m = ~a_plus_b［6］;

assign d = c^{6{m}};

delta_function delta1(.dout(e)，.din(a_minus_b［6:1］));

delta_function delta2(.dout(f)，.din(a_plus_b［6:1］));

assign g = {e［4］，e}-{f［4］，f};

assign h = {d［5］，d} + {g［5］，g} + m;

assign select2 = h［6］^h［5］;

assign dout = (select2)? {h［6］，{5{h［5］}}} : {h［6］，h［4:0］}; //限幅

4.3 輸入緩存和輸出緩存

輸入緩存和輸出緩存是為了實現連續譯碼而引入的。當譯碼器譯一幀數據時，下一幀數據先存入輸入緩存。輸出緩存用來存儲譯碼結束后的判定數據（即最后一輪迭代后γ的符號位）。

圖4 Q函數模塊原理框圖4.4 譯碼控制

譯碼控制模塊控制整個譯碼過程，主要控制γ存儲器、λ1，λ2，λ3存儲器以及輸出緩存的讀寫時序和地址。當輸入緩存數據快存滿時，輸入控制模塊給譯碼控制模塊一個開始譯碼信號，譯碼控制模塊開始控制整個譯碼過程。譯碼控制模塊還可以控制單校驗碼譯碼器是否工作，以及需要進行的迭代次數等。

對于不同的系統，不同人設計的控制電路會有一些差異，但實現效果都一樣，在這不用贅述。

4.5 總體結構以及資源利用率

其總體結構由輸入/輸出緩存，輸入/輸出控制，譯碼控制，譯碼中間數據緩存幾個關鍵部分組成。譯碼的頂層框圖如圖5所示。

譯碼器在Altera的Stritix器件上的資源利用情況如圖6所示，由圖6可以看出，其資源占用率較低，完全可以適用于工程應用。

5 結 語

本文研究這種1 dpc譯碼使用Verilog HDL語言描述，并在Altera的Stritix器件上進行綜合仿真。這種譯碼算法較一般的迭代譯碼算法的收斂速度快，可以進行部分并行譯碼，同時需要的存儲量很小，硬件實現復雜

圖5 譯碼FPGA實現的頂層視圖圖6 在 Altera Stratix上實現的譯碼器的資源利用情況

度相對較低，具有較大的工程應用價值。

參 考 文 獻

［1］王新梅，肖國鎮.糾錯碼原理與方法\\.西安：西安電子科技大學出版社，1991.

［2］王育民，梁傳甲.信息與編碼理論\\.西安：西北電訊工程學院出版社，1986.

［3］樊昌信，詹道庸，徐炳祥，等.通信原理\\.4版.北京：國防工業出版社，1995.

［4］夏宇聞.Verilog數字系統設計教程\\.北京：高等教育出版社，2003.

［5］MacKay D J C，Neal R M.Near Shannon Limit Performance of Lowdensity Parity Check Codes\\.IEE Electronics.Lett.，1996，32(18):1 6451 646.

［6］Gallager R G.Low Density Parity Check Codes\\.IRE

Trans.Inform.Theory，1962，IT8:2128.

［7］Richardson T，Shokrollahi A，Urbanke R.Design of Capacityapproaching Irregular Lowdensity ParityCheck Codes\\.IEEE Transactions on Information Theory，2001，47(2):619637.

［8］Kschichang F R，Frey B J.Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models\\.IEEE Select.Areas Commun.，1998，16(2):219230.

［9］Ko Y J，Kim J H.Girth Conditioning for Construction of Short Block Length Irregular LDPC Codes\\.Electronics Letters，2004，40(3):187188.

［10］佟學儉，羅濤.OFDM移動通信技術原理與應用\\.北京：人民郵電出版社，2003.

［11］Mackay D J C.Good Errorcorrecting Codes Based on Very Sparse Matrices\\.IEEE Trans.on

Info.Theory，1999，45(2):339431.

作者簡介 王 博 男，1982年出生，工程師，畢業于四川大學電子信息工程專業。主要研究方向為信源編碼與信道編碼。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文