动态规划：卷积码的Viterbi译码算法.docx

动态规划：卷积码的Viterbi译码算法学院：网研院姓名：xxx学号：xxx动态规划原理动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象有哪些信誉好的足球投注网站或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。卷积码的Viterbi译码算法简介在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。（2,1,3）卷积码编码器是最常见的卷积码编码器，在本次实验中也使用了（2,1,3）卷积码编码器，下面介绍它的原理。（2,1,3）卷积码是把信源输出的信息序列，以1个码元为一段，通过编码器输出长为2的一段码段。该码段的值不仅与当前输入码元有关，而且也与其之前的2个输入码元有关。如下图所示，输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出out2是输入和第二个编码器存储的值逻辑加操作的结果。（2,1,3）卷积码编码器（2,1，3）卷积码编码器的状态转移图如下所示，圆圈中的数字表示当前编码器中的状态，箭头指向下一个可能的状态，箭头边上的数字是状态转移对应的输出out1、out2。（2,1,3）卷积码编码器状态转移图维特比译码中使用了汉明距离的概念，下面了解一下汉明距离的原理。汉明距离是两个等长字符串对应位置的字符不同的个数，如0 1 1 0 0 1 0 0和0 0 1 11 0 00的汉明距离是4。维比特译码的基本思想是把接收到的矢量，和网格图上诸种可能的路径比较，删去距离大的路径，保留距离小的路径，以距离最小路径作为发码的估值。如输入信息比特1 0 0 1，则（2,1,3）卷积码编码器输出的信息比特是1 11 01 111，假设经过信道干扰后接收到的信息比特是1 10 01 111，则维特比译码过程是：从T0时刻的全零状态开始，零状态初始度量（汉明距离）为0，其它状态初始度量为正无穷；在任一时刻t向t+1时刻前进，对每一个状态只记录到达路径中度量最小的一个(残留路径）及其度量；前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到8条路径；在t+1时刻，对到达每一个状态的2条路径进行比较，找到一个度量最小的作为残留路径；直到码的终点，如果终点是一个确定状态，则最终保留的路径就是译码结果。维特比译码算法执行过程卷积码的Viterbi译码算法算法输入比特流个数、比特流和有噪信道的误码率（0~1）；对比特流数据进行补0操作（在比特流的最后编码器中仍保存着2个之前输入比特的状态，因此需要进行补0操作，即给输入比特流加上2个0比特）；对补0后的比特流进行（2,1,3）卷积码编码操作，编码输出的第一个结果是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，第二个结果是输入和第二个编码器存储的值逻辑加操作的结果；对（2,1,3）卷积码编码输出的数据进行传输（加上误码）；对从信道得到的有误码的比特流进行维特比译码：对比特流进行分组，2个一组循环；根据这2个比特对当前的4个状态（StateNode）计算从它出发到它可能到达的2个状态对应路径的汉明距离，并保存对应的译码序列和汉明距离；根据上一步的结果，取汉明距离小的更新这4个状态；最后，第1个状态（0状态）对应的译码序列就是维特比译码的结果（因为补零操作保证了最后肯定会回到0状态）。算法复杂度假设输入比特流序列的长度为L。由于（2,1,3）卷积码的状态数是4，对每个时刻要做4次“加-比-选”操作得到4个状态的残留路径，每次“加-比-选”操作包括2次加法和1次比较，因此总运算量约为4L次“加-比-选”操作。同时要能保存4条残留路径，因此需要4L个存贮单元。由此可见，（2,1,3）卷积码的维特比译码算法的时间和空间复杂度均与比特流序列长