Codes For Error Free Transmission Computer Science Essay

Published:

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

Error Detection and Correction or Error Control is techniques that enable reliable delivery of Digital data over Unreliable Communication [1],[2] Channel. Some Codes will provide only Error detection and some will provide Detection also. Forward Error Correction is now needed in all types of Digital Communication Systems for receiving error free digital data without the need for retransmission of data which is the backbone for Space Communications. Shannon Channel Capacity Limit is universal. All the types of codes which is used for Error Detection and Correction Should achieve the performance close to the Shannon limit so that reliable Error free transmission is achieved even at bad channel conditions. Channel coding techniques are widely used in Satellite transmission. The NASA and ESA use all possible techniques to make error free [11] transmission. Deep Space Communications are very difficult without proper employment of channel coding techniques as the noise level in the Space is extremely high than earth atmosphere. There are many types of codes used for error free transmission. Linear codes, Convolution codes and Turbo Codes play an important role in Communication engineering. In this paper am going to explain more in detail about the structure, encoding, decoding,code performance in AWGN channel conditions and applications of these codes at NASA space missions.

2) LINEAR CODES:

Linear code is an Error correcting code for which any linear combination of code-words is another codeword. [2].They are used for Forward Error correction. Some examples of Linear codes are 1)Parity Codes 2) Repetition Codes 3) Cyclic Codes 4)Hamming Codes 5)Reed-Solomon Codes 5)Reed-Muller Codes 6)Linear density parity check codes . Linear codes are classified into two types of codes namely Block Codes and Convolution codes. Hamming Distance between any two distinct code-words is needed for the estimation possible received message (Code-word).If we want to correct one error in a codeword the minimum Hamming distance should be three. The first Error correcting code was invented by Richard W. Hamming Bell Telephone Laboratories

2.1) Linear Block codes:

The encoder for a linear block code divides the information sequence into blocks. Linear block codes are a class of parity check codes that can be characterized by the notation (n, k) .The encoder transforms a block of k message bits into a longer block of n code-word bits called a code vector. The k-bit messages form 2k distinct message sequences referred to as k-tuples (sequence of k digits).[1] The n-bit blocks can form as many as 2^n distinct sequences referred to as n-tuples . A block code represents a one-to-one mapping of all set of message sequences to all possible code-word set. The mapping is Linear therefore it is called as Linear Block Codes.

Generator Matrix :

If the information bits are very large we can't use the look up table implementation of the encoder to find the possible codeword.[1] The main drawback is the memory of the encoder for storing the all possible codeword set .Generator Matrix generates the code-words when in need so that the complexity of storing all the possible codeword set in the encoder is reduced. Generator Matrix in general is (k Ã- n) array. G= [v1 v2.....vk]

Message m, a sequence of k message bits is given by m= m1,m2,....,mk The generation of the codeword U is given by the product of G and m

U= mÃ-G

Generator matrix consist of two elements 1) Parity array portion 2) Identity Matrix

G= [P: Ik]

P-Parity Array portion

Ik-Identity Matrix

Error Detection and Correction Using Linear Block Codes:

Error Correction is done by using Syndrome testing procedure, Let r be a received vector resulting from the transmission of U. The received vector is given as r= U+e , where e denotes the error vector e= e1,e2,.....,en is the error pattern introduced by the channel during transmission . The syndrome of r is defined as S =rÃ-HT . If r has some correctable errors it will have some non-zero value .if S= 0 then that codeword is the valid member in the codeword set. [3] Next we have to verify that the syndrome of the erroneous code vector is the same as the syndrome of the error pattern that caused the error . Syndrome of the error pattern is calculated by S=eÃ-HT

Error Correction procedure:

Calculate the syndrome of r. Locate the error pattern. Error pattern is assumed to be corruption caused by the channel.We can get the valid codeword by subtracting out the identified error ( in modulo2 arithmetic we can assume subtraction as addition )

Applications of Linear Block codes:

Compression of data in computers to reduce network load

To correct for scratches and dust in CD

Mobile Communications to reduce multi-path fading

Linear block codes provide powerful Channel coding techniques that are used by the NASA

e) Performance of Linear Block codes:

Code performance is commonly measured against channel capacity. The Capacity curve is associated with EB/N0. For many codes the error correcting capability does not come for free. For achieving such performance over AWGN channel Trade-off between Signal bandwidth and Data rate is very big issue especially when measuring performance of Linear Block codes in AWGN channel. When Compared with Convolution and Turbo codes, linear block codes performance is very low.

(Fig1)Performance of Linear Block codes

(Fig1)We use BPSK Modulation and AWGN channel conditions for the above graph explaining about the Performance of Linear Block Codes. All depends upon the Decoding Algorithm and simulation tools used for estimating the code performance.

Applications of Linear Block Codes in NASA Space missions:

Low density parity check codes is a Class of Linear Codes which are widely used in Near-Earth and Deep Space Communications. LDPC codes with code rate =7/8 are used for Space Communications. All the Future Space missions will put severe constraints on communication links in terms of data rate, bandwidth occupancy, performance and complexity. The NASA missions to Jupiter and Saturn in the year 1979 and 1981 used binary golay codes for getting higher resolution images from the planets. Golay codes are also a class of linear block codes. Reed Solomon codes are also used for deep space and submarine communications.

3) CONVOLUTIONAL CODES:

Convolutional codes are widely used in telecommunications. Convolutional codes map information to code bits sequentially by convolving a sequence of information bits[1] with "generator" sequences. Convolutional codes are generally specified by three parameters, (n, k , m) where n= number of output bits , k= no of input bits ,m= number of memory registers. Generally for calculating the efficiency of the code we use code-rate that is given by R=k/n. code rate 1/8 to 7/8 is used for deep space communications Convolutional code chip manufacturers will specify the code parameters by (n , k , L) , where L denotes the constraint length of the code, which is given by L=k(m-1) .

ENCODER STRUCTURE:

A binary convolutional encoder takes a stream of information bits and converts into a set of all possible code-words using shift registers. Convolutional codes were first introduced by Elias in the year 1955 as an alternative to block codes. The main difference between convolutional codes and block codes is that convolutional code encoder contains memory and the encoder output at any given time unit depends not only on the current inputs but also on previous inputs. Convolutional code encoder can be implemented with a digital sequential circuit [4]. The major building block of the circuits is shift registers and modulo-2-adders which is shown below.

(Fig 2) Convolutional Encoder

3.2 Encoding Procedure:

The information sequence enters the encoder one bit at a time

The shift registers shifts the information bits bit by bit

The output sequences are obtained by the convolution of input sequence u with two encoder's impulse responses

The impulse responses can be from generator matrix or generator polynomial

We get the encoder output as discrete convolution operation between the input sequence u and impulse responses

A convolutional encoder belongs to a class of devices known as [1] finite-state machine. There are many ways to represent convolutional code encoder the best among them are 1) state diagram representation 2) Tree diagram 3) Trellis diagram

3.3 Decoding algorithm:

When encoded information is transmitted in a channel it gets distorted. The convolutional code decoder regenerates the information by estimating the likely path of state transition in the trellis. There are several different approaches to the decoding of convolutional codes they are 1) Sequential decoding-Fano decoding algorithm 2) Maximum likelihood decoding algorithm

Sequential decoding:

In sequential decoding we are dealing with only one path of the trellis at a time. Sequential decoding allows both forward and backward movements through the trellis. The decoder keeps track of its decisions if it makes an ambiguous decision it tallies, If the number of tallies increases faster than some threshold value the decoder gives up that path and retraces the path back to the last fork where the tally was below the threshold. The memory requirement of sequential decoding is manageable and so this method is used with long constraint length codes where S/N is also low. Some NASA space missions have used sequential decoding.

Maximum-Likelihood decoding (viterbi algorithm) :

Viterbi decoding is the best known implementation of Maximum decoding algorithm. The viterbi algorithm consists of three major parts 1) Branch metric calculation 2)path metric calculation 3)Trace-back. Branch metric calculation differs for hard decision and Soft decision decoders. For a[4] Hard decision decoder branch metric is finding the minimum Hamming distance between the possible set of received code-words and for a soft decision decoder we calculate the Euclidean distance between the code-words. The advantage of viterbi decoding is that complexity of a viterbi decoder is not a function of number of symbols in the code-word sequence .The main aim of viterbi decoder is to find the survivor path. The selection of survivor paths is performed for all the states .The decoder makes decision by eliminating the least likely paths. Viterbi decoder is the optimum decoder for the decoding of convolutional codes.

3.4 PERFORMANCE OF CONVOLUTION CODES:

When comparing Linear block codes performance of convolutional codes is very optimum in the AWGN channel .For Bluetooth transmissions convolutional codes helps in achieving the performance that the system needed for reliable communication via the channel. for Bluetooth transmission Rayleigh field channel is used. The simulation result (Fig 3) shows that the convolution code performance in AWGN channel .It shows the performance of ½ rate convolutional code by plotting BER Vs EB/N0 using BPSK modulation.

C:\Users\user\Downloads\simulationresults.jpg(Fig 3)Performance of Convolutional codes

3.5 Applications of Convolutional codes:

Satellite Communications

Digital video broadcasting

Telecommunications

Submarine Communications

Bluetooth Communications

CDMA technology

3.6 Convolution codes in NASA space missions:

Viterbi decoded convolutional codes are used in space missions from the voyager program which was one of the United States of America unmanned space missions to Saturn and Jupiter. ½ code rate with constraint length 7 was used. Other NASA space missions which used convolutional codes are Mars path finder, Mars exploration rover and the cassini probe to Saturn. Punctured convolutional codes then made advancement in all the NASA space missions before the introduction of turbo codes.

4. TURBO-CODES:

Turbo-codes were first introduced by Berrou, Glaveiux and Thitimajshima in the year 1993.Turbo-codes[3] finds application in deep space communications and in bandwidth constrained communication links. The major competence for Turbo-codes is LDPC codes. This code is a parallel concatenation of two component convolutional codes separated by a random interleaver. One big advantage of turbo-codes is that there is enough code structure to decode efficiently. In technical terms turbo-codes is defined as parallel concatenated convolutional codes. Random codes are very difficult to decode, the solution for this problem is turbo codes because randomness is achieved through interleaving. Turbo codes achieve most of the gain promised by the channel coding theorem.

4.1 TURBO ENCODER:

In a simplified turbo encoder there are two convolutional encoders connected in parallel. In general we can have multiple turbo encoders. For simplification we are considering only two [4],[5] encoder branches. Convolution codes at each branch are called as consitituent codes (CC) .The CC can have same or different generator functions. A simple Turbo encoder is shown below.

(Fig 4) Turbo Encoder

Interleaver is used to scramble the information bits to achieve randomness. PAD is used to append the proper sequence of bits to terminate all the encoders to the zero state. The puncturing block is used to increase the code rate of the convolutional code and it depends upon the puncturing matrix. Puncturing matrix calculations are used in space communication applications.

4.2 TURBO DECODER:

The turbo decoder works in an iterative manner. We are considering only one iteration at a time. [4] In practical situations the number of iterations will not go beyond 18. The working principle of turbo-decoder is very simple. The first decoder will decode the sequence and it passes the hard decision to the second decoder. The second decoder will have extra information so that it can easily make its decision about the optimum received message. Turbo decoder works in the same way as a turbo engine so its name. A simplified Turbo decoder is shown below.

(Fig 5) Turbo Decoder

Soft output viterbi algorithm achieves the maximum likelihood decoding performance in Turbo-codes. The first introduced soft ouput decoding algorithm had some disadvantages. Normalised SOVA provides good optimum decoding algorithm for turbo-codes.

4.3 Applications of Turbo-Codes:

Satellite communications

Space Exploring Systems

Telecommunications

Image Processing

3G mobile telephony

Fibre Optic Communications

4.4 PERFORMANCE OF TURBO CODES:

Turbo-codes give good performance of bit error rate (BER) relatively at lower EB/N0. Turbo codes achieves BER=10-5 [4] over AWGN channel at EB/N0= 0.7 decibels which is very near to Shannon limit. When considering the Rayleigh fading channel turbo codes achieves a gain of 2.3 decibels more when comparing with classical convolutional codes at BER =10-5 . The turbo code performance also depends upon the decoding algorithm used. This can be shown from the graph shown in (Fig 6)

(Fig 6) Performance of Turbo Codes

From (fig 6) the MAP decoding algorithm achieves the coding gain of 2 decibels than the soft output viterbi algorithm. MAP algorithm provides good error performance when compared with SOVA.

4.5 APPLICATIONS OF TURBO CODES IN NASA:

Turbo codes are best suited for deep space and near earth [11],[12] satellite communications. Turbo code version 4.2 with aero-elastic modifications was used for the Quick high speed fan flutter calculations. This forms the most important design parameter in NASA space shuttle and vehicle design. Turbo codes have found a place in all the NASA space missions from the year 1993.New NASA missions such as Mars Reconnaissance orbiter now use turbo codes as an alternative to RS-viterbi codes. Turbo codes make it possible to increase the data rate without increasing the transmission power. But the decoding complexity and high latency was the major problems when turbo codes used for space missions at NASA. Later they were solved by low complexity decoding algorithm like Fast chase decoding algorithm.

5. CONCLUSION:

For real time systems and for non-real time systems we need error free transmission. Real time applications in military need data without any error. All types of error detecting and correcting codes are playing an important role in all the communications links. ECC codes are used in all types of applications from computer communications to Deep space communications. Although the three types of codes are different in their performance they are very much suited for its own applications. So without proper channel coding techniques we can't assure reliable transmission in a noisy channel. Turbo codes outperformed both convolutional and linear block codes, because reliable transmission can be maintained even at low EB/N0.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.