#it #5 /coding theory)

The following block diagram represents the various aspects of transmission

of information. channel
line etc.
seephone
↑
_ wireles

Es/Encoded
D Decoded
Message Chan a >
Received &
Message Massage

in
Th to be is
ent inter
encode using
·

message
an
and
encoding -

is done
by a
, function)
function called ecoding
word channel
& When the coded passes through the cross
, may occur .
The
decoder corrects the Grow in the distated message and decode the
corrected version using decoding
rule into the original message .
(The
process
is called decoding and is done using a function , called decoding
function

geo
A finite sequence of characters from a finite alphabet is called
message.
e is "HELLO" is a
message from english alphabet .

(i) TODAY IS SUNDAY 11

9 11

Word :
=
-

of symbols
Seuence from an
alphabet is called a
Ford
Code :
-
code is a collection of words that are to be und to represent
messages .

Code word : A word in a code is called code word.

-

is which
-A
block code a code consists of words of
same
length .

Leg
.

000 101 11

Remark
=
& We assume that the alphabet is the binary alphabet 20117 ·

There are In binary words of longe n

.

& Let B" = zeXZX--- XZw where Z2 = Go , 13

-
n times
 2 .

g .
B3 =
2000 ,
001
,
010 ,
011
, 100 , 101 ,
110
, 1117
Def ! - A I , ms code for a
binary message is IBM BY , ,
E , D)

B" -
set of all binary me tuples
BY >
- Set of all binary i tuples where >m

E Bm in is
: -
encoding function
D: RED") >
- Bh is decoding function.

if bEBM then Elb) is called the code word representing b .

#nor-detecting code : -

It is used to detect the presence of

ess &

Inor correcting code : -

It is used to correct those esses which
occur because of noise in thetransmission channel.

& -

(Imm ,
m) -

parity check code (

In this code ,
the
encoding function
E! Bm >
- Boa is defined by

Elana2---am) =
[Link] Aman

if
Go
where ama even number of tis in 9, 92---am

L it odd number is
of in aaz- . am .

Write (4 , 3)
parity check code

E : B - BY
E1000s =
0000 El100) =
1006

Eloo1) =
0011 Ello1 =
1010

=
010 Ell10) =
1100

E 1011) = 0118 ElIII) = 111I are codes .

 If we receive 0100 too Floo then 0100 Is
not validlode belo2 these is odd number of Is instead of
even number of his , so this code is error detecting Gode
but We can not correct it becom it is not possible to
tell which digit is at fault .
⑧ In 0100 that an old number of errors has occurred .
we can
say
code.
&
mark ! -

Parity check code is an

example of error detecting

C encoding functi EB
!
(smm) Triple Repetition code)
-
The

El @a2 .
--
am) =
GA---am A 92
,
- -

Aml An ---

Am
e .
.
g if m =3

E10007 =
000000000 El100) = 100100100

El001 = 001001001 El101) =

10110/ 10

El010) =
010010010 Ell10) = 110110110

E(o11) = OllOlO11 El111) =

111IIIIII

is transmitted with digit

Suppose a 101 error in the Sixth
=

and the received word is be 101100101

clearly this is not
code word Ibecoz not in the range of E) . Thus we can detect
a single error and can also correct the .
ear

This code can also defect two essers ,

but can correct only one error.

with two
C if 100100000 is received as 10/10/100 ↓ essa

then it may come form 100100000 L

also for 1011010
= 10/10010 essor
↑ with one

furthermore decode b
we by examining
can ,
the first , fourth
I seventh

positions to see which digit appears more times . Here I occurs all three
times so the first entry in the decoded message is .
L

16 too second entry we examine 2nd , sch oth ,

position
& two third ente we examine 320 san se position .
,
,

Ultimately if we divide
two
b in
block will
three equal block there was
be same and then take one block
& If
only one essor then
from that and that will be the decoded
message b.
#Humming
weight weight is the function W : Al =
B") >
-
2012 ... In

defined by wiss = number ofIs in 22.

& W10000 = 0
WHOOD = 2
,
WIllll) =
4
,
.

Hamming distance
:

function d : B"XB"
-
Hamming distance is the >
- Go 2--n) ,

defined by dixy) = number of positions where the code words

& y have the different symbols.

& d1011 ,
011) = 0
,
d1011 ,
000 =
1

d/1110000 ,
0001111) =
7 .

#etised
:
Let v, 2 , 2 Bh the
,

Is &14 , 4) = dians

(ii) d (4 , 2) >, 0

(611) d14 31 = 0 iff u

y
=
,

(iv) diaries [dlu , 2) +12 , 2)

(v) dista ,
Ita) =
dix,y) (word ut a means word followed
-
- by a)
(v) d(x , 2) = winty) .2
2 .
Olo + 11 = 01011

The minimum
distance function Br-h is
of an
encoding E !

mindd(Eins , Elz1) /U
&
, 2 -
EIU) #Ely)
Bm
&
it minimum of the distances
blu all distinct pairs of
code words .

e . Let E: B -B
El00) =
000 =
2 ElO1) =
101 = Us

E(10) =
Oll =aL E111) =
010 = Mr
 dix in2)
, = 2 dIx , 4) =
2

dick Ms) ,
= 2 d /U2 , (n) =
L

dlu 2) ,
=
1 didy (n),
=
3

Thus minimum distance of E is 1 .

I: -
A code IBM B" E D) can
,
detect at most R errors it and
, ,

is
only if the minimum distance blu any two distinct code words
R+

Hence this code can detect two or fewer errors

.
 upcodes (line c
a

IBM +) is a commutative group

, -

under
component wise addition (mod 2)
& Bm is closed I becom of mod 2)
· addition is in
Associativity hold becos associative each
component
& zero word 00--o is the identity element
⑨ Each element is the self inverse.
& u+
y y+ BR.
=
+ u, 3t

& B =
500 10 01
116 is a
group addition
under
componentwise
, , ,

mod 2.

+ 00 10 01 11

00 00 10 01 11 E = 00

Do 10 0011 0 10 : 10

or =
0
01 01 L 00 10 IT' = 11

11 11 0 10 00

Leth) -
Let E ! BM - &" be an
coding function .

The C it
Rangeo
ElBM)
is
code =

is called a code
up is 6 .
-

Q :- Show that
=
15, 2)
encoding function 2 : B-B defined by

21007 = 00000 2101) =

Oll10
2 (10) =
1010 e (11) = 11011
is a group code
Soln ~
-
-
form group table !
# In a
groupcode theminimumdistembudistinct wor
,
code a
the
code .

rout ! Let (B4 , BY , E , D) be a group code .

let d = minimum distance blu two distinc code words.

I
then YIUtElBY) with UER & dlu ,
v) =
.
d
Now let1 be a nonzero code word S A
.
.
Will ways nonzero codewordy.

: dedim 0 ,
= was

cluivs
Again d= =
W/ +) <, will

Here d =
wis) ·

The Parity check Matrix & Generator matrix

000 G
O I I

= 0 10 + 00L

11 0

IB , Bu

E : B2-B3