第27卷第1期遥测遥控Vol.27,№.12006年1月JournalofTelemetry,Tracking,andCommandJanuary2006一种维特比译码改进算法的研究刘国芳,程乃平(装备指挥技术学院北京101416收稿日期:2005204212收修改稿日期:2005207208摘要:介绍传统维特比译码算法的基本原理;,,提出一种维特比译码的改进算法,仿真结果表明,;,量小、译码延迟短的优点。关键词:卷积码;21:A:CN11-1780(200601-0030-03前言为了提高系统传输的质量,克服数据传输错误,一般采用差错控制编码,卷积编码是一种很好的纠错编码方法。它满足线性叠加原理,且子生成元不随时间变化;与之相应的维特比算法是加性高斯白噪声信道下卷积码的最优译码算法[1]。维特比译码算法是1967年Viterbi提出的一种译卷积码的最大似然译码算法。在码的约束度较小时,它的译码效率较高、速度较快,因此广泛应用于数传系统,特别是卫星通信系统中。传统的维特比算法中的回溯算法采用通用的存储器作为存储主体,存储幸存路径的格状连接关系,通过读写存储器来完成数据的写入和回溯输出。但其译码延时较长。针对此,本文提出(2,1,7卷积编码的维特比译码回溯算法的改进算法,该算法克服了传统算法的不足,有效地减少了存储器的存储空间,缩短了译码延迟。1传统的维特比译码算法的基本原理[2,3]维特比算法可用网格图来表示,它是一个时间序列的状态图。图1是一个简单的表示两个状态的状态转移网格图。在n-1时刻,两个可能状态x0、x1根据输入的信息可能转移到n时刻的两个状态0x、1x。维特比算法就是通过在网格图中寻找最小路径度量值来判决最大似然状态序列,幸存路径存储就是存储具有最小路径度量值的信息。在传统的算法中,幸存路径存储器的组织采用类似指针的方法,将幸存路径分成前序状态的幸存路径和指向前序状态的指针两部分。在幸存路径存储器写满后要进行截尾译码,截图1两状态转移网格图尾译码的过程就是找出当前时刻n的所有状态中具有最小路径度量值的状态,这个状态对应的路径就是最大似然路径,然后根据存储的指针找到其n-1时刻的前序状态,再根据该状态存储的指针找到其n-2时刻的前序状态,直到找到起始状态为止,它所存储的信息即为译码输出。在该算法中,幸存路径存储器所存储的内容既包括路径的信息,又包括前序状态的指针,因而需要大量的存储空间。同时,每输出一个译码结果需要回溯整个译码深度(即读L次存储器,因而降低了译码速度。2改进的维特比译码算法(2,1,7卷积码有27-1个状态,根据其编码原理,可以得出当旧状态输入分别为0和1时对应的输出新状态和输出值,将旧状态与新状态以及输入输出值制成表1所示的(2,1,7卷积码的子网表。表1表1(2,1,7卷积码的子网表状态序号旧状态输入0输入1新状态输出新状态输出Tab表01000000000001000000000000001110000010000011001318962300001000001100000100000101101000011001141416694511002187295210100011100011100134703725………………6262111110111111011111011111110011111111111100113276431999表2Tab表结构图旧状态1(6bit输出(2bit旧状态2(6bit输出(2bitG1G0GG只给出前八个状态和最后两个状态的对应值。最后一列称为Tab表,共有64个不同的状态,其结构为旧状态1(6bit+输出(2bit+旧状态2(6bit+输出(2bit。如表2所示。完整的(2,1,7卷积码Tab表为:Tab=[131,896,1414,1669,2187,2952,3470,3725,5008,4243,5781,5526,7064,6299,7837,7582,9120,8355,9893,9638,11176,10411,11949,11694,12467,13232,13750,14005,14523,15288,15806,16061,16834,18372,17607,19663]:状态数分成相应的存储单元,每单元的位数由译码深度决定,并对每个单元按状态排序。每一个状态当前的数值由其前一状态和该状态的奇偶决定。②搜索Tab表的每一个状态,将输入值x0x1与G0G1、G′0G′1进行比较(将Tab表中的数据经过移位得G0G1、G′0G′1,得到分支码距,与旧的路径度量值相加得到新的路径度量值,每个状态得到了两个分支累加路径度量值,将这两个分支累加路径度量值进行比较,找出比较小的一条分支累加距离,并将这条分支保存。同时把这条分支对应的路径(包含译码信息写到此状态的存储中,写入的同时,将此信息向左移位1次,在最低位写入1或者是0,当该节点为偶数时,“向...