Discrete Mathematics
Unit-6
Algebraic Structure &
Coding Theory
Dr. Nihar M. Ranjan
JSPM Narhe Technical Campus
Number Systems
• The set of natural numbers is the infinite set of
the positive integers. It is denoted N and can
have different representations
• {1,2,3,4,........} or {1,10,11,100,101,.....}
are alternative representations of the same set
expressed in different bases.
• Nm is the set of the first m positive numbers i.e.
{1,2,3,4, ......,m}.
•N0 is the set of natural numbers including 0 i.e.
{0,1,2,3,5,....}
• Q denotes the set of rational numbers i.e. signed
integers and fractions
{0,1,-2,2,-3,3,-3,....,1/2,-1/2,3/2,-3/2,5/2,
-5/2,....,1/3,-1/3,2/3,-2/3,........}
• R is the set of real numbers i.e. the coordinates
of all the points on a line.
• Z is the set of all integers, both positive and
negative {.....,-3,-2,-1,0,1,2,3,......}
Closure Properties
• Let G be nonempty set
+ will be closed binary operation if and
only if a ,b belongs to G and a+b also in
G
a
b
a+b
Natural Number set is closed under addition
and multiplication but it is not closed under
subtraction
Properties
Commutative
a * b = b*a
Associative
a * (b*c) = (a* b)*c
Idempotent
a*a = a
Is * Commutative ?
• The following table of binary operation *
is commutative ?
* a b c
a b c a
b c b a
c a b c
* is not Commutative
Example 2
* is Commutative ?, associative ?
* a b c d
a a c b d
b d a b c
c c d a a
d d b a c
* is not Commutative since b*d not
equal to d*b
* is not associative since a*(b*c)
not equal to (a*b)*c
Semigroup
Monoid
Group
Semigroup
A, is a semigroup if the following conditions
are satisfied:
1. is a closed operation i.e. if a A
b G then a b A
2. is associative
Example: The set of positive even integers
{2,4,6,.....} under the operation of ordinary
addition (+) since
• The sum or two even numbers is an even number
• + is always associative
If Semigroup follow the Commutative property
then it is Commutative Semigroup
+ 0 2 4 6
0 0 2 4 6
2 2 4 6 8
4 4 6 8 10
6 6 8 10 12
Identity Element
Left Identity
e * X=X
Right Identity
X * e =X
Identity Ement
e * X=X *e =X
Identity Element
* a b c
a a a a
b a b c
c c c c
Left Identity – Rows - b
Right Identity – Column – b
Identity Element – b
Monoid
A, is a monoid if the following conditions
are satisfied:
1. is a closed operation i.e. if a A and
b G then a b A
2. is associative
3. There is an identity element
Monoid is a semigroup having Identity
Element
• Let E={0,2,4,6,….}
(E,+) is monoid ---?
+ 0 2 4 6
0 0 2 4 6
2 2 4 6 8
4 4 6 8 10
6 6 8 10 12
(E,+) is monoid with identity
Element 0
Submonoid
• Let (A,*) be a monoid
Let (B,*) be a nonempty subset of A
Then (B,*) is called submonoid of (A,*)
if
1. B is closed under *
2. The identity element e ϵ B
Example: Let E={0,2,4,6,-----} Then (E,+) is
a submonoid of (Z,+)
(Z,+)
(E,+)
Example 1:
Find the submonoid of (Z,+)
generated by set {-4,6}
i) 0,6,-4 ϵ B
ii) If x,y ϵ B then x+y ϵ B
iii) <B> contains only the elements
obtained from i and ii
<B>={0,6,-4,2,8,-2,10,----}
<B>= set of Even numbers
Example 2:
Find the submonoid of (Z,+)
generated by set {-3,5}
i) 0,-3,5 ϵ B
ii) If x,y ϵ B then x+y ϵ B
iii) <B> contains only the elements
obtained from i and ii
<B>={0,-3,5,2,-1,7,-4,4,----}
<B>= set of integers
Groups
A group G, is a set G with binary
operation which satisfies the following properties
1. is a closed operation i.e. if a G and
b G then a b G
2. a,b,c G a b c a b c this is the
associative law
3. G has an element e, called the identity,
such that a G a e = e a = a
4. a G there corresponds an element
-1 -1 -1
a G such that a a a a = e
Group
Associative Law
Unique Identity
Element
Unique Inverse
Example
* a b c d
a a b c d
b b a a b
c c b a a
d d a a a
Inverse
a a
b b
c c,d
d d, c
(d*b)*c = a*c = c
d*(b*c) = d*a = d
Example:
Prove that A={1,5,7,11} under
multiplication modulo 12 is a
group.
* 1 5 7 11
1 1 5 7 11
5 5 1 11 7
7 7 11 1 5
11 11 7 5 1
• Identity element =1
Inverse
1 1
5 5
7 7
11 11
Abelian Groups
If G, is a group and is also commutative
then G, is referred to as an Abelian group
(the name is taken from the 19’th century
mathematician N.H. Abel)
is commutative means that
a,b G, a b = b a
properties
Semigroup monoid group Abelian Group
SubGroup
Let H be subset of Group G,
Then H is called subgroup of G if
H is a group under the operation
of G.
A set H is subgroup of G if
1. The identity element is in H
2. H is closed under the operation
3. H is closed under the inverses.
Example:
Prove that (E,+) is subgroup of
(Z,+) under modulo 8
Identity element : 0
Inverse:
0- 0 2- 6 4- 4 6- 2
+ 0 2 4 6
0 0 2 4 6
2 2 4 6 0
4 4 6 0 2
6 6 0 2 4
Normal Subgroups
Let H, be a subgroup of G, . Then H,
is a normal subgroup if, for any a G , the left
coset a H is equal to the right coset H a
H, is a normal subgroup where H = , ,
e.g. H = , , ,,
H , , ,,
Theorem: In an Abelian group, every subgroup
is a normal subgroup
Cyclic Group
A Group G is called cyclic group if for
any a G
every element of G is the form an, where
n is some integer.
The element a is called the Generator of
G.
Example:
Consider the Group G=
{1,2,3,4,5,6} under multiplication
modulo 7
1. Find the multiplication table of
G.
2. Find 2-1 , 3-1 , 6-1
3. Find the orders and subgroups
generated by 2 and 3.
4. Is G Cyclic ?
* 1 2 3 4 5 6
1 1 2 3 4 5 6
2 2 4 6 1 3 5
3 3 6 2 5 1 4
4 4 1 5 2 6 3
5 5 3 1 6 4 2
6 6 5 4 3 2 1
2-1 =4, 3-1 =5, 6-1 =6
• Order and subgroup generated by
2 and 3
21=2, 22=4, 23=1, 24=2, 25=4, 26=1
Order is |2|=3 and gp(2)={1,2,4}
31=3, 32=2, 33=6, 34=4, 35=5, 36=1
Order is |3|=6 and gp(3)=G.
• G is cyclic. Generator of G is 3.
Homomorphisms
Let A, and B, be two algebraic systems
then a homomorphism from A, to B,
is a functional mapping f : A B
such that
f x y f x f y
Example: Let (A1,*) and (A2, .) be an
algebric system.
Determine two algebric systems
are Homomorphic, Isomorphic.
(A1,*) (A2, .)
* a b c . 1 w w2
a a b c 1 1 w w2
b b c a w w w2 1
c c a b w2 w2 1 w
f( a) = 1 f( b) = w f( c) = w2
f( a* b) = f(a).f(b)
f(b) 1.w
w w
f( b* c) = f(b).f(c)
f(a) w. w2
1 1
Isomorphic
• Let (G1,*) and (G2,.) be two
algebric system where * and .
Are binary operation. If the
system is homomorphic and in
addition f is one-to-one and
onto then f is called
isomorphic.
a 1
b w
c w2
Automorphism
• An isomorphism of a
semigroup onto itself is
called Automorphism.
• Two groups are equal then it
is called automorphic.
Ring
An algebraic system A, , is called a ring if
the following conditions are satisfied:
(1) A, is an Abelian group
(2) A, is a semigroup
(3) The operation is distributive over the
Operation
Example: Z, +, is a ring since
Z, + is an Abelian group
Z, is a semigroup
distributive over +
A commutative ring is a ring in which is
commutative
A ring with unity contains an element 1 such
that
x A x 1 = 1 x = x
(R,+,*) is Ring
(R,+) is abelian group
(R,*) is semigroup
Distribution Law
a*(b+c)= a*b + a*c
(b+c)*a=b*a+c*a
Example:
1. Let Z7 = {0,1,2,…….,6}
Let R is a relation under the
operation addition modulo 7 and
multiplication modulo 7. Does this
system form Ring? Is it commutative
ring.
(R,+) under modulo 7
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5
R+ is an abelian Group
(R,*) under modulo 7
* 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
R * is a semigroup
* is distributive over +
* is also commutative so commutative Ring
Zero Divisors
* 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
An element a of a ring is called a right zero
divisor if there exists a nonzero y such that
ya = 0. An element that is a left or a right zero
divisor is simply called a zero divisor
Integral Domain
• A commutative Ring R is an
integral domain if R has no zero
divisors i.e if a.b = 0 implies a = 0
or b = 0
Field
• Field is the integral domain.
• If every nonzero element has
a multiplicative inverse then
R is Field.
A field is an integral domain. However,
not every integral domain if Field.
Example:
Prove (Z7,+,*) is field
Z* under modulo 7
* 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
(Z,+) under modulo 7
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5
• Z7 is an integral domain
• All nonzero element has multiplicative
inverse
• So (Z7,+,*) is a field
Coding Theory
In transmitting the data, noises from the external sources may introduce
errors and change the original data. So it is important to detect and
correct the data transmitted over the communication channels
Encoded
Message
Message
Channel
Received Message
Decoded Message
Hamming weight
• Weight of X denoted by w(x) to
be the number of 1 in X.
Example :
w(11001001)=4
w(10110101) = 5
w(0001010)= 2
Hamming Distance
The Hamming distance is simply
distance between x and y denoted by
d(x,y) is the number of coordinates for
which xi and yi are different
e.g
x = ( 001101 )
y = ( 111110 )
d(x,y)= w(x⊕ y) = 4
Properties:
i) d(x,y) ≥ 0
ii) d(x,y) =0 ⇔ x = y
iii) d(x,y) = d(y,x)
iv) d(x, z) ≤ d(x,y) + d(y,z)
Parity checks
Parity digits are the redundant digits introduced
to hamming code for encoding purpose
Even parity: making entire message containing
even number of 1.
e .g {(00),(01),(10),(11)}
{(000),(011),(101),(110)}
Odd parity : making entire message containing odd
number of 1.
e .g {(00),(01),(10),(11)}
{(001),(010),(100),(111)}
• Find Hamming Distance between
code words of
c = {(0000), (0101),(1011),(0111)}
Rewrite the message by adding even
parity checks.
x = (0000)
y = (0101)
z = (1011)
t = (0111)
d(x,y)=2 d(x,z)=3 d(x,t)=3
d(y,z)=3 d(y,t)=1 d(z,t)=2
00000
01010
10111
01111
Encoding function
The encoding function e: Bm⇒ Bm+1 is called the parity
(m,m+1) check code .
Suppose, b= b1 b2 b3…….bm ∈ Bm , we define the
encoding e(b) as
e(b) = b1 b2 b3…….bm bm+1
Where bm+1 = 0 if | b | is even
= 1 if | b | is odd
The encoding function defined above enable us to detect
an error, if bm+1 = 0 then numbers of 1 in | b | must be
even and vice - versa
Examples
Example 1:
Consider the (3,4) parity check code. For each of the
following words determine whether an error will be
detected or not?
i) 0100
| b | = 1 , since odd number of 1 so 1 should be at last
position but here is 0 so error detected
ii) 1100
| b | = 2, since even number of 1 so 0 should be at last
position and here is 0 so no error detected
Example 2:
Generation of encoding function for m=3 ie parity check
code (3,4)
e(000) = 0000
e(001) = 0011
e(010) = 0101
e(011) = 0110
e(100) = 1001
e(101) = 1010
e(110) = 1100
e(111)= 1111
Thank You !!!
