动态规划:卷积码的Vitｅrｂi译码算法学院:网研院ﻩ姓名:ｘxx 学号：xxｘ一、动态规划原理动态规划（dynamｉc programminｇ)是运筹学的一个分支,是求解决策过程(decｉsioｎ procｅsｓ）最优化的数学方法。
动态规划算法通常用于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。
不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。
动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。
二、卷积码的Ｖｉterbi译码算法简介在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。
(2,１，3)卷积码编码器是最常见的卷积码编码器,在本次实验中也使用了(2,1，３)卷积码编码器,下面介绍它的原理。
（2,１,３)卷积码是把信源输出的信息序列，以1个码元为一段,通过编码器输出长为2的一段码段。
该码段的值不仅与当前输入码元有关，而且也与其之前的２个输入码元有关。
如下图所示,输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出ouｔ２是输入和第二个编码器存储的值逻辑加操作的结果。
（２,1,３)卷积码编码器(2，１，3）卷积码编码器的状态转移图如下所示,圆圈中的数字表示当前编码器中的状态，箭头指向下一个可能的状态,箭头边上的数字是状态转移对应的输出out1、oｕt2。
（２，1,３）卷积码编码器状态转移图维特比译码中使用了汉明距离的概念，下面了解一下汉明距离的原理。
汉明距离是两个等长字符串对应位置的字符不同的个数,如０ 1 1 0 ０ 1 0 ０和0 ０ 1 1 １ 0 0 0的汉明距离是4。
维比特译码的基本思想是把接收到的矢量,和网格图上诸种可能的路径比较,删去距离大的路径，保留距离小的路径,以距离最小路径作为发码的估值。
如输入信息比特1 0 0 1,则（2,1,３)卷积码编码器输出的信息比特是1 １ 1 0 1 1 1 １，假设经过信道干扰后接收到的信息比特是1 1 0 0 1 １ 1 1，则维特比译码过程是：1.从Ｔ0时刻的全零状态开始，零状态初始度量(汉明距离）为0,其它状态初始度量为正无穷；2.在任一时刻t向t+1时刻前进，对每一个状态只记录到达路径中度量最小的一个(残留路径）及其度量；3.前进过程中，对ｔ时刻的每个状态作延伸,即在状态度量基础上加上分支度量,得到8条路径；4.在ｔ＋１时刻，对到达每一个状态的2条路径进行比较,找到一个度量最小的作为残留路径;5.直到码的终点，如果终点是一个确定状态,则最终保留的路径就是译码结果。
维特比译码算法执行过程三、卷积码的Viterbi译码算法1.算法●输入比特流个数、比特流和有噪信道的误码率（0~１)；●对比特流数据进行补０操作（在比特流的最后编码器中仍保存着2个之前输入比特的状态，因此需要进行补0操作,即给输入比特流加上2个０比特);●对补0后的比特流进行（2,1,3）卷积码编码操作，编码输出的第一个结果是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果,第二个结果是输入和第二个编码器存储的值逻辑加操作的结果；●对(2,1，3)卷积码编码输出的数据进行传输（加上误码）；●对从信道得到的有误码的比特流进行维特比译码：•对比特流进行分组，2个一组循环;•根据这2个比特对当前的４个状态(ＳtateＮodｅ)计算从它出发到它可能到达的2个状态对应路径的汉明距离,并保存对应的译码序列和汉明距离;•根据上一步的结果，取汉明距离小的更新这４个状态；•最后，第1个状态(０状态)对应的译码序列就是维特比译码的结果(因为补零操作保证了最后肯定会回到0状态）。
2.算法复杂度假设输入比特流序列的长度为Ｌ。
由于(２,1，3）卷积码的状态数是4，对每个时刻要做４次“加-比－选”操作得到4个状态的残留路径，每次“加－比－选”操作包括２次加法和1次比较,因此总运算量约为4L次“加-比－选”操作。
同时要能保存4条残留路径,因此需要4L个存贮单元。
由此可见，(2,1,3)卷积码的维特比译码算法的时间和空间复杂度均与比特流序列长度呈线性关系,但维特比译码算法的时间空间复杂度与卷积码的约束长度呈指数关系。
3.可能的改进由于维特比译码算法的时间空间复杂度与卷积码的约束长度呈指数关系,因此对状态数很大的卷积码编码，维特比算法要经一定的修正后才可能实用，常用的算法是缩减状态的维特比译码,即在每一时刻，只处理部分的状态。
四、算法实现框架本次实验使用的语言是jａｖa，具体的算法实现包含4个类:ViterbｉDｅcode、ＳｔaｔeNodｅ、CoｎvEncode和Cｈanｎeｌ。
ViｔeｒｂiDｅcode类用于实现维特比译码，它有一个静态的decoｄe()方法用于译码和一个静态的hammｉngDistance（)方法用于计算汉明距离,VitｅrbiＤecode的ｍａｉn方法是程序的入口；ＳtａteNode是一个实体类，它用于保存状态，有ｖaｌuｅ(状态，如“00”)、ｄｉstａnce(汉明距离)和solutｉoｎ(对应译码序列）属性;ConvＥｎcode类用于实现（2,1，3)卷积码编码,它只有一个静态的ｅｎcode(）方法用于编码和一个静态的addＺero（)方法用于补0操作；Cｈannel类用于模拟有噪信道，它只有一个静态的transfｅr()方法用于给比特流序列加上误码。
五、总结本科的时候曾经学习过卷积码编码和维特比译码的知识，考研的时候也复习了该方面知识,在理解题目上没有遇到困难。
但由于从未尝试编程实现维特比译码，因此在本次实验的过程中还是遇到了许多问题。
经过查看课件及网上查找资料，我对如何编码实现卷积码的维特比译码算法有了一个较好的理解，知道了算法主要应该包括补0、卷积编码、信道传输和维特比译码4步操作,并使用了ja ｖａ语言自主完成了该实验。
由于该实验完成的比较仓促，程序中仍有许多地方能进行优化,但总的来说，通过本次试验，我对维特比译码有了一个直观的理解,同时锻炼了使用ｊavａ语言编程的能力,有不小的收获。
附录程序运行示例：源程序：impｏrt javａ.utiｌ.Raｎdom；import jａva.util.Scanner；ｐubｌｉｃcｌass ViｔeｒbiDecｏdｅ{pｕbｌiｃｓｔatｉc byte[] ｄｅｃｏdｅ(byte［] inＢｙｔes) {StateNｏdｅ[] ｓtateＮｏdｅs = neｗ StateＮoｄe[4];ＳtatｅＮｏｄｅ[］tｍpNｏdes = ｎew StateNoｄe[4］;stateＮodeｓ[0] = ｎeｗStａｔeNｏde（"０0＂, ０, "")；ﻩﻩｆor (iｎt i = 0；ｉ＜ inＢytes.length - 4; i = ｉ + 2) {byte［] ｔwｏBytes = ｛ iｎBytｅs［ｉ], inByｔeｓ［i + 1］ };ﻩｆor (iｎt j ＝ 0; j < stａｔｅNodes．lenｇth; j++） {ﻩﻩiｆ (ｓtatｅNｏdｅs[j] ！= nuｌl） {ﻩﻩﻩSｔｒinｇ vaｌue = ｓtateNｏdes[j].vａｌue;ﻩﻩﻩbｙtｅ[] byteVａlｕe = ｛ﻩﻩﻩＢｙte.parseＢyte(vaｌuｅ.substring(0,ﻩﻩﻩﻩﻩﻩvalｕｅ.lenｇth（) - １)),ﻩﻩﻩﻩByte.parseByte（valuｅ．suｂｓtｒinｇ(vaｌue．leｎgth(）－1）) };ﻩﻩbytｅ［］[] ｐoｓsibｌeNextValue = ｛｛０, bytｅVａlue[0] ｝,ﻩﻩﻩ{ 1, bｙteValuｅ[0] } };ﻩﻩﻩ／／ Strｉng[] poｓsｉbleNeｘtＯutpｕt ＝｛};ﻩﻩﻩbyte［][] posｓiｂleNextＯutｐut = {ﻩﻩﻩﻩﻩ{ﻩﻩﻩ（bytｅ) （(bｙteＶａｌｕe［0] ＋ｂyｔeＶaｌuｅ［1] + ｐosｓib ｌeNexｔValue[０][0]) % 2),ﻩﻩ(ｂｙｔe) ((byteVａlue［1] + ｐoｓsｉblｅNexｔValue[０]［0]） % 2） }，ﻩﻩﻩﻩ{ﻩﻩﻩﻩ(ｂytｅ) ((byｔeVａlｕe[0] + ｂyteVaｌｕe［1] ＋ posｓibleNｅｘtVa ｌue[1][0］) % 2），ﻩﻩﻩﻩ(bｙte) ((ｂyｔeＶalｕe［1］ + possｉbleNｅｘtValuｅ[１］[0］) % ２) } };ﻩﻩﻩinｔ[] ｄiｓtances ＝｛ﻩﻩﻩsｔateNodes[j].ｄiｓｔanceﻩﻩﻩﻩﻩﻩ＋ViterｂｉＤｅcode.ｈａｍｍingDisｔanｃe（tｗoBｙtｅs，ﻩﻩﻩﻩｐoｓｓibleNｅｘtＯｕtput［0]）,ﻩﻩﻩstateNoｄes[j].disｔａnｃｅﻩﻩﻩ+ ViｔerbiDecｏｄe．ｈaｍmingDｉstａnce(twｏBｙteｓ,ﻩﻩﻩposｓｉｂleNｅxｔＯuｔput［1]） };ﻩﻩﻩﻩfor (int ｋ = 0； k < poｓsｉｂleNextValue.lｅnｇth； k+＋) {ﻩﻩbyte[］ nexｔ = possibｌｅNｅｘtVａlue［k]；ﻩﻩﻩﻩStateＮode ｔmpNodｅ = tmpNｏdeｓ[nｅxｔ[１] ＋ 2 * nｅｘt[0]];ﻩﻩﻩﻩif （ｔmpNode ！= null) {ﻩﻩint d = tmpＮode．diｓtancｅ;ﻩﻩﻩﻩｉf (dｉsｔances［k］< d）｛ﻩﻩﻩﻩtmpＮode．dｉsｔａnce ＝dｉstanceｓ[k];ﻩﻩﻩﻩﻩtmpNode.solutｉｏn ＝ sｔａteＮｏｄes［ｊ].solutiｏｎﻩﻩﻩﻩ＋pｏｓsibleNeｘtValue[k][0];ﻩﻩﻩ}ﻩﻩﻩ} elｓe ｛ﻩﻩﻩﻩtmｐNoｄes［next[１] ＋ 2 * nｅxt[0]] = ｎew StａteNｏde(ﻩﻩﻩﻩﻩﻩneｘt［０] + "＂＋ nｅｘt[1], disｔancｅs［ｋ],ﻩﻩﻩﻩﻩstateNｏdｅs[ｊ］.solutｉoｎﻩﻩﻩﻩﻩﻩﻩﻩ+ poｓsibleＮextVａlｕe［k][0］);ﻩﻩﻩﻩﻩ}ﻩﻩﻩ｝ﻩﻩ}ﻩ}ﻩｆoｒ (int ｍ = 0; m < tｍpNodes.leｎgth; m++) {ﻩsｔatｅNｏdes[m] ＝ tｍpNodｅs[m］;ﻩﻩﻩtｍpNodes[m] = null;ﻩ}｝ﻩfｏr （ｉnt ｉ = inBytes．leｎgth - 4; i < iｎBytes.lengtｈ; ｉ = ｉ＋2) { ﻩﻩｂytｅ［］ twｏBytｅs = { inBytｅs［i], inＢｙteｓ［ｉ＋ 1] };ﻩfｏr (iｎt j ＝ 0； j < ｓtatｅNodes.lｅnｇth; j++) {ｉf （sｔateNoｄeｓ[j] != nulｌ） {ﻩＳｔrｉng vaｌｕe ＝ stａteNodeｓ［ｊ].value；ﻩﻩﻩbytｅ［] bytｅValuｅ = {ﻩﻩﻩﻩﻩＢｙtｅ.ｐａrsｅBｙte（ｖalue.ｓuｂｓtrinｇ（０,ﻩﻩﻩｖalｕe．lenｇｔh() - 1）),ﻩﻩﻩﻩByｔｅ.parseBｙｔe(vａlｕe.suｂstring(vａlｕｅ．ｌengｔh() - 1)) }; ﻩﻩﻩﻩbyte[] posｓibleNextValｕe = { ０, byteVａlue[0] }；ﻩﻩbytｅ[］ｐosｓiblｅNeｘｔOutpｕt = ｛ﻩﻩﻩﻩﻩ(byte) (（byｔeＶaｌｕe[0] ＋ byteValue[1]) ％ 2),ﻩﻩﻩﻩ(bytｅ) ((ｂyｔeValue[１]） % ２） };ﻩﻩﻩﻩｉｎt dｉsｔance ＝sｔatｅＮodｅs[j］.dｉｓtanceﻩﻩﻩﻩ＋ViterbiDeｃoｄe.hamｍingＤｉsｔanｃｅ（twｏＢｙtes,ﻩﻩﻩﻩﻩpossibleNextOutｐuｔ）;ﻩﻩﻩﻩＳtａteNodｅｔmpＮode = tmpＮoｄes[ｐｏssibｌeNextValue［1］＋２ﻩﻩﻩ* possiｂｌｅNextValｕe[０]］;ﻩﻩｉf （tmｐNodｅ！＝ nｕll) {ﻩﻩﻩﻩint ｄ = ｔｍpNｏde.ｄistance；ﻩﻩﻩﻩif （dｉstａnce < ｄ) {ﻩtmpNode．disｔance = ｄｉsｔanｃｅ;ﻩﻩﻩtmpNｏｄe.soluｔiｏn = staｔeNoｄｅｓ[ｊ].solutionﻩﻩﻩﻩ+ poｓsibleＮeｘtValｕe[０];ﻩﻩﻩ}ﻩﻩﻩ} else {ﻩﻩﻩtmpNodｅs[ｐossiｂleNexｔVaｌue[1］＋２ﻩﻩﻩ* possibｌeＮextＶａlue[0］］ = new StaｔeＮｏde( ﻩﻩﻩpｏssibleNextＶaluｅ[０] + ""ﻩﻩﻩﻩ+ possｉbleNeｘtValue[1], ｄistance,ﻩﻩﻩﻩstateＮodeｓ［j]．soｌutiｏn + possibleNｅｘtＶaｌue[0]);ﻩﻩﻩﻩ｝}ﻩ｝ﻩｆoｒ(ｉnｔ m = 0；m ＜ｔmpNodeｓ．ｌeｎgth; m++） {ﻩﻩﻩｓｔateNｏdes［m] = tmpNｏdes[m];ﻩtｍpNodｅｓ[ｍ］ = nulｌ;ﻩ}ﻩ}bｙtｅ[] outBytｅs ＝neｗbｙtｅ[stateＮodeｓ[0].sｏlｕtion.lengtｈ()];ﻩﻩfｏr (int ｉ = 0； i < oｕｔBytｅｓ.lengtｈ; i++) {ﻩﻩoutBytes[ｉ] = Byｔe．ｐarｓeＢytｅ(stateＮｏdｅs［０].solｕtion．substriｎg(i，ﻩﻩﻩﻩi + 1))；}ﻩﻩreturn outＢytｅs；}ﻩ// ａ和b都是0 1,且ａ b等长ﻩpublｉc staｔｉc ｉｎt hammｉngDistance(ｂｙte［] a, byte[] ｂ) {ﻩint diｓｔance ＝０;ﻩﻩｆoｒ (ｉnt i = 0; i < a．ｌｅnｇth; ｉ＋+) ｛ﻩﻩif （ａ[i］ != b[i］）ﻩdistancｅ++;ﻩ}ﻩreturn ｄiｓtance;ﻩ}ﻩｐｕｂliｃstaｔic void mａin(Ｓtrｉｎg［］args） {ﻩ／/ 输入参数ﻩＳcaｎner iｎ＝ｎeｗSｃanner(Syｓtem.ｉｎ);ﻩﻩwｈiｌe (true) {ﻩﻩﻩＳyｓtem．ｏutﻩﻩ.printｌn(＂***＊**＊*模拟实现比特流的(２,1,３)卷积编码->经过有噪信道->维特比译码********");ﻩSｙstem.out.ｐrintｌn("请输入比特流的长度并回车："）;ｉnｔ n = in．ｎextInt();ﻩﻩﻩSｙstem.out.prinｔln("请输入比特流(0或者1,空格隔开)并回车:");ﻩﻩbｙte[] a = new byte[ｎ］;ﻩｆor (ｉnt i = 0; i < a.lｅngth; i++) {ﻩﻩa[ｉ] = in.nextByｔe（);}ﻩﻩﻩSyｓtｅｍ．out．prinｔｌｎ("请输入有噪信道误码率(０~１)并回车：");ﻩﻩﻩdoubｌe ｒ＝ in.nextDoubｌｅ(）;ﻩﻩ／／记录信道传输造成的误码个数erｒ１和维特比译码还原结果的误码个数err２ﻩﻩiｎt err1 = ０；ﻩint err2 = 0;ﻩ// 输出原始比特流数据ﻩﻩﻩSyｓtem.out.prinｔln("原始比特流数据："）;ﻩﻩｆor (int ｉ = 0; ｉ < ａ.length; ｉ+＋) {ﻩﻩＳyｓｔem．oｕｔ.pｒint(a[ｉ］ + ＂");ﻩ}Sｙｓｔｅm.oｕt．println(＂")；ﻩﻩﻩ// 输出卷及编码结果ﻩﻩﻩSystｅm．out.priｎtｌn（＂经过（2，１,3)卷积编码后的比特流数据：");ﻩﻩｂyte[] b = CｏnvEｎcode.enｃode(a）；ﻩfｏr (iｎt i = 0； i < ｂ.ｌength; i＋＋) {ﻩSystｅｍ.out.ｐrint(ｂ[ｉ］ + " ");}ﻩﻩSｙstem.out．priｎtln（＂"）;ﻩﻩﻩ// 输出信道传输结果Sｙsteｍ.oｕt．prｉntlｎ("经过误码率为" ＋ r + ＂的有噪信道后的比特流数据：");byte[] ｃ＝ Channｅl.tｒaｎｓfer(ｂ, r)；ﻩﻩfｏr (ｉnt i ＝ 0；i < ｃ.length; ｉ++) {ﻩSysｔeｍ.ｏut.pｒｉnt（c［i] + " ")；ﻩiｆ（c[i] != ｂ[i]) ｛ﻩﻩﻩﻩﻩerr1+＋；ﻩﻩ}ﻩ｝ﻩﻩﻩSyｓｔeｍ．out.println("");ﻩﻩ/／输出有噪信道造成的误码个数ﻩSｙsｔeｍ.out.println("经过有噪信道后造成的误码个数是" + err1)；ﻩ/／输出维特比译码结果Syｓtｅm.out.println(＂经过维特比译码还原的比特流数据:＂);ﻩbyte［］ d = VitｅｒbiDｅｃode.dｅcode(ｃ);ﻩfor (int ｉ＝０; ｉ < d.length - 2; i++) ｛ﻩﻩSｙstｅm.out.print(ｄ[ｉ] + " ")；ﻩiｆ（d[i] != a［i]) {ﻩerr2++;ﻩﻩ｝}ﻩSysteｍ．out.prｉnｔln("");ﻩ／／输出维特比译码还原结果的误码个数ﻩSyｓtem.out.priｎtｌｎ(＂经过维特比译码还原后，与原始比特流数据相比的误码个数是" + ｅｒｒ2)；ﻩﻩＳyｓtem.out.prｉntln(＂")；ﻩ}ﻩ}}clasｓ SｔａtｅNode ｛Strｉｎｇ value;ﻩint ｄistａnｃe;Stｒｉｎg soｌutｉon;ｐublic SｔateNodｅ（String valuｅ, ｉnt dｉstance, Striｎg soｌuｔion) {ﻩthis.valuｅ = value;ﻩﻩｔhiｓ.ｄiｓtance ＝ distａnce;ﻩthｉs.solutiｏn = solutｉon;}}// 模拟实现(2,1,３)卷积码ｃlａss ConvＥncode {ﻩ// 输入只能是0 １,编码器的顺序是输入->s１->s2->丢弃pubｌic stａｔiｃbyte[］ encode(byte［] inBytes) {ﻩbｙｔe[] aｃtｕalBytes ＝ ConvEncode.addＺerｏ（inBytｅs);ﻩbyte[] oｕtByteｓ= neｗ byｔe[2 * ａctｕａｌByteｓ.length];ﻩｂytｅs1 = ０;ﻩﻩbyｔe s2 ＝0;ﻩｆor (ｉnｔｉ＝0; i < actuａlBytes．length； i++）｛ﻩﻩｏutBytｅs［2 * i] = (bytｅ) （(s１ + ｓ2 ＋ａctｕalBytes[ｉ]) ％ 2 =＝ 0 ? 0ﻩ: 1)；ﻩﻩoutBytes［2 * ｉ＋１] = (byｔe） ((ｓ2 ＋ａcｔualBｙtｅｓ［i］） % ２＝= ０？０ﻩﻩﻩﻩ: １)；ﻩﻩs2 = s１;ﻩﻩs1 = aｃtualBytｅs[i]；ﻩ}rｅtｕrn outBytes;｝ﻩpｒivate stａtｉc byte［] addＺeｒｏ（bytｅ[］ inBytes） {--ﻩﻩbyte［] ouｔByteｓ = new byte[inＢyｔes.ｌenｇｔh ＋2］;ﻩfor (int i = 0; i < outBｙtes.lｅngth - 2; i++) {ﻩoutＢytes[i] = inＢｙtes[i];}ﻩｏutByteｓ[outByteｓ.length － 2］ = 0;ﻩﻩｏuｔBytes[ｏuｔBytｅｓ.lengtｈ－ 1] ＝0；retuｒn oｕtByｔes;ﻩ}}/／模拟传输信道,为比特增加误码claｓs Cｈannel ｛// 输入只能是０1，erｒoｒRatｅ取值0（包含)~1(不包含)ﻩpublｉc static bｙte[］ transfer（byte[] inBytes, ｄouｂｌe errｏｒRaｔe) ｛ﻩﻩbytｅ[] ｏｕｔBｙtｅs ＝ｎew bｙte[inByteｓ.lengｔｈ];ﻩRanｄｏｍ r = nｅw Randoｍ（)；ﻩdouｂle randｏmDｏuble;ﻩｆｏr (inｔ i ＝0； i < ｏutByteｓ．lengｔｈ; i++) ｛ouｔBytes［i］＝ inBｙtes[ｉ];ｒａndomDoublｅ＝ r.nｅｘtＤoｕbｌe（)；ﻩif （randｏmDｏuble < ｅｒrorRａte） {ﻩﻩﻩｏutByteｓ[i］ = (byte) (ｏｕｔByteｓ[i] =＝0 ? １ : 0）;ﻩﻩ}ﻩ}ｒeturn oｕｔBytes;ﻩ}}--。