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

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

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

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

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

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

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

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

1　LDPC碼譯碼算法簡(jiǎn)介

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

1.1BP迭代譯碼算法原理

LDPC碼所采用的BP迭代譯碼算法，簡(jiǎn)單的說，就是信道估計(jì)和接收信號(hào)在給定的條件下，每迭代一次，都對(duì)有噪序列的每一個(gè)符號(hào)估算其后驗(yàn)概率，再將所得到的結(jié)果輸入下一次進(jìn)行迭代，來獲得更好的結(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)點(diǎn)：第一，在BP迭代譯碼算法中，并不是進(jìn)行固定次數(shù)的迭代，而是當(dāng)試驗(yàn)譯碼得到成功時(shí)，譯碼就立刻結(jié)束.這樣就大大減少了迭代的次數(shù).第二，BP算法的復(fù)雜度較低，計(jì)算量不會(huì)因?yàn)榇a長(zhǎng)的增加而增加.第三，由于該算法是一種并行算法，所以當(dāng)硬件實(shí)現(xiàn)該算法時(shí)，可以提高譯碼速率.

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

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

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

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

1）初始化

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

2）迭代處理

①校驗(yàn)節(jié)點(diǎn)的更新

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

上式也可寫為：

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

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

③判決譯碼

計(jì)算所有變量節(jié)點(diǎn)的判決消息：

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

3）停止

2　對(duì)數(shù)似然比BP算法的簡(jiǎn)化

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

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

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

則式（6）可寫為

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

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

2.2對(duì)數(shù)似然比BP算法的簡(jiǎn)化

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

則簡(jiǎn)化后的校驗(yàn)節(jié)點(diǎn)的更新可寫為：

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

2.3簡(jiǎn)化后的譯碼算法的性能仿真及分析

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

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

圖2　簡(jiǎn)化后算法與未簡(jiǎn)化算法的性能比較

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

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

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

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

1）未簡(jiǎn)化的對(duì)數(shù)似然比BP算法

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

2）簡(jiǎn)化后的對(duì)數(shù)似然比BP算法

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

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

3　簡(jiǎn)化后的LDPC碼譯碼器的設(shè)計(jì)

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

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

3.2變量節(jié)點(diǎn)處理器的設(shè)計(jì)

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

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

圖3　變量節(jié)點(diǎn)處理器時(shí)序仿真圖

3.3校驗(yàn)節(jié)點(diǎn)處理器的設(shè)計(jì)

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

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

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

圖4　校驗(yàn)節(jié)點(diǎn)處理器時(shí)序仿真圖

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

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

圖5　頂層模塊時(shí)序仿真圖

4　結(jié)語

由于LDPC碼的應(yīng)用十分廣泛，因此對(duì)LDPC碼的硬件設(shè)計(jì)就變得十分重要.如果要對(duì)LDPC碼進(jìn)行硬件設(shè)計(jì)首先要考慮的就是采用何種編碼和譯碼算法.目前，編碼算法和譯碼算法有很多種，特別是譯碼算法：有些算法注重譯碼的速率，但譯碼的準(zhǔn)確度不高；有些算法注重譯碼的精度，但譯碼速率較慢，資源消耗較大，硬件難以實(shí)現(xiàn).本文正是根據(jù)這一問題，對(duì)LDPC碼的對(duì)數(shù)似然比BP算法進(jìn)行了簡(jiǎn)化.簡(jiǎn)化后的算法較原算法相比，極大地降低了原算法的復(fù)雜度.并以簡(jiǎn)化算法為基礎(chǔ)，以QuartusⅡ8.0為仿真平臺(tái)，設(shè)計(jì)了一種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-），男，助教，博士研究生，研究方向?yàn)闊o線通信

網(wǎng)絡(luò)出版時(shí)間：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ì)[J].宜賓學(xué)院學(xué)報(bào),2015,15（6）：76-80.