孫增友，李歡歡

(東北電力大學(xué)信息工程學(xué)院，吉林吉林 132012)

從1993年，Turbo碼被 C.Berrou等人［1］提出以來，就以其優(yōu)異的性能和相對簡單可行的編譯碼算法吸引了眾多研究者的目光。Turbo碼的實質(zhì)是并行級聯(lián)的卷積碼，它與以往所有碼的不同之處在于它通過一個交織器的作用，達到接近隨機編碼的目的。它所采用的迭代譯碼策略，使得譯碼復(fù)雜性大大降低。Bahl等人［2］于1974年首次提出可以由最大后驗概率(MAP)迭代譯碼算法進行譯碼。Turbo碼已被應(yīng)用于各種通信系統(tǒng)，如深空通信、蜂窩移動通信和衛(wèi)星通信網(wǎng)絡(luò)，并且作為第三代移動通信標準，如CDMA2000。

MAP譯碼算法由于存在非線性函數(shù)和大量的乘法和加法運算［3］，實際中Turbo碼譯碼器的硬件實施很困難。因此，在次優(yōu)譯碼算法——Log-MAP譯碼解決方案中，通常在對數(shù)域運算。次最優(yōu)譯碼算法的目的是降低譯碼復(fù)雜度，同時保持編碼的誤碼率(BER)性能在適度的水平，與最優(yōu)譯碼(MAP)相比，只有很小分貝的譯碼性能損失。

近幾年，提出的各種算法均旨在簡化Turbo譯碼算法Log-MAP算法中的max*運算，包括:改進的Max-Log-MAP算法、Constant Log-MAP 算法［4］、Linear Log-MAP 算法、Lookup Log-MAP算法等。這些次最優(yōu)算法采用近似的方法使得譯碼算法簡化，但性能與最優(yōu)算法相比略有損失，為了減少性能的損失，額外的修正項需要添加到max運算中。本文提出了一種新的max*運算的近似方法，應(yīng)用于Turbo碼的Log-MAP譯碼算法中。這種近似方法可以很好地降低每個譯碼步驟運算的復(fù)雜度，相對于傳統(tǒng)的Log-MAP算法，性能降低很少。

1 Turbo碼的編譯碼

1.1 Turbo碼編碼方案

基于并行級聯(lián)卷積碼(PCCC)的Turbo碼編碼器結(jié)構(gòu)圖如圖1所示，在Turbo碼編碼過程中，信息序列u={u1，u2，…，uN}經(jīng)過交織器后，形成一個新的序列u'={u1'，u2'，…，uN'}。然后將這兩個序列u和u'分別傳送到兩個分量編碼器(RSC1，)中進行編碼，令生成的編碼序列分別為Xp1和Xp2，經(jīng)過刪余器，刪除一些校驗位，形成新的校驗序列Xp，這樣做的目的是為了提高碼率和系統(tǒng)頻譜效率。最后將校驗序列Xp與未編碼的系統(tǒng)信息Xs經(jīng)過復(fù)接器生成Turbo碼的編碼序列X。

圖1 PCCC型Turbo編碼結(jié)構(gòu)

1.2 Turbo碼譯碼方案

Turbo碼譯碼是基于兩個SISO譯碼器之間的迭代過程。如圖2所示，第一個SISO譯碼器的輸入端是由比特先驗信息Lin，2，經(jīng)信道傳輸?shù)男畔⒈忍豶s，以及第一個編碼器輸出的校驗比特rp，1這3部分構(gòu)成。然后產(chǎn)生一個軟輸出值Le，1，作為隨后SISO譯碼器2的先驗信息Lin，2，稱為外部信息。SISO譯碼器2的輸出經(jīng)過解交織后作為先驗信息Le，2又反饋給SISO譯碼器1作為輸入，這樣就完成了一次迭代的過程。經(jīng)過一定的迭代次數(shù)后，SISO譯碼器2的輸出L^u，2進行解交織后經(jīng)硬判決就是Turbo碼的譯碼輸出。

圖2 Turbo碼的迭代譯碼示意圖

工程中常用的譯碼算法有基于最大后驗概率的軟輸出算法和軟輸出Viterbi算法兩大類。由于MAP算法中的Log-MAP和Max-Log-MAP計算復(fù)雜度較低而更適合并行計算。假設(shè)u是N比特的信息塊。經(jīng)過Turbo編碼和BPSK調(diào)制，通過AWGN信道，接收的信息序列為y。在Turbo譯碼之前先進行軟解調(diào)。設(shè)由輸入引起的柵格由K-1時刻的狀態(tài)S'轉(zhuǎn)移為K時刻狀態(tài)S。前向遞歸和后向遞歸可以遞歸計算為［5］

式中:ˉαk和 ˉβk應(yīng)先進行初始化［2］;ˉγk是在迭代過程中與之對應(yīng)的柵格狀態(tài)過渡的分支轉(zhuǎn)移概率。傳輸比特uk的譯碼軟輸出，可以用對數(shù)似然比(LLR)計算，即

其中，max*運算，可以利用Jacobian算法定義為

式中:fc(·)為相關(guān)函數(shù)。為了使得Log-MAP算法復(fù)雜度最低，相關(guān)函數(shù)fc(·)可由查找表來實現(xiàn)。如果忽略相關(guān)函數(shù)的值，采用這種簡化方法得到的就是Max-Log-MAP算法［6］。

2 Log-MAP近似譯碼算法

2.1 簡化的max*運算

max*運算是Log-MAP算法的計算核心。當編碼器中寄存器個數(shù)為M時，譯碼器中就有2M個max*運算，且max*運算需要遞歸運算，當M≥3時，這種算法硬件實現(xiàn)復(fù)雜，而采用Max-Log-MAP算法譯碼后性能損失很大，因此提出一種簡化的Log-MAP算法。

為了降低對n個輸入變量參數(shù)的max*運算近似算法的復(fù)雜度，針對這個問題，采用Chebyshev不等式，所提出的改進的Log-MAP算法的n輸入max*運算為

式中:y1=max{x1，x2，…，xn}為n個輸入值中的最大值;y2=max{x1，x2，…，xn|y1}是次最大值;δ=y1-y2;K1=(n-1)/n，K2=ln［2n/(n+1)］。近似的第一項是一個簡單的max運算，第二項可以認為是另一個校正功能的函數(shù)fc(·)。

在計算信息比特的L(uk)時，式(3)中的max*運算用式(7)中的max運算。而對式(1)和式(2)中2個變量的max*運算均如式(4)作精確計算。

式(7)中，K2是一個正常數(shù)，在迭代譯碼過程中可以忽略，當n的值很大時，K1≈1，所以式(7)可以簡化為

3.2 max*運算中相關(guān)函數(shù)的實現(xiàn)及硬件結(jié)構(gòu)簡化

式(8)的實現(xiàn)需要設(shè)計合適的數(shù)字電路找出y1和y2，計算出δ，然后應(yīng)用于相關(guān)函數(shù)fc(·)。在文獻［7］中提出的一種有效的基于樹結(jié)構(gòu)的最大值產(chǎn)生器(MVGs)，用于從n個元素中找出y1和y2。這種結(jié)構(gòu)由2個(n/2)-MVG結(jié)構(gòu)和3個最大值單元(MVUs)組成，如圖3所示。則式(8)可以通過一個n-MVG結(jié)構(gòu)結(jié)合減法器計算δ，利用查找表(LUT)計算fc(δ)的值，再通過加法器實現(xiàn)。其中，s表示A-B。

圖3 改進的結(jié)構(gòu)圖(灰色框為改進部分)

Log-MAP算法中簡化的max*運算中的相關(guān)函數(shù)曲線fc(x)=lg(1+e-x)和Constant Log-MAP算法的近似的相關(guān)函數(shù)fc(x)如圖4所示。Log-MAP算法的近似算法中，Constant Log-MAP算法具有最低的復(fù)雜度，并且接近最優(yōu)的Turbo碼BER性能。

圖4 Log-MAP相關(guān)函數(shù)fc(x)和近似的fc(x)

Constant Log-MAP相關(guān)函數(shù)算法［4］為一個8位二進制的補碼整數(shù)運算，數(shù)值表示為5個整數(shù)位和3個小數(shù)位，因此，fc(x)的最小值為1/8，對應(yīng)x的最大值為2.0。如果x≥2，那么fc(x)≈0。另外，根據(jù)文獻［4］，當x ＜2，fc(x)可以近似為［0，2)的平均值，即，最佳取值為fc(x)≈3/8(即0.375)，因此Constant Log-MAP算法的近似相關(guān)函數(shù)fc(x)為

Constant Log-MAP算法可以通過其相關(guān)函數(shù)fc(x)的實現(xiàn)進一步降低其硬件結(jié)構(gòu)復(fù)雜度。

因為δ≥0，fc(δ)的實現(xiàn)可以更簡化。設(shè)c是給定δ={δp-1…δ0}時 fc(δ)的取值，c={cp-1…c0}。可以看出:

1)如果 c=3/8，則 cp-1…c0=“0…0．011”，或 cp-1…c0=“0…0．000”。

2)如果 δ＜2，那么 δp-2…δ0=“0…0x．xxx”，其中 x 任意表示為1或0。因此c0和c1僅當δj=0，4≤j≤p-2時等于1，即

式中:(·)表示非邏輯運算，∨表示或邏輯運算。所以在硬件實現(xiàn)式(8)時，在計算得出δ后，進行c0的計算時，只需在原有的Constant Log-MAP譯碼算法硬件結(jié)構(gòu)中引入幾個額外的門結(jié)構(gòu)(非門和或門)。改進的結(jié)構(gòu)圖如圖3中的灰色框部分。這樣，所提出的算法利用了δ≥0的優(yōu)勢，使得相關(guān)函數(shù)的硬件實現(xiàn)的復(fù)雜度大約降為Constant Log-MAP譯碼算法的一半。

3 MATLAB仿真分析

3.1 Turbo碼在CCSDS標準中的應(yīng)用仿真

將所提出的max*近似方法應(yīng)用于Turbo譯碼中，對應(yīng)信噪比下(Eb/N0)的BER性能仿真如圖5所示。4條BER曲線分別代表Constant Log-MAP算法［4］、本文提出的改進算法(用Log-MAP max*表示)、Log-MAP和Max-Log-MAP算法的BER性能。

圖5 不同譯碼算法的在CCSDS標準中的性能仿真比較

仿真的Turbo碼參數(shù)為移位寄存器具有16個狀態(tài)，碼率為R=1/2，生成多項式為(1，33/23)o，33和23為8進制數(shù)，分別代表前饋多項式和反饋多項式。信息序列N=103bit，傳輸幀總數(shù)為106。

為了保證仿真結(jié)果性能的準確性，每個性能仿真實驗中至少引入了100個位錯誤。使用了偽隨機Turbo交織器，在接收端最多進行10次迭代，采用BPSK調(diào)制，應(yīng)用于CCSDS標準［8］中。由圖5可知，所提出的改進的Log-MAP算法(用虛線表示)總能達到接近最優(yōu)的譯碼算法的BER性能，其譯碼復(fù)雜度接近Max-Log-MAP算法，而糾錯能力明顯強于Max-Log-MAP算法;在低誤碼率時，如10-6時，改進的譯碼算法可以實現(xiàn)與另外兩種算法大致相同的BER性能。

3.2 Turbo碼在WiMAX標準中的應(yīng)用仿真

將雙二進制的Turbo碼，考慮其含有8種狀態(tài)的分量卷積碼的情況，應(yīng)用于WiMAX標準［9］中，碼率為 R=1/3，2/3和4/5，信息序列長度為N=752 bit，調(diào)制方式為QPSK。在接收器端，至少進行10次譯碼迭代。仿真結(jié)果如圖6所示。

圖6 不同譯碼算法在WiMAX標準中的性能仿真比較

在圖6中，與使用二進制Turbo碼的性能仿真相比，所提出的算法與Constant Log-MAP算法的BER性能之間的差異減小，Log-MAP算法與Max-Log-MAP算法的BER性能差異也減小。尤其，當R＞1/2時，可以看出所提出的算法達到了與Constant Log-MAP算法幾乎相同的性能，BER=10-6時，甚至更低。

4 硬件復(fù)雜度分析

表1給出了所提出的n輸入近似max*算法結(jié)構(gòu)(用C表示)在空間(用A表示)和延遲(用D表示)兩個方面與兩種基于樹結(jié)構(gòu)的算法進行比較:1)基于3 bit LUT的2輸入的Log-MAP算法結(jié)構(gòu)(用A表示);2)2輸入的Constant Log-MAP算法結(jié)構(gòu)［4］(用 B 表示)。

表1 不同算法的硬件結(jié)構(gòu)空間及延遲比較

實驗均表明，所提出算法的結(jié)構(gòu)不但比基于LUT的Log-MAP算法的遞歸結(jié)構(gòu)和近似的Constant Log-MAP算法的結(jié)構(gòu)空間大大減小，而且在更高的時鐘頻率運行時具有較低的延遲。如表1中，假設(shè)n=16，p=16時，所提出的n輸入的max*結(jié)構(gòu)需要5 768個等同的門，具有2 ns的最小延遲，而2輸入的Constant Log-MAP結(jié)構(gòu)需要7 312個等同的門，具有2.8 ns的最小延遲。因此所提出的n輸入的max*結(jié)構(gòu)空間減少了21%，延遲降為2輸入Constant Log-MAP結(jié)構(gòu)的28.5%。在具有與Constant Log-MAP算法(B)相同的延遲時(DB)作更近一步比較，對應(yīng)的比較結(jié)果如表1中最后一列所示?？梢钥闯觯藭r與Constant Log-MAP硬件復(fù)雜度相比，所提出的結(jié)構(gòu)平均節(jié)省了大概30%的空間。

5 小結(jié)

本文給出了Turbo碼譯碼的簡化的Log-MAP譯碼算法，對其譯碼過程中的max*運算進行新的近似，并對其硬件實現(xiàn)結(jié)構(gòu)進行了簡化。max*運算是廣義上的對n個輸入值計算的簡化，將max*運算近似為簡單的max運算和相關(guān)函數(shù)的計算。仿真結(jié)果表明，這種方法相對于Log-MAP譯碼算法，性能有很小的損失，可以忽略不計。從實踐的角度來看，新的改進算法的優(yōu)勢是顯著降低了每個譯碼步驟的譯碼復(fù)雜度，簡化了硬件結(jié)構(gòu)，降低了延遲，具有廣闊的工程應(yīng)用前景。

［1］ BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding and decoding:Turbo codes［C］//Proc.the IEEE International Conference on Communications.Geneva:IEEE Press，1993:1064-1070.

［2］ BAHL L R，COCKE J，JELINEK F，et al.Optimal decoding of linear codes for minimizing symbol error rate［J］.IEEE Trans.Information Theory，1974，3(20):284-287.

［3］孫增友，張利杰，田勇.SF-MAX-Log-MAP并行譯碼算法及其在LTE中的應(yīng)用研究［J］.東北電力大學(xué)學(xué)報，2012，32(4):35-39.

［4］ GROSSW J，GULAK P G.Simplified MAP algorithm suitable for implementation of turbo SISOalgorithms based on Log-MAPand Max-Log-MAP turbo decoding［J］.IET Proc.Commun.，2007，1(1):49-57.

［5］ PAPAHARALABOSS，SWEENEY P，EVANS B G.SISO algorithms based on Log-MAP and Max-Log-MAP turbo decoding［J］.IET Proc.Commun.，2007，1(1):49-57.

［6］劉東華.Turbo碼原理與應(yīng)用技術(shù)［M］.北京:電子工業(yè)出版社，2004.

［7］ WEY CL，SHIEH M D，LIN SY.Algorithms of finding the first two minimum values and their hardware implementation ［J］.IEEE Trans.Circuits Syst.I，2008，55(11):3430-3437.

［8］張凱.CCSDS標準Turbo碼譯碼器設(shè)計及實現(xiàn)［D］.北京:北京郵電大學(xué)，2013.

［9］ IEEE802.16e-2005，Standard for local and metropolitan area networks.Part16:air interface for fixed and mobile broadband wireless access systems［S］.2006.