卷积码编码和译码(十)

最大似然和维特比 Viterbi 译码

维特比译码是最成功的最大似然译码思想的实现. 这个算法中,在每个时刻点逐步系统地缩窄可能译码出来的序列范围. 使用的基本准则有:

1.     错误的发生不是很频繁,即错误概率比较小

2.     两个连续的错误概率远小于单个错误的概率,即错误的分布是比较均匀的

 

维特比译码对给定长度的整个接收序列按照整体来评估. 译码器为每条路径计算度量,基于度量做决策. 跟踪所有的路径,除非有两个路径都转移到同一个状态节点上,具有高度量的路径将被保留,低度量路径将被舍弃. 留下来的路径称为幸存者.

 

N个比特的序列,则所有可能接收到的序列有  种可能, 其中只有  种是合法的. 维特比算法使用最大似然概率的准则, 仅仅比对个幸存路径而不是检查所有的 2^N 种可能.

 

最常用的度量是汉明距度量( Hamming Distance Metric), 刚好是接收到的比特序列和正确序列的点积. 还可以用其他度量,后面我们再讨论.

(英文原文中，此处确实是用 dot product，译者认为这里应该理解为如果相同的话，就加1，如果不同的话，就加 0 ，取相同的比特的个数相加）

 

 

沿着路径,这些度量被累加起来, 有最高度量值的路径将是最后的胜利者.

 

这些描述听起来不是那么容易理解,我们看一个具体的译码例子就很清楚了.

 

我们用维特比译码算法来译码接收到的序列 01 11 01 11 01 01 11.

 

1.     在 t=0, 我们收到比特01. 译码器从状态000开始. 有两个路径可以走, 虽然两个路径的输出都没有完全匹配接收到的01.译码器对两个路径分别计算度量, 然后两个路径都继续往下走,不像顺序译码算法中在每个时刻点都要做决策. 现在,这两个路径的度量都是1, 意味这只有一个比特与正确的码字相匹配.

 

2.     在t=1,译码器从两个状态都继续延展. 路径度量都各自分别计算,用正确的码字与接收到的比特11做比对. 新的度量信息被显示在栅格图的右边一列.

3.     在 t=2, 四个状态继续延展出8个状态,至此所有可能路径都被延展出来. 路径度量也被计算和更新出来,用正确的码字与接收到的比特01做比对,把新计算出来的汉明距加上从 t=1 时刻来的度量,得到新的度量.

 

在t=3,栅格图已经延展出所有的路径了.每个节点都有一个路径进来. 度量值显示在上图的右侧.

在t=4,所有路径继续延展,现在开始有多个路径集中到一个节点上.每个节点有两个路径进来,两个度量值都分别计算出来.根据最大似然准则,在每个节点,我们舍弃地度量值的路径,因为其发生的可能性更低. 在每个节点舍弃路径,有助于减少我们需要检查的路径的数量, 这也是维特比译码的优点.

 

现在,有一个或者多个路径来到同一个节点. 路径度量在右侧列出.在每个节点,我们只保留最高度量的路径, 舍弃其他的(图中红色路径被舍弃). 经过舍弃后的结果如下图, 留下的路径的度量被列在右侧.

 

在t=5,经过舍弃后,如下图所示,我们继续向前延展,计算新的度量.在下一个节点,又有路径集中在一个节点,然后舍弃低度量的路径.

 

在t=6,接收到的比特11. 对所有路径计算度量,舍弃所有小的度量.

 

接下来的一步就是最后一步,如下图.我们选择最高度量的路径作为胜利者. 沿着这个路径回溯,得到正向顺序的各个状态:000,100,010,101,110,011,001,000, 对应输入的比特为 1011 000.

 

 

栅格的长度是 4 + m 比特.理想情况下,应该等于发送消息的长度.但是,使用截断操作, 存储容量的需求可以降低,因为译码不用等到所有传输的序列都收完才开始. 典型的截断长度是128比特,或者是5到7倍的约束长度.

 

维特比译码是非常重要的,因为也被用于分组码的译码. 这种栅格译码也被用于Trellis-Coded  Modulation(TCM).