Viterbi译码介绍课件【精选】.ppt

Viterbi译码 问题：根据接收序列求解最可能的发送序列 例： 收到序列是： 11 10 11 00 11 00 11 求最可能的发送序列 已知条件： 卷积码的结构G=[7;5] 信息的长度是L=5比特+m=2tail bits 0始0终的路径 苯办法 所有可能的发送结果有32种 收端用所有5比特组合进行编码，将结果同接收序列比较，纪录汉明距离。 汉明距离最小的就是最可能的发送序列。 如果L很大，这种方法根本不能考虑。 计算量指数增长 思考：地图上的最短路径问题 从城市a到城市g的最短距离=？ 搜寻路径 从a到d有许多的路，群举有哪些信誉好的足球投注网站不是办法 不过 到达g的前一站必然通过h、e、i。 如果知到了到达h、e、i的最短路径，则原问题易解。 问题求从a出发，到e、h、i最短路径和原问题相同，只是地图变小了一些。 再往前推一站，地图更小。 每一种发送序列都是格图上的一条路径，它从0状态出发，最后到达0状态 11 10 00 10 10 00 00 发送序列与接收序列的距离就是汉明距离，它等于各支路距离之和 11 10 11 00 11 00 11 11 10 00 10 10 00 00 为了寻找最短路径，我们从第一站出发 11 10 11 00 11 00 11 第二站 11 10 11 00 11 00 11 第三站 11 10 11 00 11 00 11 第三站：保留到达各状态最短的路径 11 10 11 00 11 00 11 第四站 11 10 11 00 11 00 11 第五站 11 10 11 00 11 00 11 第六站 11 10 11 00 11 00 11 第七站 11 10 11 00 11 00 11 最终结果 11 10 11 00 11 00 11 11 10 11 00 11 10 11 Viterbi译码算法概要 一些定义 称距离为度量,累积距离为累积度量,分支的距离为分支度量 称到达每步的累积度量最小的那个路径为幸存路径。 称全局最优路径为最大似然路径 算法： 每一步：用前一状态的幸存路径和本步的分支度量计算出达到每个状态的累积度量，保留幸存路径。 从第一步开始执行此过程，到最后一步得到最优路径。 复杂度 每步需要比较8条路（每状态两条），计算量与步数成正比 苯搜的办法，计算量和步数成指数关系 截短译码 全部译完需要L+m个时钟周期，如果L很大，延迟可能受不了。 注意到译到一定步数时，前面的路已经聚合了，故此可以输出其结果。 如果前面已经聚合，ML路径必然也经过聚合部分 如果没有聚合则以当前看上去最可能的路径（当前累积度量最小的幸存路径），输出前面的比特。 当前看上去最佳的未必全局最优，因此会有少许性能损失 这种方法叫截短译码，它能加快译码速度，并能节约内存。 关于Viterbi译码就是最大似然译码 首先，上述过程表明Viterbi算法得到的是所有可能路径中离接收序列汉明距离最近的。 无论是否为卷积码，对于二进制编码及BSC信道，可以确定，汉明距离最近的就是ML解。 发送码字c=[c1c2c3…cN]，经过误码率为p的BSC信道成为y=[y1y2…yN]，似然概率是 d越小，似然概率越大 软判决译码 无论是否为卷积码，将汉明距改为欧氏距就是软译码 例如偶校验码，发送信息000，编码为0000，BSPK调制后为 x=[-1,-1,-1,-1] 叠加噪声收到 y=[-1.3 -2.3 -0.2 +0.2] 硬判决结果为 0 0 0 1 不能断定发送的是什么 但如果观