维特比译码介绍

1、1The Viterbi Algorithm刘超杭州电子科技大学通信学院网络通信教研室杭州电子科技大学通信学院刘超2教学内容：卷积码的简要介绍维特比译码的基本原理维特比译码的基本过程教学目标掌握维特比译码的基本原理熟悉用栅格描述维特比译码的过程教学内容与目标杭州电子科技大学通信学院刘超3卷积码编码器卷积码编码器结构框图k=2输出输出1234编码器相关术语(m,k,n)码，约束长度m，每次移位的比特k，码速率Rc=k/n 状态S=(4 3 2 1)，共2km种状态m=2输入输入123n=3杭州电子科技大学通信学院刘超4例例1 (2,1,2)码的状态向量为码的状态向量为S=(21)，共有，共有4种

2、状态种状态S0=(0,0),S1=(0,1),S2=(1,0),S3=(1,1)，如图所示。，如图所示。卷积码的状态转移图与数学方程杭州电子科技大学通信学院刘超5该码的状态转移方程和输出方程分别为该码的状态转移方程和输出方程分别为 1=U U 2=1 V V1=UU +1+2 V V2=UU +2 卷积码的相关数学方程杭州电子科技大学通信学院刘超6卷积码的状态转移图编码器及其对应的状态转移图如下编码器及其对应的状态转移图如下杭州电子科技大学通信学院刘超7卷积码的状态转移图杭州电子科技大学通信学院刘超8卷积码的栅格图卷积码的栅格图(篱笆图篱笆图)状态图不能反映出状态转移与时间的关系状态图不能反映

3、出状态转移与时间的关系栅格图栅格图/篱笆图：篱笆图：将开放型的状态转移图按时间顺序将开放型的状态转移图按时间顺序级联形成一个栅格图。级联形成一个栅格图。编码路径：编码路径：状态序列状态序列在栅格图中形成的一条有向路在栅格图中形成的一条有向路径。径。当有向路径始于全当有向路径始于全“0”状态状态S0，又终于，又终于S0时，表明此时，表明此时编码器又回到全时编码器又回到全“0”状态，状态，卷积码的状态转移图与栅格描述杭州电子科技大学通信学院刘超9红实线红实线表示表示UU=0时输入产生的转移分支时输入产生的转移分支;黄虚线黄虚线表示表示UU=1时输入产生的转移分支时输入产生的转移分支;转移分支上数字

4、表示输出的编码比特转移分支上数字表示输出的编码比特V V1和和V V2。卷积码的状态转移的栅格描述杭州电子科技大学通信学院刘超10卷积码的栅格描述杭州电子科技大学通信学院刘超11最大似然译码最大似然译码/最小距离译码最小距离译码待编码的信息序列待编码的信息序列MM：MM=MM0, MM1, MML1；编码器输入序列的总长度：编码器输入序列的总长度：k(L+m)；编码器输出的码序列编码器输出的码序列C C：C C=C C0, C C1,C CL1，其中，其中每个子码每个子码C Ci含有含有n个比特；个比特；经离散无记忆信道经离散无记忆信道(DMC)传输后，传输后，译码器接收的序列译码器接收的序列

5、 R R：R R=R R0, R R1,R RL1；对于对于DMC信道：信道：码序列码序列 C C 的的路径度量路径度量 MM(R R/C C)：计算第：计算第 l 时刻到达状态时刻到达状态 i 的最的最大似然路径的相似度大似然路径的相似度log p(R R/C C)；子码子码 C Ci 度量度量MM(R Ri/C Ci) ：计算第：计算第 l 时刻接收子码时刻接收子码 R Ri 相对于各码相对于各码字的相似度字的相似度 log p(R Ri/C Ci)，也称为，也称为分支度量分支度量。1log(R /C)log(R /C )L miiipp杭州电子科技大学通信学院刘超12最大似然译码最大似然

6、译码/最小距离译码最小距离译码译码器接收到译码器接收到 R R 序列后，按最大似然法序列后，按最大似然法则力图寻找编码器在篱笆图上原来走过的则力图寻找编码器在篱笆图上原来走过的路径，也就是寻找具有最大度量的路径；路径，也就是寻找具有最大度量的路径；对对BSC信道，就是寻找与信道，就是寻找与 R R 有最小汉明有最小汉明距离的路径，即计算和寻找距离的路径，即计算和寻找 mind(R R, C Cj)，j=1,2,2Lk 。注：二进制对称信道注：二进制对称信道BSC（Binary Symmetry Channel）杭州电子科技大学通信学院刘超13最大似然译码最大似然译码/最小距离译码最小距离译码最

7、大似然译码方法只是提供了一个译码准则，最大似然译码方法只是提供了一个译码准则，实现起来尚有一定困难。因为它是考虑了长实现起来尚有一定困难。因为它是考虑了长度为度为 (L+m)n 的接收序列来译码的，这样的的接收序列来译码的，这样的序列可能有序列可能有 2Lk 条；条；若实际接收序列中，若实际接收序列中，L=50，k=2，则可能的，则可能的路径有路径有 2100 条。译码器每接收一个序列条。译码器每接收一个序列 R R，就要计算就要计算 1030 个似然函数才能做出译码判决。个似然函数才能做出译码判决。若若 kL 再大一些，译码器按最大似然译码准则再大一些，译码器按最大似然译码准则译码将是很困难

8、的。译码将是很困难的。杭州电子科技大学通信学院刘超14维特比译码工作原理维特比译码工作原理维特比提出了一种算法：维特比提出了一种算法：译码器不是在篱笆图上一次就计算和比译码器不是在篱笆图上一次就计算和比较较 2Lk 条路径，而是接收一段，就计算、比较一段，从而在每个状条路径，而是接收一段，就计算、比较一段，从而在每个状态时，选择进入该状态的最可能的分支。态时，选择进入该状态的最可能的分支。维特比译码的基本思想：维特比译码的基本思想：将接收序列将接收序列 R R 与篱笆图上的路径逐分与篱笆图上的路径逐分支地比较，比较的长度一般取支地比较，比较的长度一般取 (56)mn，然后留下与，然后留下与 R

9、 R 距离最小的距离最小的路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径路径，称为幸存路径，而去掉其余可能的路径，并将这些幸存路径逐分支地延长并存储起来。逐分支地延长并存储起来。幸存路径的数目等于状态数：幸存路径的数目等于状态数：2km 以以 (2,1,2) 卷积码为例说明维特比译码的一般卷积码为例说明维特比译码的一般过程：过程：设发送序列设发送序列 C C 为全为全0；接收序列接收序列 R R=10,00,01,00,00,00,00, 维特比译码的基本原理杭州电子科技大学通信学院刘超15假设译码器的初始状态为全假设译码器的初始状态为全0；第第0个时刻：个时刻：接收序列的第接收序

10、列的第0个分支个分支 R R0=10 进入译码器。进入译码器。从从 S0 状态有两个分支，它们是状态有两个分支，它们是 00 和和 11，R R0与这两个分支与这两个分支比较，比较的结果和到达的状态如表比较，比较的结果和到达的状态如表1 所示：所示：每个状态每个状态/节点都有两个存储器：节点都有两个存储器：路径存储器：存储该状态的部分路径；路径存储器：存储该状态的部分路径；路径值存储器：存储达到该状态的部分路径值路径值存储器：存储达到该状态的部分路径值 (累加距累加距离离)。 维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州电子科技大学通信学院刘超16第

11、一个时刻：第一个时刻：进入译码器的接收码组进入译码器的接收码组 R R1=00 和此时刻和此时刻出发出发的的四条分支四条分支比较，比较结果和达到状态如表比较，比较结果和达到状态如表2所示：所示：从第一个时刻到第二个时刻：从第一个时刻到第二个时刻：共有四条路径，到达共有四条路径，到达S0, S1, S2和和S3。在第二个时刻以前译码器不做任何选择和判决。在第二个时刻以前译码器不做任何选择和判决。每个状态的路径存储器每个状态的路径存储器存储下此时刻的幸存路径：存储下此时刻的幸存路径：0000,0011,1110,1101；每个状态的路径值存储器每个状态的路径值存储器存储了此时刻到达该状态的幸存存储

12、了此时刻到达该状态的幸存路径累加值路径累加值 (累加距离累加距离)。维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州电子科技大学通信学院刘超17维特比译码的基本原理杭州电子科技大学通信学院刘超18从第二个时刻起：从第二个时刻起：第二个接收码组第二个接收码组 R R2=01 进入译码器，从进入译码器，从篱笆图篱笆图上可见，从第二个时刻到第三个时刻，进入每个状态上可见，从第二个时刻到第三个时刻，进入每个状态的分支有两个（或者说在第三个时刻，进入每个状态的路径的分支有两个（或者说在第三个时刻，进入每个状态的路径有两条）。译码器将接收码组有两条）。译码器将接收码

13、组 R R2 与进入每个状态的两个分支与进入每个状态的两个分支进行比较和判决，选择一个累加距离（部分路径值）最小的进行比较和判决，选择一个累加距离（部分路径值）最小的路径作为进入该状态的幸存路径。这样的幸存路径共四条，路径作为进入该状态的幸存路径。这样的幸存路径共四条，比较和判决的过程如下：比较和判决的过程如下： 维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,杭州电子科技大学通信学院刘超19经过比较后选择：经过比较后选择：部分路径部分路径 000000为到达为到达 S0 状态的幸存路径；状态的幸存路径；部分路径部分路径 000011为到达为到达 S1 状态

14、的幸存路径；状态的幸存路径；部分路径部分路径 110101为到达为到达 S2 状态的幸存路径；状态的幸存路径；部分路径部分路径 001101为到达为到达 S3 状态的幸存路径。状态的幸存路径。按照上述方法，接收序列的诸码组依次进入译码器，每个时按照上述方法，接收序列的诸码组依次进入译码器，每个时刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累刻进入一个码组，沿着篱笆图对每个状态按部分路径值（累加距离）的大小，选择一条幸存路径。在每个状态上进行判加距离）的大小，选择一条幸存路径。在每个状态上进行判决时，可能出现进入这一状态的两条路径的距离值相同，这决时，可能出现进入这一状态的两条路径的距离值

15、相同，这时可以任选其一，因为对以后的判决而言，无论选择那一条时可以任选其一，因为对以后的判决而言，无论选择那一条路径，累加距离是相同的。路径，累加距离是相同的。维特比译码的基本原理杭州电子科技大学通信学院刘超20对本例而言，按上述算法进行到对本例而言，按上述算法进行到第十一个第十一个分支分支后，四条路径后，四条路径的前面分支都合并在一起。所以，只要译码深度足够，就可的前面分支都合并在一起。所以，只要译码深度足够，就可达到较低的错误概率。一般，约为达到较低的错误概率。一般，约为 (56)mn，所以，维特比译，所以，维特比译码的延时可达码的延时可达 (56)m 个单位时刻（每个单位时刻为个单位时刻

16、（每个单位时刻为 n 个码元个码元长度）就可以对第长度）就可以对第0个接收码组的信息元进行判决。依此类推，个接收码组的信息元进行判决。依此类推，对接收序列中的诸码组进行译码。对接收序列中的诸码组进行译码。维特比译码的一次运算：维特比译码的一次运算：计算每个输入分支的度量值（分支距离、累加距离）；计算每个输入分支的度量值（分支距离、累加距离）；比较各部分路径的度量值，选择一条作为幸存路径。比较各部分路径的度量值，选择一条作为幸存路径。篱笆图中共有篱笆图中共有 2km 个状态，因此，维特比译码的计算量与编码存个状态，因此，维特比译码的计算量与编码存储储 m 成指数关系变化，所以采用维特比算法译码的

17、卷积码，其成指数关系变化，所以采用维特比算法译码的卷积码，其 m 不能选的太大。不能选的太大。 维特比译码的基本原理杭州电子科技大学通信学院刘超21 维特比译码的基本原理杭州电子科技大学通信学院刘超22维特比译码的基本原理杭州电子科技大学通信学院刘超23维特比译码的基本原理杭州电子科技大学通信学院刘超24 维特比译码的基本原理杭州电子科技大学通信学院刘超25维特比译码的基本原理杭州电子科技大学通信学院刘超26总结维特比算法的步骤总结维特比算法的步骤在第在第 j(j=m)个时刻以前，译码器计算所有的长为个时刻以前，译码器计算所有的长为 m 个分支的部分个分支的部分路径值，对进入路径值，对进入 2

18、km 个状态的每一条部分路径都保留。个状态的每一条部分路径都保留。第第 m 个时刻开始，对进入每一个状态的部分路径进行计算，这样个时刻开始，对进入每一个状态的部分路径进行计算，这样的路径有的路径有 2k 条，挑选具有最大部分路径值的部分路径为幸存路径，条，挑选具有最大部分路径值的部分路径为幸存路径，删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。删去进入该状态的其它路径，然后，幸存路径向前延长一个分支。重复第二步的计算、比较和判决过程。若输入接收序列长为重复第二步的计算、比较和判决过程。若输入接收序列长为 (L+m)k，其中，后，其中，后 m 段是人为加入的全段是人为加入的全0段，则译码一直进行到段，则译码一直进行到 (L+m) 个时刻为止。个时刻为止。若进入某个状态的部分路径中，有两条的部分路径值相等，则可若进入某个状态的部分路径中，有两条的部分路径值相等，则可