姜春強，唐震宇，甘 明

（1.海裝重慶局，成都　610036；2.國網(wǎng)四川省電力公司，四川　自貢　643000；3.中國西南電子技術(shù)研究所，成都　610036）

一種低復(fù)雜度雙二元卷積Turbo碼譯碼算法*

姜春強1，唐震宇2，甘 明**3

（1.海裝重慶局，成都610036；2.國網(wǎng)四川省電力公司，四川自貢643000；3.中國西南電子技術(shù)研究所，成都610036）

雙二元卷積Turbo碼（DB CTC）的非二進制編碼使得譯碼復(fù)雜度增加，限制了其在某些實際通信工程中的使用。在最大后驗概率（MAP）譯碼算法的基礎(chǔ)上，提出了一種優(yōu)化算法，將譯碼的存儲量和計算量降為原來的1/4。仿真結(jié)果表明：在不同編碼長度和碼率的情況下，優(yōu)化算法與原算法性能相當(dāng)；在誤碼率為10-5的條件下，兩者的Eb/N0差異同樣不大于0.1 dB。

卷積Turbo碼；Log-MAP算法；循環(huán)遞歸；低復(fù)雜度譯碼

1　引言

Berrou等人［1］于1999年首次提出非二進制卷積Turbo碼，常見的是雙二元卷積Turbo碼（Double Binary Convolutional Turbo Code，DB CTC），與普通Turbo碼相比，具有編碼效率高、譯碼延時小、更大的最小自由距離、降低了誤碼平層等優(yōu)點。CTC已經(jīng)采納成為歐洲衛(wèi)星網(wǎng)絡(luò)（DVB-RCS）、WiMAX和IEEE802.16e的前向糾錯（Forward Error Correction，F(xiàn)EC）方案。

CTC的譯碼采用最大后驗概率算法，包括最大后驗概率算法（Maximum A Posteriori，MAP）、Log-MAP、Max-Log-MAP以及MAP算法的改進，這些改進集中在通過一些近似方法，在不顯著增加計算復(fù)雜度基礎(chǔ)上，提升Max-Log-MAP的算法性能。文獻［2-4］提出了一種constant-Log-MAP算法，在max運算后加上一個常量，補償max*運算簡化帶來的性能損失。文獻［5-6］提出一種En-Max-Log-MAP算法，用一個與信噪比無關(guān)的參數(shù)來加權(quán)分量譯碼器輸出的外信息。CTC是雙二元卷積Turbo碼，在計算前后向狀態(tài)度量時，狀態(tài)輸入的轉(zhuǎn)移條件由Turbo碼的（0，1）變?yōu)椋?0，01，10，11），使得譯碼的計算量增加，增大了實現(xiàn)的硬件資源要求。為此，本文提出一種減少前后向度量計算復(fù)雜度的譯碼算法，分析了該方法的計算量和存儲量，并通過仿真驗證了所提算法的有效性。

2　CTC編碼原理

CTC的子編碼器采用循環(huán)遞歸系統(tǒng)卷積碼，保證碼字通過編碼器時初始狀態(tài)和結(jié)束狀態(tài)相同，即tail-biting方案。編碼器結(jié)構(gòu)如圖1所示。

圖1　CTC編碼器結(jié)構(gòu)示意圖Fig.1 CTC encoder structure

下面介紹具體的編碼過程。

首先，將長度為2N的信息序列的奇偶位分開，形成兩個長度為N的序列，A端輸入奇位序列，B端輸入偶位序列。預(yù)編碼時初始狀態(tài)為全零狀態(tài)S0，經(jīng)過N步編碼后編碼器的終止?fàn)顟B(tài)為SN。在循環(huán)狀態(tài)查找表中，根據(jù)終止?fàn)顟B(tài)SN得到循環(huán)狀態(tài)SCI。在實際編碼時，用SCI初始化寄存器，再對A、B序列進行編碼，得到校驗序列Y、W。

接著，對A、B序列經(jīng)過交織器后得到的序列A'、B'同樣進行預(yù)編碼和實際編碼，得到校驗序列Y'、W'。

最終得到碼字序列A、B、Y、Y'、W、W'，根據(jù)不同碼率，對校驗序列進行刪余，得到最終的碼字序列。

3　CTC譯碼算法

3.1迭代譯碼結(jié)構(gòu)

CTC的譯碼器由兩個軟輸入輸出（Soft Input Soft Output，SISO）的分量譯碼器并行級聯(lián)而成，如圖2所示［7］。譯碼過程如下：首先譯碼未交織的信息序列，子譯碼器1的輸入為接收解調(diào)器輸出的信息軟值Le（xk）、校驗軟值Le（yk）和第二級子譯碼器傳遞的先驗信息L（dk），進行譯碼后輸出信息的后驗對數(shù)似然比L（dk｜xk）和外信息Le（dk），Le（dk）經(jīng)過交織器后作為子譯碼器2的先驗信息；其次，子譯碼器2利用交織后的信息比特軟值Le（xk）、校驗比特軟值Le（yk）以及子譯碼器1傳遞的外信息Le（dk）進行譯碼，譯碼過程與子譯碼器1一樣。在每次迭代后兩個譯碼器互相交換外信息Le（dk），并在隨后的迭代譯碼中不斷提高先驗信息L（dk）的準(zhǔn)確性，逐漸使譯碼輸出的Le（xk）收斂到一定范圍內(nèi)；最后，對子譯碼器2的輸出信息的后驗對數(shù)似然比L（dk｜xk）進行解交織和硬判決得到譯碼結(jié)果。

圖2　CTC譯碼框圖Fig.2 CTC decoder schematic

3.2MAP算法

MAP算法利用輸入序列的信息及前后碼元的相關(guān)性進行軟值判決。在對每個碼元的似然比進行計算時，除計算當(dāng)前信息位dk的譯碼信息外，還計算前向度量αk和后向度量βk。αk-1（i）為接收的前k-1個碼字為Rk-11的條件下，從0時刻Sc狀態(tài)出發(fā)，在k-1時刻到達狀態(tài)i的概率，反映了k時刻之前的碼元對dk的影響；βk（k）為接收的后N-k個碼字為RNk+1的條件下，由N時刻Sc狀態(tài)回推，在k時刻為狀態(tài)j的概率，反映了k時刻之后的碼元對dk的影響。

MAP算法包含大量指數(shù)和乘法運算，復(fù)雜度高，在實際實現(xiàn)時，通常將MAP算法中的變量做對數(shù)運算，即Log-MAP算法。αk、βk的對數(shù)域遞推公式如下：

式中：Sjb（m）是指從m的一個前狀態(tài)出發(fā)，輸入為j時，轉(zhuǎn)移到狀態(tài)m；Sjf（m）是指在m狀態(tài)時輸入為j，轉(zhuǎn)移到的狀態(tài)；δi（Rk，m）是指第k個時刻，輸入為i，轉(zhuǎn)移到狀態(tài)m時，接收到Rk的概率。其中，Rk=（xk，yk），代表時刻k的輸入序列。其中xk、yk定義為

式中：dk為信息比特組（d1k，d2k）；Yk是校驗位。

δi（Rk，m）的計算式如下：

式中：L_a（1，k）和L_a（2，k）分別是xk，1、xk，2的邊信息。

4　CTC譯碼算法簡化

CTC譯碼器的實現(xiàn)，計算量和存儲量最大的部分在前向度量αik（m）和后向度量βik（m）。以前向度量為例，因其與輸入i（00，01，10，11）有關(guān)，因此時刻k、狀態(tài)m的前向度量分別為α0k0（m）、α0k1（m）、α1k0（m）和α1k1（m），其計算如下：

式中：k=2，3，…，N。

在Turbo譯碼中，前向度量αk（m）、后向度量βk（m）只與時刻k、狀態(tài)m有關(guān)。以前向度量為例，其迭代公式如下：

對比CTC和Turbo的譯碼算法，在同樣信息碼長和碼率的情況下，CTC由于采用雙二進制輸入，使得編碼塊長度減半，即N為Turbo編碼的1/2，但由于其前后向度量與輸入有關(guān)，使得的存儲項由1項變?yōu)?項，求和項也由1項變?yōu)?項，因此，總的來看，CTC的存儲量和計算量為Turbo譯碼的2倍。這使得CTC在一些對譯碼資源和速度要求較高的地方，應(yīng)用受到限制。

參照Turbo的譯碼思想，減少CTC譯碼器前后向度量的存儲狀態(tài)，保存的αk（m）只與時刻k、狀態(tài)m有關(guān)，而與輸入i無關(guān)，即令

將式（12）代人式（7）～（10），得αk（m）的計算如下：

同樣令

得βk（m）的計算如下：

下面以Turbo譯碼的前后向度量的計算復(fù)雜度為基準(zhǔn)，分析CTC標(biāo)準(zhǔn)和簡化算法的性能。表1給出了3種算法的存儲量和加法器數(shù)量，可見CTC算法簡化后，使得前后向度量中每個時刻的存儲項和求和項比CTC標(biāo)準(zhǔn)算法減少為1/4，與Turbo碼一致，由于CTC的編碼塊深度減半，因此總的存儲量和計算量為Turbo譯碼的1/2。

表1　前后向度量的計算復(fù)雜度Tab.1 Computational complexity of forward metrics and backward metrics

5　CTC譯碼性能仿真

本節(jié)提供了CTC碼采用標(biāo)準(zhǔn)MAX-Log-MAP譯碼算法和本文優(yōu)化后的MAX-Log-MAP（Op-MAX-Log-MAP）譯碼算法的性能仿真結(jié)果，為充分比較兩者性能，仿真了不同編碼長度和不同碼率的誤碼性能。

圖3給出了數(shù)據(jù)幀長2N（N為512、256、128）的條件下誤碼率（Bit Error Rate，BER）的仿真曲線。仿真環(huán)境為加性白高斯噪聲（Additive White Gaussi-an Noise，AWGN）信道，碼率為1/3，Eb/N0為0～3 dB，BPSK調(diào)制，迭代譯碼次數(shù)8。從圖中可以看出：N值越大，CTC的誤碼率曲線不斷降低；在相同數(shù)據(jù)幀長的情況下，MAX-Log-MAP和Op-MAXLog-MAP的誤碼性能幾乎相當(dāng)；在誤碼率為10-5的條件下，兩者的Eb/N0差異不大于0.1 dB。

圖3　不同編碼長度下譯碼性能曲線Fig.3 BER performance of different block size

圖4給出了碼率為1/3、1/2和2/3的條件下誤碼率的仿真曲線。仿真環(huán)境為AWGN信道，數(shù)據(jù)幀長2N（N=512），Eb/N0為0～4 dB，BPSK調(diào)制，迭代譯碼次數(shù)8。從圖中可以看出：隨著碼率降低，CTC的性能提高；在不同碼率的情況下，MAX-Log-MAP和Op-MAX-Log-MAP的誤碼性能相當(dāng)；在誤碼率為10-5的條件下，兩者的Eb/N0差異同樣不大于0.1 dB。

圖4　不同碼率下譯碼性能曲線Fig.4 BER performance of different code rate

6　結(jié)論

CTC是IEEE 802.16等標(biāo)準(zhǔn)的物理層數(shù)據(jù)幀傳輸?shù)那跋蚣m錯碼型，在保證譯碼性能的前提下，設(shè)計低計算復(fù)雜度和存儲量的譯碼算法，有利于降低實際通信工程的硬件需求，實現(xiàn)高速CTC譯碼器。本文研究了基于MAX-Log-MAP譯碼算法的前后向度量計算方法，提出了一種減少前后向度量計算復(fù)雜度的譯碼算法，將CTC譯碼的存儲量和計算量降為原來的1/4，可用于高速CTC譯碼器的設(shè)計。

［1］BERROU C，JEZEQUEL M，DOUILLARD C，et al.The advantage of non-binary Turbo codes［C］//Proceedings of 2001 IEEE Information Theory Workshop.Caims，Australia：IEEE，2001：61-63.

［2］SOLEYMANI M R.Turbo coding for satellite and wireless communications［M］.Norwell，Massachusetts：Kluwer Academic Publishers，2002：155-165.

［3］GROSS W J，GULAK P G.Simplified MAP algorithm suitable for implementation of Turbo decoders［J］.Electronics Letters，1998，34（16）：1577-1578.

［4］PAPAHARALABOS S，SWEENEY P，EVANS B G.Constant log-MAP decoding algorithm for duo-binary Turbo codes［J］.Electronics Letters，2006，42（12）：709：710.

［5］VOGET J，F(xiàn)INGER A.Improving the max-log-MAP Turbo decoder［J］.Electronics Letters，2000，36（23）：1937-1939.

［6］OULD-CHEIKH-MOUHAMEDOU Y，GUINAND P，KABAL P.Enhanced Max-Log-MAP and enhanced Log-APP decoding for DVB-RCS［C］//Proceedings of the 3rd International Symposium on Turbo codes&Iterative Information Processing.Brest，F(xiàn)rance：IEEE，2003：259-263.

［7］IM S B，KIM M G，CHOI H J.An efficient tail-biting map decoder for convolutional Turbo codes in OFDM systems［C］//Proceedings of 2004 IEEE Region 10 Conference on TENCON.Chiang Mai，Thailand：IEEE，2004：589-592.

姜春強（1977—），男，山東威海人，2010年獲工程碩士學(xué)位，主要從事無線通信系統(tǒng)的研究工作；

JIANG Chunqiang was born in Weihai，Shandong Province，in 1977.He received the M.S.degress in 2010.His research concerns wireless communications.

唐震宇（1989—），男，四川自貢人，現(xiàn)為工程師，主要從事無線通信系統(tǒng)的研究工作；

TANG Zhenyu was born in Zigong，Sichuan Province，in 1989.He is now an engineer.His research concerns wireless communications.

甘 明（1978—），男，四川資陽人，2004年于電子科技大學(xué)獲碩士學(xué)位，現(xiàn)為高級工程師，主要研究方向為抗干擾通信、編碼和調(diào)制。

GAN Ming was born in Ziyang，Sichuan Province，in 1978. He received the M.S.degree from University of Electronic Science and Technology of China in 2004.He is now a senior engineer.His research concerns anti-jamming communication，coding and modulation.

Email：18080962525@189.cn

A Low-complexity Decoding Algorithm for Double Binary Convolutional Turbo Codes

JIANG Chunqiang1，TANG Zhenyu2，GAN Ming3
（1.Military Representative Bureau of Navy Equipment Academy in Chongqing，Chengdu 610036，China；2.State Grid Sichuan Electric Power Company，Zigong 643000，China；3.Southwest China Institute of Electronic Technology，Chengdu 610036，China）

The double binary convolutional Turbo code（DB CTC）cannot be widely applied in some projects due to the high-complexity of decoding algorithm.In this paper，a new decoding algorithm with lowcomplexity for DB CTC is proposed based on the classic maximum a posteriori probability（MAP）decoding algorithm.By using the proposed algorithm，the storage cost and the computation complexity decrease by 3/4 compared with previous algorithm.Simulation results show that，when the bit error rate（BER）is 10-5，the Eb/N0deference between the proposed algorithm and the previous algorithm is not larger than 0.1 dB for various lengths of code and code-rates.

conventional Turbo code；Log-MAP algorithm；cycle recursion；low-complexity decoding

TN911.22

A

1001-893X（2016）04-0412-04

10.3969/j.issn.1001-893x.2016.04.011

姜春強，唐震宇，甘明.一種低復(fù)雜度雙二元卷積Turbo碼譯碼算法［J］.電訊技術(shù)，2016，56（4）：412-415.［JIANG Chunqiang，TANG Zhenyu，GAN Ming.A low-complexity decoding algorithm for double binary convolutional Turbo codes［J］.Telecommunication Engineering，2016，56（4）：412-415.］

2015-12-10；

2016-03-02 Received date:2015-12-10；Revised date:2016-03-02

**通信作者:18080962525@189.cn Corresponding author：18080962525@189.cn