Viterbi算法解码过程

https://zhuanlan.zhihu.com/p/63087935

[图片上传失败...(image-a8906b-1587025432526)]

<figcaption style="margin-top: 0.66667empadding: 0px 1emfont-size: 0.9emline-height: 1.5text-align: centercolor: rgb(153, 153, 153)">开局一张图，内容全靠编</figcaption>

维特比算法作为HMM，CRF中的经典解码算法。

本文试图用简单的例子+图片来帮助理解该算法。

任务／问题是什么？

给定观察序列 [图片上传失败...(image-b17bc5-1587025432527)]

，每个观察点对应一个标注(或称为state) [图片上传失败...(image-676d8c-1587025432527)]

。

我们的任务是解码（decode）衡森薯x 每个点上所对应的 y 是 y1 , y2 ,还是 y3。

如何解决？

naive：算出每种情况的概率，再取最大值

[图片上传失败...(image-5538f6-1587025432527)]

复杂度为 [图片上传失败...(image-626996-1587025432527)]

，太大了。L为label(或称为state)的个数，N为输入的长度。我们需要维特比算法来简化。

为什么需要维特比算法？

维特比算法通过DP（动态规划）思想，在每个时间点+每个label上储存到该位置的最大概率。复杂度简化为： [图片上传失败...(image-7a1f8e-1587025432527)]

维特比算春嫌法需要什么？

假设我们已经有Transition matrix和Emission matrix

Transition matrix: [图片上传失败...(image-6be6eb-1587025432526)]

, e.g., [图片上传失败...(image-72c382-1587025432526)]

Emission matrix: [图片咐者上传失败...(image-e4f474-1587025432526)]

, e.g., [图片上传失败...(image-aa4c73-1587025432526)]

外加初始每个state的概率 = [图片上传失败...(image-66da6e-1587025432526)]

T1: 用来保存每个时间点上，到每个state的最大概率； [图片上传失败...(image-44068c-1587025432526)]

T2:用来保存这个最大概率是从上一个时间点的哪个state过来的；

[图片上传失败...(image-514cd3-1587025432526)]

初始化：初始概率 x 发射概率

初始化完成

从时间点1到时间点2，

从上一时间点A 到 当前时间点A的概率乘以A观测到2的概率：[图片上传失败...(image-1211c4-1587025432526)]

同理从B到A

同理从C到A

求得最大值并保存到T1，T2

同理求A到B

同理求B到B

同理求C到B

求得最大值并保存

同理求得A，B，C到C

求得最大值并保存

同理求得时间点2到时间点3，ABC到A的最大值并保存。

同理求的ABC到B，最大值并保存。

同理求的ABC到C的最大值并保存。

在最后时间点上，求argmax可得A为最大，放入解码path中。

通过T2可得A是从C过来的，将C放入解码path中。

通过T2可得，C是从A过来的，将A放入解码path中。最后反转可得最终解码path为[A,C,A]。

点个赞把～

Viterbi译码算法是由Viterbi于1967年提出的一种最大似然译码办法，译码器根据接收序列R按最大似然准则力图找出正确的原始码序列。随着大规模集成电路技术的发展，采用Viterbi算法的卷积编码技术已成为广泛应用的纠错方案。Viterbi译码过程可用状态表示。Sj，t和Sj N/2，t表示t时刻的两个状态。在t1时刻，这两个状态值根据路径为0或者1，转移到状态S2j，t1和S2j1，t1。每一种可能的状态转移都根据接收到的有噪声的序列R计算路径度量，然后选择出各个状态的最小度量路径(幸存路径)。Viterbi算春宽法就老肆是通过在状态中寻找最小量路径向前回溯L步，最后得到的即为译码输出。

在卷积码(n，k，m)表示法中，参数k表示每次输入信息码位数，n表示编码的输出卷积码位数，m称为约束长度(一些书中采用k=m1为约束长度，也可称(2，1，2)码网格图，r=k/n称为信息率，即编码效率。侍森轿本文运用的是(2，1，3)码，约速长度为2，状态数为22=－4。

TMS320C6000系列DSPs(数字信号处理器)是TI公司推出的一种并行处理的数字信号处理器，是基于TI的VLIW技术的。本文采用的是TMS320C6211。该处理器的工作频率经过倍频可达到150MHz，每个时钟周期最多可并行执行8条指令，从而可以实现1200MIPS定点运算能力。

---