The problem of sequence detection in frequency-nonselective/time-selective fading channels, when channel state information (CSI) is not available at the transmitter and receiver, is considered in this paper. The traditional belief is that exact maximum-likelihood sequence detection (MLSD) of an uncoded sequence over this channel has exponential complexity in the channel coherence time. Thus, for slowly varying channels, i.e., channels having coherence time on the order of the sequence length, the complexity appears to be exponential in the sequence length. In the first part of this work, it is shown that exact MLSD can be computed with only polynomial worst case complexity in the sequence length regardless of the operating signal-to-noise ratio (SNR) for equal-energy signal constellations. By establishing a relationship between the aforementioned complexity and the rank of the correlation matrix of the fading process, an understanding of how complexity of the optimal MLSD receiver varies as the channel dynamics change is provided. In the second part of this paper, the problem of decoding turbo-like codes in frequency-nonselective/time-selective fading channels without receiver CSI is examined. Using arguments similar to the ones used for the MLSD case, it is shown that the exact symbol-by-symbol soft-decision metrics (SbSSDMs) implied by the min-sum algorithm can be evaluated with polynomial worst case complexity in the sequence length regardless of SNR for equal-energy signal constellations. Finally, by simplifying some key steps in the polynomial-complexity algorithm, a family of fast, approximate algorithms is derived, which yield near-optimal performance

The related problems of maximum likelihood sequence detection (MLSD) and symbol-by-symbol soft-decision metric (SbSSDM) generation in complex Gaussian flat-fading channels are considered in this paper. Traditional methods for the exact solution of these problems have exponential complexity with respect to the sequence length. In this paper, it is shown that both these problems can be solved in polynomial complexity with respect to the sequence length. Furthermore, motivated by the polynomial-complexity exact algorithm, an approximate fast algorithm is also derived. Simulation results for a low-density parity-check (LDPC) code transmitted on the aforementioned channel show that the performance of the approximate algorithm is very close to the exact sum-product algorithm.

The problem of generating symbol-by-symbol soft decision metrics (SbSSDMs) in the presence of unknown channel parameters is considered. The motivation for this work lies in its application to iterative decoding of high-performance turbo-like codes, transmitted over channels that introduce unknown parameters in addition to Gaussian noise. Traditional methods for the exact evaluation of SbSSDMs involve exponential complexity in the sequence length. A class of problems is identified for which the SbSSDMs can be exactly evaluated with only polynomial complexity with respect to the sequence length. Utilizing the close connection between symbol-by-symbol and sequence detection, it is also shown that for the aforementioned class of problems, detection of an uncoded data sequence in the presence of unknown parameters can be performed with polynomial complexity. The applicability of this technique is demonstrated by considering the problem of iterative detection of low-density parity-check codes in the presence of unknown and time-varying carrier-phase offset. Finally, based on the proposed exact schemes, an ultra-fast approximate algorithm for performing joint iterative decoding and phase estimation is derived that is well suited for hardware implementation.

Iterative decoding in the presence of unknown channel parameters requires the generation of symbol-by-symbol soft-decision metrics (SbSSDMs), jointly with parameter estimation. Traditional methods for the exact evaluation of these metrics have exponential complexity with the length of the data sequence. In this paper, a class of problems is identified, for which the exact SbSSDMs can be obtained with only polynomial complexity with the data sequence length. The applicability of this technique is demonstrated by considering the problem of iterative detection of low-density parity-check codes in the presence of unknown and time-varying carrier-phase offset.