Exact And Approximate Algorithms for ML Decoding on Tail-Biting Trellises

We analyze an algorithm for exact maximum likelihood(ML) decoding on tail-biting trellises and prove that under certain assumptions the complexity of of the exact algorithm is O(S logS), where S is the number of states of the tail-biting trellis. We also propose an approximate variant whose simulated performance is seen to be virtually indistinguishable from that of the exact one at all values of signal to noise ratio. We analyze the approximate algorithm and deduce the conditions under which its output is different from the ML output. We report the results of simulations for the exact and approximate algorithms on tail-biting trellises for the 16 state (24,12) Extended Golay Code, and two rate 1/2 convolutional codes with memory 4 and 6 respectively. An advantage of our algorithms is that they do not suffer from the effects of limit cycles or the presence of pseudo-codewords.