一種改進(jìn)的LDPC碼譯碼算法

汪漢新，尹 超

(中南民族大學(xué)電子信息工程學(xué)院，武漢430074)

低密度奇偶校驗(yàn)碼(LDPC)具有較大靈活性及較低的錯(cuò)誤平層特性［1］，在碼長較長時(shí)，其譯碼性能甚至超過了Turbo碼，LDPC譯碼采用了線性復(fù)雜度的置信傳播(BP)算法，能夠?qū)崿F(xiàn)并行譯碼以及具有譯碼錯(cuò)誤可檢測的特點(diǎn)，與目前3G移動通信中使用的Turbo碼相比，LDPC碼更易于硬件實(shí)現(xiàn).然而短碼長的LDPC碼的Tanner圖中往往會出現(xiàn)短環(huán)，使得變量節(jié)點(diǎn)之間的信息不再相互獨(dú)立，導(dǎo)致BP算法的性能下降.針對此問題，本文提出了一種改進(jìn)的譯碼算法，可以加快算法的收斂速度，降低運(yùn)算量，減小譯碼延時(shí)，是一種兼顧性能與復(fù)雜度的折中譯碼算法.

1 LDPC碼的譯碼

LDPC碼的譯碼算法主要是基于雙向圖的消息傳遞算法(MPA)，其中最常用的是和積譯碼算法(SPA)，也稱為置信傳播(BP)算法［2］.

BP譯碼算法是基于Tanner結(jié)構(gòu)的信息傳遞算法，其核心思想在于利用從信道中接收到的信息在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間進(jìn)行迭代運(yùn)算，從而獲得最大的編碼增益.圖 1為(10，2，4)LDPC碼的Tanner圖，每個(gè)變量節(jié)點(diǎn)只和校驗(yàn)節(jié)點(diǎn)直接相連，而每個(gè)校驗(yàn)節(jié)點(diǎn)也只和變量節(jié)點(diǎn)直接相連.

1.1 對數(shù)域LLR BP譯碼算法

LLR BP算法將BP算法轉(zhuǎn)化到對數(shù)域，使大量的乘法運(yùn)算變?yōu)榧臃ㄟ\(yùn)算，減少了運(yùn)算量.LLR BP算法在每次的迭代過程中，所有校驗(yàn)節(jié)點(diǎn)從相鄰的變量節(jié)點(diǎn)接收信息，將這一信息處理后反饋給相鄰的變量節(jié)點(diǎn)，然后變量節(jié)點(diǎn)再對從校驗(yàn)節(jié)點(diǎn)反饋回來的信息進(jìn)行處理，并再次將處理后的信息反饋給相鄰的變量節(jié)點(diǎn)，最后根據(jù)變量節(jié)點(diǎn)的信息進(jìn)行判決.

圖1 (10，2，4)LDPC 碼的 Tanner圖Fig.1 Tanner graph for(10，2，4)LDPC

1.2 UMP BP-based 譯碼算法

雖然LLR BP算法性能優(yōu)異，但是在校驗(yàn)節(jié)點(diǎn)的更新過程中存在有非線性函數(shù)的計(jì)算，硬件實(shí)現(xiàn)時(shí)，主要是采用查找表的方法來實(shí)現(xiàn)，對非線性函數(shù)的量化直接影響到查找表的精度及復(fù)雜度，從而會影響到譯碼的性能與硬件的復(fù)雜度［3］.為了平衡譯碼的性能與硬件實(shí)現(xiàn)的復(fù)雜度，人們提出了很多簡化的BP譯碼算法，文獻(xiàn)［3-5］提出的UMP BP-based算法(最小和算法)，對校驗(yàn)節(jié)點(diǎn)消息進(jìn)行了簡化處理，用比較運(yùn)算代替了非線性運(yùn)算，同時(shí)避免了各變量節(jié)點(diǎn)的初始化計(jì)算，大大降低了運(yùn)算量.

2 改進(jìn)的LDPC譯碼算法

UMP BP-based算法與LLR BP算法相比，其運(yùn)算復(fù)雜度得到了降低，但是其抗干擾能力也有一定程度的降低［3，6］.文獻(xiàn)［7］針對其性能的損失，在對校驗(yàn)節(jié)點(diǎn)信息處理時(shí)，分別通過乘性因子和加性因子進(jìn)行修正，使UMP BP-based算法的抗干擾能力性能有所改善，但其主要是針對校驗(yàn)節(jié)點(diǎn)信息進(jìn)行處理.本文改進(jìn)的譯碼算法主要是針對變量節(jié)點(diǎn)的信息處理，即在BP-Based算法的基礎(chǔ)上，對變量節(jié)點(diǎn)的處理通過偏移因子來校正變量節(jié)點(diǎn)信息的迭代更新，用于降低由短環(huán)引入的變量節(jié)點(diǎn)消息之間的相關(guān)性，從而改善譯碼性能.設(shè) c=(c1，c2，…，cN)碼字經(jīng)過BPSK調(diào)制映射為傳輸序列x=(x1，x2，…，xn)送入到 AWGN信道傳輸，接收序列為 y=(y1，y2，…，yn).根據(jù)y譯碼得到譯碼序列為.改進(jìn)的譯碼算法步驟為:

(1)初始化.對每一個(gè)變量節(jié)點(diǎn)i，設(shè)變量節(jié)點(diǎn)傳向校驗(yàn)節(jié)點(diǎn)的初始消息:

(2)迭代處理.

a)校驗(yàn)節(jié)點(diǎn)處理.

b)變量節(jié)點(diǎn)處理.

c)譯碼判決.

對所有的變量節(jié)點(diǎn)消息進(jìn)行硬判決，若L(Qi)＞0，則ci=0，否則=1.

(3)迭代停止準(zhǔn)則.如果H=0或達(dá)到設(shè)定的最大迭代次數(shù)，則迭代結(jié)束，否則回到步驟(2).

上述算法中，Rj表示校驗(yàn)矩陣中第j行中包含的比特所形成的集合;Rji表示在Rj中除去第i個(gè)比特形成的集合;Ci表示校驗(yàn)矩陣中第i列所參與的校驗(yàn)矩陣形成的集合;Cji表示在Ci中除去第j個(gè)校驗(yàn)方程形成的集合;rji(b)表示在碼字中第i個(gè)比特ci=b和碼字中其它比特服從分布{qij'}j'≠j的情況下，第j個(gè)校驗(yàn)方程滿足的條件概率;qij(b)表示除第j個(gè)校驗(yàn)節(jié)點(diǎn)之外其它校驗(yàn)節(jié)點(diǎn)提供外信息的情況下第i個(gè)信息節(jié)點(diǎn)ci=b的概率;χ為偏移因子.

3 仿真結(jié)果及分析

實(shí)驗(yàn)中均采用(1008，3，6)LDPC碼，在BPSK調(diào)制，AWGN信道環(huán)境下進(jìn)行仿真測試.

3.1 譯碼算法復(fù)雜度比較

采用不同譯碼算法進(jìn)行仿真，表1給出了LLR BP算法、UMP BP-based算法以及本文改進(jìn)BP算法譯碼迭代一次的運(yùn)算量.由表1可知，改進(jìn)的譯碼算法相比LLR BP算法，減少了復(fù)雜的乘法和除法運(yùn)算量，運(yùn)算量大大的降低.但與BP-based算法相比，運(yùn)算量有所增加.

表1 不同譯碼算法運(yùn)算量比較Tab.1 Computation for difference decoding algorithms

3.2 不同偏移因子的譯碼性能分析

在迭代5次，信噪比分別為 2.0dB、2.5 dB 及3.0 dB時(shí)，偏移因子χ取不同的值，仿真得到譯碼性能曲線，如圖2所示.在改進(jìn)的譯碼算法下，隨著信噪比的增加，不同的偏移因子對誤碼率的影響也加大，而且在等信噪比時(shí)當(dāng)χ的取值為0.7，得到的誤碼率最小，譯碼性能達(dá)到最佳.

圖2 偏移因子的取值對BER性能的影響Fig.2 Effect of different factor for the BER performance

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

在最大迭代15次時(shí)，分別利用LLR BP算法、UMP BP-based算法以及本文中χ=0.7的改進(jìn)算法進(jìn)行譯碼得到的BER性能曲線，如圖3所示.由圖可知，3種譯碼算法在高信噪比時(shí)都可呈現(xiàn)出較低的誤碼率.LLR BP算法的誤碼率性能相對較好;BPBased算法由于對校驗(yàn)消息節(jié)點(diǎn)的處理進(jìn)行了簡化，從而造成性能上的損失，使得性能最差;而改進(jìn)的譯碼算法通過變量消息節(jié)點(diǎn)處理時(shí)的加性校正，使得性能得到了一定的改善.

圖3 LLR BP，BP-based和改進(jìn)算法的性能比較Fig.3 Comparison of performance for different algorithms

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

在最大迭代次數(shù)設(shè)為50次，LLR BP算法、BPBased算法、本文改進(jìn)算法的誤碼率為10－7時(shí)的平均迭代次數(shù)，如圖4所示(其中本文改進(jìn)算法的χ取0.7).由圖可知，改進(jìn)的譯碼算法相比與BP-Based算法，平均迭代次數(shù)大大的降低，從而減小了譯碼的延時(shí)，且相比與LLR BP算法而言，平均迭代次數(shù)幾乎相當(dāng)，這表明改進(jìn)的譯碼算法與運(yùn)算復(fù)雜度較低的BP-Based算法相比，加快了譯碼的收斂速度.

圖4 不同譯碼算法下的平均迭代次數(shù)Fig.4 Average iteration numbers of different decoding algorithms

4 結(jié)語

本文提出的改進(jìn)LDPC的譯碼算法，一方面總的運(yùn)算量比LLR BP算法低，減小了譯碼的復(fù)雜度;譯碼性能要比BP-Based算法好，提高了抗干擾能力;另一方面平均迭代次數(shù)低于BP-Based算法，降低了譯碼延時(shí)，加快了譯碼收斂速度;本文的改進(jìn)譯碼算法具有一定的實(shí)用價(jià)值.

［1］Gallager G.Low density parity check codes［J］.IEEE Transaction on Information Theory，1962，8(3):208-220.

［2］MacKay C，Neal M.Near shannon limit performance of low density parity check codes［J］.IEEE Electronics Letters，1996，32(18):1645-1646.

［3］Fossorier M，Mihaljevic M ，Imai H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation［J］.IEEE Transaction on Communication，1999，47(5):673-680.

［4］Chen J，F(xiàn)ossorier M.Near optimum universal belief propagation based decoding of LDPC codes［J］.IEEE Transaction on Communication，2002，50(3):406-414.

［5］Zarkeshvari F ，Banihashemi A.On implementation of min-sum algorithm for decoding low-density parity-check(LDPC)codes［C］//IEEE.IEEE Globecom 2002.Ottawa:Carleton University，2002:1349-1353.

［6］Yazdani R ，Hemati S.Improving belief propagation on graphs with cycles ［J］.IEEE Communications Letters，2004，8(1):57-59.

［7］Chen J，F(xiàn)ossorier M.Density evolution for two improved BP-based decoding algorithms of LDPC codes［J］.IEEE Communication Letters，2002，6(5):208-210.