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

Example : Let m  2, n  5 and H  ^ _{1 0 0} ^ . Determine the

 

_ ⁰ 1 ⁰ _

^ ^{0 0} 1 ^

group code e_H : B²  B⁵ .

^{Solution : We have B2 } ^{00, 01,10,11} ^{. Then e}⁰⁰ ^{ 00x}₁^x₂^x₃

where

x₁  0.1  0.0  0

x₂  0.1  0.1  0

x₃  0.0  0.1  0

^{ e} ⁰⁰ ^{ 00000}

Now,

where
Next

^e ⁰¹ ^{ 01x}₁^x₂ ^x₃ x₁  0.1  1.0  0

x₂  0.1  1.1  1

x₃  0.0  1.1  1

^{ e} ⁰¹ ^{ 01011
e} ¹⁰ ^{ 10 x}₁^x₂ ^x₃ x₁  1.1  0.0  1

x₂  1.1  1.0  1

x₃  1.0  0.1  0

^{ e} ¹⁰ <sup> 10110

e</sup> ¹¹ ^{ 11101}

Example : Let

^ 1 ^{0 0 }

 

_ 0 1 1 _


H 
^ 1 1 1 ^

 

_ 1 ^{0 0} _


 
^{ 0} 1 ^{0 }

 ^{0 0} 1 

be a parity check matrix. determine

the _3, 6_ group code e_H : B³  B⁶ .

Solution : First find ^e¹¹⁰^{, e}¹¹¹ <sup>.

e</sup>⁰⁰⁰ <sup> 000000

e</sup>⁰⁰¹ ^{ 001111 e}⁰¹⁰ ^{ 010011 e}¹⁰⁰ <sup> 011100

e</sup>⁰⁰⁰^{, e}⁰⁰¹^{, e}⁰¹⁰^{, e} ⁰¹¹^{, e} ¹⁰⁰^{, e} ¹⁰¹^,
e ¹⁰⁰ ^{ 100100 e} ¹⁰¹ ^{ 101011 e}¹¹⁰ <sup> 110111

e</sup>¹¹¹ ^{ 111000}

Example : Consider the group code defined by e : B²  B⁵ such that ^e⁰⁰ ^{ 00000 e} ⁰¹ ^{ 01110 e} ¹⁰ ^{ 10101 e} ¹¹ ^{ 11011.}

Decode the following words relative to maximum likelihood decoding function.

(a) 11110 (b) 10011 (c) 10100

Solution : (a) Compute

x_t  1110

_x^1, x_{t }  00000 11110  11110  4

_x^2, x_{t }  01110 11110  10000  1

_x^3, x_{t }  10101  11110  01011  3

_x^4, x_{t }  11011  11110  00101  2 min __x^{i }, x_{t } 1  _x^2, x_{t }

^{ e}⁰¹ ^{ 01110 is the code word closest to x}_t ^{ 11110 .}

 The maximum likelihood decoding function d associated with e is ^{defined by d}  ^x_t  ^{ 01.}

^(b) x_t  10011

Compute _x^1, x_{t }  00000 10011  11101  4

_x^2, x_{t }  01110 10011  00110  2

_x^3, x_{t }  10101  11110  01011  3

_x^4, x_{t }  11011  10011  01000  1 min __x^{i }, x_{t } 1  _x^4, x_{t }

^{ e}¹¹ ^{ 11011 is the code word closest to x}_t ^{ 10011 .}

 The maximum likelihood decoding function d associated with e is ^{defined by d}  ^x_t  ^{ 11.}

^(c) x_t  10100

Compute _x^1, x_{t }  00000 10100  10100  2

_x^2, x_{t }  01110  10100  11010  3

_x^3, x_{t }  10101  10100  00001  1

_x^4, x_{t }  11011  10100  01111  4 min __x^{i }, x_{t } 1  _x^3, x_{t }

^{ e}¹⁰ ^{ 10101 is the code word closest to x}_t ^{ 10100 .}

 The maximum likelihood decoding function d associated with e is ^{defined by d}  ^x_t  ^{ 10 .}

^{ 0} 1 1 ^

 

_ 1 ⁰ 1 _

Example : Let H  ^ <sub>1 

0 0</sub> ^ be a parity check matrix. decode the



_ ⁰ 1 ⁰ _

^ ^{0 0} 1 ^

following words relative to a maximum likelihood decoding function associated with e_H : (i) 10100, (ii) 01101, (iii) 11011.

^{Solution : The code words are e}⁰⁰ ^{ 00000, e}⁰¹ ^{ 00101, e}¹⁰ ^{10011, e}¹¹ ^{ 11110 . Then N } ^{00000, 00101,10011,11110} ^{. We implement} the decoding procedure as follows. Determine all left cosets of N in B5,

as rows of a table. For each row 1, locate the coset leader the row in the order.

₁, _i 

_i , and rewrite

^{Example : Consider the} ^{2, 4} ^{encoding function e as follows. How} many errors will e detect?

^e⁰⁰ ^{ 0000, e}⁰¹ ^{ 0110, e}¹⁰ ^{ 1011, e} ¹¹ ^{ 1100}
Solution :

	0000	0110	1011	1100
0000	---	0110	1011	1100
0110		---	1101	1010
1011			---	0111
1100				---

Minimum distance between distinct pairs of e  2 k 1  2 k  1.

 the encoding function e can detect 1 or fewer errors.

^{Example : Define group code. Show that} ^{2, 5} ^{encoding function e : B2  B5 defined by e}⁰⁰ ^{ 0000, e}¹⁰ ^{ 10101, e}¹¹ ^{ 11011 is a} group code.
Solution : Group Code

	00000	01110	10101	11011
00000	00000	01110	10101	11011
01110	01110	00000	11011	10101
10101	10101	11011	00000	01110
11011	11011	10101	01110	00000

Since closure property is satisfied, it is a group code.

^{Example : Define group code. show that} ^{2, 5} ^{encoding function e : B2  B5 defined by e}⁰⁰ ^{ 00000, e} ⁰¹ ^{ 01110, e} ¹⁰ ^{ 10101,}

^e¹¹ ^{ 11011 is a group code. Consider this group code and decode the} following words relative to maximum likelihood decoding function.

(a) 11110 (b) 10011.

Solution : Group Code

	00000	01110	10101	11011
00000	00000	01110	10101	11011
01110	01110	00000	11011	10101
10101	10101	11011	00000	01110
11011	11011	10101	01110	00000

Since closure property is satisfied, it is a group code.

^{Now, let} x^1  00000, x^2  01110, x^3  10101, x^4  11011 ^{. (a)} x_t  11110

_x^1, x_{t }  x^1  x_t  00000 11110  11110  4

_x^2, x_{t }  x^2  x_t  01110 1110  10000  1

_x^3, x_{t }  x^3  x_t  10101  1110  01011  3

_x^4, x_{t }  x^4  x_t  11011  1110  00101  2

^{ Maximum likelihood decoding function d} ^x_t  ^{ 01. (b)} x_t  10011

_x^1, x_{t }  x^1  x_t  00000  10011  10011  3

_x^2, x_{t }  x^2  x_t  01110  10011  11101  4

_x^3, x_{t }  x^3  x_t  10101  10011  00110  2

_x^4, x_{t }  x^4  x_t  11011  10011  01000  1

^{ Maximum likelihood decoding function d}  ^x_t  ^{ 11.}

Example : Let

^ 1 ^{0 0 }

 

_ 0 1 1 _


 
H  ^{ 1 1 1 } be a parity check matrix. Determine

_ 1 ^{0 0} _


 
^{ 0} 1 ^{0 }

 ^{0 0} 1 

^the ^{3, 6} ^{group code e}_H <sup>: B3  B6 .

Solution : B3 </sup> ^{000, 001, 010, 011,100,101,110, 111}

^eH ^000 ^^000000	eH	^001 ^^001111	eH	^010 ^^010011
^eH ^011 ^^011100	eH	^100 ^^100100	eH	^101 ^^101011
^eH ^110 ^^110111	^eH ^111 ^^111000

^{ Required group code =} <sup>000000 , 001111, 010011, 011100, 100100,

101011, 110111,111000</sup>

^{Example : Show that} ^{2, 5} ^{encoding function e : B}₂ ^{ B}₅ ^{defined by e}⁰⁰ ^{ 00000, e} ⁰¹ ^{ 01110, e}¹⁰ ^{ 10101, e} ¹¹ ^{ 11011 is a} group code.

^{Test whether the following} ^{2, 5} <sup>encoding function is a group code.

e</sup>⁰⁰ ^{ 00000, e}⁰¹ ^{ 01110, e}¹⁰ ^{ 10101, e} ¹¹ ^{ 11011}

Solution :

	00000	01110	10101	11011
00000	00000	01110	10101	11011
01110	01110	00000	11011	10101
10101	10101	11011	00000	01110
11011	11011	10101	01110	00000

Since closure property is satisfied, it is a group code.

^{Example : Show that the} ^{3, 7} ^{encoding function e : B3  B7} defined by

^e⁰⁰⁰ ^{ 0000000 e} ⁰⁰¹ ^{ 0010110 e} ⁰¹⁰ ^{ 0101000}

^e⁰¹¹ ^{ 0111110 e} ¹⁰⁰ ^{ 1000101 e} ¹⁰¹ <sup> 1010011

e</sup>¹¹⁰ ^{ 1101101 e} ¹¹¹ ^{ 1111011 is a group code.}

Solution :

	0000000	0010110	0101000	0111110	1000101	1010011	1101101	1111011
0000000	0000000	0010110	0101000	0111110	1000101	1010011	1101101	1111011
0010110	0010110	0000000	0111110	0101000	1010011	1000101	1111011	1101101
0101000	0101000	0111110	0000000	0010110	1101101	1111011	1000101	1010011
0111110	0111110	0101000	0010110	0000000	1111011	1101101	1010011	1000101
1000101	1000101	1010011	1101101	1111011	0000000	0010110	0101000	0111110
1010011	1010011	1000101	1111011	1101101	0010110	0000000	0111110	0101100
1101101	1101101	1111011	1000101	1010011	0101000	0111110	0000000	0010110
1111011	1111011							0000000

Since closure property is satisfied, it is a group code.

^{Example: Consider the} ^{3, 8} defined by

encoding function e : B³  B⁸

^e⁰⁰⁰ ^{ 0000000 e} ¹⁰⁰ ^{ 10100100 e} ⁰⁰¹ <sup> 10111000

e</sup>¹⁰¹ ^{ 10001001 e} ⁰¹⁰ ^{ 00101101 e} ¹¹⁰ ^{ 00011100 e}⁰¹¹ ^{ 10010101 e} ¹¹¹ ^{ 00110001 .}

How many errors will e detect?

Solution :

	00000000	10100100	10111000	10001001	00101101	00011100	10010101	00110001
0000000	00000000	10100100	10111000	10001001	00101101	00011100	10010101	00110001
10100100	10100100	00000000	00011100	00101101	10001001	10111000	00110001	10010101
10111000	00000000	00011100	00000000	001100001	10010101	10100100	00101101	10001001
10001001	10001001	00101101	00110001	00000000	10100100	10010101	00011100	10111000
00101101	00101101	10001001	10010101	10100100	00000000	00110001	10111000	00011100
00011100	00011100	10111000	10100100	10010101	00110001	00000000	10001001	00101101
10010101	10010101	00110001	00101101	00011100	10111000	10001001	00000000	10100100
00110001	00110001	10010101	10001001	10111000	00011100	00101101	10100100	0000000

Minimum distance between pairs of e  3.

k  1  3 k  2 The encoding function e can detect 2 or fewer errors.

Example: Consider parity check matrix H given by

^ 1 1 <sup>0 

 0</sup> 1 1 ^

 

H  ^ _{1 0 0} ^ . Determine the group code e_H : B₂  B₅ . Decode the

 

_ ⁰ 1 ⁰ _

^ ^{0 0} 1 ^

following words relative to a maximum likelihood decoding function associated with e_H : 01110, 11101, 00001, 11000 . [Apr-04, May-07]

^{Solution : B}₂ ^ ^{00, 01, 10, 11}

^e_H ⁰⁰ ^{ 00x}₁^x₂ ^x₃

^e_H ⁰¹ ^{ 01x}₁^x₂ ^x₃

^e_H ¹⁰ ^{ 10x}₁^x₂ ^x₃

^e_H ¹¹ ^{ 11x}₁^x₂ ^x₃

where

where

where

where

x₁  0.1  0.0  0

x₂  0.1  0.1  0

x₃  0.0  0.1  0
x₁  0.1  1.0  0

x₂  0.1  1.1  1

x₃  0.0  1.1  1
x₁  1.1  0.0  1

x₂  1.1  0.1  1

x₃  1.0  0.1  0
x₁  1.1  1.0  1

x₂  1.1  1.1  0

x₃  1.0  1.1  1
^e_H ⁰⁰ <sup> 00000

e</sup>_H ⁰¹ <sup> 01011

e</sup>_H ⁰¹ <sup> 10110

e</sup>_H ⁰¹ ^{ 11101}

^{ Desired group code =} ^{00000, 01011, 10110, 11101}

⁽¹⁾ x_t  01110

_x^1, x_{t }  x^1  x_t  00000  01110  01110  3

_x^2, x_{t }  x^2  x_t  01011  01110  00101  2

_x^3, x_{t }  x^3  x_t  10110  01110  11000  2

_x^4, x_{t }  x^4  x_t  11101  01110  10011  3

^{ Maximum likelihood decoding function d}^x_t  ^{ 01}

⁽²⁾ x_t  11101

_x^1, x_{t }  x^1  x_t  00000  11101  11101  4

_x^2, x_{t }  x^2  x_t  01110  11101  10110  3

_x^3, x_{t }  x^3  x_t  10101 11101  01011  3

_x^4, x_{t }  x^4  x_t  11011 11101  00000  0

^{ Maximum likelihood decoding function d}^x_t  <sup> 11

(3)</sup> x_t  00001

_x^1, x_{t }  x^1  x_t  00000  00001  00001  1

_x^2, x_{t }  x^2  x_t  01011  00001  01010  2

_x^3, x_{t }  x^3  x_t  10110  00001  10111  4

_x^4, x_{t }  x^4  x_t  11101  00001  11100  3

^{ Maximum likelihood decoding function d}^x_t  <sup> 00

(2)</sup> x_t  11000

_x^1, x_{t }  x^1  x_t  00000 11000  11000  2

_x^2, x_{t }  x^2  x_t  01110  11000  10011  3

_x^3, x_{t }  x^3  x_t  10101  11000  01101  3

_x^4, x_{t }  x^4  x_t  11011 11000  10000  1

^{ Maximum likelihood decoding function d}  ^x_t  ^{ 11}
***