Exact And Approximate Algorithms for ML Decoding on Tail-Biting Trellises
Priti Shankar, A.S. Madhu and Aditya Nori
IISc-CSA-TR-2005-3
(March 2005) Available formats: [pdf]
Filed on March 24, 2005
Updated on March 24, 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 \log S)$, 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 pseudocodewords.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2005/3/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]