第13周2007-5-22Viterbi译码`问题：根据接收序列求解最可能的发送序列`例：`收到序列是：11101100110011`求最可能的发送序列`已知条件：…卷积码的结构G=[7;5]…信息的长度是L=5比特+m=2tailbits…0始0终的路径笨办法`所有可能的发送结果有32种`收端用所有5比特组合进行编码，将结果同接收序列比较，纪录汉明距离。`汉明距离最小的就是最可能的发送序列。`如果L很大，这种方法根本不能考虑。`计算量指数增长思考：地图上的最短路径问题从城市a到城市g的最短距离？=4.5ab45h5.526.4e62c4g7846f4id2搜寻路径`从a到d有许多的路，群举搜索不是办法`不过`到达g的前一站必然通过h、e、i。`如果知到了到达h、e、i的最短路径，则原问题易解。`问题求从a出发，到e、h、i最短路径和原问题相同，只是地图变小了一些。`再往前推一站，地图更小。每一种发送序列都是格图上的一条路径，它从0状态出发，最后到达0状态11100010100000发送序列与接收序列的距离就是汉明距离，它等于各支路距离之和1110001010000011101100110011为了寻找最短路径，我们从第一站出发11101100110011第二站11101100110011第三站11101100110011第三站：保留到达各状态最短的路径11101100110011第四站11101100110011第五站11101100110011第六站11101100110011第七站11101100110011最终结果1110110011001111101100111011Viterbi译码算法概要`一些定义`称距离为度量,累积距离为累积度量,分支的距离为分支度量`称到达每步的累积度量最小的那个路径为幸存路径。`称全局最优路径为最大似然路径`算法：`每一步：用前一状态的幸存路径和本步的分支度量计算出达到每个状态的累积度量，保留幸存路径。`从第一步开始执行此过程，到最后一步得到最优路径。`复杂度`每步需要比较8条路（每状态两条），计算量与步数成正比`苯搜的办法，计算量和步数成指数关系截短译码`全部译完需要L+m个时钟周期，如果L很大，延迟可能受不了。`注意到译到一定步数时，前面的路已经聚合了，故此可以输出其结果。`如果前面已经聚合，ML路径必然也经过聚合部分`如果没有聚合则以当前看上去最可能的路径（当前累积度量最小的幸存路径），输出前面的比特。`当前看上去最佳的未必全局最优，因此会有少许性能损失`这种方法叫截短译码，它能加快译码速度，并能节约内存。关于Viterbi译码就是最大似然译码`首先，上述过程表明Viterbi算法得到的是所有可能路径中离接收序列汉明距离最近的。`无论是否为卷积码，对于二进制编码及BSC信道，可以确定，汉明距离最近的就是ML解。`发送码字c=[c1c2c3…cN]，经过误码率为p的BSC信道成为y=[y1y2…yN]，似然概率是PPyyyccc(yc||)=(12""NN12)N==−Py|1cpdpNd−∏()()iid越小，似i=1d然概率越大⎛⎞pN=−⎜⎟()1p⎝⎠1−p软判决译码`无论是否为卷积码，将汉明距改为欧氏距就是软译码`例如偶校验码，发送信息000，编码为0000，BSPK调制后为x=[−1,−1,−1,−1]`叠加噪声收到y=[−1.3−2.3−0.2+0.2]`硬判决结果为0001不能断定发送的是什么`但如果观察判决前的软值y，则通过比较欧氏距离就能断定发送的是0000。自由距`所有0始0终的非全0路径中，最小的码重称为自由距，记为df。该路径称为自由路径。`自由距表示：从任何一个节点岔开时，所形成的两条路至少差多少距离。`自由距本质上代表卷积码的最小码距。但严格说是不相同的。`码距是对两个等长的码字定义的`卷积码的长度可以任意`任意截取一段有可能截在自由路径中间。`如同分组码的dmin，卷积码的设计应该使df尽可能大。交织`交织就是打散次序，例如原序列：a1a2a3a4a5a6a7a8交织后：a7a1a3a6a2a5a4a8`交织的用途之一是打散突发错（先前所学的编码大部分对突发错无能为力）`发端把多个码字交织后发送`在信道中遇到突发错`收端反交织为多个码字`效果是：发端没有采用交织，但信道错误的次序被打乱了常用的交织