维特比译码介绍.ppt

The Viterbi Algorithm刘超杭州电子科技大学通信学院网络通信教研室1.杭州电子科技大学通信学院刘超教学内容：卷积码的简要介绍维特比译码的基本原理维特比译码的基本过程教学目标掌握维特比译码的基本原理熟悉用栅格描述维特比译码的过程教学内容与目标2024/5/7 周二2.杭州电子科技大学通信学院刘超卷积码编码器卷积码编码器结构框图k=2输出出1234编码器相关术语(m,k,n)码，约束长度m，每次移位的比特k，码速率Rc=k/n 状态S=(4 3 2 1)，共2km种状态m=2输入入123n=32024/5/7 周二3.杭州电子科技大学通信学院刘超例例1 (2,1,2)码的状的状态向量向量为S=(21)，共有，共有4种状种状态S0=(0,0),S1=(0,1),S2=(1,0),S3=(1,1)，如，如图所示。所示。卷积码的状态转移图与数学方程2024/5/7 周二4.杭州电子科技大学通信学院刘超该码的状的状态转移方程和移方程和输出方程分出方程分别为 1=U 2=1 V1=U+1+2 V2=U+2 卷积码的相关数学方程2024/5/7 周二5.杭州电子科技大学通信学院刘超卷积码的状态转移图编码器及其器及其对应的状的状态转移移图如下如下2024/5/7 周二6.杭州电子科技大学通信学院刘超卷积码的状态转移图2024/5/7 周二7.杭州电子科技大学通信学院刘超卷卷积码的的栅格格图(篱笆笆图)状状态图不能反映出状不能反映出状态转移与移与时间的关系的关系栅格格图/篱笆笆图：将开放型的状将开放型的状态转移移图按按时间顺序序级联形成一个形成一个栅格格图。编码路径：路径：状状态序列序列在在栅格格图中形成的一条有向路中形成的一条有向路径。径。当有向路径始于全当有向路径始于全“0”状状态S0，又，又终于于S0时，表明，表明此此时编码器又回到全器又回到全“0”状状态，卷积码的状态转移图与栅格描述2024/5/7 周二8.杭州电子科技大学通信学院刘超红实线表示表示U=0时输入入产生的生的转移分支移分支;黄虚黄虚线表示表示U=1时输入入产生的生的转移分支移分支;转移分支上数字表示移分支上数字表示输出的出的编码比特比特V1和和V2。卷积码的状态转移的栅格描述2024/5/7 周二9.杭州电子科技大学通信学院刘超卷积码的栅格描述2024/5/7 周二10.杭州电子科技大学通信学院刘超最大似然最大似然译码/最小距离最小距离译码待待编码的信息序列的信息序列M：M=M0,M1,ML1；编码器器输入序列的入序列的总长度：度：k(L+m)；编码器器输出的出的码序列序列C：C=C0,C1,CL1，其中，其中每个子每个子码Ci含有含有n个比特；个比特；经离散无离散无记忆信道信道(DMC)传输后，后，译码器接收的序列器接收的序列 R：R=R0,R1,RL1；对于于DMC信道：信道：码序列序列 C 的的路径度量路径度量 M(R/C)：计算第算第 l 时刻到达状刻到达状态 i 的最的最大似然路径的相似度大似然路径的相似度log p(R/C)；子子码 Ci 度量度量M(Ri/Ci)：计算第算第 l 时刻接收子刻接收子码 Ri 相相对于各于各码字的相似度字的相似度 log p(Ri/Ci)，也称，也称为分支度量分支度量。2024/5/7 周二11.杭州电子科技大学通信学院刘超最大似然最大似然译码/最小距离最小距离译码译码器接收到器接收到 R 序列后，按最大似然法序列后，按最大似然法则力力图寻找找编码器在器在篱笆笆图上原来走上原来走过的的路径，也就是路径，也就是寻找具有最大度量的路径；找具有最大度量的路径；对BSC信道，就是信道，就是寻找与找与 R 有最小有最小汉明明距离的路径，即距离的路径，即计算和算和寻找找 mind(R,Cj)，j=1,2,2Lk。注：二注：二进制制对称信道称信道BSC（Binary Symmetry Channel）2024/5/7 周二12.杭州电子科技大学通信学院刘超最大似然最大似然译码/最小距离最小距离译码最大似然最大似然译码方法只是提供了一个方法只是提供了一个译码准准则，实现起来尚有一定困起来尚有一定困难。因。因为它是考它是考虑了了长度度为(L+m)n 的接收序列来的接收序列来译码的，的，这样的的序列可能有序列可能有 2Lk 条；条；若若实际接收序列中，接收序列中，L=50，k=2，则可能的可能的路径有路径有 2100 条。条。译码器每接收一个序列器每接收一个序列 R，就要就要计算算 1030 个似然函数才能做出个似然函数才能做出译码判决。判决。若若 kL 再大一些，再大一些，译码器按最大似然器按最大似然译码准准则译码将是很困将是很困难的。的。2024/5/7 周二13.杭州电子科技大学通信学院刘超维特比特比译码工作原理工作原理维特比提出了一种算法：特比提出了一种算法：译码器不是在器不是在篱笆笆图上一次就上一次就计算和比算和比较 2Lk 条路径，而是接收一段，就条路径，而是接收一段，就计算、比算、比较一段，从而在每个状一段，从而在每个状态时，选择进入入该状状态的最可能的分支。的最可能的分支。维特比特比译码的基本思想：的基本思想：将接收序列将接收序列 R 与与篱笆笆图上的路径逐分上的路径逐分支地比支地比较，比，比较的的长度一般取度一般取(56)mn，然后留下与，然后留下与 R 距离最小的距离最小的路径，称路径，称为幸存路径，而去掉其余可能的路径，并将幸存路径，而去掉其余可能的路径，并将这些幸存路径些幸存路径逐分支地延逐分支地延长并存并存储起来。起来。幸存路径的数目等于状幸存路径的数目等于状态数：数：2km 以以(2,1,2)卷卷积码为例例说明明维特比特比译码的一般的一般过程：程：设发送序列送序列 C 为全全0；接收序列接收序列 R=10,00,01,00,00,00,00,维特比译码的基本原理2024/5/7 周二14.杭州电子科技大学通信学院刘超假假设译码器的初始状器的初始状态为全全0；第第0个个时刻：刻：接收序列的第接收序列的第0个分支个分支 R0=10 进入入译码器。器。从从 S0 状状态有两个分支，它有两个分支，它们是是 00 和和 11，R0与与这两个分支两个分支比比较，比，比较的的结果和到达的状果和到达的状态如表如表1 所示：所示：每个状每个状态/节点都有两个存点都有两个存储器：器：路径存路径存储器：存器：存储该状状态的部分路径；的部分路径；路径路径值存存储器：存器：存储达到达到该状状态的部分路径的部分路径值(累加距累加距离离)。维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,2024/5/7 周二15.杭州电子科技大学通信学院刘超第一个第一个时刻：刻：进入入译码器的接收器的接收码组 R1=00 和此和此时刻刻出出发的的四条分支四条分支比比较，比，比较结果和达到状果和达到状态如表如表2所示：所示：从第一个从第一个时刻到第二个刻到第二个时刻：刻：共有四条路径，到达共有四条路径，到达S0,S1,S2和和S3。在第二个。在第二个时刻以前刻以前译码器不做任何器不做任何选择和判决。和判决。每个状每个状态的路径存的路径存储器器存存储下此下此时刻的幸存路径：刻的幸存路径：0000,0011,1110,1101；每个状每个状态的路径的路径值存存储器器存存储了此了此时刻到达刻到达该状状态的幸存的幸存路径累加路径累加值(累加距离累加距离)。维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,2024/5/7 周二16.杭州电子科技大学通信学院刘超维特比译码的基本原理2024/5/7 周二17.杭州电子科技大学通信学院刘超从第二个从第二个时刻起：刻起：第二个接收第二个接收码组 R2=01 进入入译码器，从器，从篱笆笆图上可上可见，从第二个，从第二个时刻到第三个刻到第三个时刻，刻，进入每个状入每个状态的的分支有两个（或者分支有两个（或者说在第三个在第三个时刻，刻，进入每个状入每个状态的路径有两的路径有两条）。条）。译码器将接收器将接收码组 R2 与与进入每个状入每个状态的两个分支的两个分支进行行比比较和判决，和判决，选择一个累加距离（部分路径一个累加距离（部分路径值）最小的路径作）最小的路径作为进入入该状状态的幸存路径。的幸存路径。这样的幸存路径的幸存路径共四条共四条，比，比较和判和判决的决的过程如下：程如下：维特比译码的基本原理接收序列接收序列 R=10,00,01,00,00,00,00,2024/5/7 周二18.杭州电子科技大学通信学院刘超经过比比较后后选择：部分路径部分路径 000000为到达到达 S0 状状态的幸存路径；的幸存路径；部分路径部分路径 000011为到达到达 S1 状状态的幸存路径；的幸存路径；部分路径部分路径 110101为到达到达 S2 状状态的幸存路径；的幸存路径；部分路径部分路径 001101为到达到达 S3 状状态的幸存路径。的幸存路径。按照上述方法，接收序列的按照上述方法，接收序列的诸码组依次依次进入入译码器，每个器，每个时刻刻进入一个入一个码组，沿着，沿着篱笆笆图对每个状每个状态按部分路径按部分路径值（累加距（累加距离）的大小，离）的大小，选择一条幸存路径。在每个状一条幸存路径。在每个状态上上进行判决行判决时，可能出可能出现进入入这一状一状态的两条路径的距离的两条路径的距离值相同，相同，这时可以任可以任选其一，因其一，因为对以后的判决而言，无以后的判决而言，无论选择那一条路径，累加那一条路径，累加距离是相同的。距离是相同的。维特比译码的基本原理2024/5/7 周二19.杭州电子科技大学通信学院刘超对本例而言，按上述算法本例而言，按上述算法进行到行到第十一个第十一个分支分支后，四条路径的后，四条路径的前面分支都合并在一起。所以，只要前面分支都合并在一起。所以，只要译码深度足深度足够，就可达到，就可达到较低的低的错误概率。一般，概率。一般，约为(56)mn，所以，所以，维特比特比译码的的延延时可达可达(56)m 个个单位位时刻（每个刻（每个单位位时刻刻为 n 个个码元元长度）度）就可以就可以对第第0个接收个接收码组的信息元的信息元进行判决。依此行判决。依此类推，推，对接接收序列中的收序列中的诸码组进行行译码。维特比特比译码的一次运算：的一次运算：计算每个算每个输入分支的度量入分支的度量值（分支距离、累加距离）；（分支距离、累加距离）；比比较各部分路径的度量各部分路径的度量值，选择一条作一条作为幸存路径。幸存路径。篱笆笆图中共有中共有 2km 个状个状态，因此，因此，维特比特比译码的的计算量与算量与编码存存储 m 成指数关系成指数关系变化，所以采用化，所以采用维特比算法特比算法译码的卷的卷积码，其，其 m 不不能能选的太大。的太大。维特比译码的基本原理2024/5/7 周二20.杭州电子科技大学通信学院刘超 维特比译码的基本原理2024/5/7 周二21.杭州电子科技大学通信学院刘超维特比译码的基本原理2024/5/7 周二22.杭州电子科技大学通信学院刘超维特比译码的基本原理2024/5/7 周二23.杭州电子科技大学通信学院刘超 维特比译码的基本原理2024/5/7 周二24.杭州电子科技大学通信学院刘超维特比译码的基本原理2024/5/7 周二25.杭州电子科技大学通信学院刘超总结维特比算法的步特比算法的步骤在第在第 j(j=m)个个时刻以前，刻以前，译码器器计算所有的算所有的长为 m 个分支的部分路个分支的部分路径径值，对进入入 2km 个状个状态的每一条部分路径都保留。的每一条部分路径都保留。第第 m 个个时刻开始，刻开始，对进入每一个状入每一个状态的部分路径的部分路径进行行计算，算，这样的路径有的路径有 2k 条，挑条，挑选具有最大部分路径具有最大部分路径值的部分路径的部分路径为幸存路径，幸存路径，删去去进入入该状状态的其它路径，然后，幸存路径向前延的其它路径，然后，幸存路径向前延长一个分支。一个分支。重复第二步的重复第二步的计算、比算、比较和判决和判决过程。若程。若输入接收序列入接收序列长为(L+m)k，其中，后，其中，后 m 段是人段是人为加入的全加入的全0段，段，则译码一直一直进行到行到(L+m)个个时刻刻为止。止。若若进入某个状入某个状态的部分路径中，有两条的部分路径的部分路径中，有两条的部分路径值相等，相等，则可任可任选其一作其一作为幸存路径。幸存路径。维特比译码的基本原理2024/5/7 周二26.杭州电子科技大学通信学院刘超硬判决硬判决译码器：器：以最小距离以最小距离为度量的度量的译码器。它适用于器。它适用于 BSC 信信道。道。软判决判决译码器：器：把信道解把信道解调器器输出的信号出的信号进行行 Q 电平量化，其平量化，其中中 Q 2，然后再，然后再输入到入到维特比特比译码器器进行行译码。充分利用了信道。充分利用了信道输出信号的有关信息，提高出信号的有关信息，提高译码的可靠性。它适用于的可靠性。它适用于DMC信道。信道。软判决判决译码器比硬判决器比硬判决译码器可以改器可以改进码的性能。在一定信道条件的性能。在一定信道条件下，用下，用软判决判决译码器可以器可以获得更小的得更小的误码率；或者在同等率；或者在同等误码率条率条件下，件下，获得得较高的高的编码增益。增益。无无论是采用硬判决是采用硬判决还是是软判决判决译码器，所不同的只是路径量度的器，所不同的只是路径量度的计算方法不同，其算方法不同，其译码的基本的基本过程都是相同的。程都是相同的。注：注：离散无离散无记忆信道信道DMC（Disperse Memory channel）BSC是是DMC的一种特殊情况。的一种特殊情况。软、硬判决维特比译码2024/5/7 周二27.杭州电子科技大学通信学院刘超2024/5/7 周二28.