基于Viterbi-双向搜索的咬尾码最大似然译码算法

Viterbi-bidirectional Searching Based ML Decoding Algorithm for Tail-biting Codes

传统咬尾码最大似然(ML)译码算法在译码时存在两个问题:复杂度高和消耗存储空间大。针对这两个问题,该文提出了一种基于Viterbi算法和双向搜索算法的最大似然译码算法。新算法利用Viterbi算法得到的幸存路径度量值与最大似然咬尾路径度量值的关系,删除不可能的起始状态及其对应的咬尾格形子图,缩小搜索空间;然后利用双向搜索算法中门限值与最大似然咬尾路径度量值的关系来降低双向搜索算法的复杂度,从而得到一种在咬尾格形图上高效率的最大似然译码算法。新的最大似然译码算法不仅降低了译码复杂度,同时降低了译码器对存储空间的需求。

There exist two problems with the conventional Maximal Likelihood（ML） decoding algorithms： high decoding complexity and large memory space consumption.To solve these problems,a new algorithm that is based on Viterbi and bidirectional searching algorithm is proposed.By comparing the accumulated path metrics of survived paths with the path metric of ML tail-biting path,all of which are obtained in the Viterbi searching phase,the new algorithm deletes impossible starting states and their corresponding sub-tail-biting trellises to reduce the searching space for the second phase.In the second phase,the decoding complexity can be further reduced by comparing the path metric of ML tail-biting path with the threshold used in the bidirectional searching algorithm.Combing the Viterbi algorithm and bidirectional searching algorithm,a new ML decoding algorithm for tail-biting codes,which can be performed on tail-biting trellis with high efficiency,is obtained.The results of experiments show that the new algorithm improves the decoding efficiency and reduces the memory space consumption.