用TMS320C54X实现Vertibi译码器_DSP论文
关键词：vertibi译码 tms320c54x dsp 度量值 回溯 卷积编码
引言
随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信系统中。其基本做法是：在发送端将被传输的信息序更上附加一些监督码元，这些多余的码元与信息序列之间以某种确定的规则相互约束；接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生错误，则信息码元与监督码元之间的关系将受到破坏，从而发现错误，甚至纠正错误。按照码元和监督码元之间的约速方式，可以分为组码和卷积码。在gsm和is-95中主要采用了卷积码，在每三代移动通信中，话音信号也主要采了卷积编码。卷积码的译码方法有许多种，其中最重要的就是vertibi算法。为此，本文讨论用dsp实现vertibi译码器的方法。
1 卷积编码器简介
卷积码是一种对付突发错误的有效编码方法，通常记作（n,k,n）。它将k个信息编码为n个比特，编码效率为rc=k/n。n为约束长度。与分组码不同，卷积码中编码后的n个码元不但与当前段的k个信息有关，而且与前面n-1段的有关，编码过程中相互关联的码元为nn个。其纠错能力随着n的增加而增大，而差错率随着n的增加而指数下降。卷积编码器的结构如图1所示。
由图1可知，卷积编码器包括两部分：一个由n段组成的输入移位寄存器，每段有k段，共有n·k位移位寄存器；n个模2和相加，其输入分别对应于n个基于生成多项式的线性代数方程组。每输入k个比特，编码器输出n个比特。在编码器复杂度相同的情况下，卷积码的性能优于分组码。
2 vertibi译码的基本原理
卷积码的译码方法主要包括vertibi算法、fano算法和堆栈算法等等，其中最重要的和最常用的就是vertibi算法。vertibi算法是一种关于解卷积的最大似然译码法。它不是在网格上依次比较所有的可能路径，而是接收一段，计算一段，保留最有可能的路径，从而达到整个码序列是一个最大似然序列。
vertibi算法可以算法描述如下：把在时刻i、状态sj所对应的网格图节点记作（sj，i），给每个网格图节点赋值v（sj，i）。节点值按照如下步骤计算：
①设v(s0,0)=0，i=1。
②在时刻i,对于进入每个节点的所有路径计算其不完全路径的长度。
③令v(sj，i)为在i时刻，到达与状态sj相对应的节点（sj,i）的最小不完全路径长度，通过在前一节点随机选择一条路径就可产生新的结果，非存留支路将从网格图中删除。以这种方式，可以从（s0,0）处产生一组最小路径。
④用l表示输入编码段的数目。其中，每段为k比特，m为编码器中最大寄存器的长度。如果i<l+m，则令i=i+1，返回第②步。
一旦计算出所有节点值，则从i=l+m时刻，状态s0开始，沿网格图中的幸存路径反向追寻即可。这样被定义支路与解码输出将是一一对应的。关于不完全路径长度，硬判断决解码采用汉明距离，软判决解码采用的是欧几里德距离。软判决的特性比硬判决要好2～3db。
（n,k,n）卷积编码器共有2 kn个状态，因此vertibi译码器必须具有同样的2 kn个状态，并且在译码过程中要存储各状态的幸存路径和长度。vertibi译码器的复杂程度随2 kn指数增加。一般要求n<10。
3 vertibi译码器的dsp实现
译码过程就是根据接收到的数据符号，按最大似然译码准则找出编码器在网络图上所走过的路径。vertibi译码的处理过程如图2所示。
3.1 度量值更新
度量值的更新包括以下4个步骤：
①计算每条可能输入路径的度量值；
②为每条支路计算总的距离；
③选择保存最小度量值；
④保存幸存路径。
vertibi译码时，每收到一个符号就进行状态转移，需要计算前一个状态到各个新状态的分支度量值。我们用dsp设计的译码器采用软判决输入，度量值用欧氏距离表示。当编码速率为1/c时，欧氏距离为：
其中sdn表示接收序列，gn(j)为网格上每个路径状态的期望输入值，j是路径指示值，c为编码速率的倒数。将（1）式展开得：
对于所有的路径来说，都是一样的，2只是个常数，在进行各路径度量值比较时，可以不考虑。这样可简化为：
省去胶面的负号，在度量值的比较时取最大值。对于编码速率为1/2的卷积码，分支度量为：
t=sd0g0(j)+sd1g1(j) (4)
当编码速率为1/3时，分支度量为：
t=sd0g0（j）+sd1g1(j)+sd2g2(j) （5）
gn(j)用双极性表示，即0用+1表示，1用-1表示。这样分支度量值的计算可以进一步简化为接收数据的加和减。
下面给出编码速率为1/3时，dsp实现具体程序。
ld *ar1+，16，a ；a=sd(2*i)
add*ar1+,16,b,b ;b=sd（2*i）+sd（2*i+1）
add*ar1-，16，b，b ;b=sd(2*i)+sd(2*i+)+sd(2*i+2)
sth b,*ar2+ ;temp(0)=sd(2*i)+sd(2*i+2)
sub*ar1+,16,a,b ;b=sd(2*i)-sd(2*i+)
add *ar1-,16,b,b ;b=sd(2*i)-sd(2*i+1)+sd(2*i+2)
sthb,*ar2+ ;temp(1)=sd(2*i)-sd(2*i+1)+sd（2*i+2）
sub *ar1+，16，a，b ；b=sd(2*i)-sd(2*i+1)
sub *ar1-,16,b,b ;b=sd(2*i)-sd(2*i+1)-sd(2*i+)
sth b,*ar2+ ;temp(2)=sd(2*i)-sd(2*i+1)-sd(2*i+2)
add *ar1+,16,a,b ;b=sd(2*i)+sd(2*i+1)
sub *ar1+,16,b,b ;b=sd(2*i)+sd(2*i+1)-sd(2*i+2)
sth b,*ar2 ;temp(3)=sd(2*i)+sd(2*i+1)-sd(2*i+2)
加比选单元是vertibi译码器的核心单元。它的主要功能是取出当前状态的量度值，分别与其两个后续支路的量度相加并比较，选择罗小的一个作为后续状态的量度，并保存幸存支路。图3给出了该算法的示意图。
c54x片内的比较、选择和存储单元（cssu）就是专门为viterbi算法设计的加法/比较/选择（acs）运算的硬件单元。图3所示的运算包括加法、比较和选择三部分操作。其加法运算由dsp的alu完成。只要将状态寄存器st1中的c16位置成1，alu就被配置成双16位工作方式，这样，就可以在一个机器周期内执行两次加法运算。其结果（old_met1+d1和old_met2+d2）都是16位数，分别存放在累加器的高16位和低16位中。然后，利用cmps指令对累加器的高16位和低16位进行比较，并选择出较大的一个数放到指令所指定的存储单元中。在cmps指令执行的过程中，状态转移寄存器trn自动记录比较的结果，这一点非常有用。实现一个蝶式运算的程序如下：
ld *ar2，t ；t=本地距离
dadst *ar5，a ；a=old_met(2*j)+t//old_met(2*j+1)-t
cmps a,*ar4+ ;new_met(j)=(max(old_met(2*j)+t,old_met(2*j+1)-t)
；trn=rtn<<1
;若（old_met(2*j)+t=<old_met(2*j+1)-t则
trn[0]=1
cmps b，*ar3+ ;new_met(j+2 k-2)=(max(old_met(2*j)-t,old_met(2*j+1)+t)
trn=trn<<1
；若（old_met(2*j)-t=<old_met(2*j+1)+t）则trn[0]=1
3.2 回溯
当接收完1帧数据后，添加尾比特，强迫网格图的最后一个状态（0状态）开始，反向追踪最大似然路径，完成原始数据的译码。回溯的计算过程如下：
①计算当前状态在转移数据块中的数据；
②利用bitt指令从t寄存器中读取当前状态相应的转称比特；
③用上面读取的转移比特更新状态。
溯的主要功能是，从每个符号间隔的转移数据中提取正确的位。为了完成该功能，需要保存每个状态相应的转移比特。该比特表示选定碟形网络的是上面分支还是下面分支，所有这些转移比特构成一块转移字。表1给出转移字块中状态数与相应转移比特之间的关系。
表1 一个符号间隔内数据转移的状态顺序
| 状态字中的比特序号 | |||||||||
| 15 | 14 | 13 | 12 | … | 2 | 1 | 0 | ||
| 转移字序号 | 0 | 0 | 2k-2 | 1 | 2k-2 +1 | … | 2k-2 +6 | 7 | 2k-2 +7 |
| 1 | 8 | 2k-2 +8 | 9 | 2k-2 +9 | … | 2k-2+e | f | 2k-2 +f | |
| 2 | 10 | 2k-2+10 | 11 | 2k-2 +11 | … | 2k-2 +16 | 17 | 2k-2 +17 | |
| … | … | … | … | … | … | … | … | … | |
| 2k-5 -1 | 2k-2 -8 | 2k-1 -8 | 2k-2 -7 | 2k-2 -7 | … | 2k-1 -2 | 2k-2 -1 | 2k-1 -1 | |
实现回溯的程序如下：
；以下程序中，累加器a存放状态值，累加器b存放临时的数据
；k为约束长度，mask=2 k-5-1，one=1
rsbx ovm ；关闭溢出模式
stm *ntran_end，ar2；转移表的结束地址
stm#nbwords-1，ar1；要计算的输出字的序号
mvmm ar1，ar4 ；复制ar1的数值到ar4中
stm #output+nbwords-1，ar3
；输出比特的地址指针
ld #0，a 初始0状态存入累加器a中
stm#15，brc ；do i=0,nbwords-1
back：rptb tbend-1 ；do j=0,15
；在转移字中计算比特位置
sftl a，-（k-2），b ；b=a>>(k-2)
and one，b ；b=b&1=msb of state
add a,1,b ;b=b+a<<1=2*state+msb of state
stlm b,t ;t=b(bit position)
；修正转移字
sftl a，-3，b ；b=a/8=state/8
and mask，b ；b=b&mask=(k-5)lsb'sof state/8
stlm ar0 ;ar0=转称字索引
mar *+ar2（-2k-5） ；修正寄存器值使其复位
mar *ar2+0 ；加偏移量修正转移字
bitt*ar2-0 ；测试转移字中的比特位
roltc a
tbend：stl a，*ar3-
banzd：back，*ar1-
stm #15，brc ；指向输出缓冲区的首地址
ld*ar3，a ；将第一个字装入累加器a中
rvs：sfta a，-1，a
stm #15，brc
rptb rvs2-1
rol b
sfta a，-1，a
rvs2：banzd rvs，*ar4- ；判断所有的字是否都计算完
stl b，*ar3+ ；保存刚计算完的字
ld *ar3，a ；装入下一个字