通信工程 / 系统课时

维特比译码

维特比译码

维特比译码用于从卷积码接收序列中寻找最可能的发送序列。核心不是逐个码元独立判决,而是在网格图上累计路径度量、逐状态保留幸存路径,最终选出整体度量最优的那条路径。

学习目标

  • 理解路径度量、分支度量和幸存路径之间的关系。
  • 能根据网格图完成一次基本的维特比译码推演。
  • 理解维特比算法为什么等价于最大似然序列译码。

从逐符号判决转向整条路径判决

卷积码带有记忆,同一个时刻的输出不仅由当前输入决定,还与编码器先前状态有关。因此,接收端不能只看某一组码字“像不像”,而要判断哪一条状态演化路径最可能产生整段观测序列。

设接收序列为 r\mathbf{r},某条候选编码序列为 c\mathbf{c}。在等概率先验下,最大似然译码就是选择使 P(r∣c)P(\mathbf{r}\mid\mathbf{c}) 最大的候选序列。对于常见的独立噪声信道,这个目标可以转化为寻找累计距离最小或累计相关度最大的路径。

维特比译码的网格路径与幸存路径

路径度量怎样累计

维特比算法把“整条序列有多可信”拆成每一步的局部代价。某条分支对应一个可能的状态转移和输出码字,接收值与该码字之间的差异形成分支度量;从起点到当前状态的累计值就是路径度量。

硬判决时常用汉明距离。若某一步期望输出为 00,实际硬判决收到 01,分支度量就是 1。软判决时则通常直接使用接收幅度计算欧氏距离或等价的对数似然度量,因此能保留“这个比特有多可靠”的信息,性能通常优于先硬判决再译码。

若以“距离越小越好”为约定,递推可写成:

Mt(s)=min⁡s′[Mt−1(s′)+γt(s′→s)]M_t(s)=\min_{s'}\left[M_{t-1}(s')+\gamma_t(s'\to s)\right]

其中 Mt(s)M_t(s) 是时刻 tt 到达状态 ss 的最小累计路径度量,γt\gamma_t 是对应分支度量。算法只需要比较所有进入同一状态的候选路径。

幸存路径为什么可以丢弃其他路径

如果两条路径在同一时刻进入同一个状态,那么从这一时刻往后,它们拥有完全相同的未来可选分支。此时累计度量较差的那条路径,无论后面怎么延伸,都不可能反超度量更优且状态相同的路径。

因此,每个状态只保留一条当前最优的“幸存路径”。这一步大幅减少了搜索规模:如果暴力枚举长度为 NN 的二进制输入,需要比较约 2N2^N 条序列;维特比算法只在每个时刻维护有限个状态,复杂度随序列长度近似线性增长。

一次简化推演

假设某时刻有两条路径都进入状态 S1S_1。路径 A 之前的累计度量为 3,本次分支度量为 1;路径 B 之前累计度量为 2,本次分支度量为 3。则新路径度量分别为 4 和 5,因此只保留路径 A。

下一时刻继续对所有状态重复“扩展分支、累加度量、同状态比较、保留幸存者”。到达足够深度后,可以从当前最优状态沿保存的前驱指针向前回溯,得到最可能的输入比特序列。实际译码器通常不会无限保存整条路径,而是设置有限回溯深度,在延迟与误码性能之间折中。

最大似然与维特比算法的关系

维特比算法不是一种近似“猜路径”的启发式方法,而是利用卷积码有限状态结构,对最大似然序列搜索做动态规划。关键条件是路径度量可以按时间累加,并且未来只与当前状态有关。

这也解释了两个易混点:第一,维特比译码优化的是整条序列,不是每个码元单独最优;第二,路径度量的绝对数值通常不重要,真正重要的是同一时刻不同候选路径之间的相对大小。只要分支度量与信道统计相匹配,幸存路径和回溯过程就能把指数级穷举压缩为可实现的序列译码。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

维特比译码

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通