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

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.