On noncoherent sequence detection of coded QAM

New noncoherent sequence detection algorithms for combined demodulation and decoding of coded linear modulations transmitted over additive white Gaussian noise channels are presented. These schemes may be based on the Viterbi algorithm and have a performance which approaches that of coherent detection for increasing complexity. The tradeoff between complexity and performance is simply controlled by a parameter referred to as implicit phase memory and the number of trellis states     

Noncoherent sequence detection

New noncoherent sequence detection algorithms for combined demodulation and decoding of coded linear modulations transmitted over additive white Gaussian noise channels, possibly affected by intersymbol interference, are presented. Optimal sequence detection in the presence of a random rotation of the signal phase, assumed to be constant during the entire transmission, requires a receiver complexity exponentially increasing with the duration of the transmission. Based on proper approximations, simple suboptimal detection schemes based on the Viterbi algorithm are presented, whose performance approaches that of coherent detection. In a companion paper by Colavolpe and Raheli (see ibid., vol.47, no.9, p.1303-7, 1999), noncoherent sequence detection is extended to continuous phase modulations. In the proposed schemes, the tradeoff between complexity and performance is simply controlled by a parameter, referred to as implicit phase memory, and the number of states of a trellis diagram. Besides being realizable, these schemes have the convenient feature of allowing us to remove the constant phase assumption and encompass time-varying phase models. The proposed schemes compare favorably with other solutions previously proposed in the technical literature     

Soft-Output BEAST Decoding With Application to Product Codes

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 approximate a posteriori probabilities (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.      

Soft-Output Decoding of Rotationally Invariant Codes Over Channels With Phase Noise

We consider rotationally invariant (RI) trellis-coded modulations (TCMs) transmitted over channels affected by phase noise. To describe the main ideas of this paper, we first concentrate, as a case study, on the simplest RI scheme, namely the differentially encoded M-ary phase-shift keying (M-PSK) signal. For this problem, we use the framework based on factor graphs (FGs) and the sum-product algorithm (SPA), to derive the exact maximum a posteriori (MAP) symbol detection algorithm. By analyzing its properties, we demonstrate that it can be implemented by a forward-backward estimator of the phase probability density function, followed by a symbol-by-symbol completion to produce the a posteriori probabilities of the information symbols. To practically implement the forward-backward phase estimator, we propose a couple of schemes with different complexity. The resulting algorithms exhibit an excellent performance and, in one case, only a limited complexity increases with respect to the algorithm that perfectly knows the channel phase. The properties of the optimal decoder and the proposed practical decoding schemes are then extended to the case of a generic RI code. The proposed soft-output algorithms can also be used in iterative decoding schemes for concatenated codes employing RI inner components. Among them, in the numerical results, we consider repeat-accumulate (RA) codes and other serially concatenated schemes recently proposed in the technical literature.     

Extrinsic information in iterative decoding: a unified view

We address the use of the extrinsic information generated by each component decoder in an iterative decoding process. The BJCR algorithm proposed by Bahl et al. (1974) and the soft-output Viterbi algorithm (SOVA) are considered as component decoders. In both cases, we consider, in a unified view, various feedback schemes which use the extrinsic information in different fashions. Numerical results for a classical rate-1/2 turbo code and a serially concatenated code transmitted over a memoryless additive white Gaussian noise (AWGN) channel are provided. The performance of the considered schemes leads to interesting remarks about the nature of the extrinsic information     

An efficient decoding algorithm for block turbo codes

An efficient soft-input soft-output iterative decoding algorithm for block turbo codes (BTCs) is proposed. The proposed algorithm utilizes Kaneko's (1994) decoding algorithm for soft-input hard-output decoding. These hard outputs are converted to soft-decisions using reliability calculations. Three different schemes for reliability calculations incorporating different levels of approximation are suggested. The algorithm proposed here presents a major advantage over existing decoding algorithms for BTCs by providing ample flexibility in terms of performance-complexity tradeoff. This makes the algorithm well suited for wireless multimedia applications. The algorithm can be used for optimal as well as suboptimal decoding. The suboptimal versions of the algorithm can be developed by changing a single parameter (the number of error patterns to be generated). For any performance, the computational complexity of the proposed algorithm is less than the computational complexity of similar existing algorithms. Simulation results for the decoding algorithm for different two-dimensional BTCs over an additive white Gaussian noise channel are shown. A performance comparison of the proposed algorithm with similar existing algorithms is also presented     

Complexity Reduction in SISO Decoding of Block Codes

SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP) algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN) channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme and of the conventional SOVA.     

Adaptive Iterative Detectors for Phase-Uncertain Channels via Variational Bounding

The problem of iterative detection/decoding of data symbols transmitted over an additive white Gaussian noise (AWGN) channel in the presence of phase uncertainty is addressed in this paper. By modelling the phase uncertainty either as an unknown deterministic variable/process or random variable/ process with a known a priori probability density function, a number of non-Bayesian and Bayesian detection algorithms with various amount of suboptimality have been proposed in the literature to solve the problem. In this paper, a new set of suboptimal iterative detection algorithms is obtained by utilizing the variational bounding technique. Especially, applying the generic variational Bayesian (VB) framework, efficient iterative joint estimation and detection/decoding schemes are derived for the constant phase model as well as for the dynamic phase model. In addition, the relation of the VB-based approach to the optimal noncoherent receiver as well as to the classical approach via the expectation-maximization (EM) algorithm is provided. Performance of the proposed detectors in the presence of a strong dynamic phase noise is compared to the performance of the existing detectors. Furthermore, an incremental scheduling of the VB (or EM) algorithm is shown to reduce the overall complexity of the receiver.     

High rate concatenated coding systems using bandwidth efficienttrellis inner codes

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved     

A 40 Mb/s soft-output Viterbi decoder

Soft-output decoding has evolved as a key technology for new error correction approaches with unprecedented performance as well as for improvement of well established transmission techniques. In this paper, we present a high-speed VLSI implementation of the soft-output Viterbi algorithm, a low complexity soft-output algorithm, for a 16-state convolutional code. The 43 mm² standard cell chip achieves a simulated throughput of 40 Mb/s, while tested samples achieved a throughput of 50 Mb/s. The chip is roughly twice as big as a 16-state Viterbi decoder without soft outputs. It is thus shown with the design that transmission schemes using soft-output decoding can be considered practical even at very high throughput. Since such decoding systems are more complex to design than hard output systems, special emphasis is placed on the employed design methodology     

Noncoherent iterative decoding of spectrally efficient coded modulations

In this paper, we consider possible solutions for noncoherent decoding of concatenated codes with spectrally efficient modulations. Two main classes of schemes are considered. A first class is obtained by concatenating parallel coding schemes with differential encoding. A second class considers serially concatenated coding structures and possible schemes derived from turbo trellis coded modulation (t-tcm), which do not employ differential encoding. In the first case, at the receiver side we consider separate detection and decoding, while in the second case we consider joint detection and decoding. The major problem connected with such an iterative decoding procedure is that taking into account an augmented channel memory leads to an intolerable trellis size, and hence to an impractical decoding complexity. Reduced-complexity techniques suited to iterative decoding become fundamental, and we consider a recently proposed state-reduction technique. This way, the performance of a coherent receiver is approached, by keeping the number of receiver states fixed.     

Noncoherent block-coded MPSK

For coherent detection, block-coded modulation is a bandwidth efficient scheme. In this paper, we propose theorems about the error performance of block-coded modulation using M-ary phase-shift keying (MPSK) for noncoherent detection. Based on these theorems, we propose a novel block-coded modulation scheme for noncoherent detection called noncoherent block-coded MPSK. The proposed scheme provides flexible designs of noncoherent block codes with different code rate, block length and error performance. Good noncoherent block codes can be easily obtained by properly choosing binary linear block codes as the component codes. Moreover, noncoherent block codes of this new scheme can be decoded by multistage decoding, which has the advantage of low complexity and satisfactory error performance. In this paper, two algorithms of multistage decoding for noncoherent detection are proposed as well. The error performance of some designed codes and decoding algorithms is verified by computer simulation.     

Coded continuous phase modulation with low-complexity noncoherentreception

Coded continuous phase modulation based on a feedback-free modulator with noncoherent detection is discussed. Low-complexity receiver processing is achieved by using only two or three linear filters for demodulation and applying noncoherent sequence estimation with reduced-state Viterbi decoding and simple branch metric calculation. Overall, the proposed noncoherent receiver provides significant advantages over previously presented approaches     

Two decoding algorithms for tailbiting codes

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.     

State Transparent Convolutional Codes and Their Novel Maximum-Likelihood Decoding Algorithm

Almost all the probabilistic decoding algorithms known for convolutional codes, perform decoding without prior knowledge of the error locations. Here, we introduce a novel maximum-likelihood decoding algorithm for a new class of convolutional codes named as the state transparent convolutional (STC) codes, which due to their properties error detection and error locating is possible prior to error correction. Hence, their decoding algorithm, termed here as the STC decoder, allows an error correcting algorithm to be applied only to the erroneous portions of the received sequence referred to here as the error spans (ESPs). We further prove that the proposed decoder, which locates the ESPs and applies the Viterbi algorithm (VA) only to these portions, always yields a decoded path in trellis identical to the one generated by the Viterbi decoder (VD). Due to the fact that the STC decoder applies the VA only to the ESPs, hence percentage of the single-stage (per codeword) trellis decoding performed by the STC decoder is considerably less than the VD, which is applied to the entire received sequence and this reduction is overwhelming for the fading channels, where the erroneous codewords are mostly clustered. Furthermore, through applying the VA only to the ESPs, the resulting algorithm can be viewed as a new formulation of the VD for the STC codes that analogous to the block decoding algorithms provides a predecoding error detection and error locating capabilities, while performing less single-stage trellis decoding.     

Noncoherent sequence detection of CPM

Schemes in which noncoherent sequence detection based on the Viterbi algorithm are proposed for linearly modulated signals transmitted over additive white Gaussian noise channels, have recently been proposed by the authors. These schemes are attractive because their performance closely approaches that of coherent receivers with acceptable complexity, and they avoid the drawbacks of phase-locked loops. The authors extend these results to M-ary continuous phase modulation (CPM) signals     

Polynomial-complexity noncoherent symbol-by-symbol detection with application to adaptive iterative decoding of turbo-like codes

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.     

On the equivalence between SOVA and max-log-MAP decodings

It is shown that after a proper simple modification, the soft-output Viterbi algorithm (SOVA) proposed by Hagenauer and Hoeher (1989) becomes equivalent to the max-log-maximum a posteriori (MAP) decoding algorithm. Consequently, this modified SOVA allows to implement the max-log-MAP decoding algorithm by simply adjusting the conventional Viterbi algorithm. Hence, it provides an attractive solution to achieve low-complexity near-optimum soft-input soft-output decoding     

Performance of parallel and serial concatenated codes on fading channels

The performance of parallel and serial concatenated codes on frequency-nonselective fading channels is considered. The analytical average upper bounds of the code performance over Rician channels with independent fading are derived. Furthermore, the log-likelihood ratios and extrinsic information for maximum a posteriori (MAP) probability and soft-output Viterbi algorithm (SOVA) decoding methods on fading channels are developed. The derived upper bounds are evaluated and compared to the simulated bit-error rates over independent fading channels. The performance of parallel and serial codes with MAP and SOVA iterative decoding methods, with and without channel state information, is evaluated by simulation over independent and correlated fading channels. It is shown that, on correlated fading channels, the serial concatenated codes perform better than parallel concatenated codes. Furthermore, it has been demonstrated that the SOVA decoder has almost the same performance as the MAP decoder if ideal channel state information is used on correlated Rayleigh fading channels.