案例库 · 工程与运营 · 技术决策 · 1967
维特比算法让每部手机都能解码自己的信号
1967年，维特比找到了网格中最可能的路径，这一解码器隐身在几乎每部手机中。
Qualcomm · UCLA
那一手
无线链路上的数字通信是与噪声的搏斗，噪声会破坏天线接收到的比特。显而易见的解决办法是添加纠错码，但解码需要从含噪的接收流中推算出实际发送的消息。
维特比1967年的算法正是做到了这一点。卷积编码器约束发射机在一组有限状态中转移，接收机保持这些状态的网格；每一步只保留进入每个状态的最廉价路径，所以结束时找到的是单一最可能消息，而非逐比特独立选择。
通过使短约束长度码变得实用，该算法让前向纠错足够便宜，得以部署到真实无线电中。它将模糊的“消息是什么”转化为清晰的动态规划搜索，如今用于从背景噪声中分离语音和数据。
为什么管用
- 只保留进入每个状态的最廉价路径使搜索时间与消息长度成线性关系。
- 它从含噪数据中恢复最大似然序列，无需逐比特猜测。
- 卷积码以此方式解码才能获得真正的纠错能力。
值了多少选出最可能的隐藏状态序列聪明
可以搬走什么
当信号太嘈杂难以直接读取时，重构它可能来自的最可能序列；你添加的结构让这种搜索几乎不费力气。
后来呢
维特比算法应用于全球绝大多数手机，以及卫星接收器、磁记录、语音识别和DNA分析中；维特比后来于1985年共同创立了高通，该算法帮助CDMA和数字蜂窝电话变得可行。
资料来源
发现哪里写错了？告诉我们。