List decoding of binary block codes for the additive white Gaussian noise (AWGN) channel is considered. The output of a list decoder is a list of the$L$most likely codewords, that is, the$L$signal points closest to the received signal in the Euclidean-metric sense. A decoding error occurs when the transmitted codeword is not on this list. It is shown that the list error probability is fully described by the so-called list configuration matrix, which is the Gram matrix obtained from the signal vectors forming the list. The worst case list configuration matrix determines the minimum list distance of the code, which is a generalization of the minimum distance to the case of list decoding. Some properties of the list configuration matrix are studied and their connections to the list distance are established. These results are further exploited to obtain a new upper bound on the list error probability, which is tighter than the previously known bounds. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability for a given list. The results are illustrated by examples.

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximatea posterioriprobabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.

This paper investigates the performance of reduced- state trellis-based ISI equalizers, which are based on the so- called Ungerboeck and Forney observation models. Although the two models are equivalent when the Viterbi or BCJR equalizer is employed, their performances differ significantly when using reduced-complexity methods. It is demonstrated that practical equalizers operating on the Forney model outperform those operating on the Ungerboeck model for high signal-to-noise ratios (SNRs), while the situation is reversed for low SNR levels. A novel theoretical reduced-complexity equalization strategy that improves on previous Ungerboeck-based equalizers is proposed.

This paper reviews soft-input soft-output (SISO) algorithms that have been recently proposed as reduced-complexity alternatives to maximumaposteriori(MAP) trellis-based decoding or equalization. The M*-BCJR, LISS, and BEAST algorithms are chosen as representatives of reduced-state trellis- and tree- search procedures. The former two algorithms have been initially developed for intersymbol interference (ISI) equalization, while BEAST is tailored for decoding. All three algorithms are modified for either application and their advantages and shortcomings are studied for each case. Comparisons in terms of performance and complexity are presented.

A new upper bound on the list error probability is presented. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability with respect to a given list. Connections between the list distance and the eigenvalues of the covariance matrix of the code are studied.

The performance and convergence behavior of the iterative schemes for decoding two-dimensional product codes are investigated. The decoding trajectories of the extrinsic and the a posteriori information are used as a main tool for predicting and explaining the behavior of the iterative decoding process. The component-wise optimal BCJR decoder is compared to the suboptimal max-log-MAP decoder and the list-based BEAST-APP decoder in terms of convergence and bit-error-rate performance. The results are illustrated by examples, which show that the BEAST-APP decoder achieves near-BCJR performance with significantly lower complexity.

The BEAST-APP decoding algorithm is a low-complexity bidirectional algorithm that searches code trees to find the list of the most likely codewords, which are used to compute approximate a posteriori probabilities (APPs) of the transmitted symbols. It can be applied to APP-decoding of any linear block code, as well as in iterative structures for decoding concatenated block codes. Previous work has shown that the list size sufficient to achieve the performance of true-APP decoding is very small. This paper aims at providing a theoretical justification for this result. The sufficient list size is estimated first via the minimum list distance - a parameter that is defined and analyzed as a key factor that governs the performance of list-based algorithms. Additionally, statistical properties of the codeword likelihoods are investigated and the typical list structure is presented. Preliminary simulation results for iterative BEAST decoding confirm the list-size estimates obtained from both approaches.

In this work we compare the channel estimation algorithms for use in an iterative CDMA receiver in a block fading environment. The receiver consists of a soft multiuser data estimator, a bank of single user decoders, und a multiuser channel estimator. The multiuser data estimator is implemented as parallel interference canceler with unconditional post-MMSE filtering (PIC-MMSE) and the decoder is a soft-in soft-out MAP decoder. In the channel estimator we make use of dedicated pilot symbols and fed back soft-code symbols which are exploited as additional soft pilot symbols when the iterations proceed. We show that using extrinsic information increases the receiver performance significantly compared to using a posteriori information in the feedback for channel estimation. We introduce a linear MMSE (LMMSE) estimator which takes into account the variances of fed back code symbols and compare it to approximations of the least-squares (ALS) estimator and the linear minimum-mean-square-error (ALMMSE) estimator. Performance results are illustrated in terms of bit error rate (BER) and average normalized square error (ANSE) of the channel estimators. They show that the newly proposed LMMSE algorithm outperforms the ALS and ALMMSE algorithms.

Good approximations of code-symbol a-posteriori probabilities (APPs) are obtained using a list of the most likely codewords, instead of the whole code-book. This list is found by Bidirectional Efficient Algorithm for Searching code Trees (BEAST), whose complexity is shown to be lower than of the known trellis-based algorithms.

In iterative receiver structures, soft information becomes available after the decoding stage. This information is used to enhance the quality of the channel estimates for the next iteration. We derive a generalized estimator based on the linear minimum mean square error (LMMSE) principle for deterministic pilot information combined with soft information. We present the special case of multi-carrier code division multiple access (MC-CDMA) in detail and provide simulation results. The presented channel estimation algorithm can be also applied to direct sequence (DS)-CDMA and multiple-input multiple-output (MIMO) systems.