This paper presents an improved soft-output trellis/tree M-algorithm (SOTTMA) (Wong and McClane, 2006) for reduced-complexity equalization of a high-order modulated MIMO system undergoing equal-power, Rayleigh frequency-selective fading. This improved version reduces the amount of computation by approximately half through the utilization of a mapping scheme with multi-level bit-mapping properties (de Jong and Willink, 2002). The complexity of the improved SOTTMA no longer increases with the constellation size and therefore can be applied to equalize systems with high- order modulation (such as 64-QAM).

Two reduced-complexity soft-input soft-output trellis decoding techniques are presented in this paper for equalizing single-input single-output intersymbol interference (ISI) channels and multiple-input multiple-output (MIMO) frequency selective fading channels. Given a trellis representing an ISI channel, the soft-output M-algorithm (SOMA) reduces the complexity of equalization by retaining only the best M survivors at each trellis interval. The remaining survivors are discarded. The novelty of the SOMA is the use of discarded paths to obtain soft-information. Through a simple update-and-discard procedure, the SOMA extracts reliable soft-information from discarded paths which enables a large trellis to be successfully decoded with a relatively small value of M. To decode a trellis representing a MIMO frequency selective fading channel, two challenges are faced. Not only that the trellis has a large number of states, the number of branches per trellis interval is also enormous. The soft-output trellis/tree M-algorithm (SOTTMA) expands each trellis interval into a tree-like structure and performs the M-algorithm twice: once at each trellis interval to reduce the number of states and the other at each tree sub-level to remove unwanted branches. With the proposed technique, high-order trellises with million of branches per interval can be decoded with modest complexity.

This paper presents a reduced-complexity soft-input soft-output trellis/tree multiuser equalizer for an iterative DS-CDMA system undergoing Rayleigh frequency selective fading. The algorithm first expands the equalizer-trellis to an equivalent trellis/tree structure. Then it applies the M-algorithm to the equivalent structure twice, once to reduce the number of states in the trellis and the other to reduce the number of branches emanating from each state. To compute soft-information, the algorithm utilizes not only those fully-extended paths reaching the end of the trellis but also paths that are traversed and discarded in the pruned trellis. Through a simple update-and-discard procedure, reliable soft-information is extracted from discarded paths which enables an extremely large trellis to be successfully decoded with modest complexity. BER performance is presented for a convolutional-coded DS-CDMA system employing random spreading sequences. Our results demonstrate that the proposed algorithm is capable of achieving single-user performance with a much reduced complexity. The proposed algorithm can also be applied to reduce the complexity of multiuser detection where the transmission channel is frequency flat. Single-user performance can also be achieved with the proposed technique.

This paper presents a reduced-complexity soft- output trellis/tree multiuser equalizer for an iterative DS-CDMA system undergoing Rayleigh frequency selective fading. The algorithm first expands the equalizer-trellis to an equivalent trellis/tree structure. Then it applies the M-algorithm to the equivalent structure twice, once to reduce the number of states in the trellis, and the other to reduce the number of branches emanating from each state. To compute soft-information, the algorithm utilizes not only those fully-extended paths reaching the end of the trellis, but also paths that are traversed and discarded in the pruned trellis. We show a simple and effective method of using these discarded paths without having to store them. BER performance is presented for convolutional-coded CDMA system employing random spreading sequences. Our results demonstrate that the proposed algorithm is capable of achieving single-user performance with a much reduced complexity.

This paper presents a reduced-complexity soft-output trellis/tree equalizer for a high-order modulated MIMO system undergoing equal-power, Rayleigh frequency-selective fading. The algorithm reduces the complexity of trellis decoding by applying the M-algorithm twice, once to reduce the number of states in the trellis, and the other to reduce the number of tree branches emanating from each state. For soft-information, the algorithm utilizes not only those fully-extended paths reaching the end of the trellis, but also paths that are traversed and discarded in the pruned trellis. Our results demonstrated that the proposed algorithm is capable of achieving near-optimal performance with a much reduced complexity.

A low-complexity space-time turbo equalization algorithm, the soft-output M-algorithm (SOMA), is proposed for frequency-selective time-varying MIMO channels. The SOMA is a soft-output version of the M-algorithm known in sequential decoding. It reduces the complexity of trellis-decoding by retaining only M states per trellis depth. For the log-likelihood ratio computation, the algorithm includes not only survivor paths that reach the end of the trellis but paths that are traversed and discarded. The complexity of the SOMA is independent of the trellis size and increases linearly with M. The algorithm is evaluated in a convolutional-coded system that employs transmit-diversity. Simulation results show a reduction from 4096 states to 96 states with negligible performance loss is possible using the SOMA-equalizer for a 4-tap, equal-power, Rayleigh channel. For a version of a 4-tap, EDGE-like channel, 64 states are sufficient.

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.

A novel coding and turbo equalization scheme for sparse multipath channels is presented in this paper. A burst-error-correcting convolutional code, which coding and interleaving via a sparse encoder and a convolutional interleaver, is selected as the channel code. A previously-proposed parallel-trellis framework is adopted for implementing the maximum a posteriori (MAP) equalizer and decoder in the turbo equalizer. Such a system exhibits a similar level of performance to a conventional system using a random-error-correcting convolutional code together with a row /column (R/C) or random block interleaver. Yet, the proposed system has the advantages of low latency and low memory requirements when compared to those conventional systems. This is due to (i) the elimination of the block-type interleavers and deinterleavers and (ii) the parallelism achieved in the turbo equalizer. One disadvantage of the proposed system is to decrease in throughput, as more tail symbols are required for proper termination of all sub-trellises in the decoder. Extension of the proposed system to turbo codes is considered. Also, the effect of prefiltering on a nonminimum-phase, high definition television (HDTV) channel is examined. Results indicate that using the feedforward filter (FFF) of a nonuniformly-spaced decision feedback equalizer (NU-DFE) performs almost as good as using one with a large number of uniformly-spaced taps. However, far fewer computations are needed to find the optimum tap values of the sparse prefilter.