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

1、动态规划：卷积码的 Viterbi译码算法学院：网研院姓名：XXX学号：XXX动态规划原理动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程 (decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最 优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值， 我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将 待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原 问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问 题往往不是互相独立的。若用分治法来解这类问题

2、，则分解得到的子问题数目太 多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案， 而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解 题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题， 有 各具特色的解题方法，而不存在一种万能的动态规划算法， 可以解决各类最优化 问题。二、卷积码的Viterbi译码算法简介在介绍维特比译码算法之前，首

3、先了解一下卷积码编码，它常常与维特比译 码结合使用。(2,1,3 )卷积码编码器是最常见的卷积码编码器，在本次实验中 也使用了( 2,1,3 )卷积码编码器，下面介绍它的原理。(2,1,3 )卷积码是把信源输出的信息序列，以1个码元为一段，通过编码器输出长为2的一段码段。该码段的值不仅与当前输入码元有关，而且也与其之前的2个输入码元有关。如下图所示，输出 out1是输入、第一个编码器存储的 值和第二个编码器存储的值逻辑加操作的结果，输出out2是输入和第二个编码器存储的值逻辑加操作的结果。(2,1,3 )卷积码编码器(2,1 , 3)卷积码编码器的状态转移图如下所示，圆圈中的数字表示当前编 码

4、器中的状态，箭头指向下一个可能的状态，箭头边上的数字是状态转移对应的 输出 outl、out2。维特比译码中使用了汉明距离的概念， 下面了解一下汉明距离的原理。 汉明 距离是两个等长字符串对应位置的字符不同的个数，如 0 1 1 0 0 1 00 和0 0 1 1 1 0 0 0 的汉明距离是4。维比特译码的基本思想是把接收到的矢量， 和网格图上诸种可能的路径比较， 删去距离大的路径，保留距离小的路径，以距离最小路径作为发码的估值。 如输 入信息比特1 0 0 1，贝9( 2,1,3 )卷积码编码器输出的信息比特是 1 1 1 0 1 1 1 1，假设经过信道干扰后接收到的信息比特是1 100

5、 1 1 1 1，则维特比译码过程是：1. 从T0时刻的全零状态开始，零状态初始度量(汉明距离)为 0,其它状 态初始度量为正无穷；2. 在任一时刻t向t+1时刻前进，对每一个状态只记录到达路径中度量最 小的一个(残留路径)及其度量；3. 前进过程中，对t时刻的每个状态作延伸，即在状态度量基础上加上分 支度量，得到8条路径；4. 在t+1时刻，对到达每一个状态的2条路径进行比较，找到一个度量最 小的作为残留路径；5. 直到码的终点，如果终点是一个确定状态，则最终保留的路径就是译码 结果。维特比译码算法执行过程三、卷积码的 Viterbi 译码算法1. 算法 输入比特流个数、比特流和有噪信道的误

6、码率（ 01）； 对比特流数据进行补 0 操作（在比特流的最后编码器中仍保存着2个之前输入比特的状态，因此需要进行补 0 操作，即给输入比特流 加上 2个 0比特）；对补 0 后的比特流进行（ 2,1,3 ）卷积码编码操作，编码输出的第一 个结果是输入、第一个编码器存储的值和第二个编码器存储的值逻 辑加操作的结果，第二个结果是输入和第二个编码器存储的值逻辑 加操作的结果；对（ 2,1,3 ）卷积码编码输出的数据进行传输（加上误码）； 对从信道得到的有误码的比特流进行维特比译码： ? 对比特流进行分组， 2 个一组循环；? 根据这 2 个比特对当前的 4 个状态（ StateNode ）计算从它

7、出发 到它可能到达的 2 个状态对应路径的汉明距离， 并保存对应的译 码序列和汉明距离；? 根据上一步的结果，取汉明距离小的更新这 4 个状态；? 最后，第 1 个状态（ 0 状态）对应的译码序列就是维特比译码的 结果（因为补零操作保证了最后肯定会回到 0 状态）。2. 算法复杂度假设输入比特流序列的长度为 L。由于（2,1,3 ）卷积码的状态数是4, 对每个时刻要做 4次“加-比-选”操作得到 4 个状态的残留路径，每次“加 -比-选”操作包括2次加法和1次比较，因此总运算量约为4L次“加-比- 选”操作。同时要能保存4条残留路径，因此需要4L个存贮单元。由此可 见，（ 2,1,3 ）卷积码

8、的维特比译码算法的时间和空间复杂度均与比特流序 列长度呈线性关系， 但维特比译码算法的时间空间复杂度与卷积码的约束长 度呈指数关系。3. 可能的改进由于维特比译码算法的时间空间复杂度与卷积码的约束长度呈指数关 系，因此对状态数很大的卷积码编码，维特比算法要经一定的修正后才可能 实用，常用的算法是缩减状态的维特比译码，即在每一时刻，只处理部分的 状态。四、算法实现框架本次实验使用的语言是java，具体的算法实现包含4个类：ViterbiDecode、 StateNode、ConvEncode和 Channel。ViterbiDecode类用于实现维特比译码，它有一个静态的decode()方法用于

9、 译码和一个静态的hammingDistance()方法用于计算汉明距离，ViterbiDecode 的main方法是程序的入口；StateNode是一个实体类，它用于保存状态，有 value(状态，如“ 00”)、 distanee (汉明距离)和solution (对应译码序列)属性；ConvEncode类用于实现(2,1,3 )卷积码编码，它只有一个静态的 encode() 方法用于编码和一个静态的addZero()方法用于补0操作；Channel类用于模拟有噪信道，它只有一个静态的transfer() 方法用于给比 特流序列加上误码。4 public class ViterbiDeco

10、de 亍叶 public static byte decode(lytfr inBytesJ166107/日妊bf；运0 ljia 旖芒H public static int hammi ngOi stance (byte byt e b) |j116117 + public static void main(String args) ise 161class StateNode -153String value;int distant已；135String solution;186IS*1 + public StateNode(String value int distance, Strin

11、g solution) 匚192 )193193 / 就击靳2 冲帝可15ConvlEncode 196 / 醐入只施展0 1s2-197 + public static byte encode(lyte inBtesJ 匚212213叶FivNt亡 static bytef addZero(byX& inBytei)223224 /厲莓气養它淳“茂ti鞫总忆丙希225 class Channel 226 雀入斤墜是0 1. errorRatt2.27 + public static byte transfer(byte inBytetj double errorRate) 匚 24 J五、总

12、结本科的时候曾经学习过卷积码编码和维特比译码的知识，考研的时候也复习了该方面知识，在理解题目上没有遇到困难。但由于从未尝试编程实现维特比译 码，因此在本次实验的过程中还是遇到了许多问题。经过查看课件及网上查找资料，我对如何编码实现卷积码的维特比译码算法有了一个较好的理解，知道了算法主要应该包括补0、卷积编码、信道传输和维特比译码4步操作，并使用了 java 语言自主完成了该实验。由于该实验完成的比较仓促，程序中仍有许多地方能进 行优化，但总的来说，通过本次试验，我对维特比译码有了一个直观的理解，同 时锻炼了使用java语言编程的能力，有不小的收获。附录程序运行示例:Problems 也 Jav

13、adoc 犠 Servers 曰 Cjnsle 阔 匾 D歸nratioriSearch 甩iterbiDecode Jav Apphcticn D;PrOgram AlesJaiva inj3vwRJLh：三样也前士豐萍旦生：15Afe .（041仝蚩焉f=）严巨爭；耳劑庄冃氓乍疽常轄车f 0心1）尹匡车：0.1耳垃比峙茨赴哩11001101100011009131110011610111丢丸2八巧楚匕克京若衣二域mi：llldllllll0I0eae0iiieeii0i0-0i鱼密电異兰空兰：t戎羚型匚冲畫曼3舍：！红范J庄m基貞拊三越丘爲?11001-010116001更谊曲琦疋浄希匪狠

14、肓*写说询玄療疣左炳坊吐即袞两牛蛊是曾源程序：public class ViterbiDecode public static byte decode(byte inBytes) StateNode stateNodes = new StateNode4;StateNode tmpNodes = new StateNode4; stateNodes0 = new StateNode(00, 0, ); for (int i = 0; i inBytes.length - 4; i = i + 2) byte twoBytes = inBytesi, inBytesi + 1 ; for (in

15、t j = 0; j stateNodes.length; j+) if (stateNodesj != null) String value = stateNodesj.value;byte byteValue = Byte.parseByte(value.substring(0, value.length() - 1), Byte.parseByte(value.substring(value.length() - 1) ;byte possibleNextValue = 0, byteValue0 , 1, byteValue0 ;/ String possibleNextOutput

16、= ;byte possibleNextOutput = (byte) (byteValue0 + byteValue1 + possibleNextValue00) % 2),(byte) (byteValue1 + possibleNextValue00) % 2) ,(byte) (byteValue0 + byteValue1 + possibleNextValue10) % 2),(byte) (byteValue1 + possibleNextValue10) % 2) ;int distances = stateNodesj.distance+ ViterbiDecode.ham

17、mingDistance(twoBytes, possibleNextOutput0), stateNodesj.distance+ ViterbiDecode.hammingDistance(twoBytes, possibleNextOutput1) ;for (int k = 0; k possibleNextValue.length; k+) byte next = possibleNextValuek;StateNode tmpNode = tmpNodesnext1 + 2 * next0;if (tmpNode != null) int d = tmpNode.distance;

18、if (distancesk d) tmpNode.distance = distancesk; tmpNode.solution = stateNodesj.solution+ possibleNextValuek0; else tmpNodesnext1 + 2 * next0 = new StateNode( next0 + + next1, distancesk, stateNodesj.solution+ possibleNextValuek0);for (int m = 0; m tmpNodes.length; m+) stateNodesm = tmpNodesm; tmpNo

19、desm = null;for (int i = inBytes.length - 4; i inBytes.length; i = i + 2) byte twoBytes = inBytesi, inBytesi + 1 ; for (int j = 0; j stateNodes.length; j+) if (stateNodesj != null) String value = stateNodesj.value; byte byteValue = Byte.parseByte(value.substring(0, value.length() - 1),Byte.parseByte

20、(value.substring(value.length() - 1) ; byte possibleNextValue = 0, byteValue0 ;byte possibleNextOutput = (byte) (byteValue0 + byteValue1) % 2), (byte) (byteValue1) % 2) ;int distance = stateNodesj.distance+ ViterbiDecode.hammingDistance(twoBytes, possibleNextOutput);StateNode tmpNode = tmpNodespossi

21、bleNextValue1 + 2* possibleNextValue0; if (tmpNode != null) int d = tmpNode.distance;if (distance d) tmpNode.distance = distance;tmpNode.solution = stateNodesj.solution + possibleNextValue0; else tmpNodespossibleNextValue1 + 2* possibleNextValue0 = new StateNode( possibleNextValue0 + + possibleNextV

22、alue1, distance, stateNodesj.solution + possibleNextValue0);for (int m = 0; m tmpNodes.length; m+) stateNodesm = tmpNodesm;tmpNodesm = null;byte outBytes = new bytestateNodes0.solution.length();for (int i = 0; i outBytes.length; i+) outBytesi = Byte.parseByte(stateNodes0.solution.substring(i,i + 1);

23、return outBytes;/ a 和 b 都是 0 1, 且 a b 等长public static int hammingDistance(byte a, byte b) int distance = 0;for (int i = 0; i 经过有噪信道 - 维 码 *);请输入比特流的长度并回车 :);int n = in.nextInt();请输入比特流 (0 或者 1，空格隔开 )并回车 :);byte a = new byten;for (int i = 0; i a.length; i+) ai = in.nextByte();请输入有噪信道误码率 (01) 并回车 :);

24、double r = in.nextDouble();/ 记录信道传输造成的误码个数 err1 和维特比译码还原结果的误码个数 int err1 = 0;int err2 = 0;/ 输出原始比特流数据原始比特流数据： );for (int i = 0; i a.length; i+) + );/ 输出卷及编码结果经过 (2,1,3) 卷积编码后的比特流数据： ); byte b = ConvEncode.encode(a);for (int i = 0; i b.length; i+) + );/ 输出信道传输结果经过误码率为 + r + 的有噪信道后的比特流数据： byte c = Cha

25、nnel.transfer(b, r);for (int i = 0; i c.length; i+) + ); if (ci != bi) err1+;/ 输出有噪信道造成的误码个数经过有噪信道后造成的误码个数是 + err1);/ 输出维特比译码结果经过维特比译码还原的比特流数据： ); byte d = ViterbiDecode.decode(c);for (int i = 0; i s1-s2- 丢弃public static byte encode(byte inBytes) byte actualBytes = ConvEncode.addZero(inBytes);byte outBytes = new byte2 * actualBytes.length;byte s1 = 0;byte s2