Exact And Approximate Algorithms for ML Decoding on Tail-Biting Trellises - Shankar, Priti; S, Madhu A.; Nori, Aditya (2005)
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 diﬀerent 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 suﬀer from the eﬀects of limit cycles or the presence of pseudo-codewords.