第23卷第2期常熟理工学院学报(自然科学)Vo1．23No．22009年2月JournalofChangshuInstituteTechnology(NaturalSciences)Feb．，2009Viterbi译码算法改进毛淑华，李丽华(东华理工大学信息工程学院通信与信息技术系，江西抚州344000)摘要：改进后的Viterbi译码算法，不但保持了原有Viterbi算法的特性，而且在减少译码路径的情况下，较好地解决了突发错误信道中原Viterbi译码算法性能急剧下降的问题．通过在编码信道模型上的仿真表明：正确的约束位越多、分布的越密，则性能提高越明显．关键词：信道编码；维特比译码；通信中图分类号：TN911．22文献标识码：A文章编号：1008—2794(2009)02一O115—03卷积码广泛应用于各种数字通信系统中．其中卫星通信中信道部分也大量采用卷积码．描述卷积编码的方法很多，如卷积码的矩阵描述、生成多项式描述、树图(网格图)描述、有限状态图描述等，并且卷积码的描述方法与它所采用的译码方法密切相关．目前比较成熟的方法有卷积码的生成多项式矩阵描述和网格图描述．卷积码的网格图描述是一种形象的表示卷积码编译码过程的方法，Viterbi基于网格图提出著名的Viterbi译码算法成为目前解决卷积码译码的最有效的算法．卷积码的概率译码不仅利用码自身的代数结构，而且还考虑了信道的统计特性，因而能充分发挥卷积码的特点，使译码错误概率达到最4,i．1卷积码原理卷积码是把k个信息比特的输入经编码后，形成n个比特的输出，通常k和n很小，特别适宜于以串行形式传输信息，延时小．与分组码不同，卷积码中编码后的n个码元不但与当前段的个信息有关，而且与前面(Ⅳ一1)段的信息有关，因此称J7v为约束长度．编码过程中相互关联的码元为舭个．卷积码的纠错能力随着Ⅳ的增加而增大，而差错率随着J7、r的增加而指数下降．在编码器复杂性相同的情况下，卷积码的性能优于分组码[41．卷积码的译码方法可分为两大类，一类是代数译码，利用编码本身的代数结构进行译码，不考虑信道本身的统计特性．该方法的硬件实现简单，但性能较差，其中具有典型意义的是门限译码．另一类是概率译码，这种译码通常建立在最大似然准则的基础上．由于计算用到了信道的统计特性．因而提高了译码性能，但这种性能的提高是以增加硬件的复杂度为代价的．常用的概率译码方法有维特比译码和序列译码．卷积码概率译码的基本思路是：以断续的接收码流为基础，逐个计算它与其他所有可能出现的、连续的网格图路径的距离，选出其中可能性(概率)最大的一条作为译码估值输出．概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则1．收稿日期：2008—11-29作者简介：毛淑华(1979一)，女，江西省南城县人，东华理工大学信息工程学院通信与信息技术系助教，大学计算机应用技术研究生，研究方向：通信技术．116常熟理工学院学报(自然科学)2009矩2硬判决Viterbi译码算法原理Viterbi算法是一种最大似然译码算法．它并不是在网格图上一次比较所有可能的2条路径(序列)，而是接收一段，计算、比较一段，选择一段最有可能的码段(分支)，从而达到整个码序列是一个有最大似然函数的序列．Viterbi算法的基本思路是：以断续的接收码流为基础，逐个计算它与其他所有可能出现的、连续的格状图路径的距离，选出其中可能性(概率)最大的一条作为译码估值输出．从时间单位m至，网格图中2个状态中的每一个有一条幸存路径，共有2条．但在时间单位后，网格上的状态数目减少，幸存路径也相应减少．最后到第+m单位时间，网格图上的状态数目减少，因此仅剩下一条幸存路径．这条路径就是要找的具有最大似然函数的路径，也就是译码器输出的估值序列．由此可知，在网格图上用维特比算法得到的路经一定是一条最大似然路径，因此这种方法是最佳的．3改进Viterbi译码算法原理在Viterbi译码中，对于长度为的二进制序列的最佳译码，需要对有可能发送的2个不同序列的2条路径的似然函数累加值(即路径量度)进行比较，选取其中最大的一条．当该二进制序列的某位数据已经确定为正确的时，那么，所有不符合该正确数据的路径认为是错误的，这样，可以使候选路径减半，即为2．所以我们每确定一位，就可以使候选路径减半，当确定了m位后候选路径数量变为2．当一个位被确定为正确后，其不仅自身译码正确，同时可以影响其附近的位．设编码器含有Ⅳ个状态，其从0状态开始，当经过时刻后，返回0状态，其译码的网格图见图1．在．，时刻的接收的数据，与从J-1时刻，第i-~-状态，到．，时刻，第k个状态输出的