兩種降低復雜度的符號翻轉(zhuǎn)多元LDPC譯碼算法

陳海強 王瑤玲 韋文娟 蔣炳旭 孫友明 黎相成 覃團發(fā)

(廣西大學計算機與電子信息學院 南寧 530004)

(廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室 南寧 530004)

1 引言

與2元低密度奇偶校驗碼(Low Density Parity Check code, LDPC)相比較，構(gòu)建在 q階有限域上的多元LDPC碼[1]具有更加優(yōu)秀的譯碼性能，特別在碼長較短、碼率較大時，其優(yōu)勢更加明顯。然而，多元LDPC碼的性能增益往往是以高譯碼復雜度作為代價換取的。降低多元LDPC譯碼復雜度的主要思路是降低Tanner圖上參與運算的節(jié)點數(shù)量以及每個節(jié)點的運算操作。經(jīng)典的降低復雜度的多元LDPC譯碼算法包括基于概率域的和積(Q-ary Sum Product Algorithm, QSPA)算法[2,3]以及基于擴展最小和(Extended Min-Sum, EMS)的譯碼算法[4]及其改進版本[5-8]。此外，基于大數(shù)邏輯(Majority-LoGic Decoding, MLGD)的簡化譯碼算法[9-12]，也能達到降低譯碼復雜度的目的。

基于符號翻轉(zhuǎn)的譯碼算法(Symbol Flipping Decoding, SFD)是另一類重要的簡化譯碼算法，能在性能和復雜度之間進行有效的折中。最初的SFD算法是文獻[13]提出的廣義Gallager算法B(Gallager’s Algorithm B, AlgB)及其改進版算法(weighted-Algorithm B, wtd-AlgB)。AlgB算法具有很低的譯碼復雜度，但性能較差；wtd-AlgB算法結(jié)合了漢明距離和多數(shù)邏輯(plurality-logic)準則，獲得一定的性能增益。其他傳統(tǒng)的SFD算法還包括文獻[14]的并行符號翻轉(zhuǎn)算法(Parallel Symbol Flipping Decoding algorithm, PSFD)以及基于投票機制的符號翻轉(zhuǎn)算法[15,16]等。2017年，Wang等人[17]提出了基于距離和預測機制的符號翻轉(zhuǎn)(Distance-Symbol Flipping Decoding with Prediction, D-SFDP)算法，與傳統(tǒng)的SFD算法不一樣，D-SFDP算法不僅考慮了符號翻轉(zhuǎn)之前的信息，還把翻轉(zhuǎn)后引起的目標函數(shù)變化考慮進來，以此預測和翻轉(zhuǎn)迭代過程中的硬判決符號。與非預測的符號翻轉(zhuǎn)算法相比，D-SFDP算法能獲得明顯的性能提升。2018年，Mu等人[18]提出了一種基于迭代停止準則的加權(quán)符號翻轉(zhuǎn)譯碼算法，提高了譯碼算法的收斂速度。2019年，Dai等人[19]對D-SFDP算法進行了改進，修正了算法的本地循環(huán)震蕩問題，Oh等人[20]提出了一種基于判決符號可靠性的符號翻轉(zhuǎn)譯碼算法。

雖然D-SFDP算法具有優(yōu)秀的譯碼性能，但仍是以犧牲一定的復雜度換來的。特別地，由于D-SFDP算法每次只能翻轉(zhuǎn)1個符號，這導致其平均迭代次數(shù)遠遠高于其他同類算法。因此，降低該算法每次迭代的復雜度很有必要。本文首先提出一種基于加性參數(shù)的改進型wtd-AlgB算法，通過調(diào)整距離參數(shù)避免了乘性操作，從而降低復雜度；其次，本文提出一種基于截斷型的預測機制符號翻轉(zhuǎn)譯碼算法(Truncation-based Distance-Symbol-Flipping-Decoding with Prediction, TD-SFDP)，結(jié)合翻轉(zhuǎn)函數(shù)和變量節(jié)點參數(shù)特征對節(jié)點進行截斷與劃分，使得只有滿足條件的節(jié)點參與迭代運算。此外，基于外信息頻率對預測符號進行截斷，只選取最可能的有限域符號進行翻轉(zhuǎn)和預測。仿真和數(shù)值結(jié)果顯示，TD-SFDP算法能夠在性能損失可控前提下，減少每次迭代的運算操作數(shù)，從而降低算法譯碼復雜度。

2 系統(tǒng)模型和符號定義

3 低復雜度符號翻轉(zhuǎn)多元LDPC譯碼

3.1 基于加性參數(shù)的改進型wtd-AlgB算法

文獻[13]提出了一種基于符號翻轉(zhuǎn)的加權(quán)多元LDPC譯碼算法(wtd-AlgB)：把漢明距離和多數(shù)邏輯準則進行結(jié)合，統(tǒng)一形成硬判決符號的可靠度量。但該算法性能受門限值和加權(quán)系數(shù)的影響較大，并且每次判決都需大量的實數(shù)域乘法操作。為降低算法復雜度和硬件實現(xiàn)能耗，在此對原算法進行修正和改進，描述如下：

基于上述信息處理的算法簡稱為Iwtd-AlgB，描述如表1所示。

本文后續(xù)的仿真實驗顯示，當把距離參數(shù)調(diào)整到合適范圍，改進的Iwtd-AlgB算法在譯碼性能上與原算法相當，但改進算法避免了浮點乘法運算，降低了每次迭代的計算能耗。

表1 Iwtd-AlgB算法

3.2 基于截斷型的預測機制符號翻轉(zhuǎn)譯碼算法(TDSFDP)

文獻[17]提出一種結(jié)合了漢明距離參數(shù)和預測機制的多元LDPC符號翻轉(zhuǎn)譯碼算法(D-SFDP)。與傳統(tǒng)的廣義Gallager算法B(AlgB)及其基于距離的改進版(wtd-AlgB)不一樣，D-SFDP譯碼算法有兩個顯著特征。首先，D-SFDP算法不僅考慮了符號翻轉(zhuǎn)之前的距離度量，還把符號翻轉(zhuǎn)后引起的目標函數(shù)的變化考慮進來，使得譯碼器能夠根據(jù)這種變化估計和預測最可能翻轉(zhuǎn)的符號。其次，D-SFDP算法不使用簡單的伴隨式而是基于外信息來計算距離參數(shù)。這樣，每個校驗節(jié)點到變量節(jié)點的可靠度量信息即可區(qū)分開來。同時，由于漢明距離源于有限域符號的二進制表示，D-SFDP算法實際上也結(jié)合了有限域的結(jié)構(gòu)特征。仿真顯示，D-SFDP算法能夠獲得比傳統(tǒng)符號翻轉(zhuǎn)算法更加優(yōu)秀的譯碼性能。

表2 TD-SFDP算法

4 復雜度分析

表3 譯碼算法每次迭代的計算復雜度比較

表4 F 16(255,175)多元LDPC碼的每次迭代譯碼算法復雜度

5 譯碼性能仿真實驗

譯碼性能如圖1所示，由圖可見：(1)本文提出的Iwtd-AlgB算法與wtd-AlgB算法性能相當，但由于避免了譯碼過程中的乘法操作，因此降低了每次迭代的計算復雜度；(2)D-SFDP算法和P-SFDP算法性能相當(差距在0.1 dB以內(nèi))，且由于沒有進行截斷處理，其性能表現(xiàn)最佳；(3)經(jīng)不同程度截斷處理的TD-SFDP算法存在不同程度的性能損失。具體地，當 T1=T2=0 時對應原算法；隨著T1, T2的增大，算法的復雜度將得到優(yōu)化(下降)，但也會帶來性能上的下降。例如：在BER=10-4時，門限值T1=4, T2=2 和T1=4, T2=3的TD-SFDP算法，其性能分別比D-SFDP算法下降了0.18 dB和0.25 dB。

圖1 F 16(225,147)多元準循環(huán)LDPC碼譯碼性能

算法平均迭代次數(shù)如圖2所示，由圖2可見：(1)在中低信噪比區(qū)域，D-SFDP算法，P-SFDP算法和小門限值的TD-SFDP算法平均迭代次數(shù)相當，但低于門限值較大的TD-SFDP算法。例如，在SNR=4.0 dB時， T1=4, T2=3的TD-SFDP算法的平均迭代次數(shù)約為46 次；明顯大于原算法的37次；(2)在高信噪比區(qū)域，D-SFDP, P-SFDP算法和TD-SFDP算法的迭代次數(shù)基本一致；(3)在高信噪比區(qū)域，wtd-AlgB算法與本文的Iwtd-AlgB算法的平均迭代次數(shù)更小，這是因為D-SFDP, P-SFDP算法和TD-SFDP算法每次迭代只允許翻轉(zhuǎn)1個符號。

實驗2 考慮基于有限幾何構(gòu)造的F16(255,175)規(guī) 則準循環(huán)LDPC碼[23]，該碼行重ρ =16，列重 γ =16 ，碼率R =0.68。參數(shù)設(shè)置如下：(1)對于wtd-AlgB算法，距離參數(shù) θ =(2.1,2.0,1.0,1.0)，對于Iwtd-AlgB算法， θ =(4.0,3.5,1.0,1.0)；(2)對于D-SFDP算法和TD-SFDP算法，距離參數(shù)統(tǒng)一選取為θ =(3.0,1.4,1.2,1.0)； (3)對于P-SFDP算法，η =(0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0,1.2, 1.3, 1.4, 1.5, 2.0, 2.0)為其外信息加權(quán)系數(shù)。各算法的門限參數(shù)在圖上標出。

譯碼性能和迭代次數(shù)如圖3和圖4所示，由圖可觀察到類似的結(jié)果，即本文提出的兩種降低復雜度的多元LDPC符號翻轉(zhuǎn)譯碼算法與原算法相比，在適當?shù)膮?shù)設(shè)置下，譯碼性能保持不變或者以犧牲一定性能為代價，換取復雜度方面的降低。具體地：(1)結(jié)合了外信息和距離參數(shù)的Iwtd-AlgB符號翻轉(zhuǎn)算法與wtd-AlgB算法的性能相當；(2) D-SFDP 算法和P-SFDP算法性能最佳，均優(yōu)于Iwtd-AlgB算法，在 BER=10?4時獲得了約0.9 dB的性能增益；(3)經(jīng)不同程度截斷處理的TD-SFDP算法存在不同程度的性能損失，門限值T1, T2越大，性能下降越多。在算法的平均迭代次數(shù)方面，也得到與實驗1類似的結(jié)果。

圖2 F 16(225,147)多元準循環(huán)LDPC碼平均迭代次數(shù)

圖3 F 16(255,175)多元準循環(huán)LDPC碼譯碼性能

圖4 F 16(255,175)多元準循環(huán)LDPC碼平均迭代次數(shù)

6 結(jié)論

本文提出了兩種基于符號翻轉(zhuǎn)的低復雜度多元LDPC譯碼算法，Iwtd-AlgB算法將翻轉(zhuǎn)度量函數(shù)修正為外信息頻率和距離參數(shù)的簡單求和，降低了復雜度；TD-SFDP算法根據(jù)參數(shù)和外信息特征對節(jié)點和有限域符號進行截斷與劃分，使得只有部分比例的節(jié)點和符號參與迭代過程中的處理和翻轉(zhuǎn)預測，從而降低每次迭代的譯碼復雜度。仿真結(jié)果表明：兩種改進算法的譯碼性能與原算法相差不大，適當調(diào)整參數(shù)，可在性能和復雜度之間進行折中。復雜度數(shù)據(jù)顯示，第1種算法避免了原算法的實數(shù)乘法操作；第2種算法的有限域加法運算次數(shù)約為原算法的 35%，整數(shù)/實數(shù)加法運算次數(shù)約為原算法的 40%。此外，本文提出的截斷閾值基于外信息頻率設(shè)計，仍屬于多數(shù)邏輯范疇，因此對于列重較大LDPC碼的復雜度降低效果尤為明顯；當列重減少時，截斷集合的階與原算法參與運算的節(jié)點/符號數(shù)目基本一致，其復雜度降低效果有限。