Performance of Möbius Interleavers for Turbo Codes

In this paper, we study the minimum free distance and error performance of turbo encoders with Möbius interleavers. In order to be capable of estimating the minimum free distance of these interleavers using binary-fixed point (BFP) algorithm, new deterministic interleavers called “truncated Möbius interleavers” are defined and constructed. It is shown how the shifted cycles of these interleavers can be related to the cycle structure of the primary Möbius transformation and its coefficients. By adjusting some parameters, an upper bound on the number of total tested BFPs for the proposed truncated Möbius interleavers is found. One distinctive property of Möbius interleavers is that their inverse can also be represented and computed with Möbius functions. Simulations are conducted to compare the error performance of the proposed truncated Möbius interleavers with quadratic permutation polynomial (QPP) interleavers whose inverses are also representable by a quadratic equation (Ryu and Takeshita in IEEE Trans Inf Theory 52(3):1254–1260, 2006). It is finally shown that the truncated Möbius interleavers can interleave sequences of information bits faster than QPP interleavers.     

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.     

Interleavers for turbo codes using permutation polynomials over integer rings

A class of deterministic interleavers for turbo codes (TCs) based on permutation polynomials over /spl Zopf//sub N/ is introduced. The main characteristic of this class of interleavers is that they can be algebraically designed to fit a given component code. Moreover, since the interleaver can be generated by a few simple computations, storage of the interleaver tables can be avoided. By using the permutation polynomial-based interleavers, the design of the interleavers reduces to the selection of the coefficients of the polynomials. It is observed that the performance of the TCs using these permutation polynomial-based interleavers is usually dominated by a subset of input weight 2m error events. The minimum distance and its multiplicity (or the first few spectrum lines) of this subset are used as design criterion to select good permutation polynomials. A simple method to enumerate these error events for small m is presented. Searches for good interleavers are performed. The decoding performance of these interleavers is close to S-random interleavers for long frame sizes. For short frame sizes, the new interleavers outperform S-random interleavers.     

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     

Modified Collision-Free Interleavers for High Speed Turbo Decoding

Inter-window shuffle (IWS) interleavers are a class of collision-free (CF) interleavers that have been applied to parallel turbo decoding. In this paper, we present modified IWS (M-IWS) interleavers that can further increase turbo decoding throughput only at the expense of slight performance degradation. By deriving the number of M-IWS interleavers, we demonstrate that the number is much smaller than that of IWS interleavers, whereas they both have a very simple algebraic representation. Further, it is shown by analysis that under given conditions, storage requirements of M-IWS interleavers can be reduced to only 368 storage bits for variable interleaving lengths. In order to realize parallel outputs of the on-line interleaving addresses, a low-complexity architecture design of M-IWS interleavers for parallel turbo decoding is proposed, which also supports variable interleaving lengths. Therefore, the M-IWS interleavers are very suitable for the turbo decoder in next generation communication systems with the high data rate and low latency requirements.     

A Simple Interleaver for Use with Viterbi Decoding

An interleaver/de-interleaver can be used to improve the performance of a Viterbi decoder in the presence of bursty noise. This note describes the design and a method for testing block interleavers which can be used to combat the effects of periodic pulsed RFI. Simulations show that satisfactory decoder performance can be obtained over a range of RFI parameters.     

Collision-Free Interleaver Composed of a Latin Square for Parallel-Architecture Turbo Codes

In parallel-architecture turbo codes, the constituent interleavers must avoid memory collision. This paper proposes a collision-free interleaver structure composed of a Latin square (LS) and pre-designed interleavers. Our proposed interleavers can be easily optimized for various information block sizes and for various degrees of parallelism. Their performances were evaluated by computer simulation.     

Variable-size interleaver design for parallel turbo decoder architectures

In this paper, we propose two techniques to design good S-random interleavers, to be used in parallel and serially concatenated codes with interleavers. The interleavers designed according to these algorithms can be shortened, in order to support different block lengths in such a way that all the permutations obtained by pruning, when employed in a parallel turbo decoder, are collision-free. The first technique, suitable for short and medium interleavers, guarantees the same performance of nonparallel interleavers in terms of spreading properties, simulated frame-error probabilities, and obtainable minimum distance of the actual codes. The second algorithm, to be used for large block lengths, permits achieving high degrees of parallelism at the price of a slight degradation of the spread properties, and also to change the degree of parallelism on-the-fly. The operations of a parallel turbo decoder employing these interleavers are described, and an example of the advantages of the proposed techniques is provided in a realistic system framework.     

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     

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     

基于组合交织器的高码率RA码的设计

针对一般交织器结构的重复累积(RA)码的奇偶校验矩阵中出现的短环问题,提出将一种组合技术应用于RA码的交织器结构,设计一种新型的组合交织器,使得产生的RA码具有高码率且无4环。仿真结果显示,在码长较长和高码率的情况下,组合交织的RA码译码性能优于传统交织器。     

2-Dimension Interleaver Design for IDMA Systems

A new design method interleavers, 2-dimension interleavers, are proposed for interleave division multiple access （IDMA） systems. With a same interleaving rule named I＇, the row indices and column indices of a traditional block interleaving matrix are scrambled to obtain an interleaver, which is marked as the master interleaver. F is produced by a loworder PN sequence generator. Two ways are provided for generating different interleavers. One is that all interleavers are generated by the circular shifting master interleaver. The other is that different inter leavers are generated by different Ts. Besides, we prove that the minimum distance between two adjacent bits resulted from 2-dimension interleaves is much larger than that of other schemes, such as random interleavers, power interleavers, and shiffting interleaves. The simulation results show that 2-dimension interleavers can achieve much better performance with much less resource consumption than random interleavers in IDMA systems.     

Turbo码随机性交织器设计

深空测控中为获得较高的编码增益需要用到信道编译码技术。Turbo码是一种逼近香农限的高性能的信道编译码,其中,交织器的设计是影响Turbo码性能的关键因素之一。论述了交织器设计的基本准则,并详细介绍了3种常见的随机性交织器:伪随机交织器、S随机交织器和S改进型交织器的交织原理,对比分析了3种交织器的优缺点并给出了仿真结果。结果表明,交织器生成方式的不同将带来不同的Turbo码译码性能。     

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.     

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.     

Improved method for searching interleavers from a certain set using Garello’s method with applications for the LTE standard

In this paper, we propose a method for searching interleavers within a certain class, with the aim of designing turbo codes with good distance spectrum. The method is based on a modified version of Garello’s algorithm and consists in the calculation of frame error rate truncated upper bound. Here, it is applied to quadratic permutation polynomial (QPP) interleavers able to outperform those chosen for the long-term evolution (LTE) standard, for lengths up to 1,504 bits. Three classes of interleavers have been analyzed: (1) the set of QPP interleavers with the largest spread, (2) the set of QPP interleavers with a spread parameter equal to that of LTE interleaver and the highest refined nonlinearity degree, and (3) the complete set of all QPP interleavers for lengths up to 1,008. The distance spectrum optimization is made for all classes. Compared to previous methods for finding QPP-based interleavers, the search complexity is reduced, with improved performances in terms of search time, allowing interleavers of higher length. For lengths up to approximately 450, the best interleavers were found in the first class. For longer lengths, the second class contained the best ones.     

交织在信道编码中的应用

在通信系统中信道编码的交织技术起着重要的作用，交织的使用提高了数据传输的可靠性。本文介绍了交织器的基本原理并对两种常用的交织器的性能进行了比较，提出了今后交织器研究的重点。     

信道交错器的实现方案及其优缺点

系统地介绍信道交错器(Interleaver)技术的发展状况,包括最基本的Interleaver类型和最新发展起来的一些技术,同时对比了各种Interleaver技术的优缺点,指出Interleaver技术还存在的问题,并描述Interleaver技术的应用前景。     

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.