Excerpt
Table of Contents
1. INTRODUCTION
2. BURST ERRORS
3. INTERLEAVING
4. INTERLEAVERS AND THEIR ADVANTAGES
5. MAJOR TYPES OF INTERLEAVERS
5.1. RANDOM INTERLEAVERS
5.2. CYCLIC INTERLEAVERS
5.3. POWER INTERLEAVERS
5.4. PRIME NUMBER INTERLEAVERS
5.5. TREE INTERLEAVERS
5.6. INVERSE TREE INTERLEAVERS
5.7. MODERN FISHER-YATES INTERLEAVERS
6. APPLICATIONS OF INTERLEAVERS
7. INTERLEAVER CENTRIC SYSTEMS
8. Conclusion
References
Abstract
Multiple access techniques support multiple user scenarios in advanced cellular communication systems. Interleavers and interleaving schemes are used for user separation and data shuffling in these systems. In this tutorial, an investigation on interleaving and interleavers for the multiple access systems is presented.
Keywords – 5G, interleaving, interleavers, multiple access systems, etc.
1. INTRODUCTION
Modern day communication systems target to achieve errorless transmission of data between a transmitting and receiving end. An errorless transmission ensures high quality of service (QoS), reliability and security of data. Next generation communication system i.e. 5G aims to support voice/data/multi-media contents of high data rates with better quality and security. The supporting 5G technologies like massive machine type communication (mMTC), enhanced mobile broadband (eMBB) and ultra-reliable low latency communication (URLLC) etc. also require higher reliability and availability of services with higher QoS 1-5. Therefore, error free transmission at higher data rates becomes a critical issue.
Forward error correcting (FEC) codes are deployed as an essential element of a digital communication system. Examples of the FEC codes are cyclic code, Bose-Chaudhuri-Hocquenghem (BCH) codes, linear block codes, convolution codes, turbo codes etc. These codes have potential to control those errors which occurs when digital information is passed through a communication channel. A channel may be a wireless or a wired channel. The FEC codes have the capability to detect and correct the errors present in the received data. However, only limited data bits in errors can be detected and corrected simultaneously by the FEC codes. This puts a certain limitations on efficiency of the FEC codes as modern day’s communication systems completely rely on error free transmission 6-9. In fact, in services like URLLC even much delay is also not acceptable. This serious limitation associated with the FEC codes causes to identify some alternate solutions so that the transmission can be turned into an error-free transmission; and requirements of 5G and supporting technologies can also be fulfilled.
To overcome the limited capability issue of the FEC codes and making error free transmission possible in presence of higher data rates, a data rate independent solution is strongly desired. This rate-independent solution facilitates an error control mechanism especially to compensate the failure of FEC codes. This rate independent solution is often provided in the form of a mechanism called ‘interleaving’. Interleaving is a mechanism used when there are chances of occurring burst errors 10. Modern digital communication systems possess capability of performing interleaving.
2. BURST ERRORS
Unlike single, two or three errors spreaded within a frame at some random places, burst errors are observed at a single place affecting multiple bits of a frame simultaneously 11. In simple words, these are one of the severe types of errors that affect the performance of a communication system. Numbers of errors occurring simultaneously in a group are uncorrectable by the FEC codes due to capability limitations. Therefore, burst error causes undesired erroneous information transmission.
Abbildung in dieser Leseprobe nicht enthalten
Figure 1 (b): Burst errors affected frame
Figure 1: Burst error showcase
Figure 1 resembles a burst error showcase. As shown in figure 1 (a), an initial (original) frame carrying information bits 1 to 8 is transmitted. Figure 1 (b) represents the received frame at the other end. The received frame has been affected from burst errors. 3rd, 4th, 5th and 6th bits are the error bits (shown in bold font). The reason of occurrence of burst errors may be known or unknown here. The discussion on the reasons behind the occurrence of error bits is beyond the scope of this tutorial. Since, the burst errors are affecting the four consecutive bits of the transmitted frame. These error bits can’t be corrected by any of the FEC code that has capability of correcting only three bits of errors. This was just a simple theoretical scenario. In real-time scenario, this issue will be more problematic as frame sizes are normally large and therefore errors will be more.
3. INTERLEAVING
Interleaving is a mechanism provided to control the burst errors. This mechanism facilitates a provision to put the counter measures for the expected burst errors in advance i.e. well before their actual occurrence during transmission 12-15. So, this is more analogous to a safety measure taken well before the harm actually occurs. Since, in communication systems, the probability of occurrence of the burst errors is fairly high. Therefore, making such a provision, in advance, to control the burst error is highly desired.
Interleaving is defined as a method of permutation of a set of information bits. In communication technology domain, interleaving permutes the information bits that belong to single or multiple frames. This means permutation can be performed within the same frame or among the multiple frames 16. For controlling adverse effect of the burst errors on a single frame, distribution of error bits among multiple frames is required. The interleaving mechanism helps in achieving this objective efficiently 12.
Abbildung in dieser Leseprobe nicht enthalten
Figure 2: Illustration of burst error control using interleaving mechanism
Figure 2 illustrates burst error control using interleaving mechanism. As shown in figure 2(a), initially there are three different frames i.e. frame-1, frame-2 and frame-3 each of length-4. These frames are transmitted sequentially. Due to some reasons frame-2 gets affected from the burst errors (figure 2(b)). This result in complete loss of the original information carried in frame-2 i.e. each bit of frame-2 is in error. Detection, correction and then recovery of frame-2 become critical here because of the limited capability issue of the FEC codes. Therefore, in order to avoid re-transmission of frame-2 and easy recovery of information bits of frame-2 at the receiving end, interleaving mechanism is provided. Figure 2(c) shows the distribution of error bits of frame-2 among multiple frames. By this way, instead of losing a frame completely due to burst errors, it is preferred to lose the part of the multiple frames. In this example, after interleaving, the correct amount of information carried by frame-2 is 75% i.e. error bits are 25%. This becomes possible due to information bit distribution property of interleaving mechanism. Assume that the capability of FEC code employed here is up to 3 bits per frame. Then, erroneous bits of each frame can be easily corrected by the FEC code used. Therefore, error-free detection of initial data bits is possible.
4. INTERLEAVERS AND THEIR ADVANTAGES
Interleaving mechanism changes the order of a data set and randomizes the data set for controlling burst errors. This change of order is required to be decodable at the receiving end to recover/generate the original sequence of the data set. Therefore, the randomization produced in the order of the data set must follow some rule so that at the receiving end applying the same rule original order of the bits can be recovered 10 12 17 18. This is how the term ‘interleaver’ comes into the picture.
Interleavers refer to a permutation pattern followed while performing the interleaving onto a data set. The two terms namely ‘interleaving’ and ‘interleavers’ are closely related to each other. Therefore, these are often used interchangeably in existing literature. However, the difference between interleaving and interleavers is as follows:
“Shuffling or re-ordering of bits of a data set or an array either randomly or in a pre-defined specific pattern is called as interleaving.”
“Random or a pre-defined specific pattern, following which the interleaving is performed, is called as interleavers.”
The above two definitions clarifies the basic difference between interleaving and interleavers respectively.
A simple mathematical definition of interleavers is given as follows 19 16:
“An interleaver is defined as a permutation which facilitates the one-to-one bit mapping of a data set of length- i.e. into a completely new data set, represented by , of the same length. Here, represents a permutation (interleaver) matrix. The transpose of i.e. is a de-interleaving matrix required at the receiving end to rearrange the data set into its original order.”
For instance, assume a data set of length-6 to be interleaved. The permutation pattern (i.e. interleaver) is assigned to data set . The mapping provides a permuted (i.e. interleaved) data set . This method can be extended on a data set of any length. The method is applicable at inter-frame and intra-frame levels. Figure 3.3 illustrates the functioning of interleaver.
Abbildung in dieser Leseprobe nicht enthalten
Figure 3: Illustration of functioning of interleaver
Several types of interleavers have been developed and analyzed. Every interleaver has its own certain advantages and disadvantages. Apart from the distribution or shuffling of bits of a data set and controlling the burst errors, interleavers add robustness in communication systems. The so called randomization adds security of data. Interleavers can be employed in advanced multiple access systems as a mean to distinguish among the various users i.e. each user can be assigned an interleaver that can be the only identity of the user on a communication network 20-30. The interleavers help in achieving the better QoS for modern day’s communication systems. Some other advantages of interleavers are application specific which is covered in section-4 along with applications of interleavers.
5. MAJOR TYPES OF INTERLEAVERS
Interleavers have significance in multiple independent domains. Several types of interleavers have been developed accordingly as per the requirements of these domains. In this section, introduction to some of these interleavers is being covered. Since the list containing different types of interleavers is large. Therefore, detailed introduction of only few of the selected interleavers is being presented here. From the study of literature, following interleavers have been selected for detailed description:
- Random Interleavers
- Cyclic Shift Interleavers
- Power Interleavers; also known as ‘Master Random Interleavers’
- Prime Number Interleavers
- Tree Interleavers
- Inverse Tree Interleavers (ITI)
- Modern Fisher-Yates Interleavers (MFYI)
The different selection criterions to choose only these interleavers for detailed description are:
i) relevance to the proposed work in this tutorial,
ii) popularity of interleavers among researchers,
iii) availability of sufficient reliable sources in literature to reproduce these interleavers,
iv) area-specific applications; especially in those domains where the proposed novel interleavers also have the similar applications i.e. wireless and digital communications and information theory and coding.
Thus, these interleavers have been logically chosen for detailed description and performance comparison in this tutorial.
5.1. RANDOM INTERLEAVERS
Random interleavers are one of the most popular and competitive interleavers often employed in advanced multiple access systems e.g. IDMA, integrated IDMA (IIDMA) systems etc. Random interleavers resemble the use of a random permutation to shuffle the bits of an input data set.
The random interleaving mechanism is illustrated in figure 4. It is notable to avoid confusion that the terms ‘interleaving’ and ‘interleavers’ are being used interchangeably. The interleaving performed here is random in nature because there is no specific pattern is followed to shuffle the bits of initial data set. The mechanism to generate the random permutation may differ as there are various random data shuffling algorithms are available in the literature.
Abbildung in dieser Leseprobe nicht enthalten
Figure 4: Illustration of random interleaving mechanism
Actual idea of such random data shuffle was coined by R. Fisher and F. Yates in somewhere around 1938. However, same group of the authors i.e. Fisher et al. (1948) presented and popularized the most basic form of random data shuffle in 31. The algorithm proposed in this work was associated with high complexity i.e. . Therefore, Durstenfeld (1964) and Knuth et al. (1973, 75, 76) modified this random permutation algorithm in different ways and presented better versions of this algorithm with reduced complexity 32-35. However, none of these algorithms were initially deployed in interleaving applications. Ramsay (1970) proposed optimum random data shuffle algorithm 18. This algorithm was adopted by many researchers in the area of interleaving 10 12 17 36 37. Pseudo random interleavers were proposed for convolutional interleaving in 13. Similarly, various other algorithms exist to generate random interleavers.
For understanding random interleaver generation mechanism, let us take Fisher-Yates’s shuffle algorithm as a reference. This algorithm can be understood with the help of following example shown in figure 5.
Abbildung in dieser Leseprobe nicht enthalten
[...]