Investigation Of Interleaving To Combat Burst Errors Computer Science Essay

Published:

The following report is based on the detailed investigation of interleaving to combat burst errors describing the various coding techniques used along with the different interleaving methods. It mainly deals with the block interleaving and convolutional interleaving with a brief description of the helical interleaving. The encoding and decoding techniques discussed are from the simple Single Parity Check codes and Hamming Codes to the higher complex codes like the Cyclic codes, Convolutional Codes and the Reed Solomon Codes. Further to support the theory, simulations are conducted to rationalise how these coding techniques along with interleaving reduce the burst errors.

Thus, detailed comparisons and analysis of the results obtained by simulations is made with the help of BER v/s Eb/No waterfall curves to affirm the performance efficiencies of the coding techniques with interleaving combined. Furthermore, the report ends with a description of the evolution of these coding techniques along with interleaving to bring out concatenated codes which are more resistant to burst errors.

TABLE OF CONTENTS

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

[Table of contents is automatically generated if you use section headings. Otherwise, create your own table of contents here. To update the Table of contents, Right-click on the TOC area and click Update Fields. Ensure that you do not modify any text in the TOC area. All modification should be performed in the appropriate chapter/sub-chapter/sub-sub-chapter.]

LIST OF FIGURES

[List of tables is automatically generated if you use figure captions. Otherwise, create your own list of figures here. To update the List of Tables, Right-click on the LOF area and click Update Fields. Ensure that you do not modify any text in the LOF area. All modification should be performed in the appropriate caption of the figure.]

GLOSSARY

The following report gives you a detailed study of interleaving in the communication channel along with the various coding techniques used to bring out a minimal erroneous channel or transmission media against naturally occurring burst errors.

Coding

In the nearly seven decades that have passed since the original work of Shannon, Hamming and Golay, error control coding has matured into a important branch of the communication systems engineering. The field of coding has yielded a number of coding techniques that are in use today to combat errors produced during the transmission. Consequently one sees today an increase in the use of error control coding in the digital communication world. Mainly because of the stringent requirements in electronic bank data transfers and confidential file transfers which require an error probability of almost zero [4].

In layman's language Error control coding is defined as delivering information from a source to destination with a minimum of errors. Usually, the error control coding is provided by introducing redundancy in the transmissions ,where in certain symbols are added into the message stream that are strictly needed just to convey whether information is transmitted correctly. The major benefits of coding are it increases the operational range of a communication system, reduce the error rates, and reduce the transmitted power requirements [2]. The detection and correction of the error plays an important role in the ever growing digital information media. Errors almost occur inevitably during the transmission, storage or processing of information because of the noise and interference in the communication channel or imperfections in the storage media [3]. Further coding improves the performance by eliminating intersymbol interference caused by filtering and multipath, and improves demodulation of certain frequency modulated signals by taking advantage of the natural coding provided by continuous phase [1].These coding techniques along with the decreasing costs of digital circuits help the communication system design engineer to achieve cost effective means to achieve highly efficient and reliable communication. [4]

Project Aim & Objectives:

Invariably every communication system will have noise which impairs the transmission of data within the channel and thereby degrading the channel performance. Most of these errors are detected and corrected with the use of encoders and decoders but the detrimental effect caused by the burst errors needs special technique called interleaving for detection and correction. The aim of this project is to investigate interleaving with various coding techniques that can be used to minimize or nullify the detrimental effect of the burst errors in a digital communication channel. The main coding techniques used along with interleaving are the Hamming Code, Cyclic Code, Convolutional Codes and Reed Solomon Codes. Further, after the complete understanding of the following techniques a double interleaved and coded technique called the concatenated code is discussed. For a better understanding of these techniques simulations are carried out to showcase how these techniques are employed in a bursty environment to achieve reliable transmission.

Organisation of Report:

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

The detailed structure of the report is as follows:

Chapter 1 an introduction to the project providing a fair idea of what it is based on and what are the aim and objectives of it along with its cost and marketability.

Chapter 2 gives an insight into what are burst errors and the sources producing it. Also it describes the performance problems faced by communication systems affected by burst errors.

Chapter 3 gives a detailed study of different types of interleaving used in the communication systems to reduce the detrimental effects of the burst errors.

Chapter 4 will give an in depth comprehension or understanding of the techniques of coding used in this report. The main techniques discussed are the Hamming Codes, Convolutional Codes, Cyclic codes and Reed Solomon Codes.

Chapter 5 will picturise and describe the basic block structures required for the simulation of a communication system, with a brief description of what each block does during transmission of data in a communication channel.

Chapter 6 involves results and analysis of various simulations performed during the course of work. It showcases the performance metrics of the different coding methods with or without interleaving. Moreover, comparisons have been done to state the efficiencies of these techniques. The comparisons are mainly based on the BER v/s Eb/No waveform plots.

Chapter 7 this gives a concise summary of the major findings for the work conducted in this project together with comments and future recommendations relating to the current project work field.

Project Cost ,Feasibility and Product Marketability:

The project cost is kept in check as it requires just the MATLAB software tool along with the communication toolbox to create a simulation environment. So, the basic need for this project is a computer workstation running a latest version of software.

Techniques of interleaving strive at combating burst errors thereby making data more reliable, secure and error free in wireless transmission. In short they are essential for the betterment of network security. In term of the feasibility and marketability of the product, as network security always utilises techniques and ideas that make the communication system better and safe for data transactions. Thereby, this project adds more analysis to the network security market to make it more reliable, thus, is feasible and is marketable.

Figure ‎1

[To insert a caption for a picture, Right-Click on the picture and click on Caption, or alternatively, highlight the appropriate picture, select Insert->Reference->Caption. You are advised to use word to automatically generate and manage figure numbers. Otherwise, you'll end up having to manually adjust figure numbers to match List of Figures.]

An introduction to Burst Errors:

Noise is the most prevalent factor limiting the performance of a communication system. There are majorly two noises i.e. impulse noise and thermal noise that affect the performance of the communication system. [4]

Thermal noise is always present in the electrical circuitry at the front end of the receiving equipment .the thermal noise since being a ever present noise is steady in its power levels , and has Gaussian amplitude statistics. Therefore, the thermal noise errors tend to occur independently from one signalling interval to the next and are derivable straightforward with the knowledge of Gaussian distribution and corrected.[4]

On the other hand impulse noise can be either atmospheric noise due to the thunderstorms on transmission lines or a transient noise due to repeated switching. This impulse noise presents a case where there is a long smooth transmission of data with sudden punctuations presenting short period of intense noise. This relatively short period of intense noise is called burst errors and corrupts a continuous string of symbols or bits. [4] A burst in a block code can be defined as the number of positions at error from the first error position through till the last error position. The error correction procedure for the burst errors is called as error trapping or burst trapping. [6] The best solution to reduce the detrimental effects of the burst error is to interleave the data and transmit them thereby the burst error is wide spread and is handled as independent errors for correction at the decoders with better performance.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

burst.jpg

Figure ‎2 Burst Errors [6]

Interleaving

Interleaving is a simple and effective way to improve the performance of an error correction scheme on a bursty channel. The interleaving of code words will spread the effect of long burst errors into short bursts over several encoded code words instead of a single codeword, and thus the chosen error correction scheme can correct them independently. [6]

Interleaving is done by reordering the bits before transmission and putting them back into the original order on reception. As the error locations are affected only by the deinterleaving, they become scattered through the code stream so that they appear as random errors to the decoder. In short a bursty error channel is transformed into an independent error channel, for which, many effective coding techniques are applicable. [2, 4]

Basically there are three major types of interleaving, namely, block interleaving, convolutional interleaving and helical interleaving. Each of these interleaving methods are described in detail in the sections to follow.

Block Interleaver

In block interleaving code words are written into columns of an array and the total number of column within a block is termed as the interleaving degree. Usually the interleaving degree is denoted by λ thereby if a burst error spans no more than λ symbols, then there will be at most one error in each code word. Usually for a simple interleaver the block codes are read in row wise into the frame which is called the interleaving frame and the encoded data is read out column wise. The block interleaving is found as suitable application for BCH codes on high frequency radio channel. There are two important system design issues to be taken into account for designing an interleaved communication system. Firstly, an additional level of framing or synchronization is required, namely, synchronization of the interleaver and the deinterleaver. Secondly, for most real communication channel a large interleaver is required to provide significant enhancements which can cause sizeable time delay which is not acceptable in voice communication. Therefore, block interleaving is used where there are tolerable levels of time delay and is feasible. [4]

Figure 3-1 Block Interleaving

Convolutional Interleaving:

Convolutional interleaving can be done in many different ways but the main concept behind it is the shifting of the code words into memory cells with a certain amount of delay before they are transmitted out [10]. The method of Convolutional Interleaving considered in this report is as shown in the figure below:

Figure 3 Convolutional Interleaving [4]

The code words in the columns of the array are shifted through delays which differ for each symbol. Usually the delay increases by one for each row of the array. The order in which they are shifted out are as shown in the figure above it is usually shifted of diagonally in a pyramidical structure. Any burst of errors will affect symbols in the transmission as shown and it can be seen that the burst must exceed n+ 1 symbol in length before it affects two symbols of the same codeword. If the delays increase by a degree D for each symbol then the separation of two symbols of the same codeword is Dn+1 which in turn is the interleaving degree for the convolutional interleaving. [4]

The main difference between block interleaving and convolutional interleaving are that the convolutional interleaver will extend the symbol stream through the presence of null values in the delay registers whereas in the block interleaving more delay is caused due to the need to fill the array before transmission can commence. [4]

Helical Interleaving:

Figure 3-3 Helical Interleaving [11]

The helical interleaver over comes the shortcomings of the block interleaver and convolutional interleaver it eases the pressure of synchronization of the interleaved codes between transmitter and the receiver. In the helical interleaver the synchronisation is achieved by adding a sync symbol between two consecutive code words transmitted.

The helical interleaving can be explained form the figure above. The code words are written in columns as shown above. The numbers define the sequence in which the blocks are transmitted. When the blocks are completely read into the columns it is transmitted or read out row wise. This helical interleaver used in the example has a code length of 6 and a depth of 3. The burst error must be more than 3 or more than the code depth of the helical interleaver to affect a code word more than once. As the consecutive code words are separated by 6 symbols the receiver has to know synchronization modulo 6. The entire process of interleaving and deinterleaving is symmetric in the case of helical interleavers.

The helical interleaver has a restriction on the depth of interleaving. If all code words have to fit into the columns before the repetitions start to occur the depth of the interleaver should be a prime to the codeword length. This restriction is voided in the new type of interleaving called the helical block interleaving which defines that the any interleaving depth (D) can be used to interleave N symbols. This is done by making sure D is prime to N and any D consecutive interleaved symbols belong to different encoded code words. Also any two consecutive sync symbols in the interleaved sequence are separated by exactly N symbols. Thereby the block helical interleaving uses all the modifications above along with reading the ND symbols in the interleaving array, only once, and eliminating the depth restriction while holding a good deinterleaving synchronization. Helical interleaving thus gives a better performance over all other interleaving with better synchronization and has a very hardware efficient design [6].

Error Control and Coding Techniques:

4.1 Basic of error control:

In data communication it is common for data symbol errors to occur more frequently than can be tolerated by an application and it happens so if the data transmissions are pushed close to the channel capacity. Errors can be reduced to acceptable levels by a combination of error detection and error correction. [12] Basically error control coding is concerned with methods of delivering information from source to destination with minimum number of errors. It was the work of Shannon that proved that a communication channel could be characterized by a capacity at which information could be reliably transmitted i.e. at any rate of information transmission up to the channel capacity, it should be possible to transfer information at error rates that can be reduced to any desired level. [2] Although there are many coding schemes that take in many different forms to fight error but all of them have two common basic principles in their techniques. Firstly, the use of redundancy that is the coded symbols will always have extra or redundant symbols. These symbols are used to accentuate the uniqueness of each message. They are so chosen that they make the code unique that it is very unlikely for the channel disturbance to corrupt enough of the symbols in a message to destroy its uniqueness. Secondly, the use of noise averaging which is done by making sure that the averaging effect is obtained by making the redundant symbols dependent on a span of several information symbols. [1]

Further there are basically two mechanisms for adding redundancy. These two basic mechanisms are block coding and convolutional coding. If the error detecting codes are organized in fixed length blocks of symbols it is referred to as block code .error detection is performed separately on each block to determine whether the block does or does not have any error. The trellis or the convolutional code is a class of coding that does not require segregation into blocks, it works on a special kind of trellis code where the coding process is a linear operation. To add to it there is another type of coding technique that is an evolution from these coding techniques called the concatenated coding. The concatenated codes have codes within codes. Usually the decoding process is broken down to two stages wherein the inner and the outer codes can be either block codes or convolutional codes. [12]

4.2 single parity check code:

The fundamental concept of parity check block codes are that the encoder accepts k information bits from the information source and appends asset of r parity-check digits, which are dereived from the information digits in accordance with a prescribed encoding rule. Usually the encoding rule determines the mathematical structure of the code. The total information bits transmitted is given by n=k+r. this kind of codes are usually called (n, k) block code. The n-bit block is called the code block or code word, n is called the block length. The code rate is defined by the ratio [4]:

Equation 4.1

A very simple parity check code is the one that uses single parity check bit i.e. a single bit that is appended to the end of the code word. This bit is called either parity bit or check bit which is appended to a block of k information bits. This check bit is so chosen that it satisfies the overall parity of the codeword. The encoding of the single parity check code can be described by the equation below [4]:

Equation 4.2

Where are the arbitrary information bits and is the parity bit. The equation above shows that the parity bit should be so chosen that the total number of ones within the codeword inclusive of the parity bit should be 'even' giving a modulo 2 sum of zero.

Equation 4.3

The above equation displays the condition for odd parity wherein the parity bit should be so chosen that the modulo 2 sum of all the information bits inclusive of the parity bit should be one. [4]

Once the code words are transmitted over the communication channel, it is received and processed by the decoder. At the decoder, the received codeword may possibly contain transmission errors which are checked to determine whether or not the parity relationship is satisfied by calculating the sum, S. This is done by the equation given below:

Equation 4.4

Considering an even parity at the decoder if S=0 the decoder assumes that the code word was received correctly and removes the parity bit and releases the n-1 information bits. If S=1, the decoder declares the received code to be in error. [4]

Further this kind of single parity check codes can have two decoding outcomes. Firstly, it can detect all the odd number of errors within the codeword. This kind of detection or decoding output is defined as error detection or decoding failure. Secondly, when there are even numbers of errors it goes undetected and this type of decoding outcome is defined as incorrect decoding. [4]

These kinds of parity check codes find their application in transmission of ASCII characters and in hardware application like transmission in SCSI and PCI buses. [4]

4.3 Hamming Code:

This is the widely used class of the linear block codes. For any positive integer m≥3, there exists a hamming code with the following characteristics:

Length n = 2m-1

Number of message bits k=2m-m-1

Number of parity check bits n-k=m

Error correction capability t=1,(dmin =3 )

The parity check matrix H is formed by the non-zero columns of m bits, and can be implemented in systematic form:

Equation 4.5

Where the identity sub matrix Im is a square matrix of size mÃ-m and the sub matrix Q consists of the 2m-m-1 columns formed with vectors of weight 2 or more .[3]

Let us consider an example of the most commonly used (7, 4) hamming code. Here the previously defined m equals 3. The matrix representation for the hamming code is as shown below:

H =

Figure 4-1 Hamming Parity Matrix [2]

In the above matrix, the rows of the matrix H are of even parity where in the scalar product of any codeword with any row will be zero [2]. The parity bits are calculated as shown in the figure below:

p0=a0+a1+a2

p1=a1+a2+a3

p2=a0+a1+a3.

Figure 4-2 Parity Check Bits Calculation [13]

In the above equations '+' denotes modulo-2 addition and p0, p1 and p2 are parity check bits whereas the a0, a1, a2, a3 are the given data bits.[13]

At the decoder it receives a seven-bit senseword = (a0', a1', a2', a3', p0', p1', p2') further to check for error detection and correction 'syndromes' are calculated and are given by the equations shown in the figure below:

s0=p0'+a0'+a1'+a2'

s1=p1'+a1'+a2'+a3'

s2=p2'+a0'+a1'+a3'

Figure 4-3 syndrome calculation

The three bit pattern syndrome (s0, s1, s2) does not depend on the actual data bits but only on the error pattern. There are eight possible syndromes one that corresponds to no error and one for the each of the seven other possible patterns with a single error. The only restriction on the hamming code is the minimum distance must be 3 and have a check matrix all of whose columns are distinct and non zero. [13]

4.4 Cyclic Codes:

The cyclic codes are a subclass of the linear block codes. The cyclic codes follow the theory of the Galois field. [13] For a certain values of n the polynomial codes exhibit a cyclic property. This cyclic permutation of the symbols in a code word generates a new codeword this property is the principle of the cyclic codes. [1] All the properties of the block code like linearity and the associated techniques apply to the cyclic codes. The special methods that are employed for the encoding and decoding o f the cyclic codes are best understood through the use of an algebra in which a polynomial is used to represent sequences. In the polynomial representation shown below, a multiplication by X represents a shift to the left, i.e. one position earlier in the sequence. The terms in a polynomial represent the positions of the ones in the sequence, the rightmost position being the X0 position, the next left position being the X1 position and the next being the X 2 position till the leftmost bit. The generator sequence for the codeword 1011 is given as below [2]:

Equation 4-6

The basic property of the cyclic codes can be defined such that a 'n' code symbol sequence can be represented either as an n-dimensional vector or by a polynomial of degree < n. The n dimensional vector can be represented as (c0, c1, c2… cn-1Xn-1) can be represented as:

Equation 4-7

It can be seen from the above equation that a cyclic code is a parity check code for which every cyclic shift of a code word is a code word. Further it can be seen that a (n,k) cyclic code with symbols in GF(q) has a unique lowest degree polynomial code word g(X) which is called the generator polynomial and has the following properties:

The degree of g(X) is n-k

Every code word has g(X) as a factor, and any polynomial over GF(q) in the form a(X)g(X),where the degree of a(X)<k, is a code word.

g(X) is a factor of Xn-1

The code words g(X), Xg(X), X2g(X),…….., Xk-1g(X) form a linearly independent set of k code words that as vectors span the space of code words. These code words as n-tuples could be used as the rows of a generator matrix for the code.

Thus any g(X) over the Galois field, GF(q) that substantiates the first and the third point above will generate a (n,k) cyclic code.[12]

4.4.1 Cyclic Codes for Burst Error Correction:

The cyclic codes posses' particular properties that make it very good for the burst error detection and not all of them posses it in the cyclic code family. Now as it is known that the cyclic code property means that any consecutive n-k consecutive symbols can be shifted into the parity positions and we shall still have a codeword. Any error in the parity symbols cannot produce a codeword result because the parity symbols are firmly fixed by the information. Thus, any error that spans n-k symbols or less of a cyclic codeword cannot produce a codeword result and is therefore detectable. The cyclic nature of the code means that if the error affect the first few symbols or the last few symbols considered as a single end around burst and is as shown in the figure below[2]:

Figure 4.4 End around Burst of Length 6 [2]

The maximum length of the correctable single burst within one code word is (n-k)/2. The usual decoding method for burst error correction is called error trapping and if the error pattern occupies at most (n-k)/2 consecutive symbols then we can detect this condition by the existence of (n-k)/2 consecutive zeros in the syndrome. Thus, the number of shifts to achieve this condition will show where the burst is located. [2]

4.4.2 Fire Codes:

Fire codes are cyclic codes that can correct single-burst errors with a syndrome that can be split into two components for faster decoding. The way in which the generator polynomial can be represented correcting a single burst of length up to l is:

g(X) =(X2l-1+1)h(X)

Equation 4-8

where h(X) is an irreducible binary polynomial of degree m ≥ l which is not a factor of X2l-1+1.to make it more clear let us consider an example where in h(X)=X4+X+1.this is a primitive polynomial of degree 4 which is therefore not a factor of X7+1. Therefore the polynomial will be:

g(X) =(X7+1) (X4+X+1)

Equation 4-9

The above polynomial generates a (105, 94) Fire code which can correct single bursts of length 4. [2]

4.5 Convolutional Code:

Convolutional codes are one of the important trellis codes in use for the modern times. In contrast to the block codes the trellis code also encodes a stream of data symbols into a stream of code symbols. It divides the data stream into a block of length k, called data frames. Which are usually smaller and are encoded into a block length of 'n', called codeframes. In block codes the codestream depends only on a single block of the data stream, whereas in the trellis code a single frame of code stream depends on multiple frames of data stream. The convolutional codes are trellis codes that satisfy additional linearity and time variance properties[13].

The data frames of the convolutional codes are small and typically contain no more than a few data symbols. As defined before the length of the data frame corresponds to 'k' and the length of the code frame corresponds to 'n'. Rather than coding a single dataframe into a single codeframe, the coding is done by connecting a dataframe with 'm' previous dataframes into a single codeframe. These successive code frames are linked together to form a concatenated stream to form an infinitely long codeword[13].

Figure 4-5 Shift Register Encoder [13]

The covolutional code and the trellis code can be explained by the basic shift register encoder as shown in the above figure. The incoming data frame is broken down into dataframes of 'k' symbols wherein the encoder can store 'm' dataframes, 'm' is called the frame memory of the encoder. A new 'm' number of frames are shifted in when the same number of frames are shifted out and discarded. Hence the channel must transmit 'n' code symbols to every 'k' data symbols transmitted .The set of code sequences produced by such encoder is called (n,k) convolutional code or (n,k) trellis code. This encoder has a code rate of k/n.[13]

A convolutional code is required to have two distinctive properties called the time invariance and linearity. Time invariance means if the datastream is delayed by a single dataframe then the code stream is delayed by a single code frame, this is done by zero padding in both the cases. Linearity means linear combination of any two data streams has a single codeword that is the same linear combination of the codewords of the two datastreams. Considering an example for the case of linearity for more clarity we have two data streams a1 and a2 with codewords G(a1) and G(a2), then βa1+γa2 has code word:

Equation 4-10

These two properties are not required for a trellis code thus a linear and time invariant (n, k) trellis code is a (n,k) convolutional code. Further because of implementation considerations the convolutional codes use very small integers for 'k' and 'n'. Also for the number of q-ary memory cells in a minimal encoder for a convolutional code is an important descriptor of the code and is called the constraint length and is defined by v .If two convolutional codes are of the same except for the order of the components within a frame are called equivalent convolutional codes. [13]

Figure 4-6 An encoder for (2,1) convolutional code

The above figure describes a k=1 and n=2 convolutional encoder over GF(2) where in the binary data stream is shifted into the encoder and the corresponding codestream is shifted out two output code bits for each input data bit.[13]

4.5.1 Convolutional codes for burst error correction:

A burst of length t is a sequence of t symbols, first and last of which are a non zero. A convolutional code is infinitely code and error can occur frequently anywhere in the sense word. Usually if there are infrequent burst of error on the senseword then the decoder needs to contend with only one error burst at a time. If a decoder can correct a single error burst of t provided the other burst error are spaced far enough on the code then it's found to correct a error of length t in the senseword . Thus this convolution code is said to have an error correction capability of t. the convolutional codes can correct larger error with the use of interleaving to get a (jn,jk) code from a (n,k) convolutional code . This can be done by getting j copies of the encoder and merge the codewords by alternating the symbol. If the original code could correct 't' length of bursts after interleaving it would be able to correct 'j*t' length of burst.

A class of binary convolutional codes used specifically to correct burst errors is called the Iwadare codes. An (n, n-1) Iwadare code is defined in terms of λ and can correct any burst of length t=λn or less. An unending sequence of burst errors can be corrected provided successive burst errors are separated by a guard space of not less than n(2n-1)(λ+1)-n bits. The decoders used for the convolutional codes were at first the simple syndrome decoders to complex sequential decoders but then eventually slowly evolved to use of simple decoders for simple codes such as the viterbi algorithms. [13]