Viterbi译码 》问题:根据接收序列求解最可能的发送序列 例 收到序列是: l|o00|00| 求最可能的发送序列 已知条件: 口卷积码的结构G=[7;5] 口信息的长度是L=5比特+m=2 tail bits □0始0终的路径
Viterbi译码 问题:根据接收序列求解最可能的发送序列 例: 收到序列是: 11 10 11 00 11 00 11 求最可能的发送序列 已知条件: 卷积码的结构G=[7;5] 信息的长度是L=5比特+m=2tail bits 0始0终的路径
苯办法 所有可能的发送结果有32种 收端用所有5比特组合进行编码,将结 果同接收序列比较,纪录汉明距寓。 汉明距离最小的就是最可能的发送序列。 》如果L很大,这种方法根本不能考虑。 计算量指数增长
苯办法 所有可能的发送结果有32种 收端用所有5比特组合进行编码,将结 果同接收序列比较,纪录汉明距离。 汉明距离最小的就是最可能的发送序列。 如果L很大,这种方法根本不能考虑。 计算量指数增长
思考:地图上的最短路径问题 从城市a到城市g的最短距离=? 4.5 5.5 264
思考:地图上的最短路径问题 e 4.5 a b c d f h 5.5 8 4 4 4 6.4 5 7 6 i g 2 4 6 2 2 从城市a到城市g的最短距离=?
搜寻路径 》从口到d有许多的路,群举搜索不是办法 不过 到达g的前一站必然通过h、e、i 如果知到了到达h、e、i的最短路径,则原 问题易解。 问题求从a出发,到e、h、i最短路径和原 问题相同,只是地图变小了一些。 再往前推一站,地图更小
搜寻路径 从a到d有许多的路,群举搜索不是办法 不过 到达g的前一站必然通过h、e、i。 如果知到了到达h、e、i的最短路径,则原 问题易解。 问题求从a出发,到e、h、i最短路径和原 问题相同,只是地图变小了一些。 再往前推一站,地图更小
每一种发送序列都是格图上的一条路径, 从0状态出发,最后到达0状态 0 01 11100010100000
每一种发送序列都是格图上的一条路径,它 从0状态出发,最后到达0状态 00 00 10 11 00 00 01 10 10 01 11 11 00 00 01 10 10 01 11 00 00 01 00 11 10 01 10 00 10 01 11 10 00 10 10 00 00
发送序列与接收序列的距离就是汉明距离, 它等于各支路距离之和 11100010100000 1110110011 0011 2 (00 00 0 总距离是5 10
发送序列与接收序列的距离就是汉明距离, 它等于各支路距离之和 00 00 10 11 00 00 01 10 10 01 11 11 00 00 01 10 10 01 11 00 00 01 00 11 10 01 11 00 10 01 0 0 2 1 0 0 2 总距离是5 11 10 11 00 11 00 11 11 10 00 10 10 00 00
为了寻找最短路径,我们从第一站出发 1110110011 0011 10)/00
为了寻找最短路径,我们从第一站出发 00 00 10 11 00 00 01 10 10 01 11 11 00 00 01 10 10 01 11 00 00 01 00 11 10 01 11 00 10 01 0 2 11 10 11 00 11 00 11
第二站 1110110011 0011 10 10 00 累积距离
第二站 00 00 10 11 00 00 01 10 10 01 11 11 00 00 01 10 10 01 11 00 00 01 10 01 11 00 10 01 0 2 11 00 1 1 0 2 2 3 3 0 累积距离 11 10 11 00 11 00 11
第三站 11101100110011 2 10 2 01
第三站 00 10 00 00 01 10 10 01 11 00 00 01 10 10 01 11 00 00 01 10 01 11 10 01 0 2 11 1 00 1 0 2 2 3 0 2 0 0 2 5 1 1 11 11 1 1 3 4 3 4 00 11 10 11 00 11 00 11
第三站:保留到达各状态最短的路径 11101100110011 10 2 01
第三站:保留到达各状态最短的路径 00 10 00 00 01 10 10 01 11 00 00 01 10 10 01 11 00 00 01 10 01 11 10 01 0 2 11 1 00 1 0 2 2 3 1 0 2 0 0 2 5 1 1 11 11 1 1 3 4 3 4 00 11 10 11 00 11 00 11