Reduced-Complexity Algorithms for Decoding and Equalization

Finite state machines (FSMs) and detection problems involving them are frequently encountered in digital communication systems for noisy channels. One type of FSM arises naturally in transmission over band-limited frequency-selective channels, when bits are modulated onto complex symbols using memoryless mapper and passed through a finite impulse response (FIR) filter. Another type of FSMs, mapping sequences of information bits into longer sequences of coded bits, are the convolutional codes. The detection problem for FSMs, termed decoding in the context of convolutional codes and equalization for frequency-selective channels, involve either finding the most likely input sequence given noisy observations of the output sequence (hard-output decoding), or determining a posteriori probabilty of individual information bits (soft-output decoding). These problems are commonly solved either running a search algorithm on the tree representation of all FSM sequences or by means of dynamic programming on the trellis representation of the FSM.

This work presents novel approaches to decoding and equalization based on tree search. For decoding of convolutional codes, two novel supercode heuristics are proposed to guide the search procedure, reducing the average number of visited incorrect nodes. For soft-output decoding and equalization, a new approach to the generation of soft output within the M-algorithm-based search is presented. Both techniques, when applied simultaneously, yield a particularly efficient soft output decoder for large-memory convolutional codes. Finally, a short block code is presented, which repeated and concatenated with strong outer convolutional code yields an iteratively-decodable coding scheme with excellent convergence and minimum distance properties. With the help of the proposed soft output decoder for the outer convolutional code, this concatenation has also low decoding complexity.