一种改进的Max-Log-Map译码算法的DSP实现

戚 楠，李立欣，范 捷，蒋少豪，张会生

（西北工业大学 电子信息学院，陕西 西安 710129）

Turbo码很好地应用了Shannon信道编码定理中的随机性编/译码条件，采用软输出迭代译码算法来逼近最大似然译码算法，从而获得了几乎接近Shannon理论极限的译码性能[1-2]。但是Turbo译码复杂度大，译码延时大不能较好地满足实时高速通信的要求，译码过程中变量占用的存储空间开销大。这些问题限制了Turbo码的广泛使用。而Max-Log-Map算法中分量译码器模块是Turbo译码中的关键部分，其时效性和变量存储量在很大程度上决定着Turbo码的译码性能。如何减少译码时延以提高译码时效性，以及如何减少存储开销都是Turbo码编译码应用于工程项目中的关键影响因素。

1 译码过程中的优化设计

分量译码器模块是译码过程中的关键步骤，所以改善该部分的译码性能对整个译码器的作用。常规计算步骤是先进行前向递推，计算出一帧数据所有比特的前向度量，然后再进行后向递推，计算出一帧数据所有比特的后向度量，再算出每比特的对数似然比和外信息，经过解交织作为SISO译码器1的先验信息进行下一轮迭代译码。其译码时延较大，且需要的变量存储量大。因此，改进子译码器的性能是改善Turbo译码性能的关键[3]。

2 译码过程中的优化设计

2.1 前、后向度量的简化

对于码元dk的译码，其条件联合概率定义为：

其中m是RSC分量编码器的状态数 （v级移位寄存器，状态 m=0，1，…，2v-1，共 2v种状态）；i为信息码元 dk的值；RN1是接收到的信息序列。

码元dk的后验概率对数似然比改写为

码元dk的后验概率。

式（1）可以写成：

则有

后向度量：

对数似然比：

转移度量：

其中xk、yk为接收序列对应于i的值，Λ（dk）为先验信息，Lc=2/δ2参数表示信道的可信度，δ2表示AWGN信道的方差。最终的译码器根据L（dk|RN1）作出判决。

观察可知公式（5）、（6）可以用蝶形图，如图1～图3所示。

图1 Aik（m）的迭代计算蝶形图Fig.1 Papilionaceous drawing of Aik（m）

图 2 B0k－1（m）的迭代计算蝶形图Fig.2 Papilionaceous drawing of B0k－1（m）

这种改进的数据计算采用蝶形结构，其最大优点是易于工程实现，在DSP芯片中可以直接调用CSSU（比较、选择、存储单元），一次性并行计算出（m）等，从而减小Turbo码的译码延时，提高译码效率[4]。

图 3 （m）的迭代计算蝶形图Fig.3 Papilionaceous drawing of（m）

2.2 数据溢出保护

在译码过程中，前向累计度量Ak和后向累计度量Bk会随着迭代不断增大。当交织长度达到一定程度时，定点DSP在递推计算前、后项度量时就会发生溢出现象，从而导致整个译码器性能的恶化。所以必须考虑溢出处理。分析对数似然比公式（7）可知，当减号两边同时减去任一常数时，并不影响正确结果，而且前向累积度量和后向累积度量虽然不断增大，但对于任一比特的前向累积度量或后向累积度量之间的差值的动态范围并不大。考虑到程序运行耗时及程序执行的方便处理可以每次度量结果后减去一个设定的数。本文设定为。每次执行后的结果进行下次迭代前初始化为（0） ，因此第二次以后的迭代译码前、后向度量的相对值，由于相对值很小，这样就能有效防止溢出。

2.3 分块并行设计

在译码过程中，用于存储中间结果的数据空间需求正比于交织长度，当交织长度较大时，传统的译码算法需要大量的存储空间保存变量值，这加大了计算时间和存储开销。为减少译码计算延时，将整个帧长分割成若干个子块，各个子块进行并行Max－Log－Map译码。设信息帧长为L，各个子块的长为K，则所分子块的块数N=L/K，并行译码结构图如图4所示。

图4 分块并行Max-Log-Map译码算法示意图Fig.4 Flow chart of the Max-Log-Map algorithm

译码器的结构与原译码器结构基本相同，每个子块都执行码元子序列的前向度量、后向度量、转移度量计算。其中，前一码元的前向度量将作为后一码元的前向度量Aik（m）初始值，后一码元的后向度量Bik（m）将作为前一码元后向计算的初值，由前向度量及传递过来的后向度量计算出其余变量值。

区别于传统的译码算法的是：分量译码器改为由N个分量译码器子块并行调用，每一子块进行相同的初始化，这些模块同时工作，并行执行各个分块的信息子序列译码，最终对结果拼接输出，因此该设计方案可以很大程度上减少译码延时。

2.4 子块内进一步优化设计

在每一子块的译码过程可以进一步优化来节省存储空间和译码延时。流程图如图5所示。

1）简化转移度量的计算。每比特的状态转移度量的计算只需要4次加法，而不需要乘法、加法的混合运算，在译码运算过程中，完全可以结合到计算前向累计度量Ak和后向累积度量Bk的递推过程中，从而节省了状态转移度量的存取操作，大大减少了计算量，提高了算法的执行速度，节省了4L（设交织长度为L）存储空间。

2）外信息的计算和前向度量并行进行，可省略对前向度量的存储，节省了8L存储空间，直接由硬判决单元根据外信息恢复出对数似然比，可以节省对似然比的存储，节省约1L的存储空间，同时减少了存储操作，提高了程序效率。

图5 Turbo子译码器流程图Fig.5 Flow chart of the Turbo sub-decoder algorithm

此种设计的优势分析如下：

①提高时效性

图6是经典的译码算法和改进的子译码算法对应的时序图（一个周期为T）。

图6 传统算法和改进后的算法时序比较图Fig.6 Comparison between the traditional algorithm and improved one

从图6中可以看出，优化后的方案减少了约3/5的译码时延，在很大程度上缩减了译码耗时。

②节约存储开销

本算法设计共节约了13L存储空间资源。优化后的算法的存储空间如表1所示。

表1 主要占用的存储空间分配Tab.1 Principal storage cost

3 DSP实现结果及性能分析

TMS320C6000系列是TI公司推出的高性能DSP系列。采用TI专利技术VeloiTI和新的超长指令字结构，使该系列DSP的性能达到很高的水平。DSPC6416每时钟周期同时执行8条指令，运算能力可达到 4 800MIPS（每秒百万条指令）[5-6]。

3.1 仿真分析

模拟传送400帧的随机数据作为信源信息序列，每帧256 bit。 系统编码率定为 1/2。 Turbo 码采用（7，5）码，其中交织器采用伪随机交织映射，信息长256 bit，均分为4段并行运算，采用五次迭代的改进Max-Log-Map译码算法，BPSK调制解调。在DSPC6416软件平台进行仿真。

1）改进前后的BER（误比特率）系统性能分析

图7中横坐标表示信道的信噪比。由图可知，改进前后的仿真结果相近，这从一定程度上说明了改进后算法的合理性和可靠性。但观察知改进后的算法误比特率稍高于改进前的译码误比特率。这是因为一帧数据中，校验数据之间存在联系，而采用并行译码将割裂整帧数据间的联系，必然会带来误码率的恶化。

图7 改进前后的译码BER对比图Fig.7 BER comparison between the original algorithm and the improved one

2）改进前后仿真信息传输速率分析

由于对Max-Log-Map译码算法的计算流程进行了改进，大大减少了指令对DSP芯片CPU的资源占用，信息处理速率得到大幅度提高。经CCS软件自带的代码执行时间统计模块里的Incl.Total显示代码段消耗的所有时钟周期及相应的信息传输速率如表2所示 （本例中C6416DSP芯片时钟周期为 1/600M）。

表2 改进前后消耗周期数及信息传输速率比较Tab.2 Transmission rate and consumed cycle time comparison

4 结 论

文中对Turbo码Max-Log-Map译码算法进行了改进。理论分析看到，改进后的算法在很大程度上减少了译码延时，节约了13倍交织长度的存储空间资源。同时，性能仿真结果表明，在译码BER性能相当的情况下，改进的Turbo码译码速率提高至原来的2倍，验证了优化后的算法的合理性和可靠性。因此该优化方案具有一定的实际参考与应用价值。

[1]刘东华.Turbo码原理与应用技术[M].北京:电子工业出版社，2004.

[2]Berrou C，Glvaieux A.Near shannon limit error-correcting coding and decoding:turbo-codes[J].ICC，Geneva， Switztlnad，1993（2）:1064-1074.

[3]尹成群，谢小军，宋文妙.Turbo码译码器的DSP实现[J].电子测量与仪器学报，2005，19（5）：72-76.YIN Cheng-qun，Xie Xiao-jun，SONG Wen-miao，et al.Research and Realization on DSP of Turbo decoder[J].Journal of Electronic Measurement and Instrument，2005，19（5）:72-76.

[4]王强.Turbo码在COFDM中的应用研究[D].南京：南京理工大学，2003.

[5]李方慧，王飞，何佩现.TMS320C6000系列DSPs原理与应用[M].北京:电子工业出版社，2002.

[6]岂兴明，胡小冬，周火金.DSP嵌入式开发入门与典型实例[M].北京：人民邮电出版社，2011.