焦冬莉，譚艷麗，趙永強，薄曉寧

(太原工業(yè)學院電子工程系，山西 太原 030008)

一種基于LDPC碼譯碼的改進型最小和譯碼算法及仿真

焦冬莉，譚艷麗，趙永強，薄曉寧

(太原工業(yè)學院電子工程系，山西 太原 030008)

基于LDPC碼譯碼原理提出了一種新的高效的最小和譯碼算法。對基于雙曲正切規(guī)則的校驗節(jié)點更新過程中的兩個方向的處理進行了簡化。出于減少水平處理過程中近似誤差的考慮，新算法降低了復雜度。垂直方向的部分與和積譯碼算法相同，另一部分采用MS算法簡化了計算。與嚴格的逼近方法相比，該方法具有計算復雜度低的優(yōu)點。仿真結果表明,新提出的算法可以非常接近傳統(tǒng)譯碼算法的性能。

計算復雜度；MS算法；仿真

LDPC(Low Density Parity Check)碼是一種基于稀疏奇偶校驗矩陣編碼的分組碼，是哥拉格(Gallager)[1]于1962年發(fā)現(xiàn)的。然而，由于當時計算機處理能力的限制和相關理論的薄弱，因此并未受到人們的足夠重視。隨著上世紀90年代Turbo碼的興起，人們認識到LDPC碼也是一種較好的編碼。1996年，MacKay從現(xiàn)代編碼理論觀點出發(fā)，重新研究LDPC碼，獲得了巨大的突破[2]。LDPC碼憑借其優(yōu)異性能及其在信息可靠傳輸中的良好應用前景[3](例如光通信，衛(wèi)星通信、深空通信、第4代移動通信系統(tǒng)，高速與甚高速率數(shù)字用戶線)，已引起世界各國學術界和IT業(yè)界的高度重視。

和積譯碼(簡稱SPA)算法是LDPC碼中最流行的譯碼算法之一，又稱為置信度傳播算法[4]。從該算法名稱就可以看出其保留了大量的加法、乘法數(shù)學運算，這大大限制了該算法的應用。人們基于此算法又提出了許多改進算法以降低算法的運算復雜度[5]，使其硬件實現(xiàn)更加容易。最小和譯碼算法是一種最突出的和積譯碼算法的次優(yōu)算法[6]；迭代譯碼過程中的校驗節(jié)點更新過程被大大簡化，但性能也得到了損失。本文基于最小和譯碼的簡化思路，提出一種新的校驗節(jié)點更新過程，在保留迭代譯碼過程所需的主要外信息的基礎上，使其運算量更接近于最小和譯碼算法。采用線性逼近的思路[7]，本文提出了一種新的改進方案簡化對數(shù)函數(shù)的計算。最終提出的改進算法在與最小和譯碼算法有相似運算復雜度的情況下，性能得到了較大提高。

本文內(nèi)容安排如下：第1部分簡述最小和譯碼算法；第2部分給出了改進的算法方案，第3部分進行仿真結果分析，第4部分給出結論分析。

1 最小和譯碼算法

標準的LDPC碼譯碼最小和算法(MS Algorithm)是并行迭代的軟譯碼算法。消息傳遞的過程順序與SP算法一樣，但是更新的法則具有較大不同。MS 算法的譯碼公式如下：

初始化：對于每一個n∈{0,1,2,…,N}

(1)

(2)

uml=0 .

(3)

迭代：1) 水平掃描(校驗節(jié)點更新規(guī)則)

(4)

2) 垂直掃描(變量節(jié)點更新規(guī)則)

(5)

3) 譯碼：對每一個比特，計算其后驗對數(shù)似然比(LLR)

(6)

2 改進的算法方案

本部分主要集中于簡化水平掃描過程既校驗節(jié)點的更新，降低算法運算復雜度，使硬件實現(xiàn)變得更加容易。由經(jīng)典的LLR-BP譯碼算法知道，校驗節(jié)點的更新過程可以表示如下：

(7)

其中

(8)

且

αml=sign(vml) .

(9)

對公式7中的核心函數(shù)f(x)做如下變換：

=log(1+e-|x|)-log(1-e-|x|)

≈a(x)-s(x) .

(10)

在式(10)中，用兩條分段線性函數(shù)來逼近函數(shù)f(x)。對于去除了對數(shù)和指數(shù)的校驗節(jié)點更新過程，運算量得到了較大的優(yōu)化。函數(shù)a(x)能夠被極其精確的用分段線性函數(shù)逼近，線性函數(shù)的斜率為以2為底的指數(shù)次冪。圖1中的曲線表示分段逼近

圖1 函數(shù)a(x)=log(1+e-|x|)

函數(shù)與標準函數(shù)的接近程度，表1是分段逼近函數(shù)在各個區(qū)間上的具體表現(xiàn)形式。

表1 函數(shù)log(1+exp(-x))的分段線性逼近函數(shù)

函數(shù)S(x)能夠極其精確的用分段線性函數(shù)逼近，其均方誤差小于0.05。圖2是分段逼近函數(shù)與標準函數(shù)的接近程度，表2是分段逼近函數(shù)在各個區(qū)間上的具體表現(xiàn)形式。

圖2 函數(shù)s(x)=log(1-e-|x|)

由最小和譯碼算法的思想，對經(jīng)典的SPA譯碼算法進行一種新的處理方式。隨機的保留一半數(shù)量的水平方向的校驗節(jié)點外信息，在一定的誤差范圍內(nèi)降低水平方向更新過程的計算量。式11是經(jīng)典LLR-BP算法的水平方向更新過程。

表2 函數(shù)log(1-exp(-x))的分段線性逼近函數(shù)

(11)

對式(11)進行如下操作，變化為式(12)或(13)

(12)

(13)

在水平方向的更新過程中，選擇式(12)或者(13)作為水平方向的數(shù)據(jù)處理依據(jù)。

3 仿真及仿真結果分析

圖3、4分別是BPSK調制下，使用1/2、2/3、3/4、5/6碼率碼長為576和2304時的三種不同譯碼算法的誤碼率曲線圖。仿真的實驗環(huán)境為高斯信道，所使用的迭代次數(shù)都是30次。

圖3 L=2304，迭代次數(shù)為30時性能曲線

圖4 L=2304，迭代次數(shù)為30性能曲線

從圖3、4中可以看出，無論是哪種碼率或者碼長，SPA算法都具有最好的譯碼性能，改進的算法緊隨其后，而最小和譯碼算法的性能最差，說明無論在何種情況下，改進的算法都在運算復雜度和譯碼性能上取得了一個很好的折中。從圖3中可以看出，改進算法相較于最小和譯碼算法性能最大提升0.3 dB。從圖4中可以看出，改進算法在低碼率低信噪比情況下，性能提升情況更加明顯。

表3描述了在校驗節(jié)點更新過程中的主要運算量。我們知道在LDPC碼的迭代譯碼過程中，大量的數(shù)據(jù)運算主要集中于校驗節(jié)點更新。在改進算法中，整個運算過程中已經(jīng)不再包含特殊運算，并且加法和乘法等常規(guī)的運算次數(shù)也有了大幅度的降低。相較于最小和譯碼算法，改進算法的運算隨著節(jié)點數(shù)量的增多都是呈線性增長。

表3 各種算法的運算量對比

注：dc是奇偶校驗矩陣的行重

4 結論

本文提出了一種新的改進的關于LDPC碼的迭代譯碼算法。對基于雙曲正切函數(shù)的水平更新過程，本算法得到了較大優(yōu)化。在降低算法運算量的基礎上，并沒有降低譯碼性能。而基于最小和譯碼思路的簡化過程，在減少運算量的同時也使得性能優(yōu)于最小和譯碼算法。因此改進的譯碼算法是一個完全可行的，并且優(yōu)于最小和譯碼算法的譯碼算法。

[1] Gallager R G.“Low-density Parity-check Codes,” IRE Trans[J].Inform Theory,1968，IT-8：21-28.

[2] MacKay J C.Good Error-correcting Codes Based on Very Sparse Matrices[J].IEEE Trans Inf Theory,1999,45：399-431.

[3] Chung S Y,Forney G D,Jr., T J.Richardson,et al.On the Design of Low-density Parity-check Codes Within 0.004 5 dB of the Shannon Limit[J].IEEE Commun Lett,2001,5:58-60.

[4] Richardson T,Urbanke R.The Capacity of Low-density Paritycheck Codes Under Message-passing Decoding[J].IEEE Trans Information Theory,2001,47(2):599-618.

[5] Chen J,Dholakia A,Eleftheriou E,et al.Reduced Complexity Decoding of LDPC Codes[J].IEEE Trans Commun,USA,2005,53(8):1288-1299.

[6] Wiberg N,Loeliger H A,Koetter R.Codes and Iterative Decoding on General Graphs[J].Eur Trans Telecommun,1995(6):513-526.

[7] Papaharalabos S,Sweeney P,Evans B G,et al.Performance Evaluation of a Modified Sum-product Decoding Algorithm for LDPC Codes[G].Proc.2nd Int. Symp. Wireless Commun.Systems (ISWCS),Siena,Italy,September,2005:800-804.

A Novel Modified MS Algorithm Based on LDPC Code Decoder

Jiao Dongli, Tan Yanli, Zhao Yongqiang, Bo Xiaoning

(TaiyuanInstituteofTechnology,TaiyuanShanxi030008,China)

A novel efficient Min-sum (MS) algorithm with LPDC code is proposed in this paper. Basing on the hyperbolic tangent rule, the check node update with two horizontal processes is modified with similar calculation. The proposed algorithm reduces the complexity, which is motivated by reducing the approximation error in the horizontal process. One part of the vertical process is the same with sum-product algorithm (SPA), and the other part adopts MS algorithm and simplifies the calculation. Compared with the exiting approximations, the proposed method has low computational complexity than SP algorithm. The simulation results show that the performance of this algorithm is very close to the general algorithm.

calculation complexity; MS algorithm; simulation

2016-11-10

焦冬莉(1971- )，女，山西運城人，講師，研究方向：信號分析與處理。

1674- 4578(2017)01- 0022- 04

TP301.6

A