Introduction to Electronics

Part 4: Digital Electronics

L02: Digital Design

Dr. Rik Dey

ASSISTANT PROFESSOR,
ELECTRICAL ENGINEERING, IIT KANPUR

2023-24 SEM-II ESC201A INTRODUCTION TO ELECTRONICS CIRCUITS

1
 Binary Subtraction
• For subtraction, we use the following
𝐴 − 𝐵 = 𝐴 + (−𝐵)

• How to represent negative number – 𝐵

• Example: 7 − 5 =?

• Let us use 4 bits, reserve the MSB to be 0

• Using 3 bits, we can represent 8 numbers (from 0 to 7)

• 7 = 0111

• 5 = 0101

• −5 =?

Dr. Rik Dey ESC201, 2023-24 Sem-II 2

 1’s and 2’s Complement of Positive Number
• 5 = 0101 n-bit binary number x
• −5 can be denoted by
1’s complement of 5 1’s complement 2’s complement
2’s complement of 5 (2n − 1) − x 2n − x
15 − 5 = 10 16 − 5 = 11
x = 0101,
n=4
1111 − 0101 = 1010 1010 + 1 = 1011

1’s complement is simply flip the bits and add 1

obtained by flipping a bit
(changing 1 to 0 and 0 to 1)
Note the use of reserve MSB Using 3 bits and MSB =1,
One can represent numbers one can represent numbers
from – 7 to – 1 from – 8 to – 1
Dr. Rik Dey ESC201, 2023-24 Sem-II 3
 1’s and 2’s Complement of Negative Number
• For subtraction, we can use 1’s or 2’s complements

n-bit binary
number x

1’s complement 2’s complement

2n − 1 − x 2n − x
x = 1011, n = 4

2 − 1 − 1011
4

1111 − 1011 = 0100 0100 +1 0101

1’s complement is simply obtained by flipping a bit (changing 1 to 0 and 0 to 1).

For 2’s complement, flip the bit and add 1.
Dr. Rik Dey ESC201, 2023-24 Sem-II 4
 Representing Negative Numbers in 2’s Complement
• 5 = 0101 Let us compute 2’s
• −5 is denoted by 2’s complement of 5 complement of this

x = 1011, n = 4
1’s complement
• What does this binary number represent?
1011
1111 − 1011 = 0100

2’s complement

0100 + 1 = 0101

1011 represents – 5

Dr. Rik Dey ESC201, 2023-24 Sem-II 5

 Representing Negative Numbers in 2’s Complement
1011 represents – 5

–6=? 610 ⇒ (0110)2 2’s complement of 0110 → 1010

MSB is 1 => negative

MSB is 0 => positive

With n = 4 bit,

a 4-bit number can represent 0 to 15 (unsigned), or

a 4 bit number can represent numbers from –8 to 7 (signed in 2’s complement form)

Dr. Rik Dey ESC201, 2023-24 Sem-II 6

 Representing Negative Numbers
Extra bit needed to carry sign information Sign bit = 0 represents non-negative nos.
“MSB” is often the sign bit Sign bit = 1 represents negative numbers

Unique zero
representation

magnitude

magnitude

magnitude
2n-1 – 1
positive nos.

2’s comp. of
0 and -8 are
themselves

magnitude

magnitude
magnitude

2n-1
negative nos.

Dr. Rik Dey ESC201, 2023-24 Sem-II 7

 Binary Subtraction with 2’s complement
𝟕−𝟓=?
n = 4 bit representation 710 ⇒ (0111)2 510 ⇒ (0101)2
2’s complement form of −510 ⇒ (1011)2
0111
Why does this work 1011
−5 ⇒ 16 − 5 = 11 −−− −
7 − 5 ⇒ 7 + 11 = 18 10010 Answer is +2
While adding a positive and a negative number
the result can only be: (a) positive or (b) negative
Discard the final carry and look at the MSB
if MSB is 1 => negative, else if MSB is 0 => positive
Dr. Rik Dey ESC201, 2023-24 Sem-II 8
 Binary Subtraction with 2’s complement

10 – 6 = ?
n = 5 bit representation 1010 ⇒ (01010)2 610 ⇒ (00110)2
2’s complement of 00110 is 11010
01010
11010
----------
100100 0100 2 ⇒ 410 Answer is + 4

While adding a positive and a negative number

the result can only be: (a) positive or (b) negative
Discard the final carry and look at the MSB
if MSB is 1 => negative, else if MSB is 0 => positive

Dr. Rik Dey ESC201, 2023-24 Sem-II 9

 Subtraction with 2’s complement

6 – 10 = ?
610 ⇒ (00110)2 1010 ⇒ (01010)2
2’s complement of 01010 is 10110

10110 Discard the final carry and look at the MSB

00110 11100 → it’s a negative number
----------
011100 Take the 2’s complement to get its value
2’s complement of 11100 is 00100
0100 2 ⇒ 410

Answer is – 4
Dr. Rik Dey ESC201, 2023-24 Sem-II 10
 Addition/Subtraction Computation

Dr. Rik Dey ESC201, 2023-24 Sem-II 11

 Overflow
• Take care to detect overflow when adding
+5 00101
+ 13 01101
+ 18 010010 After discarding the final carry 0,
2’s complement of 10010 is 01110 = (14)10
We get a wrong answer!
• Sum of positive numbers = negative
overflow
• Sum of negative numbers = positive

August 2016: Casino machine at Resorts World Casino printed a prize ticket of $42,949,672.76
as a result of an overflow bug. The Casino refused to pay this amount calling it a malfunction.
The Iowa Supreme Court ruled in favor of the Casino.
Dr. Rik Dey ESC201, 2023-24 Sem-II 12
 Addition
S a b S C
0 0 0 0 Truth Table
0 1 1 0
C Half Adder
1 0 1 0
1 1 0 1
a b

How to get this

S = a.b + a.b ; C = a.b
expression?

a
How to get this gate S
b
implementation?
C

Dr. Rik Dey ESC201, 2023-24 Sem-II 13

 Boolean Operators
• Basic operators
NOT: y = x AND: y = x1. x 2 OR: y = x1 + x 2

x y x1 x2 y x1 x2 y

0 1 0 0 0 0 0 0
0 1 0 0 1 1
1 0 1 0 0 1 0 1
1 1 1 1 1 1
x1 x1
AND y OR y
x2 x2
Dr. Rik Dey ESC201, 2023-24 Sem-II 14
 Gates with more than 2 inputs

x1
AND: y = x1. x 2 . x3 ... x2
x3
AND y

x1
OR: y = x1 + x 2 + x3 + .... x2
y
x3

Dr. Rik Dey ESC201, 2023-24 Sem-II 15

 NAND & NOR Gates
NAND gate NOR gate

NAND: y = x1. x 2 NOR: y = x1 + x 2

x1x2 x1+x2
x1 x1
AND x1x2 OR x1+x2
x2
x2
x1 x1
NAND y NOR y
x2 x2
Dr. Rik Dey ESC201, 2023-24 Sem-II 16
 Gate Level Abstraction: Logic Gates
NOT: y = x x y

x1
AND: y = x1 . x 2 x2
AND y

x1
OR: y = x1 + x 2 OR y
x2

x1
NAND: y = x1. x 2 x2
NAND y

x1
NOR: y = x1 + x 2 x2
NOR y
Dr. Rik Dey ESC201, 2023-24 Sem-II 17
 How to get an expression from truth table?

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

y = 1 when x1 is 0 and x2 is 1

Boolean expression y = x1 . x2 (NOT 𝑥1 ) AND 𝑥2

Dr. Rik Dey ESC201, 2023-24 Sem-II 18

 How to get an expression from truth table?

x1 x2 y y = x1 . x2 x1 x2 y
y = x1 . x2
0 0 1 0 0 0
0 1 0 0 1 0
1 0 0 1 0 1
1 1 0 1 1 0

x1 x2 y x1 . x2
0
0
0
1
1
0
y = x1 . x2 + x1. x2
1 0 0
x1 . x2
(NOT 𝑥1 ) AND (NOT 𝑥2 ) OR 𝑥1 AND 𝑥2
1 1 1
Dr. Rik Dey ESC201, 2023-24 Sem-II 19
 Boolean Expressions & Truth Tables: XOR & XNOR Gate

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

y = x1 . x2 + x1. x2 y = x1 . x2 + x1. x2
Sum of Products (SOP) form Sum of Products (SOP) form
XOR gate XNOR gate
x1 x1
XNOR
XOR y
XOR y x2
x2
Dr. Rik Dey ESC201, 2023-24 Sem-II 20
 Boolean Expressions & Truth Tables
Instead of writing expressions as sum of terms that make y equal to 1,
we can also write expressions using terms that make y equal to 0

x1 x2 y
y = x1 . x2 + x1 . x2 + x1. x2
0 0 1 Here we are telling when
0 1 1 y will be true
1 0 1
1 1 0 y = 𝑥1 . 𝑥2 FALSE when both are true
Here we are telling when
Recall
y will be false
y = 𝑥1 + 𝑥2 𝑥1 + 𝑥2 = 𝑥1 . 𝑥2

Dr. Rik Dey ESC201, 2023-24 Sem-II 21

 Boolean Expressions & Truth Tables

x1 x2 y x1 + x2
0 0 0 y = (x1 + x2 ).( x1 + x2 )
0 1 1
1 0 1 x1 + x2
1 1 0

Product of Sum (POS) form

Dr. Rik Dey ESC201, 2023-24 Sem-II 22

 Boolean Expression: SOP vs POS

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

0 0 0 0 0 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 0

Sum of Products (SOP) form Product of Sum (POS) form

Dr. Rik Dey ESC201, 2023-24 Sem-II 23

 SOP & POS Example
y = x1 . x2 . x3 + x1. x2 . x3 + x1. x2 . x3 + x1. x2 . x3
x1 x2 x3 y
0 0 0 0
0 0 1 1 Sum of Products (SOP) form
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1 Product of Sum (POS) form

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

Dr. Rik Dey ESC201, 2023-24 Sem-II 24
 Implementation via Logic Gates: Example

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

0 0 0 0 x1
x2
0 0 1 1 x3

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

1 0 1 1 x3

x1
1 1 0 0 x2

1 1 1 1 x3

Dr. Rik Dey ESC201, 2023-24 Sem-II 25

 General Rule for Implementation

A SOP or POS expression can be easily implemented using NOT, AND & OR gates.

Dr. Rik Dey ESC201, 2023-24 Sem-II 26

 NAND Gates are Universal

NAND to Inverter x. x = x
NAND to AND

x. y x. y
x
NAND to OR

y f = x. y = x + y
Dr. Rik Dey ESC201, 2023-24 Sem-II 27
 Implementation using only NAND gates
A SOP expression is easily implemented with NAND gates.
a
b
f =a.b + c.d + f .g
c
d f

g
h
AND OR

Dr. Rik Dey ESC201, 2023-24 Sem-II 28

 Implementation using NAND Gates
SOP => NAND
a
b

c
d f

g
h
a
b
There is a one-to-one mapping c
between AND-OR network and f
NAND network d

g
h
Dr. Rik Dey ESC201, 2023-24 Sem-II 29
 NOR Gates are Universal
NOR to Inverter x+ x = x
NOR to OR

x+ y x+ y
NOR to AND
x

Dr. Rik Dey y f = x + y = x. y ESC201, 2023-24 Sem-II 30

 Implementation using only NOR gates
A POS expression is easily implemented with NOR gates.

f = (𝑎 + 𝑏). (𝑐 + 𝑑). (𝑓 + 𝑔)
a
b

c
d f

g
h
OR AND

Dr. Rik Dey ESC201, 2023-24 Sem-II 31

 Implementation via NOR gates
POS => NOR
a
b

c
d f

g
h
a
b
There is a one-to-one mapping c
between OR-AND network and d f
NOR network
g
h

Dr. Rik Dey ESC201, 2023-24 Sem-II 32

 Simplification of Boolean Expression
• Simplification allows us to implement the expression
• using fewer gates
• using gates with fewer inputs

• How to simplify a Boolean expression in SOP or POS form

• Minimize the number of product terms is SOP or sum terms in POS
• Minimize the number of literals in each term

Simplification  Minimization

Dr. Rik Dey ESC201, 2023-24 Sem-II 33

 How to show equivalency of two expressions?
• Compare the truth table on both side

• Show 𝑥 + 𝑥 = 𝑥

𝑥 𝑥 𝑥+𝑥
0 0 0
1 1 1

Dr. Rik Dey ESC201, 2023-24 Sem-II 34

 How to show equivalency of two expressions?
• Compare the truth table on both side

• Show 𝑥 . 𝑦 = 𝑥ҧ + 𝑦ത

𝑥 𝒚 𝑥 .𝑦 𝑥ҧ + 𝑦ത
0 0 1 1
1 0 1 1
0 1 1 1
1 1 0 0
Dr. Rik Dey ESC201, 2023-24 Sem-II 35
 How to verify an expression?
• Using truth tables

• Using postulates

(x1.x 2 + x 2 .x 3 ) == ?x1. x 2 + x 2 .x 2 +x1 . x 3 + x 2 . x 3

Dr. Rik Dey ESC201, 2023-24 Sem-II 36

 Boolean Algebra

(x1.x 2 + x 2 .x 3 ) == ?(x1. x 2 ) . (x 2 . x 3 )

= (x1 +x 2 ) . (x 2 + x 3 )

= (x1 + x 2 ) . (x 2 + x 3 )

= x1. x 2 + x 2 .x 2 +x1 . x 3 + x 2 . x 3

= x1. x 2 + x1 . x 3 + x 2 . x 3

Dr. Rik Dey ESC201, 2023-24 Sem-II 37

 Simplification using Boolean Algebra

f = 𝑥.lj 𝑥lj + 𝑥𝑥lj + 𝑥.lj 𝑦lj + 𝑥. 𝑦lj

f = 𝑥lj + 𝑥.lj 𝑦lj + 𝑥. 𝑦lj

f = 𝑥lj + 𝑦.lj 𝑥lj + 𝑥

f = 𝑥lj + 𝑦lj

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

Dr. Rik Dey ESC201, 2023-24 Sem-II 38

 Implementation via Logic Gates after Simplification

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

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

Simplification will yield y = x3 which does not require any gates at all !

Dr. Rik Dey ESC201, 2023-24 Sem-II 39

 Digital Design Flow
x y z f
System Description 0 0 0 0
0 0 1 1
0 1 0 0
Truth Table 0 1 1 1
1 0 0 0
x 1 0 1 1
y 1 1 0 0
system f
1 1 1 1
z

Boolean Expression f = x .y . z + x . y . z + x . y . z + x . y . z

Minimized ⇒ f=𝑧
Boolean Expression

Gate Netlist
Dr. Rik Dey ESC201, 2023-24 Sem-II 40
 Compact Representation: Min-terms
• SOP => sum of min-terms

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)

f 2 =  (0, 2,3) = ? f 2 = x . y + x. y + x . y
Dr. Rik Dey ESC201, 2023-24 Sem-II 41
 Compact Representation: Min-terms
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

f 2 =  (1, 4, 7) = ? f 2 = x . y. z + x. y. z + x . y . z
Dr. Rik Dey ESC201, 2023-24 Sem-II 42
 Compact Representation: Max-terms
• POS => product of maxterms

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 )

f1 = M 0  M 3 f1 =  (M 0 , M 3 )
Dr. Rik Dey ESC201, 2023-24 Sem-II 43
 Compact Representation: Max-terms
Three variable functions
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

f12 =  (1,5, 7) = ? f 2 = (x + y + z ).( x + y + z ).( x + y + z )

Dr. Rik Dey ESC201, 2023-24 Sem-II 44
 Systematic Simplification
• Karnaugh map (K-map) is a popular technique

• An intuitive method of applying the following principles

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

y
x y min term 0 1
x
0 0 x.y m0 0 m0 m1 only x is different
0 1 x.y m1
1 0 x.y m2
1 m2 m3
1 1 x.y m3
only 1 bit is different
only y is different
Dr. Rik Dey ESC201, 2023-24 Sem-II 45
 K-map Example

x y f1 y
x 0 1
0 0 0
f1 = ෍(1,2) 0 0 1
0 1 1
1 0 1
1 1 0 1 1 0

y
x 0 1
0 1 0
f2 = 𝑥. 𝑦 + 𝑥. 𝑦 f2 = ෍(0,4)
1 0 1

Dr. Rik Dey ESC201, 2023-24 Sem-II 46

 K-map with 3 variables

yz yz
x 00 01 11 10 x 00 01 11 10
0 m0 m1 m3 m2 0 1 1 0
0
1 m4 m5 m7 m6 1 0 1 1 0 only 1 bit is different

Dr. Rik Dey ESC201, 2023-24 Sem-II 47

 K-map with 3 variables: Example

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

Dr. Rik Dey ESC201, 2023-24 Sem-II 48

 K-map with 4 variables
yz
w x y z min terms
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

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

Dr. Rik Dey ESC201, 2023-24 Sem-II 49

 How does a K-map help?

y
f2 = ෍(1,2,3) x 0 1
1s that are next to each other
0 0 1 represent possible groupings

1 1 1

𝑓 = 𝑥 ⋅ 𝑦lj + 𝑥 ⋅ 𝑦 + 𝑥lj ⋅ 𝑦
Each circle (pair of 1s)
= 𝑥 ⋅ 𝑦lj + 𝑥 ⋅ 𝑦 + 𝑥lj ⋅ 𝑦 + 𝑥 ⋅ 𝑦 represents a simplified term

= 𝑥 ⋅ 𝑦lj + 𝑦 + 𝑥lj + 𝑥 ⋅ 𝑦

Dr. Rik Dey

=𝑥+𝑦 ESC201, 2023-24 Sem-II 50
 Simplification using K-map: Grouping of 21 = 2 terms

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

1 0 1 1 0 x. z

x. z f = x . z + x. z
Dr. Rik Dey ESC201, 2023-24 Sem-II 51
 Simplification using K-map: Grouping of 22 = 4 terms

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

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

1 1 1 1 1 four 1s together represent double grouping

x

Dr. Rik Dey ESC201, 2023-24 Sem-II 52

 Simplification using K-map: Grouping of 22 = 4 terms
yz yz
x 00 01 11 10 x 00 01 11 10
0 1 1 0 0 1 0 0 1
0
1 0 1 1 0 1 1 0 0 1

z z

yz
x 00 01 11 10
𝑧
0 1 0 0 1
f=𝑥+𝑧
1 1 1 1 1

𝑥
Dr. Rik Dey ESC201, 2023-24 Sem-II 53
 K-map Caveat: Grouping Only Powers of 2 Rectangle
• Do not circle 3 terms

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

Dr. Rik Dey ESC201, 2023-24 Sem-II 54

 K-map: 4-variable Minimization

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

00 1 0 1 0 00 1 0 1 0

0 1 1 0 01 0 1 1 0
01
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

Dr. Rik Dey ESC201, 2023-24 Sem-II 55

 K-map: 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 Is this the
simplest
f = w . y. z + w . x. z + w . y. z + w . x . y. z + w . x . y. z expression ?
Dr. Rik Dey ESC201, 2023-24 Sem-II 56
 K-map: 4-variable Minimization
yz
wx 00 01 11 10
00 1 0 1 0
x. y. z 0 1 1 0
w. y . z
01
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
Can we do
ever better?
Dr. Rik Dey ESC201, 2023-24 Sem-II 57
 K-map: 4-variable Minimization
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
Dr. Rik Dey ESC201, 2023-24 Sem-II 58
 K-map Minimization: Non-uniqueness
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

Minimized expression may not be unique

Dr. Rik Dey ESC201, 2023-24 Sem-II 59
 K-map: Combining Group of 4

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

10 0 1 1 0
y.z
Dr. Rik Dey ESC201, 2023-24 Sem-II 60
 K-map: Combining Group of 8
yz yz
wx 00 01 11 10 wx 00 01 11 10

00 0 1 1 0 00 0 0 0 0

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

10 0 1 1 0 10 0 0 0 0

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

01 1 0 0 1 0 0 0 0
01
11 1 0 0 1
z 11 0 0 0 0
x
10 1 0 0 1 10 1 1 1 1
Dr. Rik Dey ESC201, 2023-24 Sem-II 61
 K-map: Combining Group of 8
yz yz
wx 00 01 11 10 wx 00 01 11 10
00 0 0 0 0 00 0 1 1 0

01 1 0 0 1 01 0 0 0 0

11 1 0 0 1
x. z 11 0 0 0 0
x. z
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 0 1 00 1 0 1 0

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 0 1 10 1 0 1 0
Dr. Rik Dey ESC201, 2023-24 Sem-II 62
 K-map: Combining Group of 2k

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 1 1 0 1
01
11 1 1 1 1 11 1 1 1 1

10 0 0 0 1 10 0 0 0 1

Dr. Rik Dey ESC201, 2023-24 Sem-II 63

 K-map Caveat: Positioning of Min-terms
Can we use a map 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. 64
Dr. Rik Dey ESC201, 2023-24 Sem-II
 K-map Caveat: Positioning of Min-terms
yz
x 00 01 10 11 f = x . y. z + x. y.z
0 0 1 0 1
= x .( y + y ).z = x.z
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.

Kmap requires information to be represented in such a way

x + x=1
that it is easy to apply the principle

Dr. Rik Dey ESC201, 2023-24 Sem-II 65