Interleaver pruning for construction of variable-length turbo codes

In this paper, we address the issue of pruning (i.e., shortening) a given interleaver in a parallel concatenated convolutional code (PCCC). The principle goal of pruning is that of construction of variable-length and hence delay interleavers with application to PCCC, using the same structure (possibly in hardware) of the interleaver and deinterleaver units. As a side benefit, it is sometimes possible to reduce the interleaver length and hence delay for nearly the same and sometimes even better asymptotic performance. In particular, we present a systematic technique for interleaver pruning and demonstrate the average optimality of the strategy. Sample simulation results are presented confirming the average optimality of the proposed scheme.     

Turbo编码中的交织技术

Turbo码是近年来提出的一种高性能的信道编码.Turbo码交织器的设计是Turbo编解码器设计中的关键.文中介绍了交织器的基本原理,详细地介绍了3种常见的交织器的交织原理.最后给出了交织器的设计准则.     

IDMA系统中交织器研究现状

近年来,香港城市大学李坪教授提出的交织分多址(IDMA,Interleaver Division Multiple Access)作为一种新的多址技术已经在各个方面均得到了广泛的研究。交织多址是根据不同的交织器来区分用户的,因此,交织器的设计是IDMA系统中的一个关键技术。许多学者在传统交织器的基础上,提出了多种适用于IDMA系统的交织器设计方案。对国内外关于IDMA系统中交织器的设计方案分类进行阐述与归纳总结,并比较了各种交织器设计方法的优缺点。     

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.     

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.     

Turbo码中快速交织器的设计

分析了交织器在Ｔｕｒｂｏ码中的重要作用，以及目前交织器存在的缺陷，介绍了一种快速交织器的设计方法。该交织器易于实现，具有交织时延低的突出优点。计算机仿真结果表明，该快速交织器可以获得优异的性能。     

确定性交织器的研究

本文分析了交织器在turbo码中的重要作用，以及随机交织器存在的缺陷，并提出了一种确定性交织器的设计方法。该交纪念品器具有简明的解析表达式，易于实现。计算机仿真结果表明，该确定交织器可以获得的性能优于随机交织器的平均性能。     

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.     

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.     

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.     

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

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

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     

基于线性同余的IDMA交织器设计及分析

本文提出了一种新的基于线性同余的IDMA交织器设计方案, 并且给出了详细的交织器设计算法. 它能满足IDMA交织器设计中低存储量、容易产生交织序列、交织器同步数据少、交织器之间相关性小的要求. 本文的仿真结果证明了这种交织器性能优于伪随机交织器。     

Analysis of Cubic Permutation Polynomials for Turbo Codes

Quadratic permutation polynomials (QPPs) have been widely studied and used as interleavers in turbo codes. However, less attention has been given to cubic permutation polynomials (CPPs). This paper proves a theorem which states sufficient and necessary conditions for a cubic permutation polynomial to be a null permutation polynomial. The result is used to reduce the search complexity of CPP interleavers for short lengths (multiples of 8, between 40 and 352), by improving the distance spectrum over the set of polynomials with the largest spreading factor. The comparison with QPP interleavers is made in terms of search complexity and upper bounds of the bit error rate (BER) and frame error rate (FER) for AWGN and for independent fading Rayleigh channels. Cubic permutation polynomials leading to better performance than quadratic permutation polynomials are found for some lengths.     

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.     

Uncoded integrated interleave division multiple access systems in presence of power interleavers

Interleaving is one of the most common methods known to eradicate the effects of multiple user interference. Removal of different interferences is one of the major challenges for advanced communication system designers. Several methods of interleaving have been proposed in literature and their performances have been analyzed on different communication systems to prove their worthiness in multiple user interference removal. One of such interleavers is power interleaver, which can be employed in communication systems as a means to control burst errors and reduce the multiple user interference. In this paper, performances of two different integrated interleave division multiple access (IIDMA) techniques i.e. SCFDM-IDMA and OFDM-IDMA have been analyzed. Novelty of this work is in the sense that the entire analysis has been performed in the presence of power interleavers for the above two IIDMA techniques as the conventional IDMA fails to mitigate the problems of inter-carrier and inter-symbol interferences. Hence, the two techniques in presence of power interleavers empower the idea of quality communication without any interference for future generation communication systems.     

Construction of turbo code interleaves from 3-regular Hamiltonian graphs

In this letter, we present a new construction of interleavers for turbo codes from 3-regular Hamiltonian graphs. The interleavers can be generated using a few parameters, which can be selected in such a way that the girth of the interleaver graph (IG) becomes large, inducing a high summary distance. The size of the search space for these parameters is derived. The proposed interleavers themselves work as their de-interleavers.     

Low-complexity BCH codes with optimized interleavers for DQPSK systems with laser phase noise

The presence of high phase noise in addition to additive white Gaussian noise in coherent optical systems affects the performance of forward error correction (FEC) schemes. In this paper, we propose a simple scheme for such systems, using block interleavers and binary Bose–Chaudhuri–Hocquenghem (BCH) codes. The block interleavers are specifically optimized for differential quadrature phase shift keying modulation. We propose a method for selecting BCH codes that, together with the interleavers, achieve a target post-FEC bit error rate (BER). This combination of interleavers and BCH codes has very low implementation complexity. In addition, our approach is straightforward, requiring only short pre-FEC simulations to parameterize a model, based on which we select codes analytically. We aim to correct a pre-FEC BER of around \(10^{-3}\). We evaluate the accuracy of our approach using numerical simulations. For a target post-FEC BER of \(10^{-6}\), codes selected using our method result in BERs around 3\(\times \) target and achieve the target with around 0.2 dB extra signal-to-noise ratio.     

Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective

An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are important because they admit analytical designs and simple, practical hardware implementation. The spread factor of an interleaver is a common measure for turbo coding applications. Maximum-spread interleavers are interleavers whose spread factors achieve the upper bound. An infinite sequence of quadratic PPs over integer rings that generate maximum-spread interleavers is presented. New properties of PP interleavers are investigated from an algebraic-geometric perspective resulting in a new non- linearity metric for interleavers. A new interleaver metric that is a function of both the nonlinearity metric and the spread factor is proposed. It is numerically demonstrated that the spread factor has a diminishing importance with the block length. A table of good interleavers for a variety of interleaver lengths according to the new metric is listed. Extensive computer simulation results with impressive frame error rates confirm the efficacy of the new metric. Further, when tail-biting constituent codes are used, the resulting turbo codes are quasi-cyclic.