Computing the free distance of turbo codes and seriallyconcatenated codes with interleavers: algorithms and applications

We present a new algorithm for computing the free distance d_free of parallel and serially concatenated codes with interleavers, the parameter that dominates the code performance at very high signal-to-noise ratios (SNRs). The knowledge of d_free allows one to analytically estimate the error floor, which may prevent the use of concatenated codes in applications requiring very low error rates. The algorithm is based on the new notion of constrained subcodes, and permits the computation of large distances for large interleavers without a constraint on the input sequence weight (e.g., up to d_free=40 for a rate-1/3 turbo code with interleaver length N=3568). Applications to practical cases of relevant interest, i.e., (1) the new Consultative Committee for Space Data Systems (CCSDS) standard for deep-space telemetry and (2) the new UMTS/3GPP standard for third-generation personal communications, are presented for the first time. Other related aspects, like a study on the free distance distribution of turbo codes with small/medium interleaver length, and a comparison between parallel and serial concatenation behavior, are also discussed     

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     

Joint design of QC-LDPC codes for coded cooperation system with joint iterative decoding

In this paper, we investigate joint design of quasi-cyclic low-density-parity-check (QC-LDPC) codes for coded cooperation system with joint iterative decoding in the destination. First, QC-LDPC codes based on the base matrix and exponent matrix are introduced, and then we describe two types of girth-4 cycles in QC-LDPC codes employed by the source and relay. In the equivalent parity-check matrix corresponding to the jointly designed QC-LDPC codes employed by the source and relay, all girth-4 cycles including both type I and type II are cancelled. Theoretical analysis and numerical simulations show that the jointly designed QC-LDPC coded cooperation well combines cooperation gain and channel coding gain, and outperforms the coded non-cooperation under the same conditions. Furthermore, the bit error rate performance of the coded cooperation employing jointly designed QC-LDPC codes is better than those of random LDPC codes and separately designed QC-LDPC codes over AWGN channels.     

On multilevel codes and iterative multistage decoding

This paper develops an approach to iterative multistage decoding of multilevel codes. This involves passing reliability information to previous and subsequent decoders instead of only hard decisions to subsequent decoders. The paper also develops an adaptive version of the suboptimal soft output decoding algorithm of Picart and Pyndiah (1996). This adaptive algorithm provides a gain of approximately 0.24 dB at a bit error rate (BER) of 10^-5 after four iterations and approximately 0.43 dB after ten iterations over the algorithm of Picart et al. If the adaptive algorithm is used in conjunction with iterative multistage decoding then a gain of approximately 0.62 dB is obtained at a BER of 10^-5 after four iterations and approximately 0.9 dB after ten iterations over the algorithm of Picart et al     

On the iterative decoding of multilevel codes

Iterative decoding of multilevel coded modulation is discussed. Despite its asymptotic optimality with proper design, the error correcting capability of multilevel codes may not be fully exploited for finite block length with conventional multistage decoding. This fact stems from the suboptimality of multistage decoding giving rise to increased error multiplicity at lower index stages and the associated error propagation to higher stages. Such problems can be overcome in many situations by introducing iterative decoding which often significantly compensates the suboptimality of a staged decoder. The class of multilevel codes achieving practically important bit-error performance near the Shannon limit becomes far wider with iterative decoding     

Turbo-like iterative least-squares decoding of analogue codes

A turbo-like iterative decoding scheme for analogue product codes is described. It is proved that the iterative decoding method is an iterative projection in Euclidean space and converges to the least-squares solution. Using this geometric point of view, any block analogue codes can be decoded by a similar iterative method. The described procedure may serve as a step towards a more intuitive understanding of turbo decoding.     

Concatenated convolutional codes with interleavers

This article presents a tutorial overview of the class of concatenated convolutional codes with interleavers, also known as turbo-like codes. They are powerful codes, formed by a number of encoders connected through interleavers, endowed by a decoding algorithm that splits the decoding burden into separate decoding of each individual code. Refinement of successive estimates of the information sequence is obtained by iterating the procedure of passing from one decoder to the other likelihood information decorrelated by the interleaver action. The key issues of code analysis and design are covered at the level of broad comprehension, without paying attention to analytical details.     

Analysis and design of interleavers for iterative multiuser receivers in coded CDMA systems

We deal with the design of interleavers in a coded code-division multiple-access (CDMA) scenario, where at the receiver an iterative turbo-like structure to perform multiuser detection is employed. The choice of the interleavers affects both the maximum-likelihood (ML) performance and the impact of the suboptimality of the iterative receiver. First, heuristic criteria of goodness for a set of interleavers, each assigned to a given active user, are introduced and motivated. One of these criteria is based on the intersection between the equivalent codes seen after the interleavers for each user pair. The design rules are valid for any kind of channel code. In particular, when the channel code used by every user is a terminated convolutional code, a very simple design rule, in the subset of congruential interleavers, is specified. The suitability of an interleaver set to iterative decoding is also treated. The analysis leads to a design rule which is shown to have great importance on the performance of a turbo-like receiver. Numerical results assess the validity of the derived design rules by showing that, for iterative multiuser receivers and reasonable block lengths, the suitability to iterative decoding is more important than the performance optimization.     

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     

Design of repeat-accumulate codes for iterative detection and decoding

Extrinsic information transfer (EXIT) charts are used to design systematic and nonsystematic repeat-accumulate (RA) codes for iterative detection and decoding. The convergence problems of nonsystematic RA codes are solved by introducing a biregular, or doped, layer of check nodes. As examples, such nonsystematic codes are designed for multi-input/multi-output (MIMO) fading channels and are shown to operate close to capacity.     

Replica horizontal-shuffled iterative decoding of low-density parity-check codes

For practical considerations, it is essential to accelerate the convergence speed of the decoding algorithm used in an iterative decoding system. In this paper, replica versions of horizontal-shuffled decoding algorithms for low-density parity-check (LDPC) codes are proposed to improve the convergence speed of the original versions. The extrinsic information transfer (EXIT) chart technique is extended to the proposed algorithms to predict their convergence behavior. Both EXIT chart analysis and numerical results show that replica plain horizontal-shuffled (RPHS) decoding converges much faster than both plain horizontal-shuffled (PHS) decoding and the standard belief-propagation (BP) decoding. Furthermore, it is also revealed that replica group horizontal-shuffled (RGHS) decoding can increase the parallelism of RPHS decoding as well as preserve its high convergence speed if an equivalence condition is satisfied, and is thus suitable for hardware implementation.     

Convergence analysis on iterative decoding of variable-length codes

The convergence characteristics of iterative decoding of variable length codes are discussed. It is observed that variable-length codes with greater redundancy perform better. This suggests that inserting more redundant information in the source-coded bits would be helpful in enhancing the overall performance when iterative decoding is employed     

乘积码基于相关运算的迭代译码

乘积码是一种能以Turbo码的思想实现译码的级联码，具有一般编码无法达到的纠错能力。本文提出一种新的乘积码迭代译码算法，其核心思想是通过输出软信息与接收软信息进行线性迭加的方式来实现反馈，此时只须提供-1和1组成的软输出矩阵就能获得很高的编码增益，仿真表明，将子译码器译码后的结果再进行一次相关运算作为软输出，译码性能可以得到进一步的提高。     

Turbo codes with modified welch-costas interleavers

An upper bound for the minimum distance of turbo codes with Welch-Costas interleavers is established. This paper also proposes a modified Welch-Costas interleaver for which the obtained minimum distance is larger than the established upper bound. At the cost of a slight increase of memory compared to the classic Welch-Costas interleaver, the minimum distance obtained by the proposed method is comparable to that corresponding to the S-random interleaver.     

Nonlinear space-time block codes designed for iterative decoding

Iterative decoding of space-time block codes (STBCs) and channel codes have shown to achieve very good performance. Using tools such as EXIT charts, the performance can be predicted and also used for design. However almost all work so far has concentrated on linear STBCs. Therefore nonlinear STBCs that are designed to work well with iterative decoding are investigated. It is shown that they can outperform linear STBCs since their characteristics are quite different when supplying a priori information from a channel decoder. Analysis, design rules and simulation results for the nonlinear codes are presented.     

Design of interleavers for turbo codes: iterative interleavergrowth algorithms of polynomial complexity

This paper addresses the problem of designing interleavers for parallel concatenated convolutional codes (PCCCs) tailored to specific constituent codes. We start by establishing the role of the interleaver in the PCCC and the various parameters that influence the performance of the PCCC with a given interleaver. Subsequently, we define a canonical form of the interleaving engine denoted as the finite-state permuter (FSP) and demonstrate the minimal delay property of this canonical form. For any given permutation, we present a procedure for deriving the canonical FSP engine. We address the issue of implementation of the FSP and propose a very simple structure for the FSP. Next, using the structural property of the FSP engine, we develop a systematic iterative technique for construction of interleavers with a complexity that is polynomial in the interleaver size. Subsequently, we develop a cost function that, coupled with the iterative interleaver growth procedure, can be used to design optimized interleavers for PCCCs. We provide examples of application of the interleaver design technique, and compare the designed interleavers with some of the interleavers of comparable size found in the literature     

Combinatorial constructions of low-density parity-check codes for iterative decoding

This paper introduces several new combinatorial constructions of low-density parity-check (LDPC) codes, in contrast to the prevalent practice of using long, random-like codes. The proposed codes are well structured, and unlike random codes can lend themselves to a very low-complexity implementation. Constructions of regular Gallager codes based on cyclic difference families, cycle-invariant difference sets, and affine 1-configurations are introduced. Several constructions of difference families used for code design are presented, as well as bounds on the minimal distance of the codes based on the concept of a generalized Pasch configuration.     

Hybrid hard-decision iterative decoding of regular low-density parity-check codes

Hybrid decoding means to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. In this work, we introduce "time-invariant" hybrid (H/sub TI/) algorithms, and using density evolution show that for regular low-density parity-check (LDPC) codes and binary message-passing algorithms, H/sub TI/ algorithms perform remarkably better than their constituent algorithms. We also show that compared to "switch-type" hybrid (H/sub ST/) algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different iterative decoding algorithms, H/sub TI/ algorithms are far less sensitive to channel conditions and thus can be practically more attractive.     

Time-invariant and switch-type hybrid iterative decoding of low-density parity-check codes

Hybrid decoding is to combine different iterative decoding algorithms with the aim of improving error performance or decoding complexity. This, e.g., can be performed by using a specific blend of different algorithms in every iteration (time-invariant hybrid: H_TI), or by switching between different algorithms throughout the iteration process (switch-type hybrid: H_ST). In this work, we study H_TI and H_ST algorithms both asymptotically, usingdensity-evolution, and at finite block lengths, using simulations, and show that these algorithms perform considerably better than their constituent algorithms. We also investigate the convergence properties of H_TI and H_ST algorithms, under both the assumption of perfect knowledge of the channel, and the lack of it, and show that compared to H_ST algorithms, such as Gallager’s algorithm B, H_TI algorithms are far less sensitive to channel conditions and thus can be practically more attractive.