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次项代表经过两次移位以此类推。当(213)使用如下生成多项式时。即代表第一个输出由输入比特和两个移位寄存器中比特进行模2加法得到第二个输出由输入比特和经过两次移位的比特模2加法得到编码器可以表示为状态转移表通过循环输入可以得到卷积码的状态转移表输入比特寄存器当前状态寄存器下一状态第一位输出第二位输出00000000010011010011001101011001011101100011011011111110为了建立时间与状态转移的关系即可形成卷积码的网格图(终于要说到viterbi相关的内容了^_^网格图其中蓝色框是每时刻的寄存器可能的4个状态T0初始时刻寄存器状态为“00”。红色转移路径表示输入比特为0时情况绿色转移路径表示输入比特为1。这些线指向下一时刻情况线上标识了此时的输出比特。由T2时刻到T3时刻时状态已经被遍历因此画至T3时刻截至。每个时刻的每个状态可以转移至种下一时刻的状态也可由上一时刻的种状态转移而来。观察我们上面画的(2,1,3)网格图在T2到T3这完全遍历的时刻T2每个状态都有红绿两条线指向T3T3每个状态都有来自T2的红绿两条线。这是因为输入比特k为1,只有0,1两种状态。因此每种状态都有2种可能性viterbi原理最大似然译码等效与最小距离译码。我们一般使用汉明距离作为判决指标汉明距离两个码字之间的差异就是汉明距离,例如0000与0010的汉明距离为101110与10010汉明距离为3。汉明距离是我们用来寻找最大可能的原始比特流的指标汉明距离越小可能性就越大。例如编码比特流为00计算T0到T1的两条路径的汉明距离。00和00距离为000和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的汉明距离为0211。继承上一节点的权重2和0。在T2状态上方标注2(20)、4(22)、1(01)、1(01)。从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电路的个个功能模块。
从零实战：基于verilog的viterbi译码实现 （1）原理介绍
发布时间：2026/6/1 6:24:45
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次项代表经过两次移位以此类推。当(213)使用如下生成多项式时。即代表第一个输出由输入比特和两个移位寄存器中比特进行模2加法得到第二个输出由输入比特和经过两次移位的比特模2加法得到编码器可以表示为状态转移表通过循环输入可以得到卷积码的状态转移表输入比特寄存器当前状态寄存器下一状态第一位输出第二位输出00000000010011010011001101011001011101100011011011111110为了建立时间与状态转移的关系即可形成卷积码的网格图(终于要说到viterbi相关的内容了^_^网格图其中蓝色框是每时刻的寄存器可能的4个状态T0初始时刻寄存器状态为“00”。红色转移路径表示输入比特为0时情况绿色转移路径表示输入比特为1。这些线指向下一时刻情况线上标识了此时的输出比特。由T2时刻到T3时刻时状态已经被遍历因此画至T3时刻截至。每个时刻的每个状态可以转移至种下一时刻的状态也可由上一时刻的种状态转移而来。观察我们上面画的(2,1,3)网格图在T2到T3这完全遍历的时刻T2每个状态都有红绿两条线指向T3T3每个状态都有来自T2的红绿两条线。这是因为输入比特k为1,只有0,1两种状态。因此每种状态都有2种可能性viterbi原理最大似然译码等效与最小距离译码。我们一般使用汉明距离作为判决指标汉明距离两个码字之间的差异就是汉明距离,例如0000与0010的汉明距离为101110与10010汉明距离为3。汉明距离是我们用来寻找最大可能的原始比特流的指标汉明距离越小可能性就越大。例如编码比特流为00计算T0到T1的两条路径的汉明距离。00和00距离为000和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的汉明距离为0211。继承上一节点的权重2和0。在T2状态上方标注2(20)、4(22)、1(01)、1(01)。从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电路的个个功能模块。
