A Depth-First ML Decoding Algorithm for Tail-Biting Trellises

Tail-biting codes are efficient for short data packets by eliminating the rate loss in conventional known-tail codes. The existing maximum-likelihood (ML) decoding algorithms, such as the Viterbi heuristic ML decoder (VH ML decoder) and the trap detection-based ML decoder (TD-ML decoder), have to visit each state of the tail-biting trellis at least once. The decoding efficiency of these decoding algorithms can be improved further. In this paper, we propose an ML decoder for tail-biting trellises with bounded searches (BSs). We first perform a unidirectional bounded searching algorithm to estimate the lower bound of path metric of tail-biting paths on each sub-tail-biting trellis and exclude impossible candidates of starting states. In the second phase, a bidirectional searching algorithm is applied to find the ML tail-biting (MLTB) path on the survivor sub-tail-biting trellises. The proposed algorithm exhibits lower decoding complexity floor than other existing algorithms on tail-biting trellis. Simulation results for the (24, 12, 8) Golay codes and show that, for the proposed ML decoder, the average number of visited states per decoded bit is less than 2, whereas the average number of visited states per decoded bit is more than 12 for the VH ML decoder.