一种新的联合译码方案研究

石雅盟，李建平

(中国传媒大学信息工程学院，北京100024)

1 引言

1993 年，Turbo码由 C.Berrou 等人提出［1］，目前已经被广泛地应用于许多通信系统标准中。Turbo码的译码算法主要有三种:对数最大后验译码算法(Log Maximum A Posteriori，Log-Map)，Maximum Log-Map(Max-Log-Map)算法和软输出维特比译码算法(Soft-Output Viterbi，SOVA)。Log-Map算法具有较低的误码率性能，Max-Log-Map是Log-Map的简化。相比于Log-Map，后两种算法具有较低的计算复杂度，但是Max-Log-Map在误码率为10-5时比Log-Map小0.5dB的编码增益，SOVA则要比Log-Map小0.5-1.0dB的编码增益。现已有许多改进的算法来提高Max-Log-Map的性能［2，3］，但是需要增加一些必要的计算复杂度。本文不改变算法本身，提出一种新的联合译码算法结构，进一步提高Turbo译码的性能。

2 译码算法简介

2.1 MAP译码算法

最大后验概率算法(Maximum A Posteriori，MAP)，也称BCJR 算法［4］，首次由 Bahl等人于1974年提出。在MAP算法提出后的将近20年时间里，由于其计算量大和硬件实现复杂性高而一直没有得到重视。直到1993年Turbo码的发明者在其最初的Turbo迭代译码方案中采用了修正的MAP算法，相应的各种简化算法也开始不断出现。MAP算法是基于编码网格图的软输出译码算法，目的是使译码输出比特错误概率最小。根据最大似然译码原理，译码器的主要任务就是计算在接收采样条件下不同发送符号的概率，即P(uk=u|Y)。而后将接收采样判决为概率值最大的信息符号，即

u＇=arg(maxu:ujεuP(uj=u|Y)) (1)现定义一个编码网格图中边的概念，也叫做分支，如图1:

图1 网格图中的边

假设系统采用BPSK调制，则发送符号与码字的关系为:

式中，Es为信号平均功率，k时刻译码输出信息比特概率Pk(u;o)为

对于递归系统卷积码编码器，当k时刻状态SK已知时，k时刻以后发生的事件与之前的输入无关，等效一个马尔科夫源。因此，式(3)中联合条件概率αk(s)和βk(s)可分别通过前向和后向递推计算得到

其计算过程如图2所示。

图2 αk(s)和βk(s)计算过程

若编码器的初始状态S0和结束状态SN均已知，则上述递推初值可设定为

为了防止溢出，一般要将因子归一化。

式(3)中ɣk(e)称为边度量或分支度量，利用贝叶斯公式，有

式中，第一项为网格图中分支(边)的状态转移概率，由信息比特的先验信息La(uk)决定

式中，

第二项P(Xk|e)根据XK是否与边e有关而取值为1或0;最后一项根据信道模型的不同而有所区别。例如对于AWGN信道上采用BPSK调制的传输系统，有

对于二元输入，可以用对数似然比(LLR)作为判决函数

MAP算法根据L(uk)的值进行判决

2.2 Log-Map算法和MAX-Log-Map算法

上面介绍的MAP算法，由于它的运算复杂度很高，包含了大量的乘法运算，因此给实现带来了较大困难。所以在实际应用中采用的大都是MAP的对数域算法，可以化乘法为加法，可大大减少运算量如MAX-Log-Map 算法和 Log-Map 算法［5，6］。

在 Log-Map 算法中，Mk(e)、Ak(S)、Bk(S)与MAP 算法中 ɣk(e)、αk(s)、βk(s)相对应，它们之间满足对数关系

分别代入对应公式，最后得到

其中，在Log-Map算法中引入max*(.)操作，定义为

通常，可以对上述max*(.)操作进行变形，对于两个量变的情况(x和y)，有

max(x，y)为最大值函数，fc(|x-y|)为修正函数。当x与y的值相差较大时fc(|x-y|)值趋向于0，则上式可以进一步简化为

此时Log-Map算法转换为MAX-Log-Map算法，计算量进一步降低。

2.3 维特比算法

假设编码器送出的码序列C，经过离散无记忆信道传输后送入译码器的是序列R=C+E，E是信道加上的噪声序列。译码器根据接受序列R，按最大似然译码准则力图找出编码器在网格图上所走过的路径，这个过程就是译码器计算、寻找最大似然函数

的过程，或者说译码器计算、寻找有最大度量路径过程，即寻找

的过程。式中，M(R|Cj)=logbP(R|Cj)是Cj的自然函数，也称为Cj的路径度量。

可以将维特比算法步骤总结如下［7］:

第一步，在时间单元t=m开始，计算进入每一状态的单个路径的部分量度。存储每一状态下的路径(幸存的)及其量度。

第二步，t增加1。将进入某一状态的分支量度与前一时间单元有关的幸存路径的量度相加，计算进入该状态的所有2k路径的部分量度。对每一状态，比较进入该状态的所有2k路径的量度，选择具有最大量度的路径(幸存路径)，存储该路径及其度量，并删除其他所有路径。

第三步，如果t＜h+m，重复步骤2;否则停止。维特比算法执行的基本运算是步骤2中的加法、比较和选择操作。作为一个实际考虑，对每个状态，在步骤1和2中存储的是对应于幸存路径的信息序列，而不是幸存路径本身，因而当算法结束时，不需要对估计码字序列进行转化以恢复估计信息序列。

3 新的译码结构设计

在编码及调制解调方面，均采用经典编码调制系统方案在译码部分，不同于传统Turbo译码的两个SISO译码器并行级联结构，我们采用三个译码器，前两个依然按照并行结构级联，并且应用Log-Map译码算法相互进行迭代;添加的第三个译码器的输入有三个:第一个译码器输出的校验位估计软值序列Lp1，第二个译码器输出的系统位估计软值序列Ls以及最后一次更新的外信息序列Le21。第三个译码器采用软输入软输出维特比译码算法。最后将译码器三的信息软值序列进行硬判决输出。译码结构如图3所示。

在此结构中，输入到译码器3的系统位、校验位软值已经较为精准，外信息也已多次更新。基于两种算法的差异，即:Log-Map算法是逐比特译码，首先能获得比较好的性能，维特比算法利用网格图选择最优路径译码，再将Log-Map中没有译出来的比特更正，结合两者优势，联合译码性能理论上可以获得更低的误码率。

图3 Log-Map与viterbi联合译码结构图

4 仿真结果与分析

首先给出以信噪比为横坐标，交织长度为1024的Log-Map与联合译码算法性能比较，生成多项式(7，5)如图4所示。

图4 Log-Map与联合译码算法性能比较1

图4所示分别为第1、3、5和10次两种译码算法性能曲线。可以看出，在10次迭代以前，联合译码性能能够提高0.1-0.2db编码增益。通过实验进行10次及大于10次仿真，虽然译码器3仍可纠正Log-Map译码结果中个别比特错误，但此时Log-Map译码算法在10次迭代以后本身误码率较低，所以维特比译码进一步译出的错误比特就更为稀少。如图5所示为以迭代次数为横坐标的两种译码结构性能比较结果。

图5 Log-Map与联合译码算法性能比较2

在分析此实验结果前先介绍Turbo译码过程的几个经典的动力学分析成果。Richardson［8］首先将Turbo译码过程视为一个动力学系统进行研究，并发现了不动点的存在。之后，Agrawal［9］进一步分析出这些不动点的唯一性和稳定性，在此基础上将整个SNR区域分为三个部分并发现了分岔现象。通过雅克比矩阵特征值的情况我们能够判定出现分岔的具体类型。如果倍周期分岔出现，那么相应的奇异区内为周期二轨道。如果切分岔出现，那么Turbo译码算法不经历中间奇异区直接收敛到清晰不动点。最为复杂的是Neimark-Sacker分岔，奇异区内首先出现的是准周期轨道，紧接着周期三的出现预示着混沌轨道的存在。选取合适的交织长度N，将SNR从负无穷逐渐增大，就可以得到上述所提的三个区域，即不确定不动点、奇异区和清晰不动点。

简单的来说，经过大量实验统计，Turbo译码在低信噪比时会出现三种译码结果:1、随着译码迭代次数增加，错码个数逐渐收敛在一个清晰不动点上;2、由于译码算法本身的某种结构特性，会使一些帧的个别比特十分难译，这样就造成了错码个数为那些难译的比特数，即收敛在了一个不确定不动点上;3、除了以上两种结果，还会有个别被称为坏帧的情况存在。这些帧的错码个数不收敛，在一个不确定不动点周围震荡，错码个数较多，使得误码率较低。但是这种奇异区只出现在低信噪比条件下，当信噪比升高，基本只出现前两种情况。

联合译码就是利用了在低信噪比时出现的奇异区，译码器三可以继续将奇异区内的错码纠正来使曲线降低。但当译码次数增大或者信噪比更高时，联合译码的性能就表现不突出了。即，如图5，这是在0.7db下的仿真，可以看出在10次迭代左右，联合译码即使能稍微降低Log-Map性能曲线，但由于此时奇异区坏帧少，而维特比又不能继续译出不确定不动点的错误比特，在数据量很大的时候，联合译码所带来的编码增益只有0.03db。

5 结束语

本文首先介绍了三种重要的译码算法，然后在传统Turbo译码结构上进行改进，提出了一种新的联合译码算法。实验证明，在10次迭代以前，至少能够获得0.1dB的编码增益，降低了误码平台。

在对Log-Map译码算法的研究中，在低信噪比时发生的奇异区现象较为明显，假设能在分析透彻算法的情况下，修改原有的算法，降低奇异区的误码率或者使其收敛是一个值得研究的课题。

［1］Berrou C，Glavieux A，Thitimajshima P.Near Shannon limit error-correction coding and decoding:Turbo-codes［C］.Proc IEEE Int Conf on Communications，Geneva，Switzerland，1993:1064-1070.

［2］Talakoub S，Sabeti L，Shahrrava B，Ahmadi M.An improved Max-Log-Map algorithm for Turbo decoding and Turbo equalization［J］.IEEE Trans Instrum Meas，2007，56(3):1058-1063.

［3］Park S J.Combined Max-Log-Map and Log-Map of Turbo codes［J］.IEE Electronics Letters，2004，40(4):251-252.

［4］Bahl L R，Cocke J，Jelinek F，Raviv J.Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate［J］.IEEE Trans Inform Theroy，1974，20(2):284-287.

［5］Erfanian J，Pasupathy S，Gulak G.Reduced Complexity Symbol Detectors with Parallel Structures for ISI Channels［J］.IEEE Transaction on Communication，1994，42(234):1661-1671.

［6］Pietobon SS.Efficient Implementation of Continuous MAP Decoders and A Synchronization Technique for Turbo Decoders［C］.Int Symp on Information Theory and Its Application，1996，Victorial，BC:586-589.

［7］Shu Lin，Daniel J.Costello，J.Error Control Coding［M］.晏坚，等，译.北京:机械工业出版社，2007:343.

［8］Richardson.The Geometry of Turbo-Decoding Dynamics［J］.IEEE Trans Inform Theory，2000，46(1):9-23.

［9］Dakshi Agrawal，Alexander Vardy.The Turbo Decoding Algorithm and Its Phase Trajectories［J］.IEEE Trans.Informati on Theory，2001，47(2):699-722.