学文网摘 要：本文提出了一种（2，1，9）卷积编码及其Viterbi译码的软件实现方案。该方案应用软件技术实现了卷积码维特比译码器功能，在程序实现中充分运用了蝶形运算、周期性回溯等卷积码的固有特性，获得了Viterbi译码输出。重点对蝶形运算和维特比算法进行了SSE并行优化。仿真实验表明，此方案可大幅提高译码效率，缩短处理时间。
关键词：卷积编码；Viterbi译码；SSE并行优化；蝶形运算
中***分类号：TN911.2
随着通信技术的发展，特别是3G时代的普及，人们对通信的准确性提出了很高的要求，为此，在数据传输过程中都采用信道编码技术。由于卷积码编码简单，性能优良被广泛采用。Viterbi算法是一种最大似然译码，在译码过程中要遍历所有可能的状态，所以其计算复杂度很高。现有的实现方法都是单指令数据流，处理效率极低，不能满足现状移动实时通信的需求。对此Intel推出单指令多数据流扩展SSE，SSE是一套专门为单指令多数据架构设计的指令集，它可以实现数据的并行处理，效率极高利用SSE对算法进行并行优化，能提高信号处理的速度，减少时延，满足现代的高速率、大容量通信。
1 卷积码的Viterbi译码器的基本结构
卷积码译码采用经典的维特比译码算法。算法分为两大步骤：前向递推，简单概括为“加、比、选”操作；回溯找出最佳路径。***1为维特比译码器的基本结构。
2 卷积码的Viterbi译码器的结构设计
2.1 维特比译码器的三个重要的参数
维特比译码器存在三重要的参数，分别是径存贮容量、合并距离、回溯路径译码位。径存贮容量定义路径存贮的大小，规定我们周期性的回溯生成译码数据。合并距离的设置使得回溯时可以从任意一个当前状态开始，不需要从最小的度量距离节点开始。回溯路径译码位可以避免因为尽可能多的得到译码输出而增加译码延迟，设置每次的回溯时译码的位数。
2.2 加比选单元的蝶形运算
维特比译码采用向前递推算法，向前递推过程是一个状态转移的过程。TD-SCDMA无线电接收器采用（2，1，9）卷积码的编码方式，卷积码状态寄存器为8，编码器有28=256个状态数。观察卷积码的状态转移过程，可发现其规律性很强，可由多个蝶形***构成，蝶形运算如下***2，整个状态转移***由128个这样的蝶形组成。
加比选的蝶形运算中每个蝶形包括当前状态为i和i+states（states为状态数的一半，这里为128）两个节点的加，比较，和选择运算，他们的0分支和1分支在篱笆***的下一个节点合并。
2.3 分支度量的计算
在计算分支度量时，通常有软判决和硬判决两种输入。对于硬判决采用汉明距离定义，主要是以1或者0来定义。对于软判决可做相似定义，根据软判决的输入位数据顶最大欧氏距离的取值。
2.4 路径存贮记录
从当前状态经过加_比较_选的蝶形运算后，到达下一个状态，通过对每一个分支度量的积累计算留下与接收序列距离最近的幸存路径。
2.5 回溯
我们在程序中设置一个标志位，当路径存贮记录长度第一次超过回溯路径译码位长度时，将标志位复位，继续进行运算。当路径存贮记录长度达到定义的路径存贮容量时，选择从任意一个状态开始进行回溯。先回溯定义的合并距离长度，回溯时只是记录状态，不生成输出译码位，然后从刚得到的状态继续回溯以生成输出译码位。
2.6 程序设计流程***（如***3）
3 维特比算法的SSE并行优化
Viterbi算法是一种最大似然译码，在译码过程中要遍历所有可能的状态，所以其计算复杂度很高。现有的实现方法大多数是采用单指令单数据流串行处理Viterbi译码算法中的加-比-选，遍历每一种状态。这种方法效率低，对通信带来的时延很大，仅适用于低速、小容量，对实时性要求低的通信系统。随着通信技术的发展，低速、小容量的通信显然不能满足人们的需求，人们更希望速率高、实时性好的通信系统。利用SSE对维特比优化，可以大大提高译码效率，提高信号处理的速度，减少时延，满足现代的高速率、大容量通信。
3.1 SSE并行优化维特比的加比选单元
（1）将蝶形运算将其展开，由于SSE的拓展寄存器是128bit，每个状态是32bit。所以展开的次数为4。
（2）将所有出现的数组，将软比特的乘，加，比较，选择，复制到下一个状态，进行分析。
（3）并对其进行SSE并行指令优化，下***4为维特比优化状态***的比较。
3.2 SSE并行优化维特比的函数设计
（1）将软比特的数据存放在两个128bit的寄存器内存中，用bm[]表示4次蝶形运算的软比特数，通过SSE函数“uint32x4_t vld1q_u32（const uint32x4_t *）”将数组分别加载到内存中。
4 测试实验及总结
选取（2，1，9）形式的卷积码按照上述方法进行译码，译码个数分别为100，400，800。用T优化前表示使用传统的Viterbi译码方法译码的时间，T优化后表示使用并行优化后的Viterbi译码方法译码时间，用T优化倍数=T优化前/T优化后表示优化倍数。在测试试验中，分别选取了100，400和800个比特进行编码。为了比较容易看出结果，每次译码时，重复译码10000次，然后算出重复译码10000次的运行前后的时间差，每次试验对1000个时间差求平均，得到的结果如表1所示。从表1可以看出，不论编码个数是100，400还是800，其优化前的时间是优化后的将近4s倍。
5 结语
通过对维特比运算的SSE并行优化，每做一次的蝶形运算的时间，并行优化后可做四次蝶形运算，实现数据的并行处理，大大的提高了程序运行的效率，缩短了运行时间。这样可以利用SSE对算法进行优化效率极高，能提高信号处理的速度，减少时延，满足现代的高速率、大容量通信。
参考文献：
[1]徐超颖.三种使用的纠错编码技术及其软件实现[D].西安交通大学硕士学位论文.
[2]ChiP Fleming A Tutorial on Convolutional Coding with Viterbi Decoding Spectrum Applications，2001.
[3]王新梅，肖国镇.纠错码一原理与方法[M].西安：西安电子科技大学出版社，2002.
[4]青松，程岱松，武建华.数字通信系统的仿真与分析[M].北京：北京航空航天大学出版社，2003.
作者简介：刘庆文（1987-），男，山东泰安人，研究生，研究方向：电子与通信工程；李欣（1960-），男，黑龙江哈尔滨人，硕士生导师，教授，研究方向：无线通信与通信系统；王心志（1986-），男，研究方向：通信与信息系统。
作者单位：哈尔滨理工大学 通信工程系，哈尔滨 150080
转载请注明出处学文网 » Viterbi译码器的并行优化设计