This report is concerned with the encoding of the channel in the digital communication system. The purpose of this report is to present channel encoding which is a method that introduces redundancy in order to provide error detection and correction and error control, which have been caused by noise, interference, fading etc .It is method in which information sequence is converted and transformed into a encoded sequence. It may seem peculiar that in the source coding redundancy is removed and then it is added in channel encoding, but the redundancy here is introduced in a structured way to provide a capability for error control. The report explains the various methods and codes used in order bring control in the amount of error in the data conveyed. Channel encoding has been significant enabler in the telecommunications revolution, internet, space exploration and digital recording. An effort has been made to balance the engineering application and the mathematical implications by understanding the codes and the algorithms used which play a vital role in the encoding and decoding process. There is a detailed explanation of the different coding techniques and how they working on the error with a unique feature of every technique which is simplifying the vast field of coding.
1.1 Overview of Digital Communication.
Fig 1 Digital communication diagram
Fig2 Digital communication block diagram
Get your grade
or your money back
using our Essay Writing Service!
The block diagram shows the various stages of digital communication which are necessary to pass the information from the source to the destination. Source encoding of the message signal is followed by the channel encoding and modulation in the transmitter and then the corrupted modulated message is the digitally filtered and demodulation in the receiver, the demodulated message is followed by synchronisation, detection and data processing. Each stage is explained below
The source encoder converts analog signal like audio or video into digital signal and compress the data from the source by removing redundancy in order to transmit the data in a more efficient manner. This is found on a day to day practice in Internet where the "Zip" file for data compression is used to make files smaller and reduce network load .In source encoding analog signal like audio and video signal are used. The source signal and its waves are modulated with respective to time and the various methods for modulation used are .
Pulse Code Modulation (PCM), Differential PCM (DPCM), Adaptive DPCM(ADPCM)
Delta Modulation (DM), Sub-band coding etc.
Channel encoding introduces redundancy in order to provide error detection and correction and error control, which have been caused by noise, interference ,fading etc .It is method in which information sequence is converted and transformed into a encoded sequence. It may seem peculiar that in the source coding redundancy is removed and then it is added in channel encoding ,but the redundancy here is introduced in a structured way to provide a capability for error control .As the number of symbol at the input is less than the symbols at the out put of the coder .If the input symbols are 'k' and the out put symbols are 'n' then the rate of such a channel encoder is given by :
The input of the channel coder is called information or message bits. Some of the types of channel encoding methods which will be explained in detail are
1) Linear Block codes
2) Cylic codes
3) convolution codes
The symbols form the channel encoder are converted into signals which are appropriate for transmitting over the channel.. [Many channels require that the signals are sent as a continues time voltage, or electromagnetic waveform in a specified frequency band., this modulator provides appropriate channel confirming representation][Error correcting codintg by todd moon]. It is the method of varying amplitude, frequency and phase of the carrier wave with respect to the modulating wave. Some of the modulating schemes are as follows:
Always on Time
Marked to Standard
1)Frequency Shift keying
2)Binary Phase Shift Keying
3) Amplitude Shift Keying
4)Quadrature Phase Shift Keying
The transmission of signal takes place via the channel, like fibre optic cable , telephone cables microwave radio channels etc .A signal may have noise added or it may undergo attenuation due to the propagating distance or it may have time delays. Channels are influenced by noise, atmosphere like rain, clouds etc and non linearity of system .The method of creating multiple channels for transmission is called multiple Access :eg
1)Frequency Division Multiple Access Â Â
2)Code Division Multiple Access
3) Time Division Multiple Access
5)Â Frequency Hopping
These filters remove the out band components leaving the in band components required during the transmission. This process removes the frequencies below or above s particular frequency and thereby passing a range of frequencies or rejecting a set of frequencies. Some of the filters commonly used are:
1)Finite Impulse Response Filter Â Â
2)Infinite Impulse Response Filter
4)Fast Fourier Transform
5)Inverse Fast Fourier Transform
6) Hilbert Transform
It is the method of extracting the original signal form the modulated carrier wave .It is the reverse of modulation. In the reverse process coherent and non coherent carrier referencing is required.
This system is a "circuit used to estimate and compensate for frequency and phase differences between a received signal's carrier wave and the receiver's local oscillator for the purpose of coherent demodulation" like:
1)Delay Locked Loops
2)Phase Locked Loops
3)Frequency Locked Loops Â Â
It is the extraction of a particular bits from a large stream of information with having synchronisation with the source or sender. examples are:
1)Quadrature envelope detection
2)Squaring envelope detection
3)Peak signal envelope detection
The information from the detector in converted into a usable form. Some of the data processing examples are :
1)Bit to Symbol converter
2)Symbol to Bit converter
2.1 Need for channel encoding
Channel encoding introduces redundancy in order to provide error detection and correction and error control. Error correction is vital technology in order to improve the reliability if digital communication channels . There are many ways and techniques of correcting the error is also know as error correction but. Error correction techniques have two common elements in them
Redundancy-coded information or data will have some redundant or extra symbols bringing out the uniqueness in each message
Noise Averaging :noise averaging is done by making redundant symbols depends on span od several information symbols [ ]
Consider a communication channel having unwanted disturbances and error rate Pe=0.01
In the fig below we see that the curves gets smaller progressively as the length of the block goes on increasing if N is the length of the block and when N=10 we can see in the fig below that the curve is higher and at N=200 it is the steepest . therefore we can say that if the information symbols are programmed in blocks then one time . Best performance can be achieved by noise averaging as a result of increase in length .
2.2 Encoding and system improvement
In the below fig it is very clear that the from the graph for a given bit error probability Pb there is reduction in Eb/No which is called Energy per bit/ Noise Power Spectral Density(dB) the and when there is a bit error probability with coding and there is increase in the Eb/No when the bit error probability is without coding. We can therefore measure the coding gain between both point such that
Coding Gain =G[dB]= Eb/No(uncoded)(dB)- Eb/No(coded)(dB)
ERROR CONTROL TECHNIQUES
There are two basic approaches for error detection and correction
3.1Automatic Repeat Request (ARQ)-is used for error detection involves full duplex connections .In this technique the transmitter or sender has to resend the frames in which error has been detected. The three common techniques of ARQ are:
This Essay is
a Student's Work
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
Stop an Wait : in this method the sender sends the data or frame and waits for the acknowledge(ACK) from the receiver. This is a slow process and the is suitable for half duplex connections.
Fig: stop and wait between two systems
Go-back-n: The frames are sent in a sequence by the sender and are acknowledged by the receiver, when an error is detected the receiver discards the frame which is corrupted and ignores incoming frames and informs the sender of the number of frames it will receive on. Once this information is received by the sender it resends the sequence from the frame which was stopped. This method is quicker than the stop and wait method.
Fig: Go back and-n taking place between sender and receiver
Selective-repeat: when the frames are sent there is a negative acknowledgment(NACK) sent when there is a corrupt frame the sender resends only the frame that was corrupt, so there will be additional frames in the sequence receiver by the receiver.
Fig: Selective-repeat ARQ
3.2 Forward Error Correction (FEC)-This method has simplex connections, the receiver detects and corrects the error without the involvement of the sender, it provides redundancy and adds more extra bits which is done using codes, which can mainly be divided into two types:
Linear block codes
TYPES OF CODES
4.1Linear Block Codes
4.1.1 History of Linear Block Codes
Richard W. Hamming originally invented the error correction coding in the late forties, he was a theorist in the Bell Telephone laboratories . Hamming invented codes, known as Hamming codes these were the first non-trivial linear block codes. Hamming discovered a solution that would permit a computer to overcome an input error, and restore the original input without having the program restart.
4.1.2 Linear Block Codes Properties
Linear block codes have the possessions of linearity, i.e. the sum of any two codeword's in addition a code word, and they are applied to the source bits in blocks, hence the name linear blocks codes.
There are some block codes that are not linear, other than it is difficult to prove that a code is a good one without this property.
Linear block codes are distinct by high-density parity-check matrices.
4.1.3 Linear Block Codes uses
Linear block codes can be used in error correction and detection schemes.
Linear block codes are used for making more efficient encoding and decoding algorithms.
Linear block codes play an important aspect of code theory.
The elements in the binary linear block codes are called codeword's
Linear codes are useful as they indicate by blocking messages error in the communication channel when the symbols or bits are transmitted.
Linear block code has plentiful applications in error correction and detection.
Linear block codes are used in many cryptosystems.
4.1.4 Types of Linear Block Codes
Reed Solomon Codes
Algebraic Geometric Codes.
4.2 Hamming Distance
In information theory, hamming distance is denoted by dH(x, y), it measures the number of errors changing from one string to other or the smallest amount of number of substitutions required to transform from one into the other. We define the Hamming distance between x and y, denoted dH(x, y), to be the number of places where x and y are different.
4.2.1 Properties of Hamming Distance
The vector space of the words of that length is called Hamming distance, as it perceptibly fulfils the circumstances of non-negativity, individuality of imperceptible and symmetry, and it can be shown without difficulty byÂ complete initiationÂ that it satisfies theÂ triangle inequalityÂ as well. For two words a and b the hamming distance between them is also seen as the hamming weight of a-b where '-' is the an operator of appropriate choice
4.2.2 Error Correction
The procedure of correcting errors inÂ dataÂ that might have been corrupted either in transmission or inÂ storage. Data transmissions are subjected to corruptions because of errors in them , but inÂ videoÂ transmissions error correction need to be dealt with the errors and not retransmit theÂ corruptedÂ data. Video errors are corrected by forward error correction technique in the encoder or by the error concealment technique in the decoder.
4.2.3 Purpose of Error Correction
Applications that require low latency (such as telephone conversations) cannot useÂ Automatic Repeat requestÂ (ARQ); they must useÂ Forward Error CorrectionÂ (FEC). By the time anÂ ARQÂ system discovers an error and re-transmits it, the re-sent data will arrive too late to be any good.
Applications where the transmitter immediately forgets the information as soon as it is sent (such as most television cameras) cannot useÂ ARQ; they must useÂ FECÂ because when an error occurs, the original data is no longer available. (This is also whyÂ FECÂ is used in data storage systems such asÂ RAIDÂ andÂ distributed data store).
4.2.4 Single parity Check
Append an overall parity check to k information bits
Example of Single Parity Code
Message bits= 0,1,0,1,1,0,0
Parity Bit: b8 = 0 + 1 +0 + 1 +1 + 0 = 1
Codeword = 0, 1, 0, 1, 1, 0, 0, 1
If there is single error in bit 7: (0, 1, 0, 1, 1, 0, 1, 1)
numbers of 1's = 5, which is odd
Therefore Error detected
If there is errors in bits 2 and 8: (0, 0, 1, 1, 0, 0, 0, 0)
Then the no. of 1's = , which is even
Therefore Error not detected
How good is the single parity check code?
Coverage: all error patterns with odd # of errors can be detected
An error patten is a binary (k + 1)-tuple with 1s where errors occur and 0's elsewhere of 2k+1 binary (k + 1)-tuples, Â½ are odd, so 50% of error patterns can be detected
Redundancy: Single parity check code adds 1 redundant bit per k information bits: overhead = 1/(k + 1)
Is it possible to detect more errors if we add more check bits with the right codes
4.2 Reed and Solomon codes
Reed Solomon codes are subset of linear block codes and BCH codes. A Reed-Solomon code is represented by RS (n,k).
RS will correct code as long as 2s + r < 2t.
Up from "t "errors or up to "2t" erasures.
t - half the number of redundancy symbols
s - errors in block
r - erasures in block (occurs when erred symbol position is known.)
Otherwise (if 2s + r < 2t is not upheld) either:
1.The probability of each of those cases depends on the specific RS code.
2.The decoder will mis-decode and will give an incorrect code word without any indication.
3.The decoder will detect it cannot recover the original code word.