高速數(shù)據(jù)傳輸中的LDPC碼譯碼算法研究

魏瑞剛,陳 暉,邱金蕙,郝志松,雷光雄

(1.中國電子科技集團(tuán)公司第五十四研究所,河北石家莊050081;2.河北醫(yī)科大學(xué)第三醫(yī)院,河北石家莊050051)

0 引言

LDPC碼是線性分組碼中的一種,它具有接近香農(nóng)限的性能,同時(shí)具有更低的線性譯碼復(fù)雜度,而且描述簡(jiǎn)單,對(duì)嚴(yán)格的理論分析具有可驗(yàn)證性,在長(zhǎng)碼時(shí)其性能甚至超過了Turbo碼,具有較大的靈活性和較低的差錯(cuò)地板特性。此外,LDPC碼譯碼復(fù)雜度低于Turbo碼,可實(shí)現(xiàn)完全的并行操作,便于硬件實(shí)現(xiàn),吞吐量大,極具高速譯碼潛力。

1 LDPC碼譯碼算法

LDPC碼的校驗(yàn)矩陣H可以用Tanner(泰勒)圖表示,校驗(yàn)矩陣H的行與Tanner圖中的變量節(jié)點(diǎn)有關(guān),校驗(yàn)矩陣 H的列與Tanner圖中的校驗(yàn)節(jié)點(diǎn)有關(guān),每一個(gè)校驗(yàn)節(jié)點(diǎn)都有一條或多條線與變量節(jié)點(diǎn)相連,這種線被稱為邊,它代表每一個(gè)校驗(yàn)方程中具體參與的信息位,它與奇偶校驗(yàn)矩陣中的“1”是一一對(duì)應(yīng)的。

1.1 LLR-BP算法

1.1.1 初始化

根據(jù)接收信號(hào)計(jì)算變量節(jié)點(diǎn)的初始對(duì)數(shù)域的概率信息L(Pi),i=1,2,…,N,初始化完成后,設(shè)定傳向與每一個(gè)變量節(jié)點(diǎn)i相鄰的校驗(yàn)節(jié)點(diǎn)j(j∈C(i))的對(duì)數(shù)域的外部概率信息,即

1.1.2 校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)信息更新

校驗(yàn)節(jié)點(diǎn)j得到與之相鄰的變量節(jié)點(diǎn)傳來的外部概率信息后進(jìn)行信息更新,并將更新結(jié)果傳給所有與校驗(yàn)節(jié)點(diǎn)j相鄰的變量節(jié)點(diǎn)。更新公式為:

式中,l為迭代次數(shù)。

1.1.3 變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)信息更新

變量節(jié)點(diǎn)i得到與之相鄰的校驗(yàn)節(jié)點(diǎn)傳來的外部概率信息后進(jìn)行信息更新,并將更新結(jié)果傳給所有與變量節(jié)點(diǎn)i相鄰的校驗(yàn)節(jié)點(diǎn)。更新公式為:

1.1.4 譯碼判決

每次迭代譯碼的最后,進(jìn)行一次硬判決譯碼。判決公式為:

若L(l)(qi)＞0則否則

1.2 最小和譯碼算法

如果對(duì)校驗(yàn)節(jié)點(diǎn)信息更新處理算法做一近似處理,如式(5)所示,則稱為最小和譯碼算法,最小和譯碼的其他步驟和LLR-BP算法一樣。

1.3 改進(jìn)最小和算法

如果將最小和譯碼算法的變量信息前面乘以一修正因子,這樣不但能降低校驗(yàn)節(jié)點(diǎn)消息處理的復(fù)雜度,還能補(bǔ)償變量節(jié)點(diǎn)消息之間的相關(guān)性,其更新公式為:

改進(jìn)最小和譯碼算法的流程圖如圖1所示,具體步驟如下:

①初始化。同LLR-BP算法;

②校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)信息更新。同最小和算法;

③變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)信息更新;

④譯碼判決。同LLR-BP算法。

圖1 改進(jìn)最小和譯碼算法流程

2 算法仿真分析

2.1 譯碼算法復(fù)雜度分析

為了對(duì)比LLR-BP算法、最小和算法、改進(jìn)BP算法的計(jì)算復(fù)雜度,現(xiàn)選用碼率為1/2、碼長(zhǎng)為8 064 bit的(3,6)LDPC碼,得出在各種譯碼算法下的1次迭代運(yùn)算量,如表1所示。

表1 不同譯碼算法計(jì)算量比較

由表1可以看出,8 064 bit的LDPC碼在各種譯碼算法下的1次迭代運(yùn)算,運(yùn)算量最小的是最小和算法,改進(jìn)最小和算法比最小和算法多了24 192次的實(shí)數(shù)乘法運(yùn)算,LLR-BP算法的運(yùn)算量比較大。

2.2 不同修正因子的譯碼性能分析

為了分析改進(jìn)譯碼算法中的修正因子α對(duì)譯碼性能的影響,現(xiàn)選用碼長(zhǎng)為8 064 bit、碼率為1/2的(3,6)LDPC碼,仿真得到信噪比分別為0.5 dB、1.0 dB和1.5 dB時(shí),不同修正因子α的譯碼性能曲線如圖2所示。

圖2 改進(jìn)最小和算法修正因子對(duì)誤碼率影響曲線

由圖2可以看出在改進(jìn)型最小和譯碼算法下,隨著信噪比的增加,不同的修正因子對(duì)誤碼率的影響也加大,而且在等信噪比時(shí)當(dāng)α取0.8時(shí),得到的誤碼率最小,譯碼性能最好。

2.3 不同算法的譯碼性能分析

為了對(duì)比LLR-BP算法、最小和算法、改進(jìn)的最小和算法的性能,現(xiàn)選用碼長(zhǎng)為8 064 bit、碼率為1/2的LDPC碼采用BPSK調(diào)制,在高斯白噪聲信道下最大迭代次數(shù)為15次時(shí)(其中改進(jìn)最小和譯碼算法的修正因子取0.8)仿真得到的誤碼率性能曲線如圖3所示。

圖3 不同譯碼算法下的譯碼性能曲線

由圖3可以看出LLR-BP算法、最小和算法、改進(jìn)型譯碼算法在高信噪比時(shí)均可呈現(xiàn)較低的誤碼率,其中LLR-BP算法的誤碼率較好,最小和算法通過簡(jiǎn)化校驗(yàn)節(jié)點(diǎn)信息的處理造成了性能上的損失,改進(jìn)型譯碼算法通過修正變量節(jié)點(diǎn)的數(shù)據(jù)可以使性能得到較好的提高。

2.4 不同算法的平均迭代次數(shù)分析

現(xiàn)選用碼長(zhǎng)為8 064 bit、碼率為1/2的 LDPC碼,最大迭代次數(shù)為50,LLR-BP算法、最小和算法、改進(jìn)的最小和譯碼算法 3種不同算法誤碼率在10-7時(shí)的平均迭代次數(shù)曲線如圖4所示(其中改進(jìn)最小和譯碼算法的修正因子取0.8)。

圖4 不同譯碼算法下的平均迭代次數(shù)曲線

由圖4可以看出,LLR-BP算 法、最小和算法、改進(jìn)型譯碼算法這3種譯碼算法的平均迭代次數(shù)都隨著Eb/N0的增加而下降,且在相同情況下,改進(jìn)型譯碼算法的平均迭代次數(shù)幾乎與LLR-BP算法相同,這表明改進(jìn)型譯碼算法相比復(fù)雜度較低的最小和算法加快了譯碼收斂的速度。

2.5 譯碼吞吐量分析

為了分析改進(jìn)譯碼算法的譯碼吞吐量,現(xiàn)將該譯碼算法應(yīng)用在時(shí)鐘為150 MHz的某高速系統(tǒng)中,在該系統(tǒng)中選用碼長(zhǎng)為8 064 bit,碼率為7/8的準(zhǔn)循環(huán)LDPC碼,譯碼器采用并行交迭的譯碼結(jié)構(gòu),在該結(jié)構(gòu)中變量信息迭代和校驗(yàn)信息迭代共需要336*2=672個(gè)時(shí)鐘周期,再加上延遲保護(hù)的24個(gè)時(shí)鐘,所以每次迭代需要672+24=696個(gè)時(shí)鐘周期。由上述分析可知,選用15次迭代就可以達(dá)到系統(tǒng)所需的誤碼率要求,故共需要15*696=10 440個(gè)時(shí)鐘周期,再加入初始化所需的時(shí)鐘周期,最終譯碼共需要11 448個(gè)時(shí)鐘周期。因此吞吐量可達(dá)到8 064*7/8*150*2/11 448=184.906 Mbps。

3 結(jié)束語

改進(jìn)的譯碼算法一方面由于校驗(yàn)消息的處理簡(jiǎn)化為只有加法運(yùn)算,同時(shí)對(duì)變量消息進(jìn)行乘性校正,故總的運(yùn)算量要低于LLR-BP算法,譯碼性能要高于最小和算法,這在譯碼性能和計(jì)算復(fù)雜度之間達(dá)到了較好的折中;另一方面改進(jìn)的譯碼算法在相同的誤碼率的情況下譯碼的平均迭代次數(shù)略低于LLR-BP算法,這改善了算法的收斂特性,降低了譯碼延遲。因此改進(jìn)的譯碼算法不但較好地降低了譯碼復(fù)雜度,而且依然可以得到高吞吐量,這在高速譯碼中具有廣泛的應(yīng)用前景。

[1]GALLAGER R G.Low-Density Parity-Check Codes[M].Cambridge,MA:MIT Press,1963.

[2]鐘 州,李云洲.基于LDPC碼校驗(yàn)節(jié)點(diǎn)度的分類修正最小和算法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,49(1):45-48.

[3]張靖琳,劉榮科,趙 嶺.高碼率LDPC碼譯碼器的優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)[J].電子與信息學(xué)報(bào),2009,31(1):83-86.

[4]LI Z W,VIJAYA KUMAR B V K.A Class of Good Quasicyclic Low-density Parity Check Codes Based on Progressive Edge Growth Graph[C]//Signals,Systems and Computers Conference Record of the Thirty-Eighth Asi-lomar Conference on,2004:1990-1994.

[5]FOSSORIERM,MIHALJEVIC M,LMAIH.Reduced Complexity Iterative Decoding of Low Density Parity Check Codes Based on Belief Propagation[C].IEEE Transactions on Communications,1999:673-680.

[6]張金貴,斐文端,許星辰.一種提高LDPC譯碼器吞吐率的譯碼算法[J].無線電工程,2008,38(6):49-52.