State-of-the-Art. Theory of Interleavers

State-of-the-Art: Theory of Interleavers

- Interleavers are used in communication system theory for multiple purposes. In this article, an extensive state-of-the-art on theory of interleavers has been presented. It covers the major developments that occurred in the domain of interleaving and interleavers.

Keywords- Interleavers, interleaving, communication theory, interleaver, permutation, shuffling, computer application, inverse tree interleavers.

INTRODUCTION

Fifth generation (5G) communication is a giant leap in cellular communication technologies in terms of data rate, connectivity, quality of services (QoS) and use-cases. The communication theories involved in essence include multiple basic building blocks within the architectural framework. Interleaver and interleaving are two important aspects in this context. It is a fascinating journey how these interleavers have been developed in theory and explored in an unlimited and unexpected way. This article provides a summary of this journey. The only aim is to provide ready references and develop brief understanding of this journey for the researchers who are actively involved in this field.

EARLY DEVELOPMENTS

In 1948, ‘Claude E. Shannon’ introduced the classical (mathematical) theory of communication and determined the maximum limits of channel capacity for an ideal infinite bandwidth channel with additive white Gaussian noise (AWGN) [1] [2]. The extensive use of probability theory was involved in Shannon’s mathematical theories of communication. Therefore, this built the foundation for emergence of modern era of communication because Shannon’s mathematical theories led the development of another vertical branch of communication i.e. information theory. The contribution of Nyquist is equally important as both Shannon and Nyquist worked in parallel to each other in the same area i.e. data transmission. Nyquist is well-known for his contributions towards developing a quantitative understanding of thermal noise, negative feedback and data transmission [3].

Over the time, several desired features have been identified by the researchers to make the communication systems more robust, reliable and secure. Accordingly, depending on the requirements of applications several gradual improvements have also been introduced in the area of communication systems and technologies. Reliability is among one of the primary quality of service (QOS) aspects of a communication system as it ensures error-free delivery of the data to the correct destination. ‘Data shuffling’, also known as ‘interleaving’, is a technique to achieve this QOS aspect in communication domain.

Fisher et al. (1948) proposed a novel method of shuffling a set of statistical data arranged in a table format [4]. In some sense, this shuffling method promoted random data shuffle. Hence, this shuffling method is named as ‘Random Fisher-Yates shuffling method’. The method was developed much before the beginning of advanced computers era. Therefore, it was not primarily optimized in terms of complexity, memory size and time-delay. Handling the too large data sets was also very difficult using this method. Despite these facts, the method was quite important as it encouraged the design and development of new and better methods of data shuffling.

Durstenfeld (1964) provided an alternate approach of random permutation. This approach was a modified version of Fisher-Yates’s random data shuffle [5]. The random permutation approach was later deeply analyzed by Knuth et al. (1973, 75, 76, 99) in terms of quantitative and qualitative point of views. Further, the algorithm was popularized for general as well as computer applications [6]-[9]. Knuth et al. (1975, 76) also described the activities in an interleaved memory and computational complexity involved in the interleaving algorithm/s used in such memory respectively [7] [8]. These contributions added a new dimension to the researches carried out on interleaving in near future. However, an initial idea of interleaving and interleavers was proposed and patented by Forney (1972) for different interleavers i.e. periodic, modular periodic and cascaded periodic interleavers were introduced [10].

In general, error correcting codes are provided as a solution for error free transmission. However, error correcting codes have capability to correct limited numbers of erroneous bits in each frame. Therefore, these codes also fail when all the bits of a large frame are corrupted i.e. burst error scenario. Interleaving was introduced as a method of burst error control. This facilitates the distribution of errors among multiple frames because receiving a complete erroneous frame is more harmful than receiving limited erroneous bits in multiple frames. Ramsey (1970), proposed four different realizations of optimum (random) interleavers. These four realizations of interleavers were optimum in the terms of encoding delay and memory capacity for their storage and unscrambling [11].

Burnett et al. (1970) presented initial study on interleaved memory in [12]. In order to eradicate the mismatch of spin speed and data reading in disks, Kim (1985, 86) developed the idea of synchronous disk interleaving [13] [14]. With the introduction of this interleaving technique, data could be read from the disk without any delay. Even today, this interleaving technique is implemented for disk and similar other applications. Weinstein et al. (1971) showed that transmission of data by frequency division multiplexing is possible using Discrete Fourier Transform (DFT). This was an exemplary work which also led the development of orthogonal frequency division multiplexing (OFDM) and similar other DFT based multiplexing in near future [15].

Currie et al. (1983) proposed a novel interleaver and de-interleaver with the aim to provide a predetermined shuffling pattern for rearranging and rotating bits in columns and rows. Once, the bits are error encoded, this interleaver was adapted to store these bits belonged to a data sequence [16]. This interleaver was based on generation of quasi-random permutation pattern and capable to combat with burst errors and radio interferences.

Mui (1985) demonstrated that a digital signal transmitted over a transmission channel can be interleaved in a pseudo-random fashion at transmitter and de-interleaved using non-random approach at receiver [17].

Berlekamp et. al. (1985) proposed interleavers for block codes by exploiting the helical symmetry of the codes. The proposed interleaver minimizes the interleaving delay and dependence on burst onset is also reduced [18]. Berlekamp et al. (1987) enlightened the significance of error control particularly when a communication system has to handle large volume of data [19]. Pielle (1988) presented a detailed discussion on interaction among error correction, interleaving and differential pulse position modulation (PPM) in context of satellite communications [20].

Sequential block interleave coding (SBIC) method was introduced for interleaving of binary data in image processing applications by Tan et al. (1988). The SBIC provides fixed-rate output and exhibits a resistance to transmission errors. The method also eliminates the use of code book for encoding binary data over a field of blocks and decreases the size of field [21]. Dunscombe et al. (1989) are known for their significant contribution in the area of interleaving. They proposed an optimal interleaving technique for convolution coding scheme [22]. In 1990s, the development of turbo codes provided new dimensions to error correcting codes, receiver structures and interleaving approaches. After 1990s, researchers extensively employed turbo decoders for at the receiving end.

DEVELOPMENTS AFTER 1990s

Turbo codes, also known as block turbo codes or convolutional turbo codes, are high performance forward error correction (FEC) codes capable of achieving near maximum channel capacity deploying an iterative decoding scheme. These codes were developed by Berrou et al. (1993). These codes are constructed by performing parallel concatenations of two recursive systematic convolutional codes [23]. Dolinar et al. (1995) presented a discussion on weight distribution achievable for turbo codes using random, semi-random and non-random shuffling patterns in a technical report [24]. The same report concludes that self-terminating lower weight codes are more significant in designing of constituent codes than higher weight codes. Berrou et al. (1996) described their earlier presented work in more illustrative and descriptive manner [25]. Therefore, on conceptual front both the research work presented by Berrou et al. (1993, 96) are nothing but same.

Andrews et al. (1997) derived some optimality results on latency and memory requirements of interleavers for a given spread. With the help of a mathematical model, class of block interleavers was analyzed for optimality [26]. Marnane et al. (1997) talked about the no cost hardware implementation context of bit-serial interleavers in high speed digital circuit [27].

Multipath direct sequence code division multiple access (DS-CDMA) channels suffer from multiple-access interference (MAI) and intersymbol interference (ISI). To control these impediments, a special receiver structure was proposed by Wang et al. (1999). Based on the non-linear interference reduction technique, a low complexity decoder was developed for soft interference cancellation and performing filtering operation. This was an iterative decoder i.e. turbo processing based decoder meant for soft interference cancellation and decoding of DS-CDMA in coded scenario [28]. Lee et al. (1999) proposed a swap interleaver technique that takes less time in generation than semi-random (s-random) interleavers. The swap interleavers were developed for turbo codes and obtained from block interleavers. A comparison between s-random and swap interleavers was also performed in the same work and superiority of swap interleavers over s-random interleavers was analytically proven [29].

In order to improve the turbo code performance by better mapping of pseudo-random interleavers, Said et al. (1999) offered an improvement through elimination of unsuitable interleavers. A sequential five step procedure was also provided to determine such improved interleavers [30].

In modern days communication systems, interleaving is widely deployed for controlling burst errors and improving system performance. Gui et al. (2000) proposed novel chip interleavers for direct sequence spread spectrum (DS-SS) system. This work also covers a study of system performance under the effect of toned interference [31]. It concludes that interleaving performed at full-length data sequence makes the system performance more robust than on a specific portion of data sequence.

Iterative decoding procedure is a distinguish feature associated with turbo codes. Brink (2000) investigated extrinsic information transfer (EXIT) chart in such decoding procedure for bit interleaved coded modulation schemes. Exit chart comprises both decoder and de-mapper characteristics together on a single diagram. These are extremely useful tool for understanding the convergence behavior of iterative decoding techniques [32]. Orthogonal frequency division multiplexing (OFDM) is a robust scheme capable of combating certain interferences. Lei et al. (2000) demonstrated the idea of adaptive interleaving that utilizes the current channel state information (CSI) and re-shuffles the data sequences in an adaptive manner. This aims to randomize the burst errors [33]. A detailed comparison of s-random and pseudorandom interleaving approaches in terms of bit error rate (BER) was presented by Blazek et al. (2001). A modified version of s-random interleaver, popularly called as modified s-random (MSR) interleaver, was also covered in this work. It was shown that MSR interleavers require less generation time than s-random and pseudo random interleavers. In fact, MSR interleaver outperforms the rest two interleavers in terms of overall BER performance [34].

Following the two basic criterion i.e. weight distribution of code and correlation between input information and decoder output, Sadjadpour et al. (2001) offered a new design of interleavers for turbo codes. The new design of interleaver encourages short block length codes as large block length results significant performance reduction for turbo code. A short discussion on deterministic interleaver approach was also covered in this work [35].

Yuan et al. (2001) proposed the design structure of cyclic interleavers for turbo codes. The main advantages of these interleavers were its low computation complexity, low memory requirement and ease of implementation. Soft output Viterbi algorithm (SOVA) was employed for obtaining the simulation performance of cyclic interleavers. SOVA is an iterative decoding algorithm possessing less complexity than mapping method [36]. Barbulescu (2001) proposed an interesting design of interleavers which was based on sliding window algorithm. A trellis termination is ignored by adopting an interleaver design that involves a sliding window of a particular size. The decoding penalty is also reduced by adding extra constraint in design structure of interleaver [37].

Uncoded systems are the systems without any channel coding applied. In such systems, combating with ISI and multiple access interference (MAI) is a challenging task. Mahadevappa et al. (2002) described chip level interleaving for combating with ISI and MAI in uncoded system scenario. Code Division Multiple Access (CDMA) was adopted for uncoded system modeling in this work. Receiver employing turbo equalization was adopted in the same system model. An uncoded CDMA system with large interleaver size effectively combats with large scale fading. Therefore, an improved average system perform is obtained [38]. Weber et al. (2002) studied the turbo multiuser detection scheme in context of time division based CDMA (i.e. TD-CDMA) [39]. The results of the work concluded that combined multi user multi-step detection in TD-CDMA system improves the signal-to-noise ratio (SNR) performance almost by 10 dB and also enhances capacity and spectrum efficiency of the system [39]. The main advantage of this combined multi-user detection approach was that only few iteration was enough to achieve optimum performance. Ping et al. (2002) explored an optimal multiuser detection in correlation with space-time coding. The concept of interleaver centric system i.e. interleaves division multiple access (IDMA) was first coined and appeared in this work [40]. Similar to CDMA, IDMA systems also possesses capability to mitigate interference. Some other properties of CDMA systems e.g. diversity against fading etc. are the part of IDMA systems as well.

Ping et al. (2003) described IDMA systems as revolutionary systems in which interleavers are the only mean for distinguishing the users. Hence, IDMA is an interleaver centric system with capability of combating ISI and MAI [41]. IDMA was explored in great detail in later work of Li Ping and co-authors. Liu et al. (2003) extended the work on combined multiuser detection for CDMA system. Multiuser chip-by-chip detection was examined for the CDMA system [42]. In this examination, multipath and multiple antennas were assumed and chip-interleaved CDMA system was considered for analysis purpose. Soft-rake algorithm with complexity of linear order and joint Gaussian algorithm with complexity of non-linear (i.e. squared) order were tested on chip-interleaved CDMA system to mitigate ISI and MAI. The system model considered is the replica of original IDMA model [41] [42].

Ma et al. (2003) investigated the impact of frequency offset on bit error rate (BER) performance of single carrier frequency division multiple access (SC-FDMA) and multicarrier orthogonal frequency division multiplexing (OFDM) systems. The significance of this work lies in the fact that in today’s scenario IDMA systems are being integrated with some other systems such OFDM or SC-FDMA [43].

Balta et al. (2004) studied BER performance of convolution interleavers used in turbo codes [44]. Since, performance of any interleaver is also measured in terms of BER. Therefore, this work is equally significant as it provides simulation performance of these interleavers and proves their competitiveness. A comprehensive view on role of interleavers in mitigating burst errors was given by Shi et al. (2004). Single and multi-dimensional block interleaving approaches were explained in this work. Further, this work also explored different level of array generation for different degree of interleaving. The scope of interleaving approaches covered by the authors of this work lies beyond the communication applications [45].

Ying et al. (2004) proposed the generation of interleavers for turbo codes using genetic algorithms (GAs). The simulation results presented in this work concludes that the GAs based interleavers outperform semi-random (s-random) interleavers and are capable to reduce latency involved in generation of pseudorandom interleavers [46]. Ping et al. (2004) studied CDMA channel capacity under high coding gain offered by low rate turbo codes [47]. Interleavers employed in the system model were the only mean for differentiating among identities of the users. Selection of the multiple access scheme and detection scheme were the two key issues addressed in this work.

Tarable et al. (2005) presented interleaver design and analysis for coded CDMA systems [48]. The design criteria for efficient interleavers are the key feature of this work. The design rule presented here are applicable for any interleavers with any channel code. Iterative (turbo) decoding procedure was employed to de-interleave and decode the original information signal at the receiving end. An important conclusion of the work was that suitable iterative decoder provides better system performance than system parameter optimization. This work was an extension of the work presented by Mahadevappa et al. (2002) in [38] where uncoded CDMA scenario was considered.

The contributions of researchers on chip level interleaving in context of DS-SS and/or CDMA systems are available in [31][38][42]. Further, Li. Ping (2005) investigated the chip-by-chip level interleaving in context of IDMA system. The iterative decoding remained intact in this work as well. With unequal power distribution among users, the results close to the maximum theoretical limit were obtained [49]. Chip-by-chip interleaving for multiuser Ultra Wide Band (UWB) communication was explored by Yang et al. (2005) at initial level. A soft frequency notching scheme was used to eradicate narrowband interference. Similarly, MAI and frequency selective interference were also eradicated at the same time that usually comes into picture in case of UWB communication [50].

A revolutionary progress was observed in the area of interleaving and interleaver centric systems after 2006. Ping et al. (2006) comprehensively explored IDMA in single and multiuser scenario assuming different independent multiple access channel (MAC) cases namely AWGN, Rayleigh and Rician channel. In this work, IDMA was presented as a special case of CDMA and user separation was performed on the basis on interleavers. Chip-by-Chip (CBC) detection with iterative (turbo) and Maximal-Likelihood (ML) decoding was also tested in the analysis presented for IDMA [51]. This work is also a ready reference for detailed mathematical understanding of working of IDMA system.

Pupeza et al. (2006) disclosed collision freeness and simple generation as two essential key parameters for practical interleavers employed in IDMA systems [52]. Zero mathematical correlation for collision free interleavers was suggested. Since, it is little tricky and costly to ensure no collision among interleaver. Therefore, upper bound based non-orthogonal interleaving approaches were also presented in this work. These approaches ensure minimum correlation and hence, the minimum chances of collision among interleavers. For dealing with storage requirement of pattern of interleavers and maintaining acceptable computation complexity, user specific interleavers were proposed by Wu et al. (2006). These were the power efficient interleavers for IDMA in the sense that each pattern was generated in terms of power of the first interleaver [53].

Liu et al. (2006) performed the analysis of an optimized CDMA system exhibiting chip-interleaving [54]. With the help of two distinguished approaches namely linear programming and power matching, performance optimization was achieved. Simulations were performed to verify the optimization and adopted method efficiency. Choi et al. (2006) explained the idea of content aware interleaving exclusively for wireless video transmission. The technique aimed to save the bandwidth for enhancing the video quality. For content awareness a quantitative index was proposed to identify the importance of video content [55].

Integration of two or more technologies helps in compensating the various limitations associated with one particular technology. IDMA systems also have some limitations. In order to overcome these limitations, its integration with other technologies is often recommended. This is to meet the challenging requirements of modern day communication. Bie et al. (2006) coined the idea of integrated i.e. hybrid multiple access scheme. OFDM and IDMA were chosen to be integrated. The resultant technology was i.e. OFDM-IDMA was analyzed in terms of performance [56].

Mahafeno et al. (2006) integrated IDMA with OFDM technology together to mitigate interference such as ISI in a much better manner. This OFDM-IDMA technology was investigated in quasi-static Rayleigh channel [57]. The performance of both IDMA and OFDM-IDMA was simulated. The simulation results conclude that OFDM-IDMA mitigates interference in better way than convention IDMA i.e. CIDMA.

Myung et al. (2006) investigated single carrier FDMA i.e. SC-FDMA for high data rate uplink wireless transmission [58]. The main focus of this research work was reduction of peak-to-average power ratio (PAPR). The significance of this work lies in the fact that long term evolution (LTE) involves the use of SC-FDMA in uplink transmission to avoid the rapid drainage of user equipment (UE) power. The mathematical analysis of IDMA and integrated system models involves the concept of probability theory as well as information theory. Most of these concepts are available in [59].

Li et al. (2007) presented the analysis of optimized IDMA communication system using EXIT chart scheme and performance approximation technique [60]. This was a comprehensive work presented on IDMA analysis that covers both single and multi-cell scenarios. Low rate coding scheme existence was assumed in this presented IDMA system model analysis.

Trifina et al. (2007) provided a modified version of Welch-Costas interleaver that compromises with memory cost but achieves minimum distance comparable with s-random interleavers. However, the memory cost was only higher than original Welch-Costas interleaver and it still remained lower than s-random interleavers. A cyclic shift is performed applying GareIlo's method to estimate the minimum distance of turbo codes and further to calculate the upper bound [61].

Ping et al. (2007) explained integrated OFDM-IDMA in a comprehensive manner with proper mathematical analysis [62]. This work also covers the major advantages of OFDM-IDMA system. Here, additional OFDM layer is inserted into existing IDMA layer within the IDMA system model. Thus, advantages of OFDM are also exploited along with IDMA. Reminding that the initial idea of integrating the two approaches was first appeared in [56]. Koutsouveils et al. (2007) presented a method of turbo code interleaving based on bubble sorting. The main advantage of this method of interleaving was its low level complexity [63]. The scope of interleaving is not restricted to any single domain. Chen et al. (2007) suggested an interleaving algorithm for next generation versatile disk. Different patterns of existing interleaving techniques for optical/disk storage was discussed in this work; computation complexities of few of those specific patterns of interleaving e.g. T, circle-shift, spiral etc. which are normally employed in optical storage were also compared [64]. Myung (2007) described SC-FDMA from physical layer and resource management point of view. PAPR properties and channel dependent scheduling of SC-FDMA were also covered in this work [65]. This work was an extension of the research work presented by Myung et al. (2006) in [58]. Xin-rui et al. (2007) proposed a new category of interleavers appropriate for any window size [66]. The generation of these interleavers was based on permutation of modulo of interleaver length. These interleavers were claimed as maximum contention free interleavers.

[...]