Viterbi改进算法研究.docx

?

?

Viterbi改进算法研究

?

?

摘要：Viterbi译码算法是最大似然译码。本文所研究的改进Viterbi算法,不但保持了原有Viterbi算法的特性，而且在减少译码路径的情况下，能较好地解决突发错误信道中，原Viterbi译码算法则性能急剧下降的问题。通过在编码信道模型上的仿真表明，已知正确的约束位越多，分布的越密，则提高的性能越明显。

论文关键词：信道编码,约束维特比译码,通信

卷积码广泛应用于各种数字通信系统中。其中卫星通信中信道部分也大量采用卷积码。描述卷积编码的方法很多，如卷积码的矩阵描述、生成多项式描述、树图(网格图)描述、有限状态图描述等，并且卷积码的描述方法与它所采用的译码方法密切相关。目前研究比较成熟的方法有卷积码的生成多项式矩阵描述和网格图描述。卷积码的网格图描述是一种形象的表示卷积码编译码过程的方法，Viterbi基于网格图提出著名的Viterbi译码算法成为目前解决卷积码译码的最有效的算法。卷积码的概率译码不仅利用码自身的代数结构，而且还考虑了信道的统计特性，因而能充分发挥卷积码的特点，使译码错误概率达到最小。

1、卷积码原理

卷积码是把k个信息比特的输入经编码后。形成n个比特的输出，通常k和n很小，特别适宜于以串行形式传输信息，延时小。与分组码不同，卷积码中编码后的n个码元不但与当前段的k个信息有关，而且与前面(N-1)段的信息有关，因此称N为约束长度。编码过程中相互关联的码元为Nk个。卷积码的纠错能力随着N的增加而增大，而差错率随着N的增加而指数下降。在编码器复杂性相同的情况下，卷积码的性能优于分组码。

卷积码的译码方法可分为两大类。一类是代数译码，利用编码本身的代数结构进行译码，不考虑信道本身的统计特性。该方法的硬件实现简单，但性能较差，其中具有典型意义的是门限译码。另一类是概率译码，这种译码通常建立在最大似然准则的基础上。由于计算是用到了信道的统计特性。因而提高了译码性能，但这种性能的提高是以增加硬件的复杂度为代价的。常用的概率译码方法有维特比译码和序列译码。卷积码概率译码的基本思路是：以断续的接收码流为基础，逐个计算它与其他所有可能出现的、连续的网格图路径的距离，选出其中可能性(概率)最大的一条作为译码估值输出。概率最大在大多数场合可解释为距离最小，这种最小距离译码体现的正是最大似然的准则。

2、硬判决Viterbi译码算法原理

Viterbi算法是一种最大似然译码算法。它并不是在网格图上一次比较所有可能的2枕条路径(序列)，而是接收一段，计算、比较一段，选择一段最有可能的码段(分支)，从而达到整个码序列是一个有最大似然函数的序列。

Viterbi算法的基本思路是:以断续的接收码流为基础，逐个计算它与其他所有可能出现的、连续的格状图路径的距离，选出其中可能性(概率)最大的一条作为译码估值输出。

从时间单位m至L，网格图中2mk个状态中的每一个有一条幸存路径，共有2mk条。但在L时间单位后，网格上的状态数目减少，幸存路径也相应减少。最后到第L十m单位时间，网格图上的状态数目减少，因此仅剩下一条幸存路径。这条路径就是要找的具有最大似然函数的路径，也就是译码器输出的估值序列。由此可知，在网格图上用维特比算法得到的路经一定是一条最大似然路径，因此这种方法是最佳的。

3、改进Viterbi译码算法原理

在Viterbi译码中，对于长度为L的二进制序列的最佳译码，需要对有可能发送的2L个不同序列的2L条路径的似然函数累加值（即路径量度）进行比较，选取其中最大的一条。当该二进制序列的某位数据已经确定为正确的时，那么，所有不符合该正确数据的路径认为是错误的，这样，可以使候选路径减半，即为2L-1。所以我们每确定一位，就可以使候选路径减半，当确定了m位后候选路径数量变为2L-m。当一个位被确定为正确后，其不仅自身译码正确，同时可以影响其附近的位。

设编码器含有N个状态，其从0状态开始，当经过M时刻后，返回0状态，其译码的网格图见图1。在J时刻的接收的数据，与从J-1时刻，第i个状态，到J时刻，第k个状态输出的数据的汉明距离记为Cj(i,k)（i状态与k状态之间不存在连接的话，那么Cj(i,k)=∞）。从0时刻，0状态，到达第J时刻，k状态的所有路径中，其中一条路径具有最小汉明距离φj(k)，该路径在每个时刻经过的状态记录在εj(k)中，那么最终εM(0)就是译码的最优路径。

图1网格图

4、两种Viterbi译码算法性能的比较

在仿真中，令数据大小为250比特，信息位由随机数产生，加6位的状态归零码。共256比特。仿真的参数记录在表1中。

表1仿真参数

在仿真中，编码后的数据包的格式如图2所示，每个数据包被分为n个段S1-Sn，每段内含有m个比特，B1-Bm。每段（最后一段Sn除外）的第m-