Dependence of d/sub free/ in MPCCC systems

This letter first investigates the distribution of the free distance, parameter d/sub free/ for multiple parallel concatenated schemes based on random interleavers. The distribution is obtained by computer search for information weight IW=2 error events, which are the most likely events to produce d/sub free/, at least for turbo codes. The dependence upon interleaver length and code memory is also studied. The design of the S-interleaver for turbo codes is shown to depend upon a combination of IW=2 error events (which are dependent on S) and IW=2+2 "crossed" error events (which are independent of S). The limiting value of S (for which the two effects are equal) is calculated for turbo codes and a novel algorithm to increase this limit (and hence, d/sub free/) is presented. The S-random interleaver design is extended to schemes with two interleavers, for which the use of paired S-random interleavers is proposed.     

Multistage recursive interleaver for turbo codes in DS-CDMA mobileradio

A multistage recursive block interleaver (MIL) is proposed for the turbo code internal interleaver. Unlike conventional block interleavers, the MIL repeats permutations of rows and columns in a recursive manner until reaching the final interleaving length. The bit error rate (BER) and frame error rate (FER) performance with turbo coding and MIL under frequency-selective Rayleigh fading are evaluated by computer simulation for direct-sequence code-division multiple-access mobile radio. The performance of rate-1/3 turbo codes with MIL is compared with pseudorandom and S-random interleavers assuming a spreading chip rate of 4.096 Mcps and an information bit rate of 32 kbps. When the interleaving length is 3068 bits, turbo coding with MIL outperforms the pseudorandom interleaver by 0.4 dB at an average BER of 10^-6 on a fading channel using the ITU-R defined Vehicular-B power-delay profile with the maximum Doppler frequency of f_D = 80 Hz. The results also show that turbo coding with MIL provides superior performance to convolutional and Reed-Solomon concatenated coding; the gain over concatenated coding is as much as 0.6 dB     

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     

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     

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     

Weight spectrum evaluation for multi-binary tailbiting turbo codes

In this paper we propose a method for the evaluation of the weight spectrum of parallel concatenated turbo codes with tailbiting (circular) m-ary component codes. Our method is based on a two step evaluation; we search and store a set of error events for the component codes; then, we evaluate the spectrum of the concatenated code with the actual interleaver. When working with different interleavers, the first step is computed only once. We show some examples with rate 6/7 component codes.     

Stream-oriented turbo codes

This work considers the design and performance of a stream-oriented approach to turbo codes which avoids the need for data framing. The stream paradigm applies to both serial and parallel turbo codes using continuous, free-running constituent encoders along with continuous, periodic interleavers. A stream-oriented turbo code based on parallel concatenated convolutional codes (PCCC) is considered and interleaver design criteria are developed for both block and nonblock periodic interleavers. Specifically, several nonblock interleavers, including convolutional interleavers, are considered. Interleaver design rules are verified using simulations where it is shown that nonblock interleavers with small-to-moderate delay and small synchronization ambiguity can outperform block interleavers of comparable delay. For large-delay designs, nonblock interleavers are found which perform within 0.8 dB of the capacity limit with a synchronization ambiguity of N=11     

Optimized prunable single-cycle interleavers for turbo codes

This paper is aimed at the problem of designing optimized interleavers for parallel concatenated convolutional codes (PCCC) that satisfy several requirements simultaneously: 1) designing interleavers tailored to the constituent codes of the PCCC; 2) improving the distance spectra of the resulting turbo codes which dominate their asymptotic performance; 3) constructing optimized interleavers recursively so that they are implicitly prunable; and 4) completely avoiding short permutation cycles in order to reduce the risk of having strong correlations between the extrinsic information during iterative decoding. To this end, we present two theorems that lead to a modification of a previously developed iterative interleaver growth algorithm (IGA) that can be used to design optimized variable-length interleavers, whereby at every length the optimized permutation implemented by the interleaver is a single-cycle permutation. Two more modifications of the IGA are presented to improve the performance of the optimized interleavers at a reduced complexity. The optimization is achieved via constrained minimization of a cost function closely related to the asymptotic bit-error rate or frame-error rate of the code.     

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     

Interleaver design for turbo codes

The performance of a turbo code with short block length depends critically on the interleaver design. There are two major criteria in the design of an interleaver: the distance spectrum of the code and the correlation between the information input data and the soft output of each decoder corresponding to its parity bits. This paper describes a new interleaver design for turbo codes with short block length based on these two criteria. A deterministic interleaver suitable for turbo codes is also described. Simulation results compare the new interleaver design to different existing interleavers     

Zigzag codes and concatenated zigzag codes

This paper introduces a family of error-correcting codes called zigzag codes. A zigzag code is described by a highly structured zigzag graph. Due to the structural properties of the graph, very low-complexity soft-in/soft-out decoding rules can be implemented. We present a decoding rule, based on the Max-Log-APP (MLA) formulation, which requires a total of only 20 addition-equivalent operations per information bit, per iteration. Simulation of a rate-1/2 concatenated zigzag code with four constituent encoders with interleaver length 65 536, yields a bit error rate (BER) of 10^-5 at 0.9 dB and 1.3 dB away from the Shannon limit by optimal (APP) and low-cost suboptimal (MLA) decoders, respectively. A union bound analysis of the bit error probability of the zigzag code is presented. It is shown that the union bounds for these codes can be generated very efficiently. It is also illustrated that, for a fixed interleaver size, the concatenated code has increased code potential as the number of constituent encoders increases. Finally, the analysis shows that zigzag codes with four or more constituent encoders have lower error floors than comparable turbo codes with two constituent encoders     

Multilevel turbo coding with short interleavers

The impact of the interleaver, embedded in the encoder for a parallel concatenated code, called the turbo code, is studied. The known turbo codes consist of long random interleavers, whose purpose is to reduce the value of the error coefficients. It is shown that an increased minimum Hamming distance can be obtained by using a structured interleaver. For low bit-error rates (BERs), we show that the performance of turbo codes with a structured interleaver is better than that obtained with a random interleaver. Another important advantage of the structured interleaver is the short length required, which yields a short decoding delay and reduced decoding complexity (in terms of memory). We also consider the use of turbo codes as component codes in multilevel codes. Powerful coding structures that consist of two component codes are suggested. Computer simulations are performed in order to evaluate the reduction in coding gain due to suboptimal iterative decoding. From the results of these simulations we deduce that the degradation in the performance (due to suboptimal decoding) is very small     

A cost-function based technique for design of good prunable interleavers for turbo codes

This paper addresses the design of semi-random, prunable interleavers for parallel concatenated convolutional codes (PCCC). The proposed technique is iterative and is based on the growth of a smaller interleaver up to the desired length N. The optimization is achieved via a minimization using a cost-function strictly related to both the correlation properties of the extrinsic information and the concept of spread of an interleaver. Performance of the designed interleavers are given in terms of bit error rate (BER) and frame error rate (FER). Comparisons are given with respect to other prunable and ad-hoc interleaver design techniques already proposed in literature. The designed interleavers are prunable and have a behavior very similar to the interleavers designed with techniques which maximize the spread of the permutation.     

Interleaver design for serially concatenated convolutional codes: theory and application

This paper addresses the problem of interleaver design for serially concatenated convolutional codes (SCCCs) tailored to the constituent codes of the SCCC configuration. We present a theoretical framework for interleaver optimization based on a cost function closely tied to the asymptotic bit-error rate (BER) of the block code C/sub s/ resulting from proper termination of the constituent codes in the SCCC code. We define a canonical form of the interleaving engine denoted as the finite state permuter (FSP) and using its structural property, develop a systematic iterative technique for construction of interleavers. The core theoretical results focus on the asymptotic behavior of a class of cost functions and their martingale property, which is then used to develop an order recursive interleaver optimization algorithm. We address the issue of the complexity of the interleaver growth algorithm presented in the paper and demonstrate that it has polynomial complexity. Subsequently, we provide details about the application of the proposed technique and present a modification of the algorithm that employs error pattern feedback for improved performance at a reduced complexity. Sample experimental results are provided for an SCCC code of rate 1/3 and information block length 320 that achieves a minimum distance of d/sub min/=44.     

Design and performance analysis of a new class of rate compatible serially concatenated convolutional codes

In this paper, a novel class of serially concatenated convolutional codes (SCCCs) is addressed. In contrast to standard SCCCs, where high rates are obtained by puncturing the outer code, the heavy puncturing is moved to the inner code, which can be punctured beyond the unitary rate. We derive analytical upper bounds on the error probability of this code structure by considering an equivalent code construction consisting of the parallel concatenation of two codes, and address suitable design guidelines for code optimization. It is shown that the optimal puncturing of the inner code depends on the outer code, i.e., it is interleaver dependent. This dependence cannot be tracked by the analysis for standard SCCCs, which fails in predicting code performance. Based on the considerations arising from the bounds analysis, we construct a family of rate-compatible SCCCs with a high level of flexibility and a good performance over a wide range of code rates, using simple constituent codes. The error rate performance of the proposed codes is found to be better than that of standard SCCCs, especially for high rates, and comparable to the performance of more complex turbo codes.     

Prunable Collision Free Random Interleaver Design

In this article we introduce a new collision free prunable random interleaver. The suggested interleaver is a joint structure involving rectangular and S-random interleaver. It comprises a general model for all kind of collision free prunable random interleavers. In addition, it can be designed for any number of parallel processors and any length of information sequence vector and can be considered also as a template for collision free prunable interleavers. The proposed interleaver can be used with all kind of turbo-like codes. The performance of the proposed interleaver is measured with parallel decodable serially concatenated convolutional codes (PDSCCCs) and compared to the PDSCCCs?? performance with collision full S-random interleaver.     

Turbo码的优选扩散交织器设计

该文提出了Turbo码交织器的一种新的设计方法,适用于任意长度的交织设计,称为优选扩散交织,文中阐述了它的设计原则与步骤,以及对16状态Turbo码交织器的设计分析,并对其性能进行了仿真。     

On the theory and performance of trellis termination methods forturbo codes

The performance of a turbo code can be severely degraded if no trellis termination is employed. This paper investigates the implications of the choice of trellis termination method for turbo codes, and explains the origin of the performance degradation often experienced without trellis termination. An efficient method to derive the distance spectrum of turbo codes for different trellis termination methods is presented. Further, we present interleaver design rules that are tailored to each termination method. Using interleavers designed with these restrictions, we demonstrate that the performance difference between various termination methods is very small, including no trellis termination at all. For example, we demonstrate a turbo code with a 500-bit interleaver that exhibits no sign of an error floor for frame error rates as low as 10^-8, even though no trellis termination is employed     

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     

Design of flexible-length S-random interleaver for turbo codes

We introduce a method for generating a sequence of semi-random interleavers, intended to be optimally stored and employed in a turbo coding system that requires flexibility of the input block (i.e., interleaver) size N. A distinctive feature of this method is seen in the very simple rules for obtaining shorter/longer interleavers by pruning/adding positions to the interleaver currently used in the system. For each N, the obtained bit error rate (BER) is not higher than the BER for ordinary S-random interleaver of the same N. The method always converges and is suitable for obtaining interleavers of large lengths.