Efficient Convergent Maximum Likelihood Decoding on Tail-Biting Trellises

An algorithm for exact maximum likelihood(ML) decoding on tail-biting trellises is presented, which exhibits very good average case behavior. An approximate variant is proposed, whose simulated performance is observed to be virtually indistinguishable from the exact one at all values of signal to noise ratio, and which effectively performs computations equivalent to at most two rounds on the tail-biting trellis. The approximate algorithm is analyzed, and the conditions under which its output is different from the ML output are deduced. The results of simulations on an AWGN channel for the exact and approximate algorithms on the 16 state tail-biting trellis for the (24,12) Extended Golay Code, and tail-biting trellises for two rate 1/2 convolutional codes with memories of 4 and 6 respectively, are reported. An advantage of our algorithms is that they do not suffer from the effects of limit cycles or the presence of pseudocodewords.