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

动态规划：卷积码的Viterbi译码算法学院：网研院姓名：xxx学号：xxx一、动态规划原理动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。二、卷积码的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）卷积码编码器状态转移图维特比译码中使用了汉明距离的概念，下面了解一下汉明距离的原理。汉明距离是两个等长字符串对应位置的字符不同的个数，如01100100和00111000的汉明距离是4。维比特译码的基本思想是把接收到的矢量，和网格图上诸种可能的路径比较，删去距离大的路径，保留距离小的路径，以距离最小路径作为发码的估值。如输入信息比特1001，则（2,1,3）卷积码编码器输出的信息比特是11101111，假设经过信道干扰后接收到的信息比特是11001111，则维特比译码过程是：1.从T0时刻的全零状态开始，零状态初始度量（汉明距离）为0，其它状态初始度量为正无穷；2.在任一时刻t向t+1时刻前进，对每一个状态只记录到达路径中度量最小的一个(残留路径）及其度量；3.前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分支度量，得到8条路径；4.在t+1时刻，对到达每一个状态的2条路径进行比较，找到一个度量最小的作为残留路径；5.直到码的终点，如果终点是一个确定状态，则最终保留的路径就是译码结果。维特比译码算法执行过程三、卷积码的Viterbi译码算法1.算法输入比特流个数、比特流和有噪信道的误码率（0~1）；对比特流数据进行补0操作（在比特流的最后编码器中仍保存着2个之前输入比特的状态，因此需要进行补0操作，即给输入比特流加上2个0比特）；对补0后的比特流进行（2,1,3）卷积码编码操作，编码输出的第一个结果是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，第二个结果是输入和第二个编码器存储的值逻辑加操作的结果；对（2,1,3）卷积码编码输出的数据进行传输（加上误码）；对从信道得到的有误码的比特流进行维特比译码：•对比特流进行分组，2个一组循环；•根据这2个比特对当前的4个状态（StateNode）计算从它出发到它可能到达的2个状态对应路径的汉明距离，并保存对应的译码序列和汉明距离；•根据上一步的结果，取汉明距离小的更新这4个状态；•最后，第1个状态（0状态）对应的译码序列就是维特比译码的结果（因为补零操作保证了最后肯定会回到0状态）。2.算法复杂度假设输入比特流序列的长度为L。由于（2,1,3）卷积码的状态数是4，对每个时刻要做4次“加-比-选”操作得到4个状态的残留路径，每次“加-比-选”操作包括2次加法和1次比较，因此总运算量约为4L次“加-比-选”操作。同时要能保存4条残留路径，因此需要4L个存贮单元。由此可见，（2,1,3）卷积码的维特比译码算法的时间和空间复杂度均与比特流序列长度呈线性关系，但维特比译码算法的时间空间复杂度与卷积码的约束长度呈指数关系。3.可能的改进由于维特比译码算法的时间空间复杂度与卷积码的约束长度呈指数关系，因此对状态数很大的卷积码编码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的状态。四、算法实现框架本次实验使用的语言是java，具体的算法实现包含4个类：ViterbiDecode、StateNode、ConvEncode和Channel。ViterbiDecode类用于实现维特比译码，它有一个静态的decode()方法用于译码和一个静态的hammingDistance()方法用于计算汉明距离，ViterbiDecode的main方法是程序的入口；StateNode是一个实体类，它用于保存状态，有value(状态，如“00”)、distance（汉明距离）和solution（对应译码序列）属性；ConvEncode类用于实现（2,1,3）卷积码编码，它只有一个静态的encode()方法用于编码和一个静态的addZero()方法用于补0操作；Channel类用于模拟有噪信道，它只有一个静态的transfer()方法用于给比特流序列加上误码。五、总结本科的时候曾经学习过卷积码编码和维特比译码的知识，考研的时候也复习了该方面知识，在理解题目上没有遇到困难。但由于从未尝试编程实现维特比译码，因此在本次实验的过程中还是遇到了许多问题。经过查看课件及网上查找资料，我对如何编码实现卷积码的维特比译码算法有了一个较好的理解，知道了算法主要应该包括补0、卷积编码、信道传输和维特比译码4步操作，并使用了java语言自主完成了该实验。由于该实验完成的比较仓促，程序中仍有许多地方能进行优化，但总的来说，通过本次试验，我对维特比译码有了一个直观的理解，同时锻炼了使用java语言编程的能力，有不小的收获。附录程序运行示例：源程序：importjava.util.Random;importjava.util.Scanner;publicclassViterbiDecode{publicstaticbyte[]decode(byte[]inBytes){StateNode[]stateNodes=newStateNode[4];StateNode[]tmpNodes=newStateNode[4];stateNodes[0]=newStateNode(00,0,);for(inti=0;iinBytes.length-4;i=i+2){byte[]twoBytes={inBytes[i],inBytes[i+1]};for(intj=0;jstateNodes.length;j++){if(stateNodes[j]!=null){Stringvalue=stateNodes[j].value;byte[]byteValue={Byte.parseByte(value.substring(0,value.length()-1)),Byte.parseByte(value.substring(value.length()-1))};byte[][]possibleNextValue={{0,byteValue[0]},{1,byteValue[0]}};//String[]possibleNextOutput={};byte[][]possibleNextOutput={{(byte)((byteValue[0]+byteValue[1]+possibleNextValue[0][0])%2),(byte)((byteValue[1]+possibleNextValue[0][0])%2)},{(byte)((byteValue[0]+byteValue[1]+possibleNextValue[1][0])%2),(byte)((byteValue[1]+possibleNextValue[1][0])%2)}};int[]distances={stateNodes[j].distance+ViterbiDecode.hammingDistance(twoBytes,possibleNextOutput[0]),stateNodes[j].distance+ViterbiDecode.hammingDistance(twoBytes,possibleNextOutput[1])};for(intk=0;kpossibleNextValue.length;k++){byte[]next=possibleNextValue[k];StateNodetmpNode=tmpNodes[next[1]+2*next[0]];if(tmpNode!=null){intd=tmpNode.distance;if(distances[k]d){tmpNode.distance=distances[k];tmpNode.solution=stateNodes[j].solution+possibleNextValue[k][0];}}else{tmpNodes[next[1]+2*next[0]]=newStateNode(next[0]++next[1],distances[k],stateNodes[j].solution+possibleNextValue[k][0]);}}}}for(intm=0;mtmpNodes.length;m++){stateNodes[m]=tmpNodes[m];tmpNodes[m]=null;}}for(inti=inBytes.length-4;iinBytes.length;i=i+2){byte[]twoBytes={inBytes[i],inBytes[i+1]};for(intj=0;jstateNodes.length;j++){if(stateNodes[j]!=null){Stringvalue=stateNodes[j].value;byte[]byteValue={Byte.parseByte(value.substring(0,value.length()-1)),Byte.parseByte(value.substring(value.length()-1))};byte[]possibleNextValue={0,byteValue[0]};byte[]possibleNextOutput={(byte)((byteValue[0]+byteValue[1])%2),(byte)((byteValue[1])%2)};intdistance=stateNodes[j].distance+ViterbiDecode.hammingDistance(twoBytes,possibleNextOutput);StateNodetmpNode=tmpNodes[possibleNextValue[1]+2*possibleNextValue[0]];if(tmpNode!=null){intd=tmpNode.distance;if(distance