Channel Coding
INTRODUCTION
• The purpose of error control coding is to
enable the receiver to detect or correct the
errors by adding redundancy in to the data
to be transmitted.
• Error control codes are classified into:
Block coding.
Convolutional coding.
TYPES OF ECC (Error Code Channel)
Binary Codes – Encoder and decoder works on
a bit basis.
Nonbinary Codes – Encoder and decoder works
on a byte or symbol basis.
Basic Definitions
•
Basic Definitions
• Systematic codes : any linear block can be put in
systematic form.
The structure of code word in systematic form is :
n=k+r
Redundant checking part Message part
r = n – k digits k digits
Basic Definitions
Parity check code : this check code is the no. of one
bits in the data.
• Even parity check code : if the no. of one bits is even .
• odd parity check code : if the no. of one bits is odd .
E.X :-
1011 odd parity (r=1)
0011 even parity (r=0)
Basic Definitions
• Hamming weight w(v) : the no. of non-zero
elements of v .
• Hamming distance d(v , w) :the no. of places where
v & w different .
E.X :-
V=(1011101) W(v)=5
W=(0110101) D(v , w)=3
Addition & multiplication
•
The structure of encoder and decoder
Block coding
the encoder generates a block of n coded bits from k information
bits and we call this code word.
n>k , r=n-k
linear block code: the sum of any two code word is a code word .
systematic Linear block cede
•
Example :
let us consider (7 , 4) linear code where data=(1101)
solution :
k=4 ; n=7 ; r=3
G=p*I
G=
C=m*G
C = [1101] *
C = [ 1001101 ]
Detect & correct the error
• Now define the parity check matrix to be :
• Where : Code word( C ) S = (syndrome)
• If S = 0 ; NO error
• s = 1 ; found error
Example:
data = [ 0 1 1]
code word = [ 0 1 1 1 1 0 ]
now we get H :
1 0 0 0 1 1
H 0 1 0 1 0 1
0
0 0 1 1 1
1 0 0
0 1 0
0 0 1
S = [ 0 1 1 1 1 0 ] * 0
1
1
0
1
1
1 1 0
= [ 1 0 1 ]
So we find the error in the fifth bit ;then we can
correct it by replace 1 0.
C = [ 0 1 1 1 0 0 ]
Example:-Determine the set of code words for the (6,3)
code with generator matrix , M =[ 0 1 1 ].
• We get
• SO :
Determine the syndrome table for the (6,3) single error correcting
code.
The parity-check matrix of the (6,3) code is
Example : the generator matrix of a (6,3) block code is
given below .Find all code words of this code.
•
2-Hamming`s single error correction code:
•
Where :- send data [ 1 0 1 1 ]
1 0 1 1
for p1 : check 1 bit , skip 1 bit
: (1 , 3 , 5 , 7 , ……)
for p2 : check 2 bits , skip 2 bits
: (2 , 3 , 6 , 7 , ..… )
for p4 : check 3 bits , skip 3 bits
: ( 4 , 5 , 6 , 7 , 12 , 13 , 14 , 15, ….. )
We can generate this matrix :
We can detect and correct error into tow way:
•
We can do a mistake to detect and correct it:
D= [1 0 1 1] ;
Then:
The data had an error [ 0 0 1 0 1 1 1 ], so :
2-To detect error :
if p1=0 p2=0 p3=0 no error
unless one of them =1 found error
• Example : a 7 bit hamming code is received as 1 1 0 1 1 0 1 .assume even
parity & with the received code is correct or wrong, if it wrong locate the bit
in error.
• Sol.
1 1 0 1 1 0 1
• Detecting error: =1011 1
• =1001 0
• =1101 1
• Error word 1 + 4 = 5
• the correct data 1 1 0 1 0 0 1
Ex: . we have data parity bits 1 1 0 1 0 1 1 0 0 0 1 1 0 0 1
find the error bit and correct it
•
3. Linear block code:
Cyclic code.
•
Example : let (7,4) cyclic code , D= 1101 encode
the message data, or(find the 16 code word of this code).
Step 1:wright the data in polynomial form Non systematic
Step 2:multiply
v=1010001 non systematic
+
Error correction in systematic cyclic code:
Example: Find all 16 code words of systematic cyclic code for
the generator polynomial of (7,4) cyclic code is g(x)=1+x+x3 , D=(0 1
0 1).
Solution:
Let the message be D=( 0 1 0 1)
Hence, D(x)=(0)1+(1)x+(0)x2 +(1)x3
=x+x3
Therefore , xn-k D(x)=x3 (x+x3 )
=x6 + x4
The division xn-k D(x)/g(x) is as follows:
•
Application
Communications :
Satellite and deep space communications.
Digital audio and video transmissions.
Storage :
Computer memory (RAM).
Single error correcting and double error detecting code.
Advantages Disadvantages
It is the easiest and simplest technique to detect Transmission bandwidth requirement is more.
and correct errors .
Error probability is reduced. Extra bits reduces bit rate of transmitter and
also reduces its power .
Reference :
1.elements of digital communication (Sarkar )
2.Communication systems analog & digital (R P SINGH S D
SAPRE).
3. Digital Communication Principles and System Modelling
Signals and Communication Technology.
4.youtube.
Thank you
