ANALOG AND DIGITAL

ELECTRONICS
COURSE CODE 18ISI34
MODULE-3

The Basic Gates

&
Combinational Logic Circuits
1
REFERRED BOOKS
 Donald P Leach, Albert Paul Malvino &
Goutam Saha: Digital Principles and
Applications, 8th Edition, Tata McGraw Hill,
2015
 Stephen Brown, Zvonko Vranesic:
Fundamentals of Digital Logic Design with
VHDL, 7th Edition, Tata McGraw Hill, 2015.

2
 THE BASIC GATES
3
BASIC GATES-1
 A logic gate is a digital circuit with 1 or more input
voltages but only 1 output voltage.
 Logic gates are the fundamental building blocks of
digital systems.
 By connecting the different gates in different ways,
we can build circuits that perform arithmetic and
other functions associated with the human brain.
 Because the circuits simulate mental processes,
gates are often called logic circuits. NOT, OR & AND
gates are the basic types of gates.
 The inter-connection of gates to perform a variety of
logical operations is called logic design.
 The operation of a logic gate can be easily
understood with the help of "truth table".
 A truth table lists all possible combinations of inputs 4
and the corresponding outputs.
BASIC GATES-2
 NOT GATE (INVERTER)
 It is a gate with only 1 input and a

complemented output.

5
BASIC GATES-3
 AND GATE
 This is a gate with 2 or more inputs.

 The output is HIGH only when all inputs are

HIGH.

6
BASIC GATES-4

7
BASIC GATES-5
 OR GATE
 This is a gate with 2 or more inputs.

 The output is HIGH when any input is HIGH.

8
BASIC GATES-6

9
BASIC GATES-9
 NOR GATE
 This represents an OR gate followed by an

inverter.

10
BASIC GATES-10
 Universality of NOR Gate

11
BASIC GATES-11
 NAND GATE
 This represents an AND gate followed by an

inverter.

12
BASIC GATES-12
 Universality of NAND Gate

13
POSITIVE AND NEGATIVE LOGIC-1
 We use a binary 0 for low voltage and a
binary 1 for high voltage. This is called
positive logic.
 Another code known as negative logic where

binary 0 stands for high voltage and binary 1

for low voltage.

14
POSITIVE AND NEGATIVE LOGIC-2
 Positive and Negative Gates
 An OR gate in a positive logic system

becomes an AND gate in a negative logic

system.

Positive logic system Negative logic system 15

POSITIVE AND NEGATIVE LOGIC-3
 In a similar way, we can show the truth table
of other gates with positive or negative logic.
By analysing the inputs and outputs in terms
of 0s and ls, you find these equivalences
between the positive and negative logic:

16
POSITIVE AND NEGATIVE LOGIC-4
 Assertion-level logic
 Logic circuits with bubbles on all pins

with active-low signals and omit

bubbles on all pins with active-high
signals. This use of bubbles with active-
low signals is called assertion-level
logic.
 If a low input signal turns on a chip, you show

a bubble on that input. If a low output is a

sign of chip action, you draw a bubble on
that output. Once you get used to assertion-
level logic, you may prefer drawing logic 17

circuits this way.

INTRODUCTION TO HDL-1
 HDL is a language that describes the hardware of digital
systems in a textual form. It resembles a programming
language, but is specifically oriented to describing
hardware structures, dataflow and behaviors.
 The main difference with the traditional programming
languages is HDL’s representation of extensive parallel
operations whereas traditional ones represents mostly
serial operations. HDL can be used to represent logic
diagrams, Boolean expressions, and other more complex
digital circuits
 There are two standard HDL’s that are supported by IEEE.
 VHDL (Very-High-Speed Integrated Circuits Hardware
Description Language) - Sometimes referred to as VHSIC HDL,
this was developed from an initiative by US. Dept. of Defense.
 Verilog HDL – developed by Cadence Data systems and later
18
transferred to a consortium called Open Verilog International
(OVI).
INTRODUCTION TO HDL-2
 Verilog: Verilog HDL has a syntax that describes
precisely the legal constructs that can be used in the
language.
 It uses about 100 keywords pre-defined, lowercase,
identifiers that define the language constructs.
 Example of keywords: module, endmodule, input,
output wire, and, or, not , etc.,
 Any text between two slashes (//) and the end of line is
interpreted as a comment.
 Blank spaces are ignored and names are case sensitive.
 A module is the building block in Verilog. It is declared
by the keyword module and is always terminated by the
keyword endmodule. Each statement is terminated with
a semicolon, but there is no semi-colon after 19
endmodule.
INTRODUCTION TO HDL-3

20
INTRODUCTION TO HDL-4
module or_gate (A, B, Y);
input A, B; / / defines two input port
output Y; / / defines one output port
or g1(Y,A,B); /*Gate declaration with predefined
keyword or representing logic
OR, g1 is optional user defined
gate indentifier*/
endmodule

 The syntax for the basic gate

 E.g. For OR gate or (output, input 1, input 2,
input 3, input 4) 21

 For NOT gate, not (output, input)

INTRODUCTION TO HDL-5
module eg1(A,B,C,D,Y);
input A,B,C,D;
output Y;
wire and_opl, and_op2;·
and gl(and_opl,A,B); //g1 represents upper AND gate
and g2(and_op2,C,D); //g2 represents lower AND
gate
or g3(Y,and_opl,and_op2); // g3 represents the OR
gate
endmodule
22
INTRODUCTION TO HDL-6
module eg2(a,b,c,x,y);
input a,b,c;
output x,y;
wire or_op1, or_op2;
or g1(or_op1,a,b);
or g2(or_op2,b,c);
nor g13(x,c,or_op1);
nand g4(y,or_op1,or_op2);
endmodule
23
 COMBINATIONAL LOGIC
CIRCUITS
24
SUM-OF-PRODUCTS (SOP)
METHOD-1
 Possible ways to AND two or more input
signals that are in complement and
uncomplement form.
 A SOP expression is two or more AND

functions ORed together.

25
SUM-OF-PRODUCTS (SOP)
METHOD-2
 ANDing two variables and their
complements

26
SUM-OF-PRODUCTS (SOP)
METHOD-3
 The fundamental products are also called
minterms.
 Products are represented by m0, m1, m2 and

m3 respectively. The suffix i of mi comes

from decimal equivalent of binary values that
makes corresponding product term high.

27
SUM-OF-PRODUCTS (SOP)
METHOD-4
 Example:
 Fundamental Products for Three Inputs

28
SUM-OF-PRODUCTS (SOP)
METHOD-5
 The above three variable minterms can
alternatively be represented by mo, m1, m2,
m3, m4, m5, m6, and m7 respectively. Note
that, for n variable problem there can be 2n
number of minterms.
 The fundamental products by listing

each one next to the input condition

that results in a high output.
 For instance, when A = 1, B = 0 and C = 0,

the fundamental product results in an output

of
29
SUM-OF-PRODUCTS EQUATION-1
 Sum-of-Products Equation
 The Sum-of-products solution, for given a truth table shown
below.

 Write down the fundamental product for each output 1 in the

truth table. For example, the first output 1 appears for an input of 30
A = 0, B = 1, and C = 1. The corresponding fundamental product
is .
SUM-OF-PRODUCTS EQUATION-2

 To get the sum-of-products equation, all you

have to do is OR the fundamental products

 Alternate representation

31
SUM-OF-PRODUCTS EQUATION-3
 where '∑:' symbolizes summation or logical
OR operation that is performed on
corresponding minterm’s and Y = F (A, B, C)
means Y is a function of three Boolean
variables A, B and C. This kind of
representation of a truth table is also known
as canonical sum form.

32
LOGIC CIRCUIT

33
LOGIC CIRCUIT
 Lab Experiment
 Design and implement Half adder, Full Adder,
Half Subtractor, Full Subtractor using basic gates.
 Half Adder:
 Truth Table for Half Adder
Input Output
A B Sum (S) Carry (C)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
 Logic Expression

34
LOGIC CIRCUIT

35
TRUTH TABLE TO KARNAUGH
MAP-1
 A Karnaugh map (K-Map) is a visual display of
the fundamental products needed for a sum-
of-products solution.
 Also simplification of logical expression.

36
TRUTH TABLE TO KARNAUGH
MAP-2
 Two-Variable Maps
 Example: Y =F(A,B)= ∑m(2,3)

 Example: Y = F(A,B)=∑m(1,2,3)

37
TRUTH TABLE TO KARNAUGH
MAP-3
 Three-Variable Maps
 Example: Y = F(A, B, C) = ∑m(2,6,7)

38
TRUTH TABLE TO KARNAUGH
MAP-4

A B , A B , AB , A B ?

39
TRUTH TABLE TO KARNAUGH
MAP-4

A B , A B , AB , A B ?

40
TRUTH TABLE TO KARNAUGH
MAP-5
 Four-Variable Maps
 Example: Y= F(A,B,C,D)= ∑m(1,6,7,14)

41
TRUTH TABLE TO KARNAUGH
MAP-6
 Five-Variable Maps
 Example:

 Y= F(A,B,C,D,E)= ∑m(1,6,7,14,20,25,30,31)

42
TRUTH TABLE TO KARNAUGH
MAP-6
 Five-Variable Maps
 Example:

 Y= F(A,B,C,D,E)= ∑m(1,6,7,14,20,25,30,31)

1 3 7 5 0 2 6 4
1 1 1 1 1 1
9 8
1 5 3 0 4 2
2 2 3 2 2 2 3 2
5 7 1 9 4 6 0 8
1 1 2 2 1 1 2 2
7 9 3 1 6 8 2 0

43
TRUTH TABLE TO KARNAUGH
MAP-6
 Five-Variable Maps
 Example:

 Y= F(A,B,C,D,E)= ∑m(1,6,7,14,20,25,30,31)

1 3 7 5 0 2 6 4
1 1 1 1 1 1
9 8
1 5 3 0 4 2
2 2 3 2 2 2 3 2
5 7 1 9 4 6 0 8
1 1 2 2 1 1 2 2
7 9 3 1 6 8 2 0

44
TRUTH TABLE TO KARNAUGH
MAP-6
 Five-Variable Maps
 Example:

 Y= F(A,B,C,D,E)= ∑m(1,6,7,14,20,25,30,31)

1 3
0 7
1 5
0 0 2
0 6
1 4
0
0 1
0 1
0 1
0 0 1
0 1
1 1
0
9 8
1 5 3 0 4 2
1
2 0
2 1
3 0
2 0 0 1 0
2 2 3 2
5
0 7
0 1
0 9
0 4
0 6
0 0
0 8
1
1 1 2 2 1 1 2 2
7 9 3 1 6 8 2 0

45
TRUTH TABLE TO KARNAUGH
MAP-7
 Five-Variable Maps

46
PAIRS, QUADS, AND OCTETS-1
 Pairs
 The map contains a pair of 1s that are

horizontally or vertically adjacent.

 To reduce the one variable

 Y = ABC

47
PAIRS, QUADS, AND OCTETS-2
 Example

48
PAIRS, QUADS, AND OCTETS-3
 The Quad
 A quad is a group of four ls that are

horizontally or vertically adjacent.

 A quad eliminates two variables and their

complements.

49
PAIRS, QUADS, AND OCTETS-4
 The Octet
 The octet is a group of eight 1 s.

 Octet eliminates three variables and their

complements.

50
KARNA UGH SIMPLIFICATIONS-1
 The Karnaugh map uses the following rules for the
simplification of expressions
by grouping together adjacent cells containing ones.
 After drawing a Kamaugh map,
 Encircle the octets first,
 The quads second, and
 The pairs last.

51
KARNAUGH SIMPLIFICATIONS-2
 Groups may not include any cell
containing a zero.

 Groups may be horizontal or vertical,

but not diagonal.

52
KARNAUGH SIMPLIFICATIONS-3
 Groups must contain 1, 2, 4, 8, or in general
2n cells.
 That is if n = 1, a group will contain two 1's
since 21 = 2.
 If n = 2, a group will contain four 1's since 22 =
4.

53
KARNAUGH SIMPLIFICATIONS-4
 Each group should be as large as possible.

 Each cell containing a one must be in at least one

group.

54
KARNAUGH SIMPLIFICATIONS-5
 Groups may overlap.

 Groups may wrap (Rolling the Map) around the table. The leftmost
cell in a row may be grouped with the rightmost cell and the top cell
in a column may be grouped with the bottom cell.

55
KARNAUGH SIMPLIFICATIONS-6
 Rolling the Map

56
KARNAUGH SIMPLIFICATIONS-7
 Always overlap groups if possible
 Use the 1s more than once to get the largest

groups you can.

57
KARNAUGH SIMPLIFICATIONS-8
 There should be as few groups as
possible, as long as this does not
contradict any of the previous rules.

58
KARNAUGH SIMPLIFICATIONS-9
 Five Variable
 Y= F(A,B,C,D,E)= ∑m(6,12,13,14)

59
KARNAUGH SIMPLIFICATIONS-10

60
KARNAUGH SIMPLIFICATIONS-11
1. No zeros allowed (Only in SOP).
2. No diagonals.
3. Only power of 2 number of cells in each
group.
4. Groups should be as large as possible.
5. Every one must be in at least one group.
6. Overlapping allowed.
7. Wrap around allowed.
8. If possible roll and overlap to get the largest
groups you can find.
61
9. Fewest number of groups possible.
K- MAP GROUPING EXAMPLES-1
 Rolling and overlapping

62
K- MAP GROUPING EXAMPLES-2

63
ELIMINATING REDUNDANT
GROUPS-1
 A groups of 1s (or 0s for POS) whose all
members are overlapped by other groups is
called redundant group. We don’t consider
this group while writing the simplified
equations from the K-map.
 In the above K-map the group which is
represented by the oval is a redundant group
and hence while writing the equations we ignore
it or we don’t make this kind of group and the K-
map representation becomes as given next:
 The equation we get is
F= yz’w’ + x’z’w (ignoring the redundant group)
 If we consider this group then equation would be
F= yz’w’ + x’z’w + x’yz’
And this is a not the simplified expression and
hence WRONG. 64
ELIMINATING REDUNDANT
GROUPS-1
 A groups of 1s (or 0s for POS) whose all
members are overlapped by other groups is
called redundant group. We don’t consider
this group while writing the simplified
equations from the K-map.
 In the above K-map the group which is
represented by the oval is a redundant group
and hence while writing the equations we ignore
it or we don’t make this kind of group and the K-
map representation becomes as given next:
 The equation we get is
F= yz’w’ + x’z’w (ignoring the redundant group)
 If we consider this group then equation would be
F= yz’w’ + x’z’w + x’yz’
And this is a not the simplified expression and
hence WRONG. 65
ELIMINATING REDUNDANT
GROUPS-2
 A group whose 1s are already used by other
groups.

66
ELIMINATING REDUNDANT
GROUPS-2
 A group whose 1s are already used by other
groups.

67
ELIMINATING REDUNDANT
GROUPS-2
 A group whose 1s are already used by other
groups.

 All the 1 s of the quad are used by the pairs.

Because of this, the quad is redundant and
can be eliminated to get
68
ELIMINATING REDUNDANT
GROUPS-2
 A group whose 1s are already used by other
groups.

69
SUMMARY OF THE KARNAUGH-MAP
METHOD FOR SIMPLIFYING BOOLEAN
EQUATIONS
1. Enter a 1 on the Karnaugh map for each
fundamental product that produces a 1
output in the truth table. Enter 0s
elsewhere.
2. Encircle the octets, quads, and pairs.
Remember to roll and overlap to get the
largest groups possible.
3. If any isolated 1s remain, encircle each.
4. Eliminate any redundant group.
5. Write the Boolean equation by ORing the
products corresponding to the encircled
70
groups.
K- MAP GROUPING EXAMPLES
 For problem on K-Map refer text book and
VTU question papers.

71
ENTERED VARIABLE MAP-1
 One of the input variable is placed inside
Kamaugh map
 This reduces the Karnaugh map size by one

degree.
 i.e. a three variable problem that requires 23

= 8 locations in Karnaugh map will require

2(3-l) = 4 locations in entered variable map.
 This technique is particularly useful for

mapping problems with more than four input

variables.
72
ENTERED VARIABLE MAP-2
 Example
 Example: Y = F(A, B, C) = ∑m(2,6,7)

A B C Y A B Y
0 0 0 0 0 0
0
0 0 1 0 0 0
0 1 0 1 0 1
0 1 1 0 0 1
1 0 0 0 1 0
0
1 0 1 0 1 0 K-MAP for
1 1 0 1 1 1 EVM Table
1
1 1 1 1 1 1
73
Truth Table EVM Table
ENTERED VARIABLE MAP-3
 Let's choose C as map entered variable and
see how output Y varies with C for different
combinations of other two variables A and B.
 For AB= 00 we find Y = 0 and is not

dependent on C.
 For AB= 01 we find Y is complement of C

thus we can write Y = .

 Similarly,for AB= 10, Y = 0 and for AB= 11,

Y= 1.

74
ENTERED VARIABLE MAP-4
 If choose A as map entered variable write the
corresponding entered variable map.

 If choose B as map entered variable write the

corresponding entered variable map.
A C Y
0 0 0
0 1
75
1 0 C
1 1 1
SIMPLIFICATION OF ENTERED
VARIABLE MAP-1
 This is similar to Karnaugh map method.
A B Y A B Y
0 0 0 0 0
0
0 0 0 1
0 1 1 0 0
0 1 1 1 1
1 0
0
1 0 Y=B+AB
1 1
1
1 1

 Note that is grouped with 1 to get a larger 76

group as 1 can be written as 1 = 1 + .
SIMPLIFICATION OF ENTERED
VARIABLE MAP-2
 The product term representing each group is
obtained by including map entered variable
in the group as an additional ANDed term.

Y=B+AB Y=AC+B
77
EXAMPLE-1
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

78
EXAMPLE-1
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

79
EXAMPLE-1
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

80
EXAMPLE-1
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

81
EXAMPLE-1
 What is the simplified Boolean equation for
the following logic equation expressed by
minterms? Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12,
13, 14, 15)

82
EXAMPLE-2
 Simplify the following Boolean function
in sum of products form (SOP) F(x, y, z,
w) = ∑m(0, 1, 2, 5, 8, 9, 10)

 F= + +
83
DON'T-CARE CONDITIONS-1
 In digital systems, certain input conditions
never occur during normal operation;
therefore, the corresponding output never
appears. Since the output never appears, it is
indicated by an X in the truth table.
 The X is called a don 't-care condition.

Whenever you see an X in a truth table, you

can let it equal either 0 or 1, whichever
produces a simpler logic circuit.

84
DON'T-CARE CONDITIONS-2
 Truth Table with Don't-Care Conditions

 Y=F(A,B,C,D) = ∑m (9) + 85
d(10,11,12,13,14,15)
DON'T-CARE CONDITIONS-3

86
DON'T-CARE CONDITIONS-4
 Ideas about don't-care conditions:
1. Given the truth table, draw a Karnaugh map
with 0s, 1s, and don't-cares (X).
2. Encircle the actual 1s on the Karnaugh map
in the largest groups you can find by
treating the don't cares as 1s.
3. After the actual 1s have been included in
groups, disregard the remaining don't cares
by visualizing them as 0s.

87
DON'T-CARE CONDITIONS-5
 What is the simplest logic circuit for the
following truth table?
A B C D Y
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X 88
1 1 1 1 X
DON'T-CARE CONDITIONS-6
Give the simplest logic circuit for following
logic equation where d represents don't-care
condition for following locations.
F(A, B, C, D) = ∑m(7) + d(10, 11, 12, 13, 14,
15)

89
EXAM QUESTIONS
 VTU QP

cd 00 01 11 10 yz 00 01 11 10
ab wx

00 0 0
X 1
0 3
0 2
00 0 0
1 1
X 3
1 2

01 X 4
X 5
1 7
1 6
01 1 4
1 5
X 7
1 6

11 0 12
1 13
0 15
0 14
11 0 12
X 13
1 15
0 14

10 0 1 X 1 10 1 1 1 0
8 9 11 10 8 9 11 10

90
PRODUCT-OF-SUMS METHOD-1
 Given a truth table, you identify the
fundamental sums needed for a logic design.
Then by ANDing these sums, you get the
product-of-sums equation corresponding to
the truth table.
 But, in the sum-of-products method, the

fundamental product produces an output l for

the corresponding input condition. But with
the product of- sums method, the
fundamental sum produces an output 0 for
the corresponding input condition.
91
PRODUCT-OF-SUMS METHOD-2
 Converting a Truth Table to an Equation

92
PRODUCT-OF-SUMS METHOD-3
 Logic Circuit

93
PRODUCT-OF-SUMS METHOD-4
 Conversion between SOP and POS
 SOP and POS occupy complementary

locations in a truth table.

 Identifying
complementary locations,
 Changing minterm to maxterm or reverse, and
 Changing summation by product or reverse.

94
CONVERSION BETWEEN SOP AND
POS
 Mapping between canonical forms
 Minterm to maxterm conversion
 use maxterms whose indices do not appear in minterm
expansion
 e.g. F(A,B,C) = ∑m(1,3,5,6,7) = ∏M(0,2,4)
 Maxterm to minterm conversion
 use minterms whose indices do not appear in maxterm
expansion
 e.g. F(A,B,C) = ∏ M(0,2,4) = ∑ m(1,3,5,6,7)
 Minterm expansion of F to minterm expansion of
 use minterms whose indices do not appear
 e.g., F(A,B,C) = ∑ m(1,3,5,6,7) (A,B,C) = ∑
m(0,2,4)
 •Maxterm expansion of F to maxterm expansion of
 use maxterms whose indices do not appear
 e.g., F(A,B,C) = ∏ M(0,2,4) ’(A,B,C) = ∏ 95
M(1,3,5,6,7)
PRODUCT-OF-SUMS SIMPLIFICATION-1
 SOP Simplification

 Complementary
Circuit

96
PRODUCT-OF-SUMS SIMPLIFICATION-2
 Using Karnaugh map by grouping zeros

97
EXAMPLE-1
 Give SOP form of Y = F(A, B, C, D) = ∏M(0,3,
4, 5, 6, 7, 11, 15)

CD
AB
00 01 11 10
00 0 0 1 1 0 3 1 2

01 0 4 0 5 0 7 0 6

11 1 12
1 13
0 15
1 14

10 1 8
1 9
0 11
1 10

98
EXAM QUESTIONS
 Simplify the following using K-Map

 By Grouping 1’s By Grouping 0’s

BC
A
00 01 11 10 BC
A
00 01 11 10
0 0 0 1 1 0 3 1 2 0 0 0 1 1 0 3 1 2

1 1 4 1 5 1 7 0 6 1 1 4 1 5 1 7 0 6

99
EXAMPLE
Find the SOP for following expression using K-
Map
f (x1, x2, x3, x4, x5) =∑m(0, 1, 4, 8, 13, 15,
20, 21,
23, 26, 31) + D(5, 10, 24, 28)

100
SIMPLIFICATION BY QUINE-MCCLUSKY
METHOD-1
 Tabular Method of Minimisation
 Karnaugh map method though very simple

and intuitively appealing is somewhat

subjective.
 It depends on the user's ability to identify

patterns that gives largest size.

 Also the method becomes difficult to adapt

for simplification of 5 or more variables.

 Quine-McClusky method involves preparation

of two tables; one determines prime

implicants and the other selects essential
101
prime implicants to get minimal expression.
QUINE-MCCLUSKY METHOD-2
 Literal: Each appearance of a variable, either
uncomplemented or complemented, is called a literal.
 Implicant: A product term that indicates the input
valuation(s) for which a given function is equal to 1 is
called an implicant of the function.
 Prime Implicant
 An implicant is called a prime implicant if it cannot be
combined into another implicant that has fewer literals.
Another way it is impossible to delete any literal in a
prime implicant and still have a valid implicant.
 Prime implicants are expressions with least number of
literals that represents all the terms given in a truth
table. Prime implicants are examined to get essential
prime implicants for a particular expression that avoids 102
any type of duplication.
QUINE-MCCLUSKY METHOD-3
 Determination of Prime Implicants
 Example

103
QUINE-MCCLUSKY METHOD-4
 In Stage 1 of the process, to
find out all the terms that
gives output 1 from truth table
and put them in different
groups depending on how
many 1s input variable
combinations (ABCD) have.
 For example, first group has

no l in input combination,
second group has only one 1,
third two 1 s, fourth three ls
and fifth four 1s. 104
QUINE-MCCLUSKY METHOD-5
 In Stage 2, we first try to combine first and second group of
Stage I, on a member to member basis.
 The rule is to see if only one binary digit is differing between two
members and we mark that position by ‘−’. This means
corresponding variable is not required to represent those
members.
 Thus (0) of first group combines with (1) of second group to form
(0,1) in Stage 2 and can be represented by
A'B'C' (0 0 0 −).
 Proceed in the same manner to find rest of the combinations in
successive groups of Stage 1 and table them as in figure.
 Note that, we need not look beyond successive groups to find
such combinations as groups that are not adjacent, differ by
more than one binary digit. Also note that each combination of
Stage 2 can be represented by three literals.
 All the members of particular stage, which finds itself in at least 105
one combination of next stage are tick (√) marked. This is
followed for Stage 1 terms as well as trms of other stages.
QUINE-MCCLUSKY METHOD-6

106
QUINE-MCCLUSKY METHOD-7
 In Stage 3, we combine members of different
groups of Stage 2 in a similar way. Now it will
have two '−‘ elements in each combination.
This means each combination requires two
literals to represent it.
 For example (0,1,2,3) is represented by A'B' (0

0 − −).
 There are three other groups in Stage 3;

(2,10,3,11) represented by B'C, (10,14,11,15)

by AC and (12,13,14,15) by AB.
 Note that, (0,2,1,3), (10,11,14,15) and
(12,14,13,15) get represented by A'B, AC and 107
AB respectively and do not give any new term.
QUINE-MCCLUSKY METHOD-8

108
QUINE-MCCLUSKY METHOD-9
 There is no Stage 4 for this problem as no
two members of Stage 3 has only one digit
changing among them. This completes the
process of determination of prime implicants.
 The rule is all the terms that are not ticked at

any stage is treated as prime implicants for

that problem.

109
QUINE-MCCLUSKY METHOD-10
 Selection of Prime Implicants
 Once we are able to determine prime
implicants that covers all the terms of a truth
table we try to select essential prime
implicants and remove redundancy or
duplication among them.
 To find a minimum expression we construct a

prime implicant table in which there is a row

for each prime implicant and a column for
each minterm that must be covered.
 Note- don't care values are not included.

 Then we place check marks to indicate the 110

minterms covered by each prime implicant.

QUINE-MCCLUSKY METHOD-11

 Selection of essential prime implicants from this table is done in

the following way.
 If column has a single √, than the implicant associated with the
row is essential. It must appear in final expression.
 Find minimum set of rows that cover the remaining columns Or
Find minimum number of prime implicants that covers all the
minterms.
 E.g. Find A' B' and AB cover terms that are not covered by others
and they are essential prime implicants. B'C and AC among
themselves cover 10, 11 which are not covered by others.
 So, one of them has to be included in the list of essential prime
implicants making it three. 111
QUINE-MCCLUSKY METHOD-12
Get a minimized expression for
using K-map, EVM and quine mcclusky
method

112
QUINE-MCCLUSKY METHOD-13
 Get simplified expression of Y = F(A, B, C, D,
E) =∑m(0,1,2,3,4,5,12,13,14,26,27,28,29,30)
using Quine-McClusky method.
Decimal A B C D E
0 0 0 0 0 0
1 0 0 0 0 1
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 1 0 0
5 0 0 1 0 1
12 0 1 1 0 0
13 0 1 1 0 1
14 0 1 1 1 0
26 1 1 0 1 0
27 1 1 0 1 1
28 1 1 1 0 0
113
29 1 1 1 0 1
30 1 1 1 1 0
HAZARDS AND HAZARD COVERS-1
 Simplification techniques that give minimal
expression for a logic equation which in turn
requires minimum hardware for realization.
 Some practical problems, in certain cases we

may prefer to include more terms than given

by simplification techniques.
 So far we considered gates generating

outputs instantaneously. But practical circuits

always offer finite propagation delay though
very small, in nanosecond order.
 This gives rise to several hazards (Glitch) and
114
hazard covers
HAZARDS AND HAZARD COVERS-2
 Static-1 Hazard 1→0
 Static-0 Hazard 0→1

 Dynamic Hazard

115
HAZARDS AND HAZARD COVERS-3
 Static-1 Hazard
 For example output is always
logic 1.
 But the NOT gate output takes
finite time to become 1
following 1→0 transition of A.
 Thus for the OR gate there are
two zeros appearing at its
input for that small duration,
resulting a 0 at its output. The
width of this zero is in
nanosecond order and is
called a glitch.
 For combinational circuits it
may go unnoticed but in
sequential circuit may cause
major malfunctioning. 116
HAZARDS AND HAZARD COVERS-4
 For this circuit input B = 1
and A = 1 and then C makes
transition 1→0. The output
shows glitch.
 Another grouping of same K-
Map, the additional term AB
is term included.
 This circuit though require
more hardware than minimal
representation, is hazard
free.
 The additional term AB
ensures Y = 1 for A = 1, B =
1 through the third input of
final OR gate and a 1→0
transition at C does not 117
affect output.
HAZARDS AND HAZARD COVERS-5
 Static-0 Hazard
 For example output is
always logic 0.
 But the NOT gate output
takes finite time to
become 0 following a
0→1 transition of A.
 Thus for final AND gate
there are two ones
appearing at its input for
a small duration
resulting a 1 at its
output. This Y= 1 occurs
for a very small duration. 118
HAZARDS AND HAZARD COVERS-6
 If B = 0, A= 0 and C
makes a transition 0→1
there will be static-0
hazard occurring at
output.
 To prevent this we add
one additional group, i.e.
one more sum term (A+
B).
 The additional term (A +
B) ensures Y = 0 for A =
0, B = 0 through the third
input of final AND gate
and a 0→1 transition at C
does not affect output. 119
HAZARDS AND HAZARD COVERS-7
 Dynamic Hazard
 Dynamic hazard occurs when circuit output

makes multiple transitions before it settles to

a final value while the logic equation asks for
only one transition.
 An output transition designed as 1→0 may

give 1→0→1 →0 when such hazard occurs

and a 0→1 can behave like 0→1→0→1.
 E.g. or Y = (A + ).A

 These occur in multilevel circuits having

implicit static-1 and/or static-0 hazards.

120