维特比译码介绍.

1TheViterbiAlgorithm刘超[e-mail]杭州电子科技大学通信学院网络通信教研室杭州电子科技大学通信学院刘超2019/12/172教学内容：卷积码的简要介绍维特比译码的基本原理维特比译码的基本过程教学目标掌握维特比译码的基本原理熟悉用栅格描述维特比译码的过程教学内容与目标杭州电子科技大学通信学院刘超2019/12/173卷积码编码器卷积码编码器结构框图k=2输出σ1σ2σ3σ4编码器相关术语(m,k,n)码，约束长度m，每次移位的比特k，码速率Rc=k/n状态S=(σ4σ3σ2σ1)，共2km种状态m=2输入123n=3杭州电子科技大学通信学院刘超2019/12/174[例1](2,1,2)码的状态向量为S=(σ2σ1)，共有4种状态S0=(0,0),S1=(0,1),S2=(1,0),S3=(1,1)，如图所示。(2,1,2)卷积码编码器框图σ1σ2V2UV1卷积码的状态转移图与数学方程杭州电子科技大学通信学院刘超2019/12/175该码的状态转移方程和输出方程分别为σ1’=Uσ2’=σ1V1=U+σ1+σ2V2=U+σ2卷积码的相关数学方程(2,1,2)卷积码编码器框图σ1σ2V2UV1杭州电子科技大学通信学院刘超2019/12/176卷积码的状态转移图(2,1,2)码状态转移图(闭合型)(01)/(0)=(v1v2)/(u)(01)=S1(00)=S0(10)=S2(11)=S3(11)/(0)(00)/(0)(10)/(0)(00)/(1)(01)/(1)(10)/(1)(11)/(1)编码器及其对应的状态转移图如下σ=σ(t)σ'=σ(t+1)V(l)/U(l)编码器状态转移图(2,1,2)卷积码编码器框图σ1σ2V2UV1杭州电子科技大学通信学院刘超2019/12/177卷积码的状态转移图(2,1,2)码状态转移图(开放型)S1S0S2S3S1'S0'S2'S3'(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)σ=σ(t)σ'=σ(t+1)V(l)/U(l)编码器状态转移图(2,1,2)卷积码编码器框图σ1σ2V2UV1杭州电子科技大学通信学院刘超2019/12/178卷积码的栅格图(篱笆图)状态图不能反映出状态转移与时间的关系栅格图/篱笆图：将开放型的状态转移图按时间顺序级联形成一个栅格图。编码路径：状态序列σ在栅格图中形成的一条有向路径。当有向路径始于全“0”状态S0，又终于S0时，表明此时编码器又回到全“0”状态，卷积码的状态转移图与栅格描述杭州电子科技大学通信学院刘超2019/12/179红实线表示U=0时输入产生的转移分支;黄虚线表示U=1时输入产生的转移分支;转移分支上数字表示输出的编码比特V1和V2。卷积码的状态转移的栅格描述(2,1,2)码篱笆图S1S0S2S3(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)01234567000000000000000000001111111111111111111110101010101010100101010101010101杭州电子科技大学通信学院刘超2019/12/1710图6.4.19(b)(2,1,2)码栅格图及路径S1S0S2S3(00/0,11/1)(10/0,01/1)(11/0,00/1)(01/0,10/1)111001001001011111ABC路径A(S0,S1,S2,S0)消息A(100)输出A(111011)路径B(S0,S1,S2,S1,S3,S2)消息B(10110)输出B(1110000101)路径C(S0,S1,S3,S3,S2,S0)消息C(110100)输出C(1101100111)V(0)V(1)V(2)V(3)V(4)V(5)卷积码的栅格描述杭州电子科技大学通信学院刘超2019/12/1711最大似然译码/最小距离译码待编码的信息序列M：M=[M0,M1,…,ML－1]；编码器输入序列的总长度：k(L+m)；编码器输出的码序列C：C=[C0,C1,…,CL－1]，其中每个子码Ci含有n个比特；经离散无记忆信道(DMC)传输后，译码器接收的序列R：R=[R0,R1,…,RL－1]；对于DMC信道：码序列C的路径度量M(R/C)：计算第l时刻到达状态i的最大似然路径的相似度—logp(R/C)；子码Ci度量M(Ri/Ci)：计算第l时刻接收子码Ri相对于各码字的相似度—logp(Ri/Ci)，也称为分支度量。杭州电子科技大学通信学院刘超2019/12/1712最大似然译码/最小距离译码译码器接收到R序列后，按最大似然法则力图寻找编码器在篱笆图上原来走过的路径，也就是寻找具有最大度量的路径；对BSC信道，就是寻找与R有最小汉明距离的路径，即计算和寻找min[d(R,Cj)]，j=1,2,…,2Lk。注：二进制对称信道BSC（BinarySymmetryChannel）杭州电子科技大学通信学院刘超2019/12/1713最大似然译码/最小距离译码最大似然译码方法只是提供了一个译码准则，实现起来尚有一定困难。因为它是考虑了长度为(L+m)n的接收序列来译码的，这样的序列可能有2Lk条；若实际接收序列中，L=50，k=2，则可能的路径有2100条。译码器每接收一个序列R，就要计算1030个似然函数才能做出译码判决。若kL再大一些，译码器按最大似然译码准则译码将是很困难的。杭州电子科技大学通信学院刘超2019/12/1714维特比译码工作原理维特比提出了一种算法：译码器不是在篱笆图上一次就计算和比较2Lk条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。维特比译码的基本思想：将接收序列R与篱笆图上的路径逐分支地比较，比较的长度一般取(5~6)mn，然后留下与R距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。幸存路径的数目等于状态数：2km以(2,1,2)卷积码为例说明维特比译码的一般过程：设发送序列C为全0；接收序列R=[10,00,01,00,00,00,00,…]维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1715假设译码器的初始状态为全0；第0个时刻：接收序列的第0个分支R0=10进入译码器。从S0状态有两个分支，它们是00和11，R0与这两个分支比较，比较的结果和到达的状态如表1所示：每个状态/节点都有两个存储器：路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值(累加距离)。维特比译码的基本原理表1幸存路径第0分支的距离到达状态001111S0S1接收序列R=[10,00,01,00,00,00,00,…](2,1,2)码栅格图第一步S1S0S2S31110R=杭州电子科技大学通信学院刘超2019/12/1716第一个时刻：进入译码器的接收码组R1=00和此时刻出发的四条分支比较，比较结果和达到状态如表2所示：从第一个时刻到第二个时刻：共有四条路径，到达S0,S1,S2和S3。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器存储了此时刻到达该状态的幸存路径累加值(累加距离)。表2上次距离幸存路径延长分支本分支距离累加距离到达状态1100110011100102111322S0S1S2S3维特比译码的基本原理接收序列R=[10,00,01,00,00,00,00,…]杭州电子科技大学通信学院刘超2019/12/1717维特比译码的基本原理(2,1,2)码栅格图第二步S1S0S2S31113221000R=杭州电子科技大学通信学院刘超2019/12/1718表.3上次距离幸存路径延长分支本分支距离累加距离到达状态1322000000111110110100111001110001101120110222533324S0S1S2S3S0S1S2S3从第二个时刻起：第二个接收码组R2=01进入译码器，从篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组R2与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：维特比译码的基本原理接收序列R=[10,00,01,00,00,00,00,…]杭州电子科技大学通信学院刘超2019/12/1719经过比较后选择：部分路径000000为到达S0状态的幸存路径；部分路径000011为到达S1状态的幸存路径；部分路径110101为到达S2状态的幸存路径；部分路径001101为到达S3状态的幸存路径。按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选择一条幸存路径。在每个状态上进行判决时，可能出现进入这一状态的两条路径的距离值相同，这时可以任选其一，因为对以后的判决而言，无论选择那一条路径，累加距离是相同的。维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1720对本例而言，按上述算法进行到第十一个分支后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为(5~6)mn，所以，维特比译码的延时可达(5~6)m个单位时刻（每个单位时刻为n个码元长度）就可以对第0个接收码组的信息元进行判决。依此类推，对接收序列中的诸码组进行译码。维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。篱笆图中共有2km个状态，因此，维特比译码的计算量与编码存储m成指数关系变化，所以采用维特比算法译码的卷积码，其m不能选的太大。维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1721维特比译码的基本原理(2,1,2)码栅格图第三步S1S0S2S313222(3)3(3)5(2)3(4)R=100001杭州电子科技大学通信学院刘超2019/12/1722(2,1,2)码栅格图第四步S1S0S2S32223R=1000012(4)4(2)3(4)3(4)00(2,1,2)码栅格图第五步S1S0S2S32223R=100001002(5)4(3)3(4)3(4)00维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1723(2,1,2)码栅格图第六步S1S0S2S32333R=10000100002(5)4(3)4(4)4(4)00(2,1,2)码栅格图第七步S1S0S2S32344R=1000010000002(6)4(4)4(5)4(5)00维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1724(2,1,2)码栅格图第八步S1S0S2S32444R=100001000000002(6)4(4)5(5)5(5)00(2,1,2)码栅格图第九步S1S0S2S32455R=10000100000000002(7)4(5)5(6)5(6)00维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1725(2,1,2)码栅格图第十步S1S0S2S32455R=1000010000000000002(7)4(5)5(6)5(6)00(2,1,2)码栅格图第十一步S1S0S2S32455R=100001000000000000002(7)4(5)5(6)5(6)00维特比译码的基本原理杭州电子科技大学通信学院刘超2019/12/1726总结维特比算法的步骤在第j(j=m)个时刻以前，译码器计算所有的长为m个分支的部分路径值，对进入2km个