Basic Electronics

Digital Electronics

Basic Electronics, The LNMIIT

1
Jaipur
SOP AND POS
REPRESENTATIONS
Basic Electronics, The LNMIIT
2
Jaipur
 Representation of Boolean Expressions

x y f1 x y min term
0 0 0 0 0 x.y m0
0 1 1 0 1 x.y m1
1 0 1 1 0 x.y m2
1 1 0 1 1 x.y m3

f1 = x . y + x. y f1 = m1 + m2 f1 =  (1, 2)

f2 = (0, 2,3) = ? f2 = x . y + x. y + x . y

A minterm is a product that contains all the variables used in a function

Basic Electronics, The LNMIIT Jaipur 3

 Three variable functions

x y z min terms
0 0 0 x.y.z m0
0 0 1 x.y.z m1
0 1 0 x.y.z m2
0 1 1 x.y.z m3
1 0 0 x.y.z m4
1 0 1 x.y.z m5
1 1 0 x.y.z m6
1 1 1 x.y.z m7

f2 =  (1, 4,7) = ?

f2 = x . y. z + x. y. z + x . y . z
Basic Electronics, The LNMIIT Jaipur 4
 Product of Sum Terms Representation

x y f1 x y Max term
0 0 0 0 0 x+y M0
0 1 1 0 1 x+y M1
1 0 1 1 0 x+y M2
1 1 0 1 1 x+y M3

F1 = (x+y)(x’ + y’) = M0.M3 = ∏M0M3

Basic Electronics, The LNMIIT Jaipur 5

 x y z Max. terms
0 0 0 x + y + z M0
0 0 1 x + y + z M1
0 1 0 x + y + z M2
0 1 1 x + y + z M3
1 0 0 x + y + z M4
1 0 1 x + y + z M5
1 1 0 x + y + z M6
1 1 1 x + y + z M7

f1 =  (1,5, 7) = ?

f2 =(x + y + z).( x + y + z).( x + y + z)

Basic Electronics, The LNMIIT Jaipur 6
 Simplification of Boolean Expressions

x1 x2 x3 y y=  (1,3,5,7)
0 0 0 0
0 0 1 1 y = x1 . x2 . x3 + x1. x2 . x3 + x1. x2 . x3 + x1. x2 . x3
0 1 0 0
x1
0 1 1 1 x2
1 0 0 0 x3

1 0 1 1 x1
x2
1 1 0 0 x3
y
1 1 1 1 x1
x2
x3

x1
x2
x3

Simplification of Boolean expression yields : y = x3 !! which does not

require any gates at all !
Basic Electronics, The LNMIIT Jaipur 7
 Goal of Simplification
y = x1 . x2 . x3 + x1. x2 . x3 + x1. x2 . x3 + x1. x2 . x3
x1
x2
x3

x1
x2
x3
y
x1
x2
x3

x1
x2
x3

Goal of simplification is to reduce the complexity of gate circuit. This requires

that we minimize the number of gates. Since number of gates depends on
number of minterms, one of the goals of simplification is to minimize the
number of minterms in SOP expression
Basic Electronics, The LNMIIT Jaipur 8
y = x1 . x2 . x3 + x1. x2 . x3 + x1. x2 . x3 + x1. x2 . x3  y= x1 . x3 + x1. x2 . x3 + x1. x2 . x3
x1
x2
x3 x1
x3
x1
x2
x3 y
y x1
x1 x2
x2 x3
x3
x1
x1
x2
x2
x3
x3

This circuit is simpler not just because it uses 4 gates instead of 5 but also
because circuit-2 uses one 2-input and three 3-input gates as compared to five
3-input gates used in circuit-1

Basic Electronics, The LNMIIT Jaipur 9

 Goal of Simplification
In the SOP expression:

1. Minimize number of product terms

2. Minimize number of literals in each term

Simplification  Minimization

Basic Electronics, The LNMIIT Jaipur 10

 Minimization

y = x1 . x2 . x3 + x1. x2 . x3 + x1. x2 . x3 + x1. x2 . x3

y= x1 . x3.( x2 + x2 ) + x1. x3.( x2 + x2 )

y= x1 . x3 + x1. x3

y=( x1 + x1 ). x3

y = x3

Principle used: x + x = 1

Basic Electronics, The LNMIIT Jaipur 11

 f = x . y + x. y + x . y

Apply the Principle: x + x = 1 to simplify

f = x .( y + y ) + x . y

f = x + x. y
How do we simplify further?

f = x . y + x. y + x . y = x . y + x . y + x. y + x . y
Principle used : x + x = x

f = x . y + x. y + x . y + x . y
= x . ( y + y ) + ( x + x). y = x + y
Basic Electronics, The LNMIIT Jaipur 12
Simplify
f = x1. x2 . x3 . x4 + x1. x2 . x3 . x4 + x1. x2 . x3 . x4 + x1. x2 . x3. x4 +
x1. x2 . x3 . x4 + x1. x2 . x3 . x4

Principle: x + x = 1 and x + x = x

Need a systematic and simpler method for applying these two principles

Karnaugh Map (K map) is a popular technique for carrying out simplification

It represents the information in problem in such a way that the two

principles become easy to apply

Basic Electronics, The LNMIIT Jaipur 13

KARNAUGH MAPS

Basic Electronics, The LNMIIT

14
Jaipur
 K-map representation of truth table

x y min term y
x 0 1
0 0 x.y m0 0 m0 m1
0 1 x.y m1
1 0 x.y m2 m2 m3
1
1 1 x.y m3

y
x y f1 0 1
x
0 0 0 0 0 1
0 1 1
1 0 1 1 1 0
1 1 0

Basic Electronics, The LNMIIT Jaipur 15

f2 = (0, 2,3)

y
x 0 1
0 1 0 f = x.y + x. y

1 0 1

Basic Electronics, The LNMIIT Jaipur 16

 3-variable K-map representation

x y z min terms
0 0 0 x.y.z m0 yz
0 0 1 x.y.z m1 x 00 01 11 10
0 1 0 x.y.z m2
0 1 1 x.y.z m3 0 m0 m1 m3 m2
1 0 0 x.y.z m4
1 0 1 x.y.z m5 1 m4 m5 m7 m6
1 1 0 x.y.z m6
1 1 1 x.y.z m7

x y z f
yz
0 0 0 0 x 00 01 11 10
0 0 1 1
0 1 0 0 0 0 1 1 0
0 1 1 1
1 0 0 0 1 0 1 1 0
1 0 1 1
1 1 0 0
1 1 1 1
Basic Electronics, The LNMIIT Jaipur 17
 yz
x 00 01 11 10
0 1 0 1 0

1 0 1 1 0

f = x .y . z + x . y . z + x . y . z + x . y . z

Basic Electronics, The LNMIIT Jaipur 18

4-variable K-map representation

w x y z min terms yz
wx 00 01 11 10
0 0 0 0 m0
00 0 1 3 2
0 0 0 1 m1
0 0 1 0 m2 01 4 5 7 6
0 0 1 1 m3
11 12 13 15 14
1 1 1 0 m14
10 8 9 11 10
1 1 1 1 m15

yz
wx 00 01 11 10
00 1 0 1 0
f =w. x . y . z + w. x . y . z + w. x . y . z + w. x . y . z
01 0 1 1 0

11 1 0 0 1
+ w . x . y . z + w . x . y. z + w . x . y . z
10 1 0 0 0
Basic Electronics, The LNMIIT Jaipur 19
 Minimization using Kmap

f 2 =  (2,3)
y
x 0 1
0 0 0

f = x. y + x . y 1 1 1

f = x.( y + y )

f= x

Combine terms which differ in only one bit position. As a result,

whatever is common remains.

Basic Electronics, The LNMIIT Jaipur 20

 y
0 1
f = x. y + x . y
x
0 0 1

1 0 1 f = ( x. + x). y f = y

y y
x 0 1 x 0 1
0 1 0 0 1 1

1 1 0 1 0 0

f=y f =x
Basic Electronics, The LNMIIT Jaipur 21
 y
x 0 1
0 0 1

1 1 1

f = x.( y + y ) + x . y
f = x. y + x . y + x . y
= x + x. y
f = x + x. y + x. y
= x + ( x + x). y
= x+ y
The idea is to cover all the 1’s with as few and as simple terms as possible

Basic Electronics, The LNMIIT Jaipur 22

 3-variable minimization

yz
x 00 01 11 10
1 1 0
f = x .y . z + x . y . z + x . y . z + x . y . z
0 0
1 0 1 1 0
y. z

x. z

f = x .y . z + y . z + x . z

Basic Electronics, The LNMIIT Jaipur 23

 3-variable minimization

yz
x 00 01 11 10
1 0 0 1
f = x .y . z + x . y . z + x . y . z + x . y . z
0
1 0 1 1 0
x. z
x. z

f = x . z + x. z

Basic Electronics, The LNMIIT Jaipur 24

 3-variable minimization

yz
x 00 01 11 10
0 0 0 0
f = x. y . z + x . y . z + x . y . z + x . y . z
0
1 1 1 1 1

x. y f =x . y + x . y
x. y
yz
x 00 01 11 10
0 0 0 0 0
f =x .( y + y ) = x
1 1 1 1 1
x
Basic Electronics, The LNMIIT Jaipur 25
 yz
x 00 01 11 10 yz
x 00 01 11 10
0 1 1 1 1
0 1 0 0 1
1 0 0 0 0 x 1 1 0 0 1
z

yz yz
x 00 01 11 10 x 00 01 11 10
0 0 1 1 0 0 1 0 0 1

1 0 1 1 0 z 1 1 1 1 1
z
x
f =x + z
Basic Electronics, The LNMIIT Jaipur 26
 Can we do this ?

yz
x 00 01 11 10
0 0 0 0 0

1 1 1 1 0

Note that each encirclement should represent a single product term. In this
case it does not.
f =x . y. z + x. y.z + x. y.z
= x . y + x.z

We do not get a single product term.

In general we cannot make groups of 3 terms.

Basic Electronics, The LNMIIT Jaipur 27

Can we use kmap with the following ordering of variables?

yz
x 00 01 10 11
0 0 0 0 0

1 0 1 1 0

Can we combine these two terms into a single term ?

f =x . y. z + x. y.z
= x .( y. z + y.z )

Note that no simplification is possible.

Kmap requires information to be represented

Basic Electronics, The LNMIIT Jaipur 28

 yz
x 00 01 10 11
0 0 1 0 1

1 0 0 0 0

These two terms can be combined into a single term but it is not easy to
show that on the diagram.

f = x . y. z + x. y.z
= x .( y + y ).z = x.z
Kmap requires information to be represented in such a way that it is easy
to apply the principle x + x=1

Basic Electronics, The LNMIIT Jaipur 29

 4-variable minimization

yz
wx 00 01 11 10
00 1 0 1 0 w. y . z
01 0 1 1 0

11 1 0 0 1
w. x . z
10 1 0 0 0

w. y . z

f = w . y. z + w . x. z + w . y. z + w . x . y. z + w . x . y. z
But is this the simplest expression ?

Basic Electronics, The LNMIIT Jaipur 30

 yz yz
wx 00 01 11 10 wx 00 01 11 10
00 1 0 1 0 00 1 0 1 0

01 0 1 1 0 01 0 1 1 0

11 1 0 0 1 11 1 0 0 1

10 1 0 0 0 10 1 0 0 0

w. x . y . z + w. x . y . z = w. x . z w. x . y . z + w. x . y . z = x . y . z

Basic Electronics, The LNMIIT Jaipur 31

 4-variable minimization

x. y. z yz
wx 00 01 11 10
00 1 0 1 0 w. y . z
01 0 1 1 0

11 1 0 0 1
w. x . z
10 1 0 0 0
w. x . z

w. y . z

f = w . y. z + w . x. z + w . y. z + w . x . z + x . y. z
Is this the best that we can do ?
Basic Electronics, The LNMIIT Jaipur 32
 Cover the 1’s with minimum number of terms

yz yz
wx 00 01 11 10 wx 00 01 11 10
00 1 0 1 0 00 1 0 1 0

01 0 1 1 0 01 0 1 1 0

11 1 0 0 1 11 1 0 0 1

10 1 0 0 0 10 1 0 0 0

f = w . y. z + w . x. z + f = w . y. z + w . x. z +
w . y. z + w . x . z + x . y. z w . x . z + x . y. z

Basic Electronics, The LNMIIT Jaipur 33

 4-variable minimization

yz yz
wx 00 01 11 10 wx 00 01 11 10
00 1 0 0 0 00 1 0 0 0

01 1 1 0 0 01 1 1 0 0

11 0 0 0 0 11 0 0 0 0

10 1 0 0 1 10 1 0 0 1

f = w . x. y + w. x. z + w . y. z f = w . x. y + w. x. z + x . y. z

Basic Electronics, The LNMIIT Jaipur 34

Groups of 4
yz
wx 00 01 11 10
00 0 1 0 0

1 1 1 1
01 w. x
11 0 1 0 0
y.z
10 0 1 0 0

yz
wx 00 01 11 10
00 0 0 0 0
x. z
01 0 1 1 0

11 0 1 1 0
w. z
10 0 1 1 0

Basic Electronics, The LNMIIT Jaipur 35

 yz yz
wx 00 01 11 10 wx 00 01 11 10
00 0 0 0 0 00 0 1 1 0

1 0 0 1 0 0 0 0
01
x. z
01 x. z
11 1 0 0 1 11 0 0 0 0

10 0 0 0 0 10 0 1 1 0

yz
yz
wx 00 01 11 10
wx 00 01 11 10
00 1 0 1 0
00 1 0 0 1

01 0 0 0 0 ??
01 0 0 0 0
x. z
11 0 0 0 0
11 0 0 0 0
10 1 0 1 0
10 1 0 0 1
Basic Electronics, The LNMIIT Jaipur 36
Groups of 8

yz yz
wx 00 01 11 10 wx 00 01 11 10

00 0 1 1 0 00 0 0 0 0

z 1 1 1 1 x
01 0 1 1 0 01

11 0 1 1 0 11 1 1 1 1

10 0 1 1 0 10 0 0 0 0

yz
yz wx 00 01 11 10
wx 00 01 11 10
00 1 1 1 1
00 1 0 0 1

1 0 0 1 z 01 0 0 0 0
x
01
11 0 0 0 0
11 1 0 0 1
10 1 1 1 1
10 1 0 0 1 Basic Electronics, The LNMIIT Jaipur 37
 Examples

yz yz
wx 00 01 11 10 wx 00 01 11 10
00 0 1 0 1 00 0 1 0 1

01 1 1 1 1 01 1 1 0 1

11 1 1 1 1 11 1 1 1 1

10 0 0 0 1 10 0 0 0 1

Basic Electronics, The LNMIIT Jaipur 38

 Don’t care terms
a b c d y0y1y2y3y4y5y6y7y8y9
a y0
y1 0 0 0 0 1000000000
b Decimal y2
Decoder y3 0 0 0 1 0100000000
c
0 0 1 0 0010000000
d y9
0 0 1 1 0001000000
0 1 0 0 0000100000
Y3 0 1 0 1 0000010000
cd
ab 00 01 11 10 0 1 1 0 0000001000
00 0 0 1 0 0 1 1 1 0000000100
1 0 0 0 0000000010
01 0 0 0 0
1 0 0 1 0000000001
11 x x x x 1 0 1 0 xxxxxxxxxx
1 0 1 1 xxxxxxxxxx
10 0 0 x x 1 1 0 0 xxxxxxxxxx
1 1 0 1 xxxxxxxxxx
1 1 1 0 xxxxxxxxxx
y3 = a.b.c.d 1 1 1 1 xxxxxxxxxx
Basic Electronics, The LNMIIT Jaipur 39