基于DSP的Max-Log-MAP算法实现与优化

1 引 言
Turbo码接近Shannon理论极限的优越性能使其在卫星通信、深空通信、多媒体通信等领域具有非常大的诱惑力，因此自提出以来一直受到广泛而持续的关注。

Turbo码的工程应用与实现是近年来研究工作的热点。Turbo码采用反馈迭代译码结构，成员译码器使用最大后验概率(MAP)译码算法译码，由于MAP算法含有大量的指数运算与对数运算，给实现带来极大的困难，在工程应用中，通常采用其对数域的简化算法——Log-MAP和Max-Log-MAP算法。相对于Log-MAP算法，Max-Log-MAP虽然损失0.5 dB的增益，但由于其大大简化了复杂度，在应用与实现中倍受关注。本文基于TMS320C6000系列DSP芯片讨论了Max-Log-MAP算法的实现与优化。

2 Turbo码的反馈迭代译码结构与Max-Log-MAP译码算法

Turbo码又称为并行级联卷积码(PCCC)，编码器由两个RSC成员码通过交织器并行级联。与之对应，在译码端Turbo码则采用两个成员译码器串联构成的反馈迭代结构，如图1所示，其中DEC1与DEC2表示两个软输入软输出(SISO)的成员译码器，假设编码输出采用BPSK调制方式，xk，yk为解调器输出的受噪声污染的信息比特与校验比特，zk(zn)表示从另一个译码器经过解交织(交织)后得到的外信息。每个成员译码器有两个输出端口，分别输出信息比特的对数似然比LLR(L1(ak)，L2(an))及被另一个成员译码器使用的外信息叫ω1k，ω2k，经过若干次迭代和两个成员译码器的外信息交换，对信息比特的对数似然比进行硬判决即可完成Turbo码的译码。

Max-Log-MAP算法下的对数似然比可以表示如下：

其中m′，m分别对应k-1和k时刻的编码器状态，αk(m)，βk(m)分别称为前向和后向状态度量，可以根据RSC码的网格图由分支度量rk(i，m′，m)(i=±1)递推计算：

外信息若采用Robertson使用方式，AWGN信道下码率为1／2的RSC码分支度量rk(i，m′，m)计算公式可以表示为：

式中j=±1，表示对应信息比特ak=i编码应输出的双极性校验比特，Lc=4Es／N0定义为信道可信度值。外信息与对数似然比的关系为：

3 Max-Log-MAP译码算法的C语言软件编程与实现

分析可知，Max-Log-MAP算法需要根据每时刻的接收信息计算几种度量值：分支度量rk(i，m ′，m)，前向状态度量αk(m)和后向状态度量βk(m)，最后由3个度量值计算该时刻的对数似然比L(ak)，从而得到另一个成员译码器需要的外信息ωk。因此算法可以大致分为几个模块：分支度量模块，前、后向状态度量模块及对数似然比模块，各个模块的计算均是基于网格图的递推完成，故均可以使用C语言中的for循环语句实现，这里以八状态(13，15)RSC码为例逐一分析。

3.1 分支度量模块(BMU)

状态度量的递推是在分支度量的基础上进行的，因此分支度量是算法的基本量度，由式(4)可知，分支度量实际上是由接收信息与网格图上转移路径对应输出的相关运算。对于八状态(13，15)RSC码，网格图上两个相邻时刻的状态转移路径共有16条，考虑到(i，j)组合的取值只有4种，且(-1，-1)与(+1，+1)，(-1，+1)与(+1，-1)条件下的分支度量值互为相反数，故为了减少数据的存储，每一时刻只需计算两个分支度量值即可，不妨设为BM11与BM10，BMU的算法实现结构为：

这里Lx和Ly分别表示经过信道可信度值处理过的接收信息比特与校验比特软信息，z表示来自另外一个成员译码器的外信息，N为Turbo码的信息帧长度。

3.2 状态度量模块(SMU)

前向状态度量的递推与后向状态度量的递推在算法上是相似的，我们以前向状态度量为例说明状态度量模块(SMU)的算法编程实现，用FSMj表示基于RSC(13，15)码网格图j状态的前向状态度量累加值(j=0，1，…，7)，前向状态度量的递推循环语句结构为(其中语句中的temp1，temp2表示临时变量)：

事实上，SMU完成在每一个网格图状态将转移至该状态的分支度量进行“累加”、“选大”的功能即所谓的ASC操作。

3.3 对数似然比模块(LLRU)

对数似然比模块(LLRU)根据分支度量与状态度量值计算对数似然比与外信息，其基本运算也是类似SMU中的加比选(ACS)操作，相应的算法结构如下(转移路径按输入分别为0和1分为两组，状态从0～7排列)：

语句中的BSM表示后向状态度量，LLR表示对数似然比，ω为输入至另外一个成员译码器的外信息，其他均为临时变量。

4 基于DSP的Max-Log-MAP译码算法代码优化

基于C语言的DSP开发关键在于代码的精简优化，TI公司CCS开发软件中的C编译器提供了对代码的优化功能，人们可以通过选项设置、循环展开、加注关键字、使用内联函数(intrinsic)等操作完成对C代码的优化。本文主要针对TMS320C6000系列芯片的结构与特点讨论Max-Log-MAP译码算法代码的优化设计，包括软件流水、数据存取优化等，以达到充分利用DSP芯片的硬件资源，获得高效处理性能的目的。

4.1 C6000系列芯片的结构与特点

TMS320C6000系列DSP是TI公司推出的一种基于VLIW技术，具有8个功能单元的数字信号处理器，其CPU采用哈佛结构，程序总线与数据总线分开，取指令与执行指令可以并行运行，VLIW技术的使用可以使指令获取、指令分配、指令执行和数据存储等操作形成多级流水，在同一时钟周期多条指令交迭地在不同功能单元内处理。C6000系列芯片在每个时钟周期内可以同时执行8条指令。

4.2 基于DSP的各算法模块代码优化

4.2.1 BMU模块

BMU算法模块为单循环语句，由于循环体内的指令较少，为了更多地同时利用CPU资源，一个有效的做法即是将循环展开，这样在减少循环次数的同时可以使更多的操作形成流水(pipeline)，充分发挥多个功能单元的并行处理能力。优化后的代码如下：

4.2.2 SMU模块

由于状态度量的递推具有递归性，即本时刻递推得到的数值将用作下一时刻的递推初值，因此对于该算法模块的数据读入读出操作是一个值得考虑的问题。从3.2节SMU的程序分析可知，FSM的读写致使CPU寄存器与数据存储器之间频繁的进行load与store操作，为了减少该操作的指令消耗，我们引入3组临时变量FSM_tempj，FSMj_old和FSMj_new(j=0，1，…，7)用来存储FSM的计算结果，这样在下次递推时CPU可以直接从内部的寄存器读取数据，避免了从数据存储器的load操作。优化后的代码结构如下：

与先前只采用两个临时变量sum1和sum2相比，优化后的代码采用更多的变量，这样可以保持数据的独立性，避免造成CPU寄存器的关联，使代码更易于流水线操作。

4.2.3 LLRU模块

对于LLRU算法模块的代码优化主要从减少加减操作指令入手，这涉及到对算法的改进。前文提到每一时刻的转移路径有16条，如果采用3.3节的程序结构，对分支度量要进行16次加减操作。考虑到分支度量只有4种取值，结合RSC(13，15)网格图的映射关系，按照分支度量的取值将转移路径分为4组，这4组分别对于分支度量的加减操作先不予处理，即先选最大后再进行相应的分支度量加减操作，这样每一次循环可以将分支度量的加减操作由原来的16次减少至4次，故可以大大降低CPU资源的消耗。相应的优化代码结构如下：

4.3 代码优化前后消耗的指令周期对比

我们使用合众达公司的SEED—C6416仿真开发板，采用C6416-T系列DSP芯片在CCS 3.1编译环境下对各个算法模块及整个Max-Log-MAP算法进行了编译与硬件仿真，Turbo码的信息帧长选为144 b，代码的数据类型定义为int型，编译选项设置为-03-mt-pm。使用CCS附带的定时器(Timer)功能，对优化前后代码消耗的指令周期进行了测试，结果如表1所示。

可见，优化后的代码大大降低了CPU指令周期的消耗，提高了DSP的工作效率。值得提出的是，在代码优化时主要针对算法本身的指令操作与数据存储等方面进行了改进，事实上，在具体的开发过程中还可以根据实际的数据宽度采用内联函数(intrinsics)，数据封装处理(packeddata processing)等措施对代码进行进一步优化，以获得更高效的性能。

5 结 语

本文研究了基于标准C语言的Turbo码Max-Log-MAP译码算法的软件编程与实现方法，并结合TMS320C6000系列DSP芯片的结构与特点深入探讨了代码的优化设计，通过循环展开、数据存取优化、算法的改进等措施提高代码的效率，测试结果表明，经过优化的代码可以大大降低CPU的指令周期消耗，从而获得了比较高效的处理性能。