1 Viterbi算法原理简介
Viterbi译码算法是由Viterbi于1967年提出的一种最大似然译码方法，译码器根据接收序列R按最大似然准则力图找出正确的原始码序列。随着大规模集成电路技术的发展，采用Viterbi算法的卷积编码技术已成为广泛应用的纠错方案。Viterbi译码过程可用状态图表示，图1表示2个状态的状态转移图。Sj,t和Sj+N/2,t表示t时刻的两个状态。在t+1时刻，这两个状态值根据路径为0或者1，转移到状态S2j,t+1和S2j+1,t+1。每一种可能的状态转移都根据接收到的有噪声的序列R计算路径度量，然后选择出各个状态的最小度量路径（幸存路径）。Viterbi算法就是通过在状态图中寻找最小量路径向前回溯L步，最后得到的即为译码输出。
在卷积码（n,k,m）表示法中，参数k表示每次输入信息码位数，n表示编码的输出卷积码位数，m称为约束长度（一些书中采用k=m+1为约束长度，也可称（2，1，2）码网格图，r=k/n称为信息率，即编码效率。本文使用的是（2，1，3）码，约速长度为2，状态数为2 2=-4。
2 目标处理器简介
TMS320C6000系列DSPs（数字信号处理器）是TI公司推出的一种并行处理的数字信号处理器，是基于TI的VLIW技术的。本文采用的是TMS320C6211。该处理器的工作频率经过倍频可达到150MHz，每个时钟周期最多可并行执行8条指令，从而可以实现1200MIPS定点运算能力。C6000系列CPU采用哈佛结构，其程序总线与数据总线分开，取指令与执行指令可以并行运行。其程序总线宽度为256位，每一次取指操作都是取8条指令，称为一个取指包，执行时每条指令占用1个功能单元。取指、指令分配和指令译码单元都具有每周期读取并传递8条32位指令的能力。C6000系列CPU有2个类似的可进行数据处理的数据通道A和B，每个通路有4个功能单元（.L、.S、.M、.D）和1组包括16个（C64有32个）32位寄存器的通用寄存器组，每个功能单元完成一定的算术或逻辑运算。
C6000的特殊结构使多个指令交迭地在不同功能单元内处理，大大提高了微处理器的处理能力。另外在其CPU硬件结构上，C6000的流水线分为三个阶段：取指、译码、执行，每一级又包含几个节拍。流水处理使得若干条指令的不同执行阶段可以并行执行，从而能够大幅度提高程序运行速度。
3 算法的编程实现及优化
根据C6000的软件编程流程，对Viterbi算法的编程及其优化可分为三个阶段来进行。这三个阶段分别为：开发C代码、优化C代码、编写线性汇编代码。在代码编写和优化过程中，这三个阶段不是必须都要经过的，只要在某一阶段已经满足了算法代码的功能和性能要求，就不必继续进行下面的阶段。
①开发C代码。这一阶段完全是根据任务要求来完成算法的代码编写工作。在C6000的集成开发环境CCS（Code Composer Studio）下进行代码的编译和功能验证，然后可用CCS的调试工具（如Profiler）,利用在程序中设置断点的方法可找出程序中耗时最多、最影响整体性能的代码段。为改进代码性能，可进入下一阶段。如下是针对（2，1，3）码的Viterbi算法代码中完成算法功能的核心循环，也是最耗时、最影响代码整体性能的低效率段。
for(c=0;c<unmber_of_input;c++) //对每一个输入值，设number_of_input=24
{for(j=0;j<number_of_states;j++) //对于每个状态（2，1，3）状态数为4
{for(i=0;i<2;i++) //对于状态的每个可能输入，比如1，0
{/*计算度量值*/
branch_metric=hamm(conv_output,c,channel_data);
/*比较累计度量保留其中最小，并且记录其状态路径*/
if(accum_err_metric[nextstate[j][1]>accum_err_metric[j][0]+branch_metric]
{accum_err_metric[nextstate[j][1]=accum_err_metric[j][0]+branch_metri;
state_history[nextstate[j]][sh_ptr]=j;
}
}*/end of i<2*/
}/*end of j<number_of_states*/
}/*end of c<number_of_input*/
其中调用函数hanmm是计算当前输入值与网络图上的值相比较所返回的度量值。
Int hamm(char output_vector,int x,char channel_output[24])
{char target_vector=0;
int hamm=0;
int i=0;
int i=0;
target_vector=(output_vector)^channel_output[x];
for(i=1;i>=0;i--)
hamm+=(target_vector>>i)&0x01;
return hamm;
}
在验证了算法代码实现功能并以设置断点的方法测试代码的性能，这段循环运行耗时（时钟周期）为1790。显然，性能不能达到要求，就要进入代码优化的第二阶段了。
②一般在代码调试中，最影响性能的是其中的循环代码段。而软件流水是一种用于安排循环内的指令运行方式，尽可能充分利用CPU的功能单元等资源，使循环的多次迭代能够并行执行的一种技术。在C6000的C/C++编译器里，采用软件流水使编译出来的程序代码优化是一项核心技术。所以在进一步优化之前，需要调整并尽可能简化代码的结构并去除影响软件流水的因素使其能够被编译器充分流水，这对大幅提高整个代码的性能非常重要。
所以，在考虑影响因素同时对Viterbi算法的循环代码进行如下调整；
*使用内联函数（intrinsics）替代复杂的C语言程序。C6000编译器提供了许多intrinsics，可以快速优化C代码。Intrinsics是直接参与C6000汇编指令映射的内联函数。在这里使用了 _extu(x,y,z)，以简化其中hamm代码部分。
*尽管软件流水循环可包含intrinsics，但不能包含函数调用。所以需要把调用函数 hamm在循环中展开实现。
*由于编译器仅对最内部的循环执行流水，所以为了提高性能应尽可能创造一比较大的内循环。在代码中可以看到，在最内循环是i的两次循环，仅对它进行流水，对整个代码的性能提高不大。所以一个想法是，将i和j循环全部展开，使编译器直接面对最大的C循环以最大发挥软件流水的作用。
*另外，展开循环后代码中的变量如果可以确定其运行中的值，就尽量以实值代入，这样减少了变量个数，也就是减少了所需分配的寄存器个数（C62xxCPU中有32个寄存器）。
在进行上述调整后运行代码，进行测试发展，性能没有太大改善；用编译器反馈表（feedback）进行观察发现，循环并没有发生流水。这是为什么呢？原来在展开内部循环后导致C循环内代码尺寸太大，需要的寄存器数目大于C62XX 的32个寄存器，所以不能进行软件流水。为了解决这问题，需要简化循环或将循环拆成几个小循环。在这里先将C循环内部的小循环展开，然后将其拆成分别完成度量计算和累计度量比较的两个循环，这样就减小了每个循环中的代码尺寸。限于篇幅这里只写出累计度量比较的循环代码。
/*完成累计度量比较的循环*/
accum00=accum_err_metric[0];accum10=accum_err_metric[1];
accum20=accum_err_metric[2];accum30=accum_err_metric[3];
for(c=0;c<n;c++)//n=24
{sh_ptr++；
add1=accum10+branch_metric_array[c][1];
add2=accum00+branch_metric_array[c][0];
add3=accum10+branch_metric_array[c][0];
add4=accum00+branch_metric_arrcy[c][1];
add5=accum30+branch_metric_array[c][2];
add6=accum20+branch_metric_array[c][3];
add7=accum30+branch_metric_array[c][3];
add8=accum20+branch_metric_array[c][2];
if(add1>add2){accum00=add2;state_history[0][sh_ptr]=0;}
else{accum00=add1;state_history[0][sh_ptr]=1;}
if(add3>add4){accum20=add4;state_history[2][sh_ptr]=0;}
else{accum20=add3;state_history[2][sh_ptr]=1;}
if(add5>add6){accum30=add6;state_history[3][sh_ptr]=2;}
else{accum30=add5;state_history[3][sh_ptr]=3;}
if(add7>add8){accum10=add8;state_history[1][sh_ptr]=2;}
else{accum10=add7;state_history[1][sh_ptr]=3;}
}
accum_err_metric[0]=accum00;accum_err_metic[1]=accum10;
accum_err_metric[2]=accum20;accum_err_metric[3]=accum30;
其中accum_err_metric为状态i的累计度量值，branch_metric_array[][]为计算得到的各时刻量值，原来代码中的二维数码mextstate[j]被以实值代入。另外在编程考虑时要注意一点：程序中对数据的取命令（load）是非常耗时的，所以应考虑尽量减少对数据数组的操作。在上面程序的改进中，先从数组中取出要进行循环处理的累计度量值，再使用accumXX及addX作为各次迭代的中间变量，在循环后将最后的结果放入数据。这样就大大减少了对数组的操作，从而使优化进一步提高。
*编译器优化选项的选择。C6000 C/C++编译器提供了大量的编译选项，供用户在编译时选择使用。这些选项中的部分会直接影响或控制编译器优化过程，因而会影响编译输出的代码优化性能。选择适合的选项，能极大地提高优化性能。在这里使用的优化选项有：
-03——表示可得到最高程度的优化，编译器将执行各种优化循环的方法，如软件流水、循环展开等等。
-pm——在使用-o3选项进行优化时尽量联合使用-pm选项，-pm是程序级优化，使优化器访问整个程序，了解循环次数。
-op1——使用了外部变量，但未使用外部函数调用。
-g——使能符号调试和汇编源语句调试。
另外，还有不少考虑因素和优化调试方法，如消除存储器相关性、对短字长的数据使用宽离长度的存储器访问等。由于篇幅所限不能在这里一一列出，详细资料可参考TMS320C6000 Code Composer Studio Manuals中的TMS320C6000 Optimizing C Compiler User's Guide。
测试结果：在经过上述优化后运行耗时（时钟周期）已降为406个，代码的性能大为提高，已经满足系统要求。
③由上述可知，在程序中影响性能的主要代码通常是循环。优化一个循环较好的方法是抽出这个循环，使之成为一个单独文件，对其进行重新编写、重新编译和单独运行。为了提高代码性能，对影响速度的关键C代码段可以用线性汇编重新编写，使用汇编优化器进行优化后效率是非常高的。若代码性能仍未满足要求，则可进行第三阶段，将其抽出，全部用线性汇编来编写，在代码中以函数的形式将改写的部分调用。将循环代码段改写为线性汇编调用函数的格式如下：
.global_KernelLoop ；函数名定义前加_
_KernelLoop:.cproc channel_data,branch_metric_array,depunc ;定义入口形参变量
.reg c,q0,q1,y1,y2,x1,x2,cc,temp,temp0,temp1,temp2,temp3
.reg counter,valuel,value2,value3定义中间变量
no_mdep ；表明存储器地址不相关
zer0 c ；初始化变量
zero cc
loop: .trip 24 ；声明循环24次
·
·
·
运行语句
·
·
·
[counter]sub counter,23,counter;循环计数
[counter]b loop ;循环跳转
.return ;完成返回
.endproc ；结束
编写线性汇编的工作量大，开发周期长且不能像C语言程序一样移植到其它类型DSP上，所以尽量在第一、二阶段完成工作。若仍满足不了性能要求，则再对关键代码段进行线性汇编的改写。
结语
本文在TI的TMS320C6211硬件平台上实现了针对（2，1，3）卷积码的 Viterbi译码算法的优化，满足了系统对2Mb/s的视频数据流进行实时处理的要求。在对1Kb数据处理时，整个代码运行耗时约为2100个时钟周期，DSP资源占用率不到40%。目前随着理论技术的不断突破，尤其是实时图像压缩技术如H.264等新一代技术标准的提出，如何利用高速DSP进行复杂算法的开发与实现，已成为研究的重点。所以本文以Viterbi算法为例介绍TMS320C6000的编程优化，有较强实用性。