Iterative multiuser detection for asynchronous CDMA withconcatenated convolutional coding

We propose iterative multiuser detectors for asynchronous code-division multiple-access with parallel-concatenated convolutional codes (turbo codes) and with serially concatenated convolutional codes (SCCC). At each iteration we update and exchange the extrinsic information from the multiuser detector and channel decoders and regenerate soft information between constituent convolutional decoders. Simulation results show that with the proposed structure, near-single-user performance can be achieved. We also propose two reduced-complexity techniques, i.e., the reduced-state iterative multiuser detector based on the T-MAP algorithm and the iterative interference canceler based on a noise-whitening filter. Simulation results show a small performance degradation for these two techniques, particularly for the T-MAP receiver     

Turbo Product Codes Based on Convolutional Codes

In this article, we introduce a new class of product codes based on convolutional codes, called convolutional product codes. The structure of product codes enables parallel decoding, which can significantly increase decoder speed in practice. The use of convolutional codes in a product code setting makes it possible to use the vast knowledge base for convolutional codes as well as their flexibility in fast parallel decoders. Just as in turbo codes, interleaving turns out to be critical for the performance of convolutional product codes. The practical decoding advantages over serially‐concatenated convolutional codes are emphasized.     

Convergence behavior of iteratively decoded parallel concatenatedcodes

Mutual information transfer characteristics of soft in/soft out decoders are proposed as a tool to better understand the convergence behavior of iterative decoding schemes. The exchange of extrinsic information is visualized as a decoding trajectory in the extrinsic information transfer chart (EXIT chart). This allows the prediction of turbo cliff position and bit error rate after an arbitrary number of iterations. The influence of code memory, code polynomials as well as different constituent codes on the convergence behavior is studied for parallel concatenated codes. A code search based on the EXIT chart technique has been performed yielding new recursive systematic convolutional constituent codes exhibiting turbo cliffs at lower signal-to-noise ratios than attainable by previously known constituent codes     

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes In the low signal-to-noise ratio regime, the performance of concatenated coding schemes is limited by the convergence properties of the iterative decoder. Idealizing the model of iterative decoding by an independence assumption, which represents the case in which the codeword length is infinitely large, leads to analyzable structures from which this performance limit can be predicted. Mutual information-transfer characteristics of the constituent coding schemes comprising convolutional encoders and soft-in/soft-out decoders have been shown to be sufficient to characterize the components within this model. Analyzing serial and parallel concatenations is possible just by these characteristics. In this paper, we extend the method of extrinsic information transfer charts that is limited to the case of a concatenation of two component codes, to the case of multiple turbo codes. Multiple turbo codes are parallel concatenations of three or more constituent codes, which, in general, may not be identical and may not have identical code rates. For the construction of low-rate codes, this concept seems to be very favorable, as power efficiencies close to the Shannon limit can be achieved with reasonable complexity.     

Iterative turbo decoder analysis based on density evolution

We track the density of extrinsic information in iterative turbo decoders by actual density evolution, and also approximate it by symmetric Gaussian density functions. The approximate model is verified by experimental measurements. We view the evolution of these density functions through an iterative decoder as a nonlinear dynamical system with feedback. Iterative decoding of turbo codes and of serially concatenated codes is analyzed by examining whether a signal-to-noise ratio (SNR) for the extrinsic information keeps growing with iterations. We define a “noise figure” for the iterative decoder, such that the turbo decoder will converge to the correct codeword if the noise figure is bounded by a number below zero dB. By decomposing the code's noise figure into individual curves of output SNR versus input SNR corresponding to the individual constituent codes, we gain many new insights into the performance of the iterative decoder for different constituents. Many mysteries of turbo codes are explained based on this analysis. For example, we show why certain codes converge better with iterative decoding than more powerful codes which are only suitable for maximum likelihood decoding. The roles of systematic bits and of recursive convolutional codes as constituents of turbo codes are crystallized. The analysis is generalized to serial concatenations of mixtures of complementary outer and inner constituent codes. Design examples are given to optimize mixture codes to achieve low iterative decoding thresholds on the signal-to-noise ratio of the channel     

Design of parallel concatenated convolutional codes

A parallel concatenated convolutional coding scheme consists of two constituent systematic: convolutional encoders linked by an interleaver. The information bits at the input of the first encoder are scrambled by the interleaver before entering the second encoder. The codewords of the parallel concatenated code consist of the information bits followed by the parity check bits of both encoders. Parallel concatenated codes (turbo codes), decoded through an iterative decoding algorithm of relatively low complexity, have been shown to yield remarkable coding gains close to theoretical limits. We characterize the separate contributions that the interleaver length and constituent codes give to the overall performance of the parallel concatenated code, and present some guidelines for the optimal design of the constituent convolutional codes     

Design and decoding of optimal high-rate convolutional codes

This correspondence deals with the design and decoding of high-rate convolutional codes. After proving that every (n,n-1) convolutional code can be reduced to a structure that concatenates a block encoder associated to the parallel edges with a convolutional encoder defining the trellis section, the results of an exhaustive search for the optimal (n,n-1) convolutional codes is presented through various tables of best high-rate codes. The search is also extended to find the "best" recursive systematic convolutional encoders to be used as component encoders of parallel concatenated "turbo" codes. A decoding algorithm working on the dual code is introduced (in both multiplicative and additive form), by showing that changing in a proper way the representation of the soft information passed between constituent decoders in the iterative decoding process, the soft-input soft-output (SISO) modules of the decoder based on the dual code become equal to those used for the original code. A new technique to terminate the code trellis that significantly reduces the rate loss induced by the addition of terminating bits is described. Finally, an inverse puncturing technique applied to the highest rate "mother" code to yield a sequence of almost optimal codes with decreasing rates is proposed. Simulation results applied to the case of parallel concatenated codes show the significant advantages of the newly found codes in terms of performance and decoding complexity.     

Analysis, design, and iterative decoding of double seriallyconcatenated codes with interleavers

A double serially concatenated code with two interleavers consists of the cascade of an outer encoder, an interleaver permuting the outer codeword bits, a middle encoder, another interleaver permuting the middle codeword bits, and an inner encoder whose input words are the permuted middle codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers, where h>3. We obtain upper bounds to the average maximum likelihood bit-error probability of double serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer, middle, and inner codes that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a low-complexity iterative decoding algorithm. Comparisons with parallel concatenated convolutional codes, known as “turbo codes”, and with the proposed serially concatenated convolutional codes are also presented, showing that in some cases, the new schemes offer better performance     

Serial concatenation of interleaved codes: performance analysis,design, and iterative decoding

A serially concatenated code with interleaver consists of the cascade of an outer encoder, an interleaver permuting the outer codewords bits, and an inner encoder whose input words are the permuted outer codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers. We obtain upper bounds to the average maximum-likelihood bit error probability of serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer and inner encoders that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a new, low-complexity iterative decoding algorithm. Throughout the paper, extensive comparisons with parallel concatenated convolutional codes known as “turbo codes” are performed, showing that the new scheme can offer superior performance     

Unveiling turbo codes: some results on parallel concatenated codingschemes

A parallel concatenated coding scheme consists of two simple constituent systematic encoders linked by an interleaver. The input bits to the first encoder are scrambled by the interleaver before entering the second encoder. The codeword of the parallel concatenated code consists of the input bits to the first encoder followed by the parity check bits of both encoders. This construction can be generalized to any number of constituent codes. Parallel concatenated schemes employing two convolutional codes as constituent codes, in connection with an iterative decoding algorithm of complexity comparable to that of the constituent codes, have been previously shown to yield remarkable coding gains close to theoretical limits. They have been named, and are known as, “turbo codes”. We propose a method to evaluate an upper bound to the bit error probability of a parallel concatenated coding scheme averaged over all interleavers of a given length. The analytical bounding technique is then used to shed some light on some crucial questions, which have been floating around in the communications community since the proposal of turbo codes     

Advanced decoding algorithms for Reed-Solomon/Convolutional concatenated codes

The evaluation of the union bound for theber of Reed-Solomon/Convolutional concatenated codes indicates that their performance might largely improve through the application of soft iterative decoders. This paper presents an iterative decoding algorithm for concatenated codes consisting of an outer Reed-Solomon code, a symbol interleaver and an inner convolutional code. The performance improvement for iterative and non-iterative decoders is evaluated. Existing solutions for the different decoding stages and their interfaces are discussed and their performance is compared. A new procedure is proposed to define the feedback signal from the output of the Reed-Solomon decoder to the input of the convolutional decoder, which captures the reliability information that can be inferred from errors-and-era-suresrs decoders and includes the “state pinning” approach as a particular case. The decoding schemes are applied to the specificdvb-s concatenated code.     

Improved upper bounds on the ML decoding error probability ofparallel and serial concatenated turbo codes via their ensemble distancespectrum

The ensemble performance of parallel and serial concatenated turbo codes is considered, where the ensemble is generated by a uniform choice of the interleaver and of the component codes taken from the set of time-varying recursive systematic convolutional codes. Following the derivation of the input-output weight enumeration functions of the ensembles of random parallel and serial concatenated turbo codes, the tangential sphere upper bound is employed to provide improved upper bounds on the block and bit error probabilities of these ensembles of codes for the binary-input additive white Gaussian noise (AWGN) channel, based on coherent detection of equi-energy antipodal signals and maximum-likelihood decoding. The influence of the interleaver length and the memory length of the component codes is investigated. The improved bounding technique proposed here is compared to the conventional union bound and to a alternative bounding technique by Duman and Salehi (1998) which incorporates modified Gallager bounds. The advantage of the derived bounds is demonstrated for a variety of parallel and serial concatenated coding schemes with either fixed or random recursive systematic convolutional component codes, and it is especially pronounced in the region exceeding the cutoff rate, where the performance of turbo codes is most appealing. These upper bounds are also compared to simulation results of the iterative decoding algorithm     

A primer on turbo code concepts

The goal of this article is to describe the main ideas behind the new class of codes called turbo codes, whose performance in terms of bit error probability has been shown to be very close to the Shannon limit. In this article, the mathematical measures of a posteriori probability and likelihood are reviewed, and the benefits of turbo codes are explained in this context. Since the algorithms needed to implement the decoders have been well documented by others, they are only referenced here, not described in detail. A numerical example, using a simple concatenated coding scheme, provides a vehicle for illustrating how error performance can be improved when soft outputs from the decoders are used in an iterative decoding process     

Near-optimum decoding of product codes: block turbo codes

This paper describes an iterative decoding algorithm for any product code built using linear block codes. It is based on soft-input/soft-output decoders for decoding the component codes so that near-optimum performance is obtained at each iteration. This soft-input/soft-output decoder is a Chase decoder which delivers soft outputs instead of binary decisions. The soft output of the decoder is an estimation of the log-likelihood ratio (LLR) of the binary decisions given by the Chase decoder. The theoretical justifications of this algorithm are developed and the method used for computing the soft output is fully described. The iterative decoding of product codes is also known as the block turbo code (BTC) because the concept is quite similar to turbo codes based on iterative decoding of concatenated recursive convolutional codes. The performance of different Bose-Chaudhuri-Hocquenghem (BCH)-BTCs are given for the Gaussian and the Rayleigh channel. Performance on the Gaussian channel indicates that data transmission at 0.8 dB of Shannon's limit or more than 98% (R/C>0.98) of channel capacity can be achieved with high-code-rate BTC using only four iterations. For the Rayleigh channel, the slope of the bit-error rate (BER) curve is as steep as for the Gaussian channel without using channel state information     

Performance evaluation of superorthogonal turbo codes in AWGN andflat Rayleigh fading channels

Turbo codes are parallel concatenated codes whose performance in the additive white Gaussian noise (AWGN) channel has been shown to be near the theoretical limit. In this paper, we describe a low-rate superorthogonal turbo code that combines the principles of low-rate convolutional coding and that of parallel concatenation. Due to the bandwidth expansion, this code outperforms the ordinary turbo code both in AWGN and especially in fading channels. Thus, superorthogonal turbo codes are suited mainly for spread-spectrum applications. For the purposes of iterative decoding, we concisely describe the connection between the optimal maximum a posteriori symbol estimation and suboptimal soft-output decoding based on sequence estimation. The suboptimal decoder produces outputs that can directly be used as additive metrics at successive decoding iterations, without the need for estimating channel noise variance. Simulation results in AWGN and flat Rayleigh fading channels are also presented, along with analytical upper bounds of bit- and frame-error probabilities     

The Minimum Distance of Turbo-Like Codes

Worst-case upper bounds are derived on the minimum distance of parallel concatenated turbo codes, serially concatenated convolutional codes, repeat-accumulate codes, repeat-convolute codes, and generalizations of these codes obtained by allowing nonlinear and large-memory constituent codes. It is shown that parallel-concatenated turbo codes and repeat-convolute codes with sub-linear memory are asymptotically bad. It is also shown that depth-two serially concatenated codes with constant-memory outer codes and sublinear-memory inner codes are asymptotically bad. Most of these upper bounds hold even when the convolutional encoders are replaced by general finite-state automata encoders. In contrast, it is proven that depth-three serially concatenated codes obtained by concatenating a repetition code with two accumulator codes through random permutations can be asymptotically good.      

Rate-1/2 component codes for nonbinary turbo codes

The iterative decoding structure and component maximum a posteriori decoders used for decoding binary concatenated codes can be extended to the nonbinary domain. This paper considers turbo codes over nonbinary rings, specifically ternary, quaternary, penternary, hexernary, and octernary codes. The best rate-1/2 component codes are determined using a practical search algorithm. The performance of the resulting rate-1/3 turbo codes on an additive white Gaussian noise channel using q-ary phase-shift keying modulation is given.     

Mapping interleaving laws to parallel turbo and LDPC decoder architectures

For high-data-rate applications, the implementation of iterative turbo-like decoders requires the use of parallel architectures posing some collision-free constraints to the reading/writing process from/into the memory. This consideration applies to the two main classes of turbo-like codes, i.e., turbo codes and low-density parity-check (LDPC) codes. Contrary to the literature belief, we prove in this paper that there is no need for an ad hoc code design to meet the parallelism requirement, because, for any code and any choice of the scheduling of the reading/writing operations, there is a suitable mapping of the variables in the memory that grants a collision-free access. The proof is constructive, i.e., it gives an algorithm that obtains the desired collision-free mapping. The algorithm is applied to two simple examples, one for turbo codes and one for LDPC codes, to illustrate how the algorithm works.     

Turbo greedy multiuser detection

Previously, a novel scheme for iterative multiuser detection and turbo decoding was proposed by Damnjanovic and Vojcic (2000, 2001). In this scheme, multiuser detection and single-user turbo decoding are tightly coupled to maximize the overall gain. The extrinsic probabilities for the coded bits of the interfering users, obtained after each turbo decoding iteration, are used as a priori probabilities in the following multiuser iteration and the extrinsic information for the systematic bits of the desired user is used as a priori information in the next single-user turbo decoding iteration. Turbo decoding of parallel concatenated convolutional codes is carried out in parallel fashion. It has been shown that the proposed detector approaches the multiuser capacity limit within 1 dB in the low signal-to-noise ratio region. However, the main drawback of the scheme is its exponential complexity in the number of users, which is due to the complexity of the maximum a posteriori probability (MAP) multiuser detector. In this paper, we show that the complexity of the scheme can be significantly reduced by replacing the (MAP) multiuser detector with an iterative detector derived from the greedy multiuser detector proposed by AlRustamani and Vojcic (2000). In this paper, we demonstrate that, for both the additive white Gaussian noise and the frequency-nonselective Rayleigh fading, the substantial reduction in complexity of the iterative scheme proposed by Damnjanovic and Vojcic when the greedy detector is utilized introduces a slight degradation in performance