Bi-directional soft-output M-algorithm for iterative decoding

A method to produce soft-outputs is proposed for the M-algorithm. The soft-output M-algorithm (SOMA) reduces the complexity of trellis decoding by retaining only M states per trellis depth. Its complexity increases with M rather than with the number of states in the trellis. We also propose an improved SOMA that is based on bi-directional decoding. The performance of the SOMA and the bi-directional SOMA (bi-SOMA) are assessed in decoding a turbo code and in turbo equalization. Simulation results show negligible performance loss when a 16-state turbo code is decoded by the SOMA with M = 12. For turbo equalization, near-optimal performance can be achieved by retaining only a small number of equalizer states as long as the. number of states retained by the decoder is sufficiently large. For a BPSK turbo equalization system with 16 states in both trellises, a SOMA-equalizer with M = 4 and a bi-SOMA decoder with M = 8 suffices. For a QPSK system with 256 equalizer states and 16 decoder states, a SOMA-equalizer with M = 16 and a SOMA-decoder with M = 12 suffices.