B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

Important Terminology :

Let us choose an integer n  m and one-to-one function

e :B^m  Bⁿ .

1. 
   Encoding Function :
   

The function e is called an (m, n) encoding function. It means that every word in B^m as a word in Bⁿ.

2. 
   Code word :
   

If bB^{m then e(b) is called the code word}

3. 
   Weight :
   

For x Bⁿ the number of 1’s in x is called the weight of x and is

denoted by x .

^{e.g. i) x  10011B5 w} ^x <sup> 3

ii) x  001B3 w</sup> ^x ^

4. 
   x  y  Let x, yB^{n , then} x  y ^{is a sequence of length n that}
   

has 1’s in those positions x & y differ and has O’s in those positions x & y are the same. i.e. The operation + is defined as 0 + 0 = 0 0 + 1

= 1 1 + 1

= 0 1 + 0 = 1

e.g. if x, yB⁵

x  00101, y  10110

x  y  10011

w (x  y)  3

5. 
   Hamming Distance :
   

Let x, yB^m. The Hamming Distance _ x, y_ between x and y is the weight of x  y . It is denoted by x  y . e.g. Hamming distance between x & y can be calculated as follows : if x = 110110, y = 000101 x  y = 110011 so x  y = 4.

6. 
   Minimum distance :
   

Let x, yBⁿ.then minimum distance = min _d_ x, y_ / x, yBⁿ_.

^Let x₁, x₂   x_n ^{are the code words, let any} x_i, i  1   n ^{is a} transmitted word and y be the corresponding received word. Then y  x_k ^{if d}^{xk, y}^{is the minimum distane for k = 1, 2, --- n. This criteria is} known as minimum distance criteria.

7. 
   Detection of errors :
   

^{Let e : Bm  Bn} ^{m  n} ^{is an encoding function then if minimum} distane of e is ( k + 1) then it can detect k or fewer errors.

8. 
   Correction of errors :
   

^{Let e : Bm  Bn} ^{m  n} ^{is an encoding function then if minimum} distance of e is (2k + 1) then it can correct k or fewer errors.
Weight of a code word : It is the number of 1’s present in the given code word.
^{Hamming distance between two code words : Let} x  x₁ x₂ ... x_m ^and y  y₁ y₂ ... y_m ^{be two code words. The Hamming distance between them, } ^{x, y}  ^{, is the number of occurrences such that} x_i  y_i ^for i  1, m ^.

Example 1 : Define Hamming distance. Find the Hamming distance between the codes.

^(a) x  010000, y  000101 ^(b) x  001100, y  010110

Solution : Hamming distance :

^{(a) } ^{x, y}  ^{ x  y  010000  000101  010101  3}

^{(b) } ^{x, y}  ^

x  y

 001100  010110

 011010  3

Example 2 : Let d be the _4, 3_ decoding function defined by

^{d : B4  B3 . If y  y}₁ ^y₂ ^{... y}_m1 ^{, d}  ^y  ^{ y}₁ ^y₂ ^{... y}_m ^{. Determine d}  ^y  ^{for the word y is B4 .}

(a) y  0110 (b) y  1011

^{Solution : (a) d}  ^y ^{ 011 (b) d}  ^y <sup> 101

Example 3 : Let</sup> d : B⁶  B^{2 be a decoding function defined by for}

y  y₁ y₂ ... y₆ . Then d _ y _  z₁ z₂ .

where

^{zi  1 if} ^y₁^{, y}_i2 ^{, y}_i4 <sup>has at least two 1’s.

0 if</sup> ^y₁^{, y}_i2 ^{, y}_i4 ^{has less than two 1’s. Determine d}  ^y <sup>for the word y in B6 .

(a)</sup> y  111011 ^(b) y  010100
Solution : (a) d _ y _  11 (b) d _ y _  01

^{Example 4 : The following encoding function} f : B^m  B^m1 is called ^{the parity} ^{m, m  1} ^{check code. If b  b}₁ ^b₂ ^{... b}_m <sup> Bm , define

e</sup> ^b ^{ b}₁ ^b₂ ^{... b}_m ^b_m1

where

b_m1  0 if

= 1 if
b is even. b is odd.

^{Find e}^b ^{if (a) b  01010 (b) b  01110}

^{Solution : (a) e}^b ^{ 010100 (b) e}^b ^{ 011101}

Example 5 : Let e : B²  B⁶ is an (2,6) encoding function defined as e(00) = 000000, e(01) = 011101

e(10) = 001110, e(11) = 111111

1. 
   Find minimum distance.
   
2. 
   How many errors can e detect?
   
3. 
   How many errors can e correts?
   

Solution : Let x₀, x₁, x₂, x₃ B⁶ where x₀  000000, x₁  011101, x₂  001110, x₃  111111

^w  ^{x0  x1}  ^{ w} ⁰¹¹¹⁰¹ ^{ 4 w}  ^{x0  x2}  ^{ w} ⁰⁰¹¹¹⁰ ^{ 3 w}  ^{x0  x3}  ^{ w} ¹¹¹¹¹¹ ^{ 6 w}  ^{x1  x2}  ^{ w} ⁰¹⁰⁰¹¹ ^{ 3 w}  ^{x1  x3}  ^{ w} ¹⁰⁰⁰¹⁰ ^{  w} ^{x2  x3}  ^{ w} ¹¹⁰⁰⁰¹ ^{ 3} Minimum distance = e = 2

4. 
   Minimum distance = 2
   

An encoding function e can detect k or fewer errors if the minimum distance is k + 1. k  1 2k  1

The function can detect 1 or fewer (i.e. 0) error.

5. 
   e can correct k or fewer error if minimum distance is 2k + 1.
   

2k + 1 = 2

^{k = 1}

2

^{e can correct 1}

2

or less than ¹ i.e. 0 errors.

2

GROUP CODE :
An _m, n_ encoding function e : B^m  Bⁿ is called a group code ^{if range of e is a subgroup of Bn. i.e. (Ran (e),}  ^{) is a group.}
Since Ran (e) CBⁿ and if (Ran (e),  ) is a group then Ran(e) is a

subgroup of Bⁿ. If an encoding function e : B^m  B^{n (n < n) is a group} code, then the minimum distance of e is the minimum weight of a nonzero codeword.

.

DECODING AND ERROR CORRECTION :

^{Consider an} ^{m, n} ^{encoding function e : Bm  Bn , we require an} (n,m) decoding function associate with e as d : Bⁿ  B^m .

The method to determine a decoding function d is called maximum likelihood technique.

Since B^m  2^m .
Let x_k B^m be a codeword, k = 1, 2, ---^m and the received word is y then. Min 1 k  2^m _d _x_k, y_  d _x_i, y_ for same i then x_i is a codeword which is closest to y. If minimum distance is not unique then select on priority

MAXIMUM LIKELIHOOD TECHNIQUE :

^{Given an} ^{m, n} ^{encoding function e : Bm  Bn , we often need to} determine an _n, m_ decoding function d : Bⁿ  B^m associated with e. We now discuss a method, called the maximum likelihood techniques, for determining a decoding function d for a given e. Since B^m has 2^m

elements, there are 2^m

a fixed order.

code words in Bⁿ . We first list the code words in

^{ 1 2}   
₂m

x , x , ..., x

If the received word is x₁ , we compute _x^{i ,} x_{1 } for 1  i  2^{m and choose the first code word, say it is} x^{s  , such that}

min

1i2^m

__x^{i }, x_{1 } _x^{s }, x_{1 }

That is, x^{s } is a code word that is closest to x₁ , and the first in the list. If x^{s }  e _b_ , we define the maximum likelihood decoding function d associated with e by

^d  ^x_t  ^{ b}

Observe that d depends on the particular order in which the code ^{words in} e _Bⁿ _ ^{are listed. If the code words are listed in a different}

order, we may obtain, a different likelihood decoding function d associated with e.
^{Theorem : Suppose that e is an} ^{m, n} ^{encoding function and d is a maximum likelihood decoding function associated with e. Then} ^{e, d}  can correct k or fewer errors if and only if the minimum distance of e is at least 2k  1 .
^ 1 1 <sup>0 

 0</sup> 1 1 ^

 