Design of cyclic shift interleavers for Turbo Codes

In this paper we consider cyclic shift interleavers for turbo coding. The properties of cyclic shift interleavers are discussed and compared with S-random interleavers. It is shown that the cyclic shift interleavers are equivalent or better than the S-random interleavers in the ability to break low weight input patterns. We estimated the performance of turbo codes with cyclic shift interleavers and compared it with the performance of S-random interleavers for varions interleaver sizes. The simulation results show that a turbo code with a cyclic shift interleaver can achieve a better performance than an S-random interleaver if the parameters of the cyclic shift interleaver are chosen properly. In addition, the cyclic interleavers have the advantages of lower design complexity and memory requirements.     

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     

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

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

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     

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     

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     

High performance, high throughput turbo/SOVA decoder design

Two efficient approaches are proposed to improve the performance of soft-output Viterbi (1998) algorithm (SOVA)-based turbo decoders. In the first approach, an easily obtainable variable and a simple mapping function are used to compute a target scaling factor to normalize the extrinsic information output from turbo decoders. An extra coding gain of 0.5 dB can be obtained with additive white Gaussian noise channels. This approach does not introduce extra latency and the hardware overhead is negligible. In the second approach, an adaptive upper bound based on the channel reliability is set for computing the metric difference between competing paths. By combining the two approaches, we show that the new SOVA-based turbo decoders can approach maximum a posteriori probability (MAP)-based turbo decoders within 0.1 dB when the target bit-error rate (BER) is moderately low (e.g., BER<10/sup -4/ for 1/2 rate codes). Following this, practical implementation issues are discussed and finite precision simulation results are provided. An area-efficient parallel decoding architecture is presented in this paper as an effective approach to design high-throughput turbo/SOVA decoders. With the efficient parallel architecture, multiple times throughput of a conventional serial decoder can be obtained by increasing the overall hardware by a small percentage. To resolve the problem of multiple memory accesses per cycle for the efficient parallel architecture, a novel two-level hierarchical interleaver architecture is proposed. Simulation results show that the proposed interleaver architecture performs as well as random interleavers, while requiring much less storage of random patterns.     

Upper bound on the minimum distance of turbo codes

An upper bound on the minimum distance of turbo codes is derived, which depends only on the interleaver length and the component scramblers employed. The derivation of this bound considers exclusively turbo encoder input words of weight 2. The bound does not only hold for a particular interleaver but for all possible interleavers including the best. It is shown that in contrast to general linear binary codes the minimum distance of turbo codes cannot grow stronger than the square root of the block length. This implies that turbo codes are asymptotically bad. A rigorous proof for the bound is provided, which is based on a geometric approach     

A logarithmic upper bound on the minimum distance of turbo codes

We derive new upper bounds on the minimum distance, which turbo codes can maximally attain with the optimum interleaver of a given length. The new bounds grow approximately logarithmically with the interleaver length, and they are tighter than all previously derived bounds for medium-length and long interleavers. An extensive discussion highlights the impacts of the new bounds in the context of interleaver design and provides some new design guidelines.     

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     

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     

确定性交织器的研究

本文分析了交织器在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     

Interleaver properties and their applications to the trelliscomplexity analysis of turbo codes

In this paper, the basic theory of interleavers is revisited in a semi-tutorial manner, and extended to encompass noncausal interleavers. The parameters that characterize the interleaver behavior (like delay, latency, and period) are clearly defined. The input-output interleaver code is introduced and its complexity studied. Connections among various interleaver parameters are explored. The classes of convolutional and block interleavers are considered, and their practical implementation discussed. The trellis complexity of turbo codes is tied to the complexity of the constituent interleaver. A procedure of complexity reduction by coordinate permutation is also presented, together with some examples of its application     

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.     

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.     

WCDMA与cdma2000的Turbo码交织器性能比较

对一种Turbo码交织器性能分析的方法进行了讨论,用这种方法分析比较了WCDMA和cdma2000中Turbo码交织器的性能,并给出迭代译码的计算机仿真结果,以证实这种方法的正确性.此外,仿真结果还证实文献[3]中的评价交织器的方法不一定适合Turbo码交织器.     

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.     

Recent Advances in Turbo Code Design and Theory

The discovery of turbo codes and the subsequent rediscovery of low-density parity-check (LDPC) codes represent major milestones in the field of channel coding. Recent advances in the design and theory of turbo codes and their relationship to LDPC codes are discussed. Several new interleaver designs for turbo codes are presented which illustrate the important role that the interleaver plays in these codes. The relationship between turbo codes and LDPC codes is explored via an explicit formulation of the parity-check matrix of a turbo code, and simulation results are given for sum product decoding of a turbo code.