企业官网建设流程全解析

viterbi简介

viterbi译码是基于卷积码网格图的最大似然译码算法。也就是说viterbi算法会根据网格图和输入比特恢复出最大可能的原码，这意味着viterbi可以纠正在信道传输过程中出现的误码。

为了理解viterbi就必须要知道卷积码的网格图，所以我们先来学习卷积码

卷积码原理

卷积码由(n,k,L)表示，其中n为输出长度，k为输入长度，L为约束长度。例如(2,1,3)卷积码,就是将1 (k) 位输入比特，与之前2 (L-1) 位输入比特，经过计算生成2 (n) 位输出比特。这个过程由L-1阶的生成多项式描述。

L也称为记忆深度，这代表卷积码编码过程中要使用 L-1 个寄存器记住输入比特。卷积码的码率为

多项式描述了编码过程中的移位和模2加法。每个模2加法都可以用多项式表示，多项式中0次常数项代表输入，1次项代表经过一次移位，2次项代表经过两次移位，以此类推。

当(2，1，3)使用如下生成多项式时。

即代表第一个输出由输入比特和两个移位寄存器中比特进行模2加法得到，第二个输出由输入比特和经过两次移位的比特模2加法得到

编码器可以表示为

状态转移表

通过循环输入可以得到卷积码的状态转移表

为了建立时间与状态转移的关系，即可形成卷积码的网格图(终于要说到viterbi相关的内容了^_^）

网格图

其中蓝色框是每时刻的寄存器可能的4个状态，T0初始时刻寄存器状态为“00”。红色转移路径表示输入比特为0时情况，绿色转移路径表示输入比特为1。这些线指向下一时刻情况，线上标识了此时的输出比特。由T2时刻到T3时刻时，状态已经被遍历，因此画至T3时刻截至。

每个时刻的每个状态可以转移至种下一时刻的状态，也可由上一时刻的种状态转移而来。观察我们上面画的(2,1,3)网格图，在T2到T3这完全遍历的时刻，T2每个状态都有红绿两条线指向T3，T3每个状态都有来自T2的红绿两条线。这是因为输入比特k为1,只有0,1两种状态。因此每种状态都有2种可能性

viterbi原理

最大似然译码等效与最小距离译码。我们一般使用汉明距离作为判决指标

汉明距离

两个码字之间的差异就是汉明距离,例如0000与0010的汉明距离为1，01110与10010汉明距离为3。

汉明距离是我们用来寻找最大可能的原始比特流的指标，汉明距离越小，可能性就越大。

例如，编码比特流为00，计算T0到T1的两条路径的汉明距离。00和00距离为0，00和11距离为2，那么00就是无误码的信道比特流，00对应的0就是未经卷积码编码的原始比特流

viterbi算法步骤

1）在g = L - 1 个时刻前，计算每个状态的单个路径分支度量

2）第 x -1 个时刻开始时，对进入每个状态的部分路径进行计算，挑选最优路径为幸存路径保留，其余路径删除，然后幸存路径向前延申一个分支

3）重复2），直到计算完全部时刻的幸存路径。若输入比特序列长(x + L -1)k，其中后L - 1为人为加入的全0段，则译码进行至(x + L - 1)k时刻为止。

简单来说，计算指向状态的条路径上的权重，找出其中汉明距离最小一条保留，这就是幸存路径，路径权重就是该节点权重，在计算下一时刻的状态权重时，应继承上一节点的权重。

例如传入11 00 11 10 11

从T0到T1，计算11与00和11的汉明距离，为0和2。T1时刻的“00”和“10”只有1条路径，因此直接保留为幸存路径。在“00”和“10”上方用黑笔标志权重2和0。

从T1到T2，计算00与00、11、10和01的汉明距离，为0，2，1，1。继承上一节点的权重2和0。在T2状态上方标注2(2+0)、4(2+2)、1(0+1)、1(0+1)。

从T2到T3，计算8条路径的汉明距离，继承上一节点，分别标注在状态的上下。比较每个状态的两个权重，保留其中较小的一个，若权重相同可以任选其中一条。小的权重已标上红星。
需要注意的是只能淘汰指向同一个状态的路径，也就是说有种状态就必须要有个幸存路径，这4个幸存路径的优劣，在目前还不能判断。

后续T3到T5不再赘述，每个状态已经保留了最小权重。在全部完成后，T5时刻比较四个状态的权重选出最小的2，这就是最终的幸存路径。
只有到了最终时刻，我们才能完成4条幸存路径的优劣对比。

根据路径上的标识可得出，viterbi算法计算出的最大似然是11 10 11 00 11 。这就说明传入的11 00 11 10 11中有误码，根据红绿线可判断出原始比特流为 10001。

实际工程

智慧的读者应该已经发现了，在上述viterbi算法中必须要计算利用全部的编码比特流，计算出所有幸存路径后才能完成译码开始输出。

在实际工程中，这样的输出延迟是不可接受的。那我们能不能在最终时刻之前完成对幸存路径的优劣判断呢？

答案是否定的，如果一个在Tn-m时刻，条中权重最大的路径，由于没有接收后续的编码比特流，我们不能排除后续的路径权重都是0，导致这个条中权重最大的路径在最终时刻Tn反而变成了权重最小的路径。因此我们必须始终记录并保持条路径。

但是卷积码的记忆长度有限，所以对于约束长度 L 的卷积码，经过约 5L∼10L个长度后，所有幸存路径以极大概率会合并到同一个较早的比特决策。

根据这个特性，我们只需等待5-10L后，在最终时刻之前输出译码了。

作者的话

作者完全是个小白，这篇文章及还不存在的后续都是一边学习，一边写出来的。如果有任何的错误，欢迎各位大佬指正，在这里先谢过各位了。

关于下一篇，应该是写viterbi电路的个个功能模块。