MAP算法在Turbo碼譯碼中的應(yīng)用和研究進(jìn)展

1、MAP算法在Turbo碼譯碼中的應(yīng)用和研究進(jìn)展摘要：對Turbo碼譯碼算法進(jìn)行了綜述，包括SOVA、MAP、LOG-MAP、MAX-LOG-MAP等算法，并對這幾種算法進(jìn)行了比較。同時(shí)根據(jù)近年來對Turbo碼譯碼算法的研究，對幾種新的譯碼算法進(jìn)行了介紹和討論。關(guān)鍵詞：信道編碼;Turbo碼；MAP算法；LOG-MAP算法 Application and Development of MAP Algorithm in Turbo Decoding YAO Yuan, QIU Tian-shuang (Department of Electronic Engineering, Dalian Uni

2、versity of Technology,Dalian 116024,China) ：This paper summarizes the Turbo decoding algorithms, including SOVA, MAP, LOG-MAP, MAX-LOG-MAP, etc, and compares the performance of these algorithms. Based on the research in the recent years, this paper introduces new algorithms and presents detailed dis

3、cussion.： Channel code; Turbo code; MAP algorithm; LOG-MAP algorithm 一、引言Turbo碼自提出以來1，就以其優(yōu)越的譯碼性能倍受關(guān)注，并廣泛應(yīng)用于包括3G2在內(nèi)的各種通信體系中。目前對Turbo碼的研究主要集中在譯碼算法、交織器設(shè)計(jì)和譯碼結(jié)構(gòu)等方面。Turbo碼的譯碼算法總體上可分為MAP和SOVA兩類主要算法3。MAP類算法主要包括MAP算法、LOG-MAP算法、MAX-LOG-MAP算法。其中MAP算法是一種最佳后驗(yàn)率算法,LOG-MAP是MAP算法在對數(shù)域上的計(jì)算方式，MAX-LOG-MAP算法是對LOG-MAP算法簡化

4、后的次優(yōu)算法。SOVA類算法主要包括軟輸出的維特比算法（SOVA）和連續(xù)列表輸出維特比算法（SLVA）4。本文對上述各類譯碼算法做了綜述，同時(shí)針對近年來對Turbo碼譯碼算法分析和研究給出的一些新的方法和結(jié)論，進(jìn)行了介紹和展望。由于MAP算法的性能較SOVA算法優(yōu)越，所以MAP算法目前成為主要研究的算法，本文也將它作為主要的討論問題。 二、Turbo碼譯碼原理典型的Turbo碼模型為并行譯碼（PCCC，Parallel Concatenated Convolutional Code）模型5，其編碼結(jié)構(gòu)比較簡單，因此下面主要對PCCC模型中的譯碼部分進(jìn)行介紹。從結(jié)構(gòu)上看，Turbo碼和以往編碼方

5、案相比，它在譯碼方面引入了迭代譯碼方式。圖1為具有2個(gè)編碼器的Turbo碼譯碼器的結(jié)構(gòu)圖。其中譯碼器I和II分別與編碼器中的2個(gè)子編碼器相對應(yīng)，交織器、解交織器與編碼器中的交織器相對應(yīng)，譯碼器之間用交織器和解交織器相連。由圖1可以看出每個(gè)譯碼器有3個(gè)輸入：系統(tǒng)信息的信道輸出xk；相應(yīng)編碼器的校驗(yàn)比特的信道輸出yk1(或yk2)；其它譯碼器所提供的先驗(yàn)信息La?；咀g碼過程為：xk、yk1和La1進(jìn)入譯碼器，由譯碼器根據(jù)某個(gè)譯碼算法完成對RSC編碼器I所產(chǎn)生的編碼序列的譯碼，并生成信息比特uk的外部信息Le1。Le1經(jīng)過交織后，生成作為譯碼器的信息比特的先驗(yàn)信息Le2；接收的信息序列xk經(jīng)過相同

6、的交織，作為譯碼器的接收信息。譯碼器利用交織后得到的譯碼信息La2、xk和yk2完成編碼器的譯碼，得到外部信息Le2。Le2經(jīng)解交織后得的La1作為譯碼器I的先驗(yàn)信息進(jìn)入下一迭代運(yùn)算。當(dāng)?shù)螖?shù)完成或達(dá)到其它判決條件時(shí)，經(jīng)交織得到用于最終譯碼判決的值Lu。為了保證譯碼器之間能充分利用對方的譯碼信息，成員譯碼器應(yīng)該輸出軟判決譯碼信息，即取二進(jìn)制值0或1的概率。 三、Turbo碼譯碼的主要算法1. SOVA算法SOVA算法是在維特比算法基礎(chǔ)上,使其具有提供軟判決輸出和利用外部信息能力的一種算法。該算法在選擇路徑時(shí),利用先驗(yàn)信息和軟輸入信息求出系統(tǒng)序列最大似然ML路徑。SOVA算法是一種次優(yōu)算法6，

7、在AWGN信道中，它的性能與MAP算法相比下降0.5 dB。但由于它算法較為簡單,計(jì)算量和存貯量都比MAP算法小,所以在通信領(lǐng)域中應(yīng)用廣泛。目前對它的研究主要集中在改進(jìn)算法提高性能方面，如通過正向和反向分別求解SOVA綜合得到路徑7。2. MAP算法MAP算法8是一種實(shí)現(xiàn)最小位錯(cuò)概率的最大似然率法。它是運(yùn)用最佳譯碼策略,將接收序列y等效為一個(gè)馬爾可夫鏈，通過對該有擾馬爾可夫過程的每一時(shí)刻的狀態(tài)和轉(zhuǎn)移的后驗(yàn)進(jìn)行求解(APP) 并進(jìn)而得到uk的最大似然率的一種方法。 式(1)中的Ak(s)為前向遞推概率,Bk(s)為后向遞推概率, Me(e)為分支尺度,它的基本解碼步驟如下：(1)接收到序列y后,

8、初始分Ak(s)、Bk(s)及先驗(yàn)信息La(k);(2)根據(jù)La(k)和序列y，分別向前遞推求Ak(s)（k=1,N）,向后遞推求Bk(s)（k=N,1)）;(3)將Ak(s)、Bk(s)、Me(e)代入式（1）中，得到新的La(k)代入下一解碼器;(4)判斷迭代次數(shù)，如未完成，轉(zhuǎn)到(1)開始下一步迭代譯碼;如完成，作判決輸出。3. LOG-MAP算法和MAX-LOG-MAP算法LOG-MAP算法9是將MAP算法中的變量轉(zhuǎn)換到對數(shù)域中的最佳譯碼算法。它利用對數(shù)的單調(diào)遞增性使MAP算法大部分的乘法運(yùn)算轉(zhuǎn)換成加法運(yùn)算10，從而減少運(yùn)算量。下面是LOG-MAP對應(yīng)到MAP的對數(shù)似然比(LLR,Log

9、-Likelihood Ratio)： 上式中的k(e)、k(s)和k(s)分別為Mk(e)、Ak(s)和Bk(s)在對數(shù)域中表示。算子max*()是對對數(shù)和的估算, 可以通過查表法利用其估算出對數(shù)之和，它被廣泛用于LOG-MAP算法中： MAX-LOG-MAP是LOG-MAP算法的改進(jìn)算法，它是一種易于實(shí)現(xiàn)的次優(yōu)算法10，但在AWGN信道中，特別是低信噪比中性能的損失較大。MAX-LOG-MAP通過前向和后向遞歸來逼近LOG-MAP算法。它與LOG-MAP算法的區(qū)別是通過用簡單的max()函數(shù)來替代復(fù)雜的max*()函數(shù)實(shí)現(xiàn)的。研究表明：在AWGN信道中用MAX-LOG-MAP代替MAP或L

10、OG-MAP算法，性能僅下降0.5dB。 四、Turbo碼譯碼算法的新發(fā)展LOG-MAP算法通過在對數(shù)域上的運(yùn)算，在不降低性能的情況下大大減少了運(yùn)算量，所以目前對MAP類算法的討論主要集中在LOG-MAP算法上。但它也存在以下幾個(gè)缺點(diǎn)： (1）需要在接收到整幀的信息比特后，才能開始譯碼計(jì)算; (2）與接收序列大小成正比的存儲量; (3）每步計(jì)算都要進(jìn)行前向和后向迭代。 為了克服這些缺點(diǎn)，同時(shí)在不影響性能的前提下，目前已經(jīng)提出了幾種新的改進(jìn)算法。 1. 滑窗算法 運(yùn)用LOG-MAP算法的SISO(Soft-Input Soft-Output）模塊需要在收到整個(gè)序列后，才能開始進(jìn)行譯碼運(yùn)算,這種限

11、制是因?yàn)楹笙蜻f推運(yùn)算需要從柵格的最終狀態(tài)開始,這樣就產(chǎn)生了2個(gè)缺陷:首先，信息比特必需按幀傳輸，而且尾比特(加到每幀后面用于結(jié)束柵格的比特)會(huì)減小帶寬的利用率;其次，隨著幀長度增加,系統(tǒng)的延時(shí)和對內(nèi)存的需求會(huì)增加到令人無法忍受的地步。但與之相矛盾的是，幀長度的增加會(huì)提高交織增益。滑動(dòng)窗技術(shù)被用來解決以上問題11?；瑒?dòng)窗的軟輸入輸出模塊(SW-SISO)是在SISO模塊中插入一個(gè)滑動(dòng)窗口。SW-SISO將收到的序列分割成長為Nu的窗口。Nu步柵格的軟輸出由Nw=Nu+Nt步柵格產(chǎn)生。這里的Nu是修正窗的長度, Nt是訓(xùn)練窗的長度。SW-SISO在窗口的長度為中的執(zhí)行過程與SISO中一個(gè)幀的執(zhí)行過

12、程相同,僅有的不同是對后反饋路徑尺度的初始化。在每個(gè)窗口執(zhí)行完成后, Nu個(gè)軟輸出將產(chǎn)生。 接著SW-SISO跳過Nu步進(jìn)行下一個(gè)窗口長為Nw的計(jì)算。SW-SISO與SISO相比較, 前者比后者明顯減少k(s)的存貯量(從(N-1)2m降到Nu2m)。如果延遲只來自對接收信號的等待,則SISO的延遲為Nn0，而SW-SISO的延遲為(Nu+Nt)n0。另外， 因?yàn)镹u和Nt與N無關(guān)，所以系統(tǒng)的存貯量和延時(shí)不再由幀長度決定。Nu和Nt的大小的確定對滑窗效果的影響，以及它們和計(jì)算量、存儲量之間的關(guān)系，在文獻(xiàn)12、13中進(jìn)行了仿真和討論。2. WAB算法WAB（wait for the comput

13、ation of backward metrics）算法實(shí)質(zhì)上是LOG-MAP算法的實(shí)現(xiàn)方式，應(yīng)用這種方式可以有效地減少系統(tǒng)的存儲量和延時(shí)。這種方法的核心：如式（5）所示,LOG-MAP算法通常包括計(jì)算前向路徑尺度k(s)和后向路徑尺度k(s)。它們其中一個(gè)可被首先計(jì)算并存貯，然后等待另一個(gè)計(jì)算出來后代入式（5）進(jìn)行計(jì)算。為了隨著時(shí)間標(biāo)識的增加而產(chǎn)生軟輸出，后向遞歸應(yīng)被首先執(zhí)行，來得到全部k(s)，當(dāng)所有的k(s)在k(s)之前計(jì)算后，不是所有的k(s)需要保存,而僅最新計(jì)算出的k-1(s)需要保存，就可以計(jì)算出輸出當(dāng)前的LLR。在WAB中所有k(s)的值必須保存，用來計(jì)算輸出的LLR。這就產(chǎn)

14、生了一個(gè)問題，當(dāng)幀的長度是很大時(shí)，就有2mN個(gè)k(s)需要存儲。所以近年來在WAB的基礎(chǔ)上，有人提出了前向計(jì)算后向路徑尺度算法 14。前向計(jì)算后向路徑尺度算法的具體實(shí)現(xiàn)如下：設(shè)k0=1，n0=2，所以對于編碼器的每種狀態(tài)，都存在兩種輸出的可能,于是可得下式: 從上式可以看出，可通過k(s)得到k+1(s)。由仿真結(jié)果可知，這種直接運(yùn)算的方法存在數(shù)值穩(wěn)定性問題。但如果通過將幀分為大小為Nb的塊來計(jì)算，可以克服以上缺點(diǎn)。這種算法對的存取量需求減少到2mNb，很好地解決了LOG-MAP算法對存取量需求大的問題。但在計(jì)算中對進(jìn)行了前向后向二次求解，增大了計(jì)算量，而且它的信息比特也必需按幀傳輸。目前對以

15、上2個(gè)矛盾，前者還沒有有效的方法；后者可以利用滑窗技術(shù)來解決。3. Bayesian網(wǎng)絡(luò)算法Bayesian網(wǎng)絡(luò)算法15，16是在把Turbo碼的編碼序列視為馬爾可夫鏈的基礎(chǔ)上提出的。它將Turbo碼的譯碼同用于人工智能系統(tǒng)中來解決概率推理問題的peal信息傳播算法相聯(lián)系，用Bayesian網(wǎng)絡(luò)圖模型來描述Turbo碼編碼，從而利用該模型中的信息傳播機(jī)制，建立Turbo碼的譯碼算法。因?yàn)锽ayesian網(wǎng)絡(luò)的結(jié)構(gòu)特性，利用該方式譯碼的Turbo碼譯碼是并行進(jìn)行的，所以它可以有效地利用多個(gè)子譯碼器同時(shí)進(jìn)行譯碼，提高資源利用率，加快譯碼速度，減少迭代次數(shù)。由仿真可知，它在高斯信道下譯碼性能比PCC

16、C譯碼更接近香農(nóng)限。但這種算法也有其不足的地方，主要是復(fù)雜度和計(jì)算量比較大，如果要得到實(shí)際應(yīng)用還需要對該算法進(jìn)行改進(jìn)。此外近年來應(yīng)用神經(jīng)網(wǎng)絡(luò)技術(shù)來解決Turbo碼譯碼的方案17也被提出，但從目前得到的結(jié)果來看，還沒有取得理想的效果。 五、結(jié)束語到目前為止，Turbo碼已經(jīng)有了很大的發(fā)展，在各方面都到達(dá)了實(shí)用階段。但Turbo碼的作用機(jī)制尚不十分清楚，對迭代譯碼算法的性能還缺乏有效的理論解釋。同時(shí)，Turbo碼存在的主要問題,包括序列延遲、計(jì)算量大、存儲量大等矛盾還沒有得到完全解決。因此，目前對Turbo碼算法方面的研究主要從以下幾個(gè)方面著手:(1）從理論上進(jìn)行完整的分析;(2）針對各種Turb

17、o碼算法和結(jié)構(gòu)進(jìn)行仿真，比較它們在不同環(huán)境下的性能指標(biāo);(3）譯碼性能的好壞根本在于碼間距離，所以尋找構(gòu)造好碼的規(guī)律是提高Turbo譯碼性能的關(guān)鍵;(4）譯碼性能的進(jìn)一步簡化;(5）Turbo碼編碼與信道參數(shù)的綜合設(shè)計(jì)。 參考文獻(xiàn) 1CBerrou, AGlavieux, PThitimasjshima. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes(1)A. ICCC.Switztland：Geneva,1993.2TS 25. 212 V2.2.0(1999-09). 3rd Generation

18、Partnership Project(3GPP)EBOL. /.Woodardjp, Hanzol. Comparative Study of Turbo Decoding Techniques: An OverviewJ.IEEE Trans on Vehicular Technology,2000，49(6)：22082233.4CNill, WSundberg. List and soft symbol output Viterbi algorithms： extersions and comparisons. I

19、EEE Trans. Commun., 1995，43：277287.5SBenedetto，GMontorsi. Design of parallel concatenated Convolutional codes. IEEE Trans. Commun.,1996，44（5）： 591600.6JHagenauer, PHoeher. A Viterbi Algorithm with Soft-Decision Outputs and its Applications. Proc. Globecom89C.1989 16801686.7劉陳，吳成林. Turbo碼譯碼的改進(jìn)SOVA算法.

20、 南京郵電學(xué)院學(xué)報(bào)，2002，22（3）.8CBerrou, AGlavieux, PThitimasjshima. Near Shannon limit error-correcting coding and decoding: Turbo codes(1)A. Proc IEEE Int Conf on CommunicationsC. Switzerland: Geneva, 199.10641070.9SBenedetto, DDivsalar, GMontorsi, et al. Soft-output decoding algorithms in iterative decodin

21、g of turbo codes. JPL TDA Progress Report, 1996.21210PRobertson, EVillebrun, PHoeher. A comparison of optimal and suboptimal MAP decoding algorithms operating in the log domain. Proc., IEEE Int. Conf. on Commun. 1995.1009101311SABarbulescu. Sliding window and interleaver design. Electronics Letters , 2001，37（21）12NKKim，MSYang，SYKim，et al. Savingmemory in turbo trellis coded modulation using the sliding window. The 57th IEEE Semiannual（Vol