基于TMS320C6000系列DSP维特比译码程序优化设计方案
3 VA在DSP上的优化实现
ACS操作是整个VA算法中运算量最大的部分。在通常的程序设计中,使用一种对称的蝶形运算实现ACS操作,每次可以完成两个ACS操作。因此优化的核心任务就是减少每个蝶形运算所消耗的运算周期数。
蝶形运算的原理请参见图3。对前一级的两个相邻状态2i和2i+1,一共有四条支路。计算出四条支路与接收信号的欧氏距离,与两个前一级状态2i和2i+1中存储的以前路径的度量值相加得到四条路径A1、A2、B1、B2的度量值。然后在对应的两个当前状态i和i+32下两两比较,每个当前状态都留下度量值较小的一条路径(幸存路径),同时将当前状态的度量值以及与幸存路径对应的输入比特存人相应的位置,准备下一级计算。
每个蝶形运算包括:三次加载数据操作(load),因为可以证明一个蝶形中的四条支路的度量具有相同的绝对值,所以每次只需要加载一个由BMU预先计算的结果;四次加法操作;两次比较操作;比较之后的四次存储操作。其中,四次加法操作可以在一个周期内同时完成;状态i和i+32的幸存路径则是独立计算和存储的。
针对前面提到的提高并行处理程度的几个障碍,可以用以下的方法分别加以解决:
(1)解决功能模块的限制 可以用不同的命令相互替代。例如赋值操作MV只能用.L、.S和.D功能模块完成,如果这些模块都被其它的并行指令占用,可以用乘1的方法实现赋值,而乘法指令MPY是用.M单元实现的。类似地,也可以用加零或减零的指令代替MV指令。
(2)解决交叉路径的限制 需要依靠寄存器的分配和倒换,让同一指令涉及到的寄存器尽量处在同一个寄存器组中,减少需要用到交叉路径的机会。
(3)解决多周期指令的限制 加载数据的结果需要在4个周期以后才能得到。为了有效地利用等待的这段时间,在程序设计中把加载数据的指令放在前面的蝶形运算中执行,当进入本次蝶形运算时,就能立即使用加载的新数据。同样,本次蝶形运算也要执行为下一个蝶形运算加载数据的指令。B指令(跳转指令)的问题可以用类似的方法来处理。
(4)解决对长数据操作的限制 在(2,1,7)卷积码的VA译码器中,幸存路径存储在PM里。每一个输入帧对应64个可能的状态,会产生64比特的幸存路径比较结果。但TMS320C6701不能直接对64比特长的数据进行读写操作,所以把PM分成两个相同的32位数组PMO和PMl。前者用来存储状态0-31对应的幸存路径;后者存储状态32-64对应的幸存路径。PM0[i ]和PM1[i ]合在一起表示第i级网格的所有64条幸存路径。当编码约束长度更大时,也可以用同样的办法来分开存储。例如(2,1,9)卷.积码的PM就可以分成8个32位的数组来存储256个状态的信息。回溯操作的时候,先确定路径经过哪一个状态,就可以从相应的某一个数组中读出路径值,只需要一次LD(加载)操作。
图4给出了优化后的蝶形运算流程图。每次循环需要4个时钟周期,分别为图中的E0-E3,对应着一次蝶形运算。除了一些关键的加比选运算之外,还需要一些辅助运算来实现循环以及寄存器的相互拷贝,平均下来每个时钟周期可并行执行6条指令。
4优化的效果和推广
译码器输出一帧所需要的时钟周期数为
TBMC+n·TButter+Ttb
其中,TBMC、TButter和Ttb分别表示支路度量计算、蝶形运算以及回溯操作所需要的周期数,n表示每一输出帧对应的蝶形运算的次数。
对于(2,1,7)卷积码译码器,输出一个帧需要32次蝶形运算,因此n=32。在回溯幸存路径的时候,有两种方案输出译码结果:一种是输入一帧码序列,就输出一帧译码结果;另一种是输入N帧码序列,然后输出N帧译码结果。后一种方法输出每一帧所需要的周期数可以减小为Ttb/N,但同时延时也增大为(N-1) TButter/TCPS,其中TCPS是DSP每秒运行的时钟周期数,等于DSP的工作频率。
如果使用TI公司定义的线性汇编语言用图1所示的结构来实现(2,1,7)译码,经过CCS2软件编译并自动进行-o1级优化以后,每译出一个比特,大约需要1000个时钟周期(TButter =22,n=32),时钟为167MHz时译码速度不超过160kbps。
在经过本文所述方法优化以后的程序中,仍然是(2,1,7)卷积码,TBMC =20,TButter =4,n=32;Ttb=700,选择N=16,因此译出一个比特的平均时间是128+20+(700/16)=192个时钟周期。以TMS320C6701为例,它工作在167MHz,该程序的译码速率能达到大约870kbps,而延时仅为18μS。显然,本文中的优化程序性能远远高于自动优化的效果。
对于不同编码约束长度的卷积码,例如WCDMA中用到的(2,1,9)码,蝶形运算单元的流程与(2,1,7)码是完全相同的。不同的地方在于每一级的状态数增加到了256个。因此只需要对程序中的存储和回溯路径的指令做一些改动就可以使用。
对于不同的DSP系统,因为在指令集、总线、寄存器等诸多方面存在差异,针对C6000系列的优化的汇编程序不能直接应用。但译码程序优化中遇到的问题也是大致相同的,优化的重点任务都是设法减少ACS的运算量,因此本文提出的程序流程的基本思想以及一些解决问题的技巧都可以继续加以运用。
评论