Approximate decoding over tail-biting trellises

Abstract

This thesis proposes and implements soft-decision decoding algorithms on tail-biting trellises. For linear block codes, tail-biting trellises are interesting from a soft-decision decoding view-point, because of their reduced sizes as compared to their conventional counterparts. For convolutional codes, tail-biting trellises provide a technique for termination without incurring the rate loss which occurs with zero-tail termination. Decoding on tail-biting trellises though, is not as straightforward as decoding on conventional trellises, and typically approximate iterative algorithms are used. For maximum-likelihood decoding, these can sometimes fail to terminate, or produce what are termed as pseudocodewords as output instead of codewords. Brute force exact decoding algorithms on tail-biting trellises have a time complexity that is quadratic in the size of the trellis. Since the trellis size itself can be exponential in the code parameters, these algorithms are considered too expensive to be practical. Therefore of interest are non-brute-force exact algorithms as well as approximate algorithms that do not suffer from the drawbacks of iterative algorithms mentioned above. Tail-biting trellises have an interesting algebraic structure. Every linear or group tail-biting trellis corresponds to a coset decomposition of the linear block code with respect to a subgroup. We exploit this structure to design and analyze maximum-likelihood (ML) and maximum a-posteriori probability (MAP) decoding algorithms. We analyze a previously proposed non-brute-force exact ML decoding algorithm over tail-biting trellises based on the A* algorithm. Based on this analysis we propose an approximate variant which performs as well as the exact algorithm at all signal to noise ratios, with a sub-quadratic time complexity in the size of the trellis. An advantage of the approximate variant is that it is guaranteed to terminate. We also analyze the approximate algorithm and deduce the conditions under which its output is different from the ML output. Simulation results verify our theoretical claims. We also propose an approximate MAP decoding algorithm over tail-biting trellises which can be described as a best search algorithm. This is seen to perform as well in terms of bit error rates as the other techniques currently in use, for the codes we have experimented on, and better on the 16 state tail-biting trellis for the well known (24,12) Golay code. Detailed simulation results are reported.