MAP算法在Turbo码译码中的应用和研究进展

1、MAP算法在Turbo码译码中的应用和研究进展摘要：对Turbo码译码算法进行了综述，包括SOVA、MAP、LOG-MAP、MAX-LOG-MAP等算法，并对这几种算法进行了比较。同时根据近年来对Turbo码译码算法的研究，对几种新的译码算法进行了介绍和讨论。关键词：信道编码;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，就以其优越的译码性能倍受关注，并广泛应用于包括3G2在内的各种通信体系中。目前对Turbo码的研究主要集中在译码算法、交织器设计和译码结构等方面。Turbo码的译码算法总体上可分为MAP和SOVA两类主要算法3。MAP类算法主要包括MAP算法、LOG-MAP算法、MAX-LOG-MAP算法。其中MAP算法是一种最佳后验率算法,LOG-MAP是MAP算法在对数域上的计算方式，MAX-LOG-MAP算法是对LOG-MAP算法简化

4、后的次优算法。SOVA类算法主要包括软输出的维特比算法（SOVA）和连续列表输出维特比算法（SLVA）4。本文对上述各类译码算法做了综述，同时针对近年来对Turbo码译码算法分析和研究给出的一些新的方法和结论，进行了介绍和展望。由于MAP算法的性能较SOVA算法优越，所以MAP算法目前成为主要研究的算法，本文也将它作为主要的讨论问题。 二、Turbo码译码原理典型的Turbo码模型为并行译码（PCCC，Parallel Concatenated Convolutional Code）模型5，其编码结构比较简单，因此下面主要对PCCC模型中的译码部分进行介绍。从结构上看，Turbo码和以往编码方

5、案相比，它在译码方面引入了迭代译码方式。图1为具有2个编码器的Turbo码译码器的结构图。其中译码器I和II分别与编码器中的2个子编码器相对应，交织器、解交织器与编码器中的交织器相对应，译码器之间用交织器和解交织器相连。由图1可以看出每个译码器有3个输入：系统信息的信道输出xk；相应编码器的校验比特的信道输出yk1(或yk2)；其它译码器所提供的先验信息La。基本译码过程为：xk、yk1和La1进入译码器，由译码器根据某个译码算法完成对RSC编码器I所产生的编码序列的译码，并生成信息比特uk的外部信息Le1。Le1经过交织后，生成作为译码器的信息比特的先验信息Le2；接收的信息序列xk经过相同

6、的交织，作为译码器的接收信息。译码器利用交织后得到的译码信息La2、xk和yk2完成编码器的译码，得到外部信息Le2。Le2经解交织后得的La1作为译码器I的先验信息进入下一迭代运算。当迭代次数完成或达到其它判决条件时，经交织得到用于最终译码判决的值Lu。为了保证译码器之间能充分利用对方的译码信息，成员译码器应该输出软判决译码信息，即取二进制值0或1的概率。 三、Turbo码译码的主要算法1. SOVA算法SOVA算法是在维特比算法基础上,使其具有提供软判决输出和利用外部信息能力的一种算法。该算法在选择路径时,利用先验信息和软输入信息求出系统序列最大似然ML路径。SOVA算法是一种次优算法6，

7、在AWGN信道中，它的性能与MAP算法相比下降0.5 dB。但由于它算法较为简单,计算量和存贮量都比MAP算法小,所以在通信领域中应用广泛。目前对它的研究主要集中在改进算法提高性能方面，如通过正向和反向分别求解SOVA综合得到路径7。2. MAP算法MAP算法8是一种实现最小位错概率的最大似然率法。它是运用最佳译码策略,将接收序列y等效为一个马尔可夫链，通过对该有扰马尔可夫过程的每一时刻的状态和转移的后验进行求解(APP) 并进而得到uk的最大似然率的一种方法。 式(1)中的Ak(s)为前向递推概率,Bk(s)为后向递推概率, Me(e)为分支尺度,它的基本解码步骤如下：(1)接收到序列y后,

8、初始分Ak(s)、Bk(s)及先验信息La(k);(2)根据La(k)和序列y，分别向前递推求Ak(s)（k=1,N）,向后递推求Bk(s)（k=N,1)）;(3)将Ak(s)、Bk(s)、Me(e)代入式（1）中，得到新的La(k)代入下一解码器;(4)判断迭代次数，如未完成，转到(1)开始下一步迭代译码;如完成，作判决输出。3. LOG-MAP算法和MAX-LOG-MAP算法LOG-MAP算法9是将MAP算法中的变量转换到对数域中的最佳译码算法。它利用对数的单调递增性使MAP算法大部分的乘法运算转换成加法运算10，从而减少运算量。下面是LOG-MAP对应到MAP的对数似然比(LLR,Log

9、-Likelihood Ratio)： 上式中的k(e)、k(s)和k(s)分别为Mk(e)、Ak(s)和Bk(s)在对数域中表示。算子max*()是对对数和的估算, 可以通过查表法利用其估算出对数之和，它被广泛用于LOG-MAP算法中： MAX-LOG-MAP是LOG-MAP算法的改进算法，它是一种易于实现的次优算法10，但在AWGN信道中，特别是低信噪比中性能的损失较大。MAX-LOG-MAP通过前向和后向递归来逼近LOG-MAP算法。它与LOG-MAP算法的区别是通过用简单的max()函数来替代复杂的max*()函数实现的。研究表明：在AWGN信道中用MAX-LOG-MAP代替MAP或L

10、OG-MAP算法，性能仅下降0.5dB。 四、Turbo码译码算法的新发展LOG-MAP算法通过在对数域上的运算，在不降低性能的情况下大大减少了运算量，所以目前对MAP类算法的讨论主要集中在LOG-MAP算法上。但它也存在以下几个缺点： (1）需要在接收到整帧的信息比特后，才能开始译码计算; (2）与接收序列大小成正比的存储量; (3）每步计算都要进行前向和后向迭代。 为了克服这些缺点，同时在不影响性能的前提下，目前已经提出了几种新的改进算法。 1. 滑窗算法 运用LOG-MAP算法的SISO(Soft-Input Soft-Output）模块需要在收到整个序列后，才能开始进行译码运算,这种限

11、制是因为后向递推运算需要从栅格的最终状态开始,这样就产生了2个缺陷:首先，信息比特必需按帧传输，而且尾比特(加到每帧后面用于结束栅格的比特)会减小带宽的利用率;其次，随着帧长度增加,系统的延时和对内存的需求会增加到令人无法忍受的地步。但与之相矛盾的是，帧长度的增加会提高交织增益。滑动窗技术被用来解决以上问题11。滑动窗的软输入输出模块(SW-SISO)是在SISO模块中插入一个滑动窗口。SW-SISO将收到的序列分割成长为Nu的窗口。Nu步栅格的软输出由Nw=Nu+Nt步栅格产生。这里的Nu是修正窗的长度, Nt是训练窗的长度。SW-SISO在窗口的长度为中的执行过程与SISO中一个帧的执行过

12、程相同,仅有的不同是对后反馈路径尺度的初始化。在每个窗口执行完成后, Nu个软输出将产生。 接着SW-SISO跳过Nu步进行下一个窗口长为Nw的计算。SW-SISO与SISO相比较, 前者比后者明显减少k(s)的存贮量(从(N-1)2m降到Nu2m)。如果延迟只来自对接收信号的等待,则SISO的延迟为Nn0，而SW-SISO的延迟为(Nu+Nt)n0。另外， 因为Nu和Nt与N无关，所以系统的存贮量和延时不再由帧长度决定。Nu和Nt的大小的确定对滑窗效果的影响，以及它们和计算量、存储量之间的关系，在文献12、13中进行了仿真和讨论。2. WAB算法WAB（wait for the comput

13、ation of backward metrics）算法实质上是LOG-MAP算法的实现方式，应用这种方式可以有效地减少系统的存储量和延时。这种方法的核心：如式（5）所示,LOG-MAP算法通常包括计算前向路径尺度k(s)和后向路径尺度k(s)。它们其中一个可被首先计算并存贮，然后等待另一个计算出来后代入式（5）进行计算。为了随着时间标识的增加而产生软输出，后向递归应被首先执行，来得到全部k(s)，当所有的k(s)在k(s)之前计算后，不是所有的k(s)需要保存,而仅最新计算出的k-1(s)需要保存，就可以计算出输出当前的LLR。在WAB中所有k(s)的值必须保存，用来计算输出的LLR。这就产

14、生了一个问题，当帧的长度是很大时，就有2mN个k(s)需要存储。所以近年来在WAB的基础上，有人提出了前向计算后向路径尺度算法 14。前向计算后向路径尺度算法的具体实现如下：设k0=1，n0=2，所以对于编码器的每种状态，都存在两种输出的可能,于是可得下式: 从上式可以看出，可通过k(s)得到k+1(s)。由仿真结果可知，这种直接运算的方法存在数值稳定性问题。但如果通过将帧分为大小为Nb的块来计算，可以克服以上缺点。这种算法对的存取量需求减少到2mNb，很好地解决了LOG-MAP算法对存取量需求大的问题。但在计算中对进行了前向后向二次求解，增大了计算量，而且它的信息比特也必需按帧传输。目前对以

15、上2个矛盾，前者还没有有效的方法；后者可以利用滑窗技术来解决。3. Bayesian网络算法Bayesian网络算法15，16是在把Turbo码的编码序列视为马尔可夫链的基础上提出的。它将Turbo码的译码同用于人工智能系统中来解决概率推理问题的peal信息传播算法相联系，用Bayesian网络图模型来描述Turbo码编码，从而利用该模型中的信息传播机制，建立Turbo码的译码算法。因为Bayesian网络的结构特性，利用该方式译码的Turbo码译码是并行进行的，所以它可以有效地利用多个子译码器同时进行译码，提高资源利用率，加快译码速度，减少迭代次数。由仿真可知，它在高斯信道下译码性能比PCC

16、C译码更接近香农限。但这种算法也有其不足的地方，主要是复杂度和计算量比较大，如果要得到实际应用还需要对该算法进行改进。此外近年来应用神经网络技术来解决Turbo码译码的方案17也被提出，但从目前得到的结果来看，还没有取得理想的效果。 五、结束语到目前为止，Turbo码已经有了很大的发展，在各方面都到达了实用阶段。但Turbo码的作用机制尚不十分清楚，对迭代译码算法的性能还缺乏有效的理论解释。同时，Turbo码存在的主要问题,包括序列延迟、计算量大、存储量大等矛盾还没有得到完全解决。因此，目前对Turbo码算法方面的研究主要从以下几个方面着手:(1）从理论上进行完整的分析;(2）针对各种Turb

17、o码算法和结构进行仿真，比较它们在不同环境下的性能指标;(3）译码性能的好坏根本在于码间距离，所以寻找构造好码的规律是提高Turbo译码性能的关键;(4）译码性能的进一步简化;(5）Turbo码编码与信道参数的综合设计。 参考文献 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码译码的改进SOVA算法.

20、 南京邮电学院学报，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