Turbo encoding and decoding of Reed-Solomon codes through binary decomposition and self-concatenation

This paper presents a two-stage turbo-coding scheme for Reed-Solomon (RS) codes through binary decomposition and self-concatenation. In this scheme, the binary image of an RS code over GF(2/sup m/) is first decomposed into a set of binary component codes with relatively small trellis complexities. Then the RS code is formatted as a self-concatenated code with itself as the outer code and the binary component codes as the inner codes in a turbo-coding arrangement. In decoding, the inner codes are decoded with turbo decoding and the outer code is decoded with either an algebraic decoding algorithm or a reliability-based decoding algorithm. The outer and inner decoders interact during each decoding iteration. For RS codes of lengths up to 255, the proposed two-stage coding scheme is practically implementable and provides a significant coding gain over conventional algebraic and reliability-based decoding algorithms.     

The capacity of binary channels that use linear codes and decoders

This paper analyzes the performance of concatenated coding systems operating over the binary-symmetric channel (BSC) by examining the loss of capacity resulting from each of the processing steps. The techniques described in this paper allow the separate evaluation of codes and decoders and thus the identification of where loss of capacity occurs. They are, moreover, very useful for the overall design of a communications system, e.g., for evaluating the benefits of inner decoders that produce side information. The first two sections of this paper provide a general technique (based on the coset weight distribution of a binary linear code) for calculating the composite capacity of the code and a BSC in isolation. The later sections examine the composite capacities of binary linear codes, the BSC, and various decoders. The composite capacities of the (8,4) extended Hamming, (24, 12) extended Golay, and (48, 24) quadratic residue codes appear as examples throughout the paper. The calculations in these examples show that, in a concatenated coding system, having an inner decoder provide more information than the maximum-likelihood (ML) estimate to an outer decoder is not a computationally efficient technique, unless generalized minimum-distance decoding of an outer code is extremely easy. Specifically, for the (8,4) extended Hamming and (24, 12) extended Golay inner codes, the gains from using any inner decoder providing side information, instead of a strictly ML inner decoder, are shown to be no greater than 0.77 and 0.34 dB, respectively, for a BSC crossover probability of 0.1 or less, However, if computationally efficient generalized minimum distance decoders for powerful outer codes, e.g., Reed-Solomon codes, become available, they will allow the use of simple inner codes, since both simple and complex inner codes have very similar capacity losses     

The serial concatenation of rate-1 codes through uniform random interleavers

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

Performance analysis and design criteria for finite-alphabet source-channel codes

Efficient compression of finite-alphabet sources requires variable-length codes (VLCs). However, in the presence of noisy channels, error propagation in the decoding of VLCs severely degrades performance. To address this problem, redundant entropy codes and iterative source-channel decoding have been suggested, but to date, neither performance bounds nor design criteria for the composite system have been available. We calculate performance bounds for the source-channel system by generalizing techniques originally developed for serial concatenated convolutional codes. Using this analysis, we demonstrate the role of a recursive structure for the inner code and the distance properties of the outer code. We use density evolution to study the convergence of our decoders. Finally, we pose the question: Under a fixed rate and complexity constraint, when should we use source-channel decoding (as opposed to separable decoding)? We offer answers in several specific cases. For our analysis and design rules, we use union bounds that are technically valid only above the cutoff rate, but interestingly, the codes designed with union-bound criteria perform well even in low signal-to-noise ratio regions, as shown by our simulations as well as previous works on concatenated codes.     

Differential space-time turbo codes

Serial concatenation of simple error control codes and differential space-time modulation is considered. Decoding is performed iteratively by passing symbol-wise a posteriori probability values between the decoders of the inner space-time code and the outer code. An extrinsic information transfer analysis is used to predict thresholds for outer convolutional codes of various memory orders and a simple outer parity-check code. This parity-check code is well matched to the inner differential space-time code and achieves a bit-error rate (BER) of 10/sup -6/ less than 2 dB from the Shannon capacity of the fast fading multiple antenna channel. The differential space-time code can also be used to generate a priori information in the absence of channel knowledge. This information can be exploited by a channel estimator inserted into the decoding iteration. It is demonstrated that the inner space-time code provides soft training symbols from periodically inserted training symbols. The reliability of these soft training symbols does not depend on the speed of the channel variations, but on the structure of the inner code and the signal-to-noise ratio (SNR). Simulation studies confirm these findings and show that the proposed system with no initial channel knowledge achieves a performance very close to that of the system with perfect channel knowledge.     

Concatenated LDGM codes with single decoder

We propose a design criterion for serially concatenated LDGM codes which require a single decoder and a bit-interleaver. The inner LDGM code can be obtained by expanding the rows of the parity check matrix of the outer LDGM code. The resulting codes can be decoded using only the inner LDGM decoder with slight modification. Simulation results show that the performance of the proposed codes is almost the same as that of serially concatenated LDGM code's using both the inner and the outer decoders.     

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.     

A reduced-complexity sequence detector with soft outputs forpartial-response channels

Data transmission in a binary partial-response channel is often accomplished using a concatenated code consisting of an inner modulation code and an outer error-correcting code (ECC). We consider two inner decoders for such a code, each consisting of a reduced-complexity sequence detector modified to provide an estimate of the reliability of each bit. These reliability values are then used by the outer decoder to achieve improved performance. Although one of these decoders is considerably simpler than the other, their performances were comparable in the cases we considered. Both achieve considerable improvement over a decoder that uses hard-decision decoding of the inner code     

Efficient decoding algorithms for generalized Reed-Muller codes

Previously, a class of generalized Reed-Muller (RM) codes has been suggested for use in orthogonal frequency-division multiplexing. These codes offer error correcting capability combined with substantially reduced peak-to mean power ratios. A number of approaches to decoding these codes have already been developed. Here, we present low complexity, suboptimal alternatives which are inspired by the classical Reed decoding algorithm for binary RM codes. We simulate these new algorithms along with the existing decoding algorithms using additive white Gaussian noise and two-path fading models for a particular choice of code. The simulations show that one of our new algorithms outperforms all existing suboptimal algorithms and offers performance that is within 0.5 dB of maximum-likelihood decoding, yet has complexity comparable to or lower than existing decoding approaches     

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     

Accumulate codes based on 1+D convolutional outer codes

A new construction of good, easily encodable, and soft-decodable codes is proposed in this paper. The construction is based on serially concatenating several simple 1+D convolutional codes as the outer code, and a rate-1 1/(1+D) accumulate code as the inner code. These codes have very low encoding complexity and require only one shift-forward register for each encoding branch. The input-output weight enumerators of these codes are also derived. Divsalar?s simple bound technique is applied to analyze the bit error rate performance, and to assess the minimal required signal-to-noise ratio (SNR) for these codes to achieve reliable communication under AWGN channel. Simulation results show that the proposed codes can provide good performance under iterative decoding.     

Binary multilevel convolutional codes with unequal error protectioncapabilities

Binary multilevel convolutional codes (CCs) with unequal error protection (UEP) capabilities are studied. These codes belong to the class of generalized concatenated (GC) codes. Binary CCs are used as outer codes. Binary linear block codes of short length, and selected subcodes in their two-way subcode partition chain, are used as inner codes. Multistage decodings are presented that use Viterbi decoders operating on trellises with similar structure to that of the constituent binary CCs. Simulation results of example binary two-level CC's are also reported     

Improved space-time codes using serial concatenation

In this letter, a new family of space-time codes is proposed. These codes employ a serially concatenated coding scheme with a standard space-time code as the outer code and a very simple rate-1 recursive code as the inner code. Adding this simple rate-1 recursive inner code does not decrease the bit rate and introduces only negligible complexity increase to the transmitter when compared to cases with standard space-time codes. An interleaver is embedded between the inner coder and the outer coder and the size of this interleaver determines the performance gain. We also provide a relatively low complexity iterative decoding procedure. For applications which can tolerate delay, significant gain can be achieved with the proposed approach     

The capacity of low-density parity-check codes undermessage-passing decoding

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined     

State diagram connectivity and its effects on the decoding ofshift-register-based codes

Coding performance is limited not only by Shannon's (1950) bounds but also by the complexity of decoders. Decoder complexity is in turn governed by the need for the different pieces of the machine to communicate with one another. This paper calculates lower limits on the intra-system information flow for the Viterbi decoding of shift-register-based codes, e.g., convolutional codes. These limits provide practical guidance for the construction of decoders for the current generation of convolutional and trellis codes. In particular, these bounds prove that a very specialized decoder family, called graph partition decoders, have an asymptotically optimum communications growth rate. The techniques used in this paper can, moreover, be applied to the design of new (non-shift-register-based) codes which may possibly circumvent the limits derived in the paper and to the design of parallel processors     

Low-floor decoders for LDPC codes

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code?s Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.     

Code characteristic matching for iterative decoding of serially concatenated codes

The design of serially concatenated codes has yet been dominated by optimizing asymptotic slopes of error probability curves. We propose mutual information transfer characteristics for soft in/soft out decoders to design serially concatenated codes based on the convergence behavior of iterative decoding. The exchange of extrinsic information is visualized as a decoding trajectory in the Extrinsic Information Transfer Chart (exit chart). By finding matching pairs of inner and outer decoder transfer characteristics we are able to construct serially concatenated codes whose iterative decoder converges towards low bit error rate at signal- to- noise ratios close to the theoretical limits.     

A recursive approach to low complexity codes

A method is described for constructing long error-correcting codes from one or more shorter error-correcting codes, referred to as subcodes, and a bipartite graph. A graph is shown which specifies carefully chosen subsets of the digits of the new codes that must be codewords in one of the shorter subcodes. Lower bounds to the rate and the minimum distance of the new code are derived in terms of the parameters of the graph and the subeodes. Both the encoders and decoders proposed are shown to take advantage of the code's explicit decomposition into subcodes to decompose and simplify the associated computational processes. Bounds on the performance of two specific decoding algorithms are established, and the asymptotic growth of the complexity of decoding for two types of codes and decoders is analyzed. The proposed decoders are able to make effective use of probabilistic information supplied by the channel receiver, e.g., reliability information, without greatly increasing the number of computations required. It is shown that choosing a transmission order for the digits that is appropriate for the graph and the subcodes can give the code excellent burst-error correction abilities. The construction principles