李世超（甘肅政法學(xué)院公安技術(shù)學(xué)院，甘肅蘭州730070）

LDPC碼譯碼算法研究與FPGA設(shè)計

李世超
（甘肅政法學(xué)院公安技術(shù)學(xué)院，甘肅蘭州730070）

運用線性逼近法簡化LDPC碼的對數(shù)似然比BP算法中的雙曲正切函數(shù)和反雙曲正切函數(shù)，從而達(dá)到減少該算法計算次數(shù)的目的.以簡化后的算法為基礎(chǔ)，在QuartusⅡ8.0軟件平臺上，用verilog語言進行LDPC碼譯碼器的設(shè)計，用QuartusⅡ8.0軟件生成RTL門級電路.仿真結(jié)果證明簡化后的對數(shù)似然比BP算法的正確性與硬件可行性.

LDPC碼；對數(shù)似然比BP算法；線性逼近；FPGA譯碼器設(shè)計

LiSC.LDPCCode Decoding Algorithm and FPGA Design[J].Journalof Yibin University,2015,15（6）：76-80.

隨著經(jīng)濟的發(fā)展和科技的進步，人們對通信質(zhì)量的要求也在日益增加，總是希望找到一些能夠提高通信質(zhì)量的方法.對于無線通信而言，糾錯碼的性能會直接影響到通信質(zhì)量.提高通信質(zhì)量所追求的目的就是提高信息傳輸?shù)挠行耘c可靠性，而糾錯碼正是提高信息傳輸可靠性的重要方法之一.低密度奇偶校驗碼（LDPC碼）實現(xiàn)復(fù)雜度較低且性能接近于香農(nóng)極限[1-4]，業(yè)界學(xué)者廣泛認(rèn)為LDPC碼將是第五代移動通信糾錯碼的首選[5].LDPC碼已經(jīng)成為目前編譯碼界研究的熱點[5].

1　LDPC碼譯碼算法簡介

LDPC碼譯碼算法對信息傳輸?shù)挠行院桶踩云鹬陵P(guān)重要的作用.如果譯碼算法無法正確譯出所傳輸?shù)男畔?，無論信源編碼和信道編碼發(fā)揮如何巨大的作用，信息也是無法正確傳輸?shù)?LDPC碼的譯碼算法多是以BP迭代算法[6]為基礎(chǔ)改進的.

1.1BP迭代譯碼算法原理

LDPC碼所采用的BP迭代譯碼算法，簡單的說，就是信道估計和接收信號在給定的條件下，每迭代一次，都對有噪序列的每一個符號估算其后驗概率，再將所得到的結(jié)果輸入下一次進行迭代，來獲得更好的結(jié)果.設(shè)碼字c=（c1,c1,…,cn）經(jīng)過BPSK調(diào)制后映射為x=（x1,x1,…,xn）,傳輸序列x通過信道后，接收序列為y=（y1,y1,…,yn），通過y可以得到譯碼序列?.BP迭代譯碼算法的原理如圖1所示.

LDPC碼的BP算法具有如下優(yōu)點：第一，在BP迭代譯碼算法中，并不是進行固定次數(shù)的迭代，而是當(dāng)試驗譯碼得到成功時，譯碼就立刻結(jié)束.這樣就大大減少了迭代的次數(shù).第二，BP算法的復(fù)雜度較低，計算量不會因為碼長的增加而增加.第三，由于該算法是一種并行算法，所以當(dāng)硬件實現(xiàn)該算法時，可以提高譯碼速率.

圖1　BP迭代譯碼算法的原理框圖

1.2對數(shù)似然比BP算法

BP譯碼算法的過程是比較復(fù)雜的.首先，該算法需要分別計算每個變量節(jié)點和校驗節(jié)點比特分別為0和1的概率.這就需要很大的運算量.其次，該算法中有許多的乘法運算，如果用硬件去實現(xiàn)該算法會耗費大量的時間和硬件資源.考慮到這些不便，人們對BP譯碼算法提出了許多改進的方法，對數(shù)似然比BP算法[7]就是其中的一種.該算法最大的優(yōu)點就是用加法運算代替了BP算法中大量的乘法運算，從而減少了運算所需的時間，提高了效率.

對數(shù)似然比BP算法的譯碼過程[7]如下：

1）初始化

首先，需要計算信道傳送給變量節(jié)點的初始概率似然比L（Pi），其中i=1,2,…,n；其次，需要設(shè)定變量節(jié)點傳送給與其相連的校驗節(jié)點 j的初始消息.

2）迭代處理

①校驗節(jié)點的更新

當(dāng)?shù)鷏次時，變量節(jié)點i傳送給與其相連的校驗節(jié)點j的消息的計算式可寫為：

上式也可寫為：

②變量節(jié)點的更新

當(dāng)?shù)鷏次時，校驗節(jié)點j傳送給與其相連的變量節(jié)點i的消息的計算式可寫為：

③判決譯碼

計算所有變量節(jié)點的判決消息：

當(dāng)L（l）（qi）＞0時，有?=0，反之=1.

3）停止

2　對數(shù)似然比BP算法的簡化

2.1雙曲正切函數(shù)和反雙曲正切函數(shù)的線性逼近

在對數(shù)似然比BP算法中，譯碼算法的復(fù)雜度主要是在更新校驗節(jié)點時需要計算雙曲正切函數(shù)和反雙曲正切函數(shù).因此需要先對雙曲正切函數(shù)進行限幅修正，雙曲正切函數(shù)tanh（x）修正如下：

由于在（2）式中，雙曲正切函數(shù)tanh（x）輸入的值為L（qi′j）的絕對幅值，因此在該式中x的取值為[0∞]，而該式中的x0取值較小，即x0＜10.采用限幅方法修正以后，雙曲正切函數(shù)趨于無窮的輸入值被近似為tanh（x0）.其中最佳的x0值是由計算機仿真所得到的，在仿真中采用（500,3,6）的規(guī)則LDPC碼，對x0=3,4,…,10的仿真結(jié)果表明，x0為3、10時譯碼性能衰減較大，在較高信噪比時不優(yōu)于未對雙曲正切函數(shù)tanh（x）修正時的性能；x0為4、5、6時，誤碼率性能針對于未對雙曲正切函數(shù)tanh（x）修正時得到改善；x0為6、7、8、9時相對于x0為4、5的情況得到了更好的誤碼率性能.在本文接下來的部分中，x0選取為6.

則式（6）可寫為

在雙曲正切函數(shù)限幅修正的基礎(chǔ)上進行線性逼近，其表達(dá)式可以寫為：

同樣的，對反雙曲正切函數(shù)進行線性逼近也可以寫成上式分段函數(shù)的形式.

2.2對數(shù)似然比BP算法的簡化

對數(shù)似然比BP算法的主要難度在于校驗節(jié)點的更新計算中存在雙曲正切函數(shù)和反雙曲正切函數(shù)，在簡化算法中用線性逼近后的雙曲正切函數(shù)和反雙曲正切函數(shù)代替原算法中的雙曲正切函數(shù)和反雙曲正切函數(shù).

則簡化后的校驗節(jié)點的更新可寫為：

而其他的譯碼步驟和對數(shù)似然比BP算法一致，在此不再敘述.

2.3簡化后的譯碼算法的性能仿真及分析

使用matlab仿真軟件，在加性高斯白噪聲的信道下，對未簡化的對數(shù)似然比BP算法和簡化后的對數(shù)似然比BP算法進行性能仿真，并通過仿真結(jié)果對兩種算法的性能進行分析.

在本次仿真中選?。?00,3,6）的規(guī)則LDPC碼，采用BPSK調(diào)制方式，譯碼算法為對數(shù)似然比BP算法及本文簡化后的對數(shù)似然比BP算法，迭代次數(shù)定為20次，則未簡化的對數(shù)似然比BP算法和簡化后的對數(shù)似然比BP算法的性能仿真結(jié)果如圖2所示.

圖2　簡化后算法與未簡化算法的性能比較

通過圖2的仿真結(jié)果可以看出，簡化后的對數(shù)似然比BP算法與未簡化的對數(shù)似然比BP算法相比，誤碼率有較小的增加.當(dāng)信噪比小于1 dB時，兩種算法的性能是十分接近的，而隨著信噪比的不斷增加，簡化后的對數(shù)似然比BP算法的誤碼率略高于未簡化的對數(shù)似然比BP算法.當(dāng)誤碼率為2×10-4時，簡化后的對數(shù)似然比BP算法與未簡化的對數(shù)似然比BP算法相比，信噪比提高了約0.08 dB.

2.4譯碼算法計算次數(shù)的比較

比較對數(shù)似然比BP算法和簡化后的對數(shù)似然比BP算法可知，這兩種譯碼算法的區(qū)別就在于校驗節(jié)點更新的計算次數(shù)上.

通過比較這兩種算法校驗節(jié)點的更新表達(dá)式，可知這兩種算法的每次校驗節(jié)點更新的計算次數(shù)如下：

1）未簡化的對數(shù)似然比BP算法

對于未簡化的對數(shù)似然比BP算法，每次校驗節(jié)點更新計算，需要進行dcj-1次雙曲正切函數(shù)運算，1次反雙曲正切函數(shù)運算，dcj-1次符號運算，dcj-1次除法運算，dcj-1次乘法運算.

2）簡化后的對數(shù)似然比BP算法

對于簡化后的對數(shù)似然比BP算法，每次校驗節(jié)點更新計算，需要進行dcj次的雙曲正切函數(shù)的線性逼近運算，dcj-1次符號運算，dcj-1次除法運算，dcj-1次乘法運算.

通過上述譯碼算法計算復(fù)雜度的比較可以看出，簡化后的對數(shù)似然比BP算法與未簡化的對數(shù)似然比BP算法相比，在校驗節(jié)點更新過程中的計算復(fù)雜度有明顯的下降.可見，簡化后的對數(shù)似然比BP算法確實降低了運算的復(fù)雜難度.

3　簡化后的LDPC碼譯碼器的設(shè)計

3.1譯碼器的設(shè)計思路

LDPC碼譯碼器的設(shè)計，主要是由校驗節(jié)點、變量節(jié)點和Tanner圖上的連接關(guān)系所組成.通過Tan?ner圖可以看出，變量節(jié)點所得到的信息是由校驗節(jié)點所傳送的，變量節(jié)點將所得到的信息通過一定的計算，再將計算出的更新信息傳遞給校驗節(jié)點.同樣，校驗節(jié)點所得到的信息是由變量節(jié)點所傳送的，校驗節(jié)點將所得到的信息通過一定的計算，再將計算出的更新信息傳遞給變量節(jié)點.LDPC碼譯碼算法的核心就是迭代，其譯碼器的實質(zhì)就是校驗節(jié)點處理器（CNP）和變量節(jié)點處理器（VNP）進行計算并且將計算結(jié)果相互傳遞、更新的過程.在校驗節(jié)點處理器和變量節(jié)點處理器之間要加入一個中間信息存儲模塊，用來進行中間信息的存儲、控制和緩沖.另外，需要在校驗節(jié)點處理器和變量節(jié)點處理器之間設(shè)計一個控制模塊，以此來防止校驗節(jié)點處理器和變量節(jié)點處理器同時工作時所產(chǎn)生的沖突.

3.2變量節(jié)點處理器的設(shè)計

在實際設(shè)計的過程中，變量節(jié)點處理器不但需要完成校驗節(jié)點的更新處理功能，而且還應(yīng)該能夠完成信息的輸入和輸出功能.由于中間信息存儲器經(jīng)過初始化之后所存儲的數(shù)據(jù)全部為0，因此在經(jīng)過變量節(jié)點處理器的運算之后，所寫入的數(shù)據(jù)應(yīng)該是相應(yīng)的信道信息.另外，在時序的設(shè)計上還需注意，當(dāng)變量節(jié)點處理器從存儲器中讀取數(shù)據(jù)時，從存儲器的地址到讀到該地址所對應(yīng)的數(shù)據(jù)時會有一個時鐘周期的延時.圖3即為經(jīng)過QuartusⅡ8.0軟件編譯得到后的變量節(jié)點處理器時序仿真圖.

從圖3可以看出，中間信息存儲器的輸入信號和初始數(shù)據(jù)存儲器的輸入信號完全按照設(shè)計的時序每個時鐘周期都進行輸入.而經(jīng)過變量節(jié)點處理器運算之后得到的數(shù)據(jù)，大約每隔3個時鐘周期才會得到一個輸出.并且從圖3中也可以清楚地看到，輸出信號不但出現(xiàn)了一定的毛刺而且還出現(xiàn)了不定值.經(jīng)過檢查，功能符合設(shè)計的要求.

圖3　變量節(jié)點處理器時序仿真圖

3.3校驗節(jié)點處理器的設(shè)計

校驗節(jié)點處理器所完成的功能主要是校驗節(jié)點數(shù)據(jù)的更新，在電路設(shè)計中需要注意的問題是，由于校驗節(jié)點處理器所輸出的地址首先要經(jīng)過ROM才會輸入到中間信息存儲器，因此在時序方面會有兩個時鐘周期的延時.

圖4即為經(jīng)過QuartusⅡ8.0軟件編譯后得到的校驗節(jié)點處理器時序仿真圖.

從圖4可以看出，中間信息存儲器的輸入信號完全按照設(shè)計的時序每個時鐘周期都進行輸入.而經(jīng)過校驗節(jié)點處理器運算之后得到的數(shù)據(jù)，大約每隔5個時鐘周期才會得到一個輸出.從圖中還可清楚地看到，輸出信號不但出現(xiàn)了一定的毛刺而且還出現(xiàn)了不定值.經(jīng)過檢查，功能符合設(shè)計的要求.

圖4　校驗節(jié)點處理器時序仿真圖

3.4頂層模塊的設(shè)計

對所設(shè)計的所有模塊進行過仿真、且功能正確后，則對整個設(shè)計進行仿真.圖5即為經(jīng)過Quartus Ⅱ8.0軟件編譯后得到的頂層模塊時序仿真圖.

圖5　頂層模塊時序仿真圖

4　結(jié)語

由于LDPC碼的應(yīng)用十分廣泛，因此對LDPC碼的硬件設(shè)計就變得十分重要.如果要對LDPC碼進行硬件設(shè)計首先要考慮的就是采用何種編碼和譯碼算法.目前，編碼算法和譯碼算法有很多種，特別是譯碼算法：有些算法注重譯碼的速率，但譯碼的準(zhǔn)確度不高；有些算法注重譯碼的精度，但譯碼速率較慢，資源消耗較大，硬件難以實現(xiàn).本文正是根據(jù)這一問題，對LDPC碼的對數(shù)似然比BP算法進行了簡化.簡化后的算法較原算法相比，極大地降低了原算法的復(fù)雜度.并以簡化算法為基礎(chǔ)，以QuartusⅡ8.0為仿真平臺，設(shè)計了一種LDPC碼譯碼器.

[1]MacKay D JC,Neal R M.Near shannon limit performance of low density parity check codes[J].Electronics letters,1996,32（186）：1645-1646.

[2]Gallager R G.Low Density-Parity Check-Codes[M].Cambridge, MA：MITPress,1963.

[3]Tanner R M.A recursive approach to low complexity codes[J].IEEE Transactionson Information Theory,1981,27（9）：533-547.

[4]Wiberg N,Loeliger H A,Kotter R.Codes and iterative decoding on generalgraphs[J].Euro Trans Telecomm,1995,6（2）：513-525.

[5]Porcello,J C.Designing and implementing Low Density Parity Check（LDPC）decoders using FPGAs[C].Big Sky：Aerospace Con?ference.2014：1-7.doi：10.1109/AERO.2014.6836261.

[6]McEliece R J,MacKay D JC,Cheng JF.Turbo decoding as an in?stance of Pearl’s‘Belief Propagation’algprithm[J].IEEE Journal on Selected Areas in Communication,1998,16（2）：140-152.

[7]Hu X Y,Eleftheriou E,Arnold DM,etal.Efficient implementation?softhe sum-productalgorithm fordecoding LDPC codes[C].San An?tonio：GLOBECOM 2001-IEEE Global Telecommunications Con?ference.2001：1036-1041.

（編校：李青）

LDPCCode Decoding Algorithm and FPGA Design

LIShichao
（College ofPublic Security Technology,Gansu Institute ofPolitical Scienceand Law,Lanzhou,Gansu 730070,China）

The logarithmic likelihood ratio of BPalgorithm was introduced to LDPC code.The linear approximationmeth?od was used to simplify the hyperbolic tangentand inverse hyperbolic tangent function in the logarithmic likelihood ratio of BPalgorithm,which can reduce the numberof the algorithm.Based on the simplified logarithmic likelihood ratio of BP algorithm and Quartus II 8 software platform,using Verilog language for the design of LDPC decoder,the RTL gate-level circuitwas generated.The simulation results prove the correctness and hardware feasibility of the simplified logarithmic likelihood ratioof BPalgorithm.

low-density parity-check codes；the logarithmic likelihood ratio of BPalgorithm；linear approximation；FPGA decoder

TN929.53

A

1671-5365（2015）06-0076-05

2015-01-28修回：2015-03-09

李世超（1986-），男，助教，博士研究生，研究方向為無線通信

網(wǎng)絡(luò)出版時間：2015-03-17 17：16網(wǎng)絡(luò)出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20150317.1716.001.html

引用格式：李世超.LDPC碼譯碼算法研究與FPGA設(shè)計[J].宜賓學(xué)院學(xué)報,2015,15（6）：76-80.