高速數據傳輸中的LDPC碼譯碼算法研究

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

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

0 引言

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

1 LDPC碼譯碼算法

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

1.1 LLR-BP算法

1.1.1 初始化

根據接收信號計算變量節點的初始對數域的概率信息L(Pi),i=1,2,…,N,初始化完成后,設定傳向與每一個變量節點i相鄰的校驗節點j(j∈C(i))的對數域的外部概率信息,即

1.1.2 校驗節點到變量節點信息更新

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

式中,l為迭代次數。

1.1.3 變量節點到校驗節點信息更新

變量節點i得到與之相鄰的校驗節點傳來的外部概率信息后進行信息更新,并將更新結果傳給所有與變量節點i相鄰的校驗節點。更新公式為:

1.1.4 譯碼判決

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

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

1.2 最小和譯碼算法

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

1.3 改進最小和算法

如果將最小和譯碼算法的變量信息前面乘以一修正因子,這樣不但能降低校驗節點消息處理的復雜度,還能補償變量節點消息之間的相關性,其更新公式為:

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

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

②校驗節點到變量節點信息更新。同最小和算法;

③變量節點到校驗節點信息更新;

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

圖1 改進最小和譯碼算法流程

2 算法仿真分析

2.1 譯碼算法復雜度分析

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

表1 不同譯碼算法計算量比較

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

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

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

圖2 改進最小和算法修正因子對誤碼率影響曲線

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

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

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

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

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

2.4 不同算法的平均迭代次數分析

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

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

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

2.5 譯碼吞吐量分析

為了分析改進譯碼算法的譯碼吞吐量,現將該譯碼算法應用在時鐘為150 MHz的某高速系統中,在該系統中選用碼長為8 064 bit,碼率為7/8的準循環LDPC碼,譯碼器采用并行交迭的譯碼結構,在該結構中變量信息迭代和校驗信息迭代共需要336*2=672個時鐘周期,再加上延遲保護的24個時鐘,所以每次迭代需要672+24=696個時鐘周期。由上述分析可知,選用15次迭代就可以達到系統所需的誤碼率要求,故共需要15*696=10 440個時鐘周期,再加入初始化所需的時鐘周期,最終譯碼共需要11 448個時鐘周期。因此吞吐量可達到8 064*7/8*150*2/11 448=184.906 Mbps。

3 結束語

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

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

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

[3]張靖琳,劉榮科,趙 嶺.高碼率LDPC碼譯碼器的優化設計與實現[J].電子與信息學報,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.