Turbo碼MAP譯碼的重編碼方法

陳國宏， 畢 崗

(浙江大學城市學院 信息與電氣工程學院，浙江 杭州 310015)

?

Turbo碼MAP譯碼的重編碼方法

陳國宏， 畢 崗

(浙江大學城市學院 信息與電氣工程學院，浙江 杭州 310015)

為了提高Turbo碼MAP譯碼性能，提出了一種全新的重編碼方法.該方法在編碼器端采用刪余矩陣，在譯碼器前端加入一個重編碼單元，該重編碼單元由解調判決器、重編碼器、碼元比較器、BPSK調制器和復用器組成.仿真結果表明：該方法可有效減少譯碼迭代次數，縮短譯碼延遲，從而在信噪比Eb/N0=1.0 dB時，使誤比特率(BER)降到原來3.37×10-3的1/2左右.通過分析比較3種通用的MAP譯碼算法和重編碼單元的計算復雜度，驗證了重編碼方法的優越性.仿真和理論分析結果表明，重編碼方法可以顯著提高MAP譯碼性能，有較高的潛在應用價值.

Turbo碼；MAP算法；重編碼

1993年首次提出的Turbo碼已被證明是一個高性能的編碼方案[1]，主要適用于功率受限的通信系統.大多數無線通信系統功率較小，帶寬有限，同時要求低時延，Turbo碼的優異性能無疑為之帶來了福音.Turbo碼的譯碼算法分2類：一類是最大后驗概率算法(Maximum A Posteriori，MAP)及其修正算法；另一類則是基于Viterbi算法的軟輸出Viterbi算法(Soft Output Viterbi Algorithm，SOVA)以及基于SOVA算法的修正算法[2-3].總體上講，MAP算法及其修正算法性能更好，但實現復雜度高.SOVA算法最簡單，但其性能不及MAP算法.

在高斯白噪聲(AWGN)信道下，MAP算法是Turbo碼最佳迭代譯碼算法.然而，因這種算法的復雜度大而難以實現，學者們提出了MAP的修正算法，ROBERTSON等[4]提出了Log-MAP譯碼算法，KOCH等[5]提出了Max-Log-MAP譯碼算法.Log-MAP算法具有優良的譯碼性能，但是其修正函數包含指數和對數運算，增加了譯碼復雜度和時延，也不利于硬件實現.Max-Log-MAP雖然利用最大值運算降低了復雜度，但也降低了譯碼性能.

2007年，TALAKOUB等[6]提出了一種新的改進譯碼算法Improved Max-Log-MAP.與Max-Log-MAP相比，Improved Max-Log-MAP在譯碼性能上有較大提升.但在小信嗓比(Signal-to-Noise Ratio，SNR)上，其性能不如SYBIS[7]和SUN等[8]提出的Simplified Max-Log-MAP(SF-Max-Log-MAP).

在達到較為理想的譯碼性能的同時，找到一個合適的SF衰減因子很難.為此，本研究組作了探索性的研究，首先研究Log-MAP譯碼算法，提出用插值函數計算Log-MAP算法中的校正函數，并在AWGN信道上采用分段差值方法實現了Turbo譯碼，解決了計算復雜度較大的問題[9].針對Max-Log-MAP算法的譯碼性能比Log-MAP算法差0.5 dB[10]的問題，提出了用線性分段(Piecewise-Linear Term,PLT)的最大值運算來替代Log-MAP算法中雅克比公式，獲得了優化Turbo譯碼性能的方法[11].但是這些研究并沒有取得特別令人滿意的結果.

本文提出采用重編碼(Recoding)來實現MAP譯碼算法的方法，可以有效減少MAP譯碼的迭代次數，明顯縮短譯碼延遲，從而使Turbo碼譯碼器達到較為理想的誤比特率(Bit Error Rate，BER).

1 采用重編碼方法的MAP譯碼

1.1 重編碼方法的基本思想

Turbo碼編碼器可由2個并行級聯的遞歸系統卷積編碼器(Recursive Systematic Convolutional code，RSC)和一個隨機交織器(Interleaver)組成[12].在Turbo碼編碼器端采用刪余矩陣可以提高碼率[13]，見圖1.經過刪余矩陣碼率R由1/3提高到1/2，同時隨著冗余碼的減少，糾錯性能也相應降低.可見，碼率與糾錯能力之間是矛盾的.現在，在MAP譯碼器之前增加重編碼單元，可以有效恢復在編碼器端刪余的奇偶校驗碼元，增加冗余碼元，增大碼的最小距離為dmin，提高了糾錯性能，而碼率仍保持R=1/2.所以采用刪余技術和重編碼方法，不但提高了Turbo碼的信息傳輸速率，而且也大大提高了糾錯能力，從而使MAP譯碼性能得到了較大的提升.

1.2 常規Turbo碼的MAP譯碼方法

圖1 Turbo碼編碼器結構圖Fig.1 Structure diagram of Turbo code encode

圖2 Turbo碼MAP譯碼器結構圖Fig.2 Structure diagram of Turbo code MAP decoder

1.3 重編碼譯碼方案

圖3 重編碼方法的MAP譯碼框圖Fig.3 MAP decoding block diagram of re-encoding

由以上過程分析可知，重編碼方法可以有效恢復刪余的奇偶校驗比特，即得到了原來碼率R=1/3時的全部完整奇偶校驗比特.和常規MAP譯碼相比，重編碼方法增加了一半的冗余碼，意味著糾錯性能的提高，而碼率R也從1/3提高到了1/2.因此，采用重編碼方法，不僅提高了Turbo碼碼元的傳輸效率，而且也明顯提升了糾錯能力.

2 仿真和分析

2.1 仿 真

圖4 MAP譯碼器性能比較Fig.4 Comparison of MAP decoder performance

根據上述方案進行Matlab編程以驗證所提的重編碼方法.圖4給出了Turbo碼譯碼迭代次數n為4和8次，分別采用常規MAP譯碼算法和重編碼方法時的譯碼性能曲線.其中，碼率R=1/2，0dB

2.2 MAP譯碼算法的計算復雜度分析

在AWGN信道下，Turbo碼最佳迭代譯碼算法是標準MAP算法，但是由于這種算法復雜度高并不適用于實際應用.因此研究者將誤碼率與譯碼計算復雜度進行有效折衷，設計了次優的MAP譯碼算法，即Max-Log-MAP算法[14-15].下面分析其計算復雜度.

再次假設采用BPSK傳輸方式.令v=(v0, v1, …, vn-1)為碼字，且c=(c0, c1, …, cn-1)為碼字對應的雙極性信號序列，其中0≤i

(1)

(2)

(3)

γi(s′,s)=p(ri|(si,si+1)=(s′,s))=

(4)

式中N0/2為AWGN信道的方差.

根據式(2)～(4)，得到

(5)

(6)

logγi(s′,s)=-(ri-ci)2.

(7)

表1 MAP譯碼算法與重編碼單元的計算復雜度比較Table 1 Comparison of computational complexity between MAP decoding algorithm and re-encoding unit

注 1. 表中m為存儲器級數； 2. 指數和對數中的“--”符號表示計算量相當大，不作具體分析.

2.3 重編碼單元的計算復雜度分析

圖3中的解調判決和碼元比較器都是比較算法，BPSK調制相當于1次乘法運算.重編碼器RSC3和RSC1(或RSC2)原理相同，如圖1所示，存儲級數等于3的RSC編碼器的計算量相當于4個加法運算，則一個存儲級數為m的RSC編碼器的計算量相當于m+1次加法運算.因此，一個重編碼單元的總計算量為2次比較、1次乘法運算和m+1次加法運算，如表1所示.由表1中的數據可知，重編碼單元的計算復雜度遠遠小于任何一種MAP譯碼算法.因此，就MAP譯碼端的計算量而言，重編碼方法在Max-Log-MAP譯碼器中的計算量，可以忽略不計.

通過以上分析可知，重編碼方法能有效恢復刪余的奇偶校驗比特，得到碼率R=1/3時的全部完整奇偶校驗比特，增加了一半的冗余碼，而碼率仍維持R=1/2.從而大大減少了MAP譯碼的迭代次數，降低了譯碼的計算量和時延，提高了MAP譯碼算法的性能.

3 結 論

提出了一種提高Turbo碼MAP譯碼性能的新方法，在Turbo碼編碼器端采用刪余矩陣，在MAP譯碼器前加入重編碼單元，不但提高了Turbo碼信息的傳輸速率，也較好地提升了其糾錯能力.仿真結果顯示，該方案可有效提高MAP譯碼性能.因此，采用重編碼方法的Turbo碼MAP譯碼算法在時延要求低、帶寬有限、功率受限的無線通信系統中有較高的應用價值.

[1] BERROU C，GLAVIEUU A, THITIMAJSHIMA P.Near Shannon limit error-correcting coding and decoding：Turbo-codes[C]//Proceedings of IEEE International Conference on Communications 1993. Geneva:IEEE，1993：1064-1070.

[2] HAGENAUER J，HOEHER P.A viterbi algorithm with soft-decision outputs and its applications[C]//IEEE Global Telecommunications Conference and Exhibition. Dallas: IEEE,1989(3)：1680-1686.

[3] 田志剛，郭文彬，楊大成.等價于MAP的SOVA譯碼方法[J].電子與信息學報，2006，28(7):1270-1273.

TIAN Zhigang, GUO Wenbin, YANG Dacheng. MAP decoding methods derived from SOVA[J]. Journal of Electronics & Information Technology,2006，28(7)：1270-1273.

[4] ROBERTSON P，VILLEBRUN E，HOEHER P.A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain[C]//IEEE International Conference on Communications. Seattle: IEEE,1995：1009-1013.

[5] KOCH W, BAIER A. Optimum and sub-optimum detection of coded data disturbed by time-varying inter-symbol interference[C]//IEEE Global Telecommunications Conference. San Diego: IEEE,1990：1679-1684.

[6] TALAKOUB S，SABETI L，SHAHRRAVA B.An improved Max-Log-MAP algorithm for Turbo decoding and Turbo equalization[J].IEEE Transactions on Instrumentation and Measurement，2007，56(3)：1058-1063.

[7] SYBIS M.Log-MAP equivalent Chebyshev inequality based on algorithm for Turbo TCM decoding[J].Electronics Letters，2011，47(18)：1049-1050.

[8] SUN Z，ZHANG L，TIAN Y.SF-MAX-LOG-MAP parallel decoding algorithm and its application study in LTE[C]//Cross Strait Quad-Regional Radio Science and Wireless Technology Conference. Piscataway：IEEE，2011(2)：885-888.

[9] 畢崗，王建毅.低復雜度Log-MAP譯碼算法的研究[J].計算機工程與應用，2011，47(10)：89-91，97.

BI Gang, WANG Jianyi. Research on low-complexity algorithm for Log-MAP decoding[J]. Computer Engineering and Applications，2011，47(10)：89-91，97.

[10] PARK S J.Combined Max-Log-MAP and Log-MAP of Turbo codes[J].Electronics Letters，2004，40(4)：251-252.

[11] 畢崗，陳國宏，王建毅.高性能的Max-Log-MAP線性分段算法研究[J].電路與系統學報，2012，17(6)：26,27-30.

BI Gang, CHEN Guohong, WANG Jianyi. Study on piecewise-linear algorithm for high performance Max-Log-MAP[J].Journal of Circuits and Systems, 2012, 17(6):26,27-30.

[12] YOON S H，BAR-NESS Y.A parallel MAP algorithm for low latency Turbo decoding[J].IEEE Communications Letters，2002，6(7)：288-290.

[13] CHATZIGEORGIOU I，RODRIGUES M R D，WASSELL I J，et al. Analysis and design of punctured rate-1/2 Turbo codes exhibiting low error floors[J].IEEE Journal on Selected Areas in Communications，2009，27(6)：944-953.

[14] VOGT J，FINGER A.Improving the Max-Log-MAP Turbo decoder[J].Electronics Letters，2000，36(3)：1937-1939.

[15] PAPAHARALABOS S，SWEENEY P，EVANS B G.SISO algorithms based on Max-Log-MAP and Log-MAP Turbo decoding[J].IET Communications，2007，1(1):49-54.

[16] SHU L，DANIEL J C.Error Control Coding[M].2nd ed. London：Pearson Education，2004:479.

Recoding method of MAP decoding of Turbo codes.

CHEN Guohong, BI Gang

(SchoolofInformationandElectricalEngineering，ZhejiangUniversityCityCollege，Hangzhou310015，China)

In order to improve the performance of MAP decoding of Turbo codes, this paper proposed a new recoding method. The recoding method used puncturing matrix at the encoder side while adding a recoding unit in the front of the decoder. The recoding unit consisted of demodulation decision device, re-encoder, symbol comparator, BPSK modulator and multiplexer. The simulation results showed that the method effectively reduced the decoding iteration and shortened the decoding delay, thus when the Signal to Noise Ratio(SNR)Eb/N0=1.0 dB, the bit error rate(BER) decreased to about half of the original 3.37×10-3. The analysis result of the computational complexity of 3 general MAP decoding and recoding unit algorithms proved the superiority of the recoding method. Simulation and theoretical analysis demonstrate that the recoding method can significantly improve the performance of MAP decoding, so it has high potential application value.

Turbo codes; MAP algorithm; recoding

2015-04-16.

浙江省教育廳科研資助項目(Y201327825).

陳國宏(1968-)，ORCID:http://orcid.org/0000-0003-0285-7000,男，碩士，工程師，主要從事無線網絡通信、信息論與編碼研究，E-mail:chenguohong@zucc.edu.cn.

10.3785/j.issn.1008-9497.2016.04.015

TN 911

A

1008-9497(2016)04-476-05

Journal of Zhejiang University(Science Edition), 2016,43(4):476-480