  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.
