New coding applications are often limited by the huge decoding complexity required by the best possible maximum-likelihood (ML) decoding. Recently designed sub-optimal algorithms reduce the complexity exponent of ML decoding two times along with an arbitrarily small increase in decoding error probability. The project addresses the problem of designing more advanced algorithms that can further reduce the complexity exponent of ML decoding five to seven times. We are going to investigate the following topics. General study of sub-optimal algorithms. The goals are: (a) to obtain the explicit trade-offs between complexity and performance of near-ML decoding, (b) to generalize near-ML decoding for practically important channels, (c) to combine new near-ML decoding techniques with conventional trellis decoding. Design of new algorithms for near-ML decoding. The goals are: (a) to develop new presorting procedures which reduce the complexity exponent of ML decoding up to three times, (b) to design new random-search algorithms which reduce the latter exponent up to five times. Design of cascaded NML decoding algorithms. The goals are: (a) to develop cascaded near-ML decoding for concatenated codes, and to reduce the complexity exponent of ML decoding up to seven times, (b) to apply cascaded design for bursty and fading channels. Real-time software implementation of designed algorithms. The goal is to develop fast software algorithms for codes of lengths 50 to 100 used over the channels with a signal-to-noise ratio of about 1 dB.
