用TMS320C54X实现Vertibi译码器

卷积码是一种对付突发错误的有效编码方法，通常记作（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时，欧氏距离为：