Module 1 PDF

An Autonomous Institute
Affiliated to VTU, Belagavi,

Approved by AICTE, New Delhi,
Recognized by UGC with 2(f) & 12(B)
Accredited by NBA & NAAC
DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING

SUBJECT CODE : MVJ22CS33
SUBJECT NAME: DIGITAL DESIGN and COMPUTER ORGANIZATION
LECTURE PRESENTATION MODULE – 1
FACULTY : Nivedita Sahoo , Asst. Prof, Dept. of CSE
An Autonomous Institution ,Affiliated to Visvesvaraya Technological University, Belagavi. Approved By AICTE, New Delhi. Recognized
1
by UGC with 2(f) & 12(B) status. Accredited by NBA and NAAC.
COURSE OBJECTIVES
The students will be able to :
● Demonstrate the functionalities of binary logic

system
● Explain the working of combinational and sequential
logic system
● Realize the basic structure of computer system
 Illustrate the working of I/O operations and processing
unit.
2
COURSE OUTCOMES
CO1:Apply the K–Map techniques to simplify various Boolean
expressions.
CO2: Design different types of combinational and sequential
circuits along with Verilog programs.
CO3: Describe the fundamentals of machine instructions,
addressing modes and Processor performance.
CO4: Explain the approaches involved in achieving
communication between processor and I/O devices.
CO5: Analyze internal Organization of Memory and Impact of
cache/Pipelining on Processor Performance
3
TEXT BOOK:
1. M. Morris Mano & Michael D. Ciletti, Digital Design With an
Introduction to Verilog Design, 5e, Pearson Education.
2. Carl Hamacher, ZvonkoVranesic, SafwatZaky, Computer
Organization, 5th Edition, Tata McGraw Hill.
REFERENCE BOOKS:
1. Charles H Roth and Larry L Kinney, Fundamentals of Logic
design, Cengage Learning,2019.
2. Anil K Maini, Varsha Agarwal, Electronic Devices and
Circuits, Wiley, 2012
3. Donald P Leach, Albert Paul Malvino & Goutam Saha, Digital
Principles and Applications, 8th Edition, Tata McGraw Hill,
2015
4
BRIDGE CONTENTS
1.Basic logic gates
2.Universal Gates
3.Laws and Rules of Boolean Algebra
5
BRIDGE MATERIAL
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.
6
 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
and the corresponding outputs.
7
BASIC GATES-2
 NOT GATE (INVERTER)
 It is a gate with only 1 input and a complemented output.
8
BASIC GATES-3
 AND GATE ( A.B)
 This is a gate with 2 or more inputs.
 The output is HIGH only when all inputs are HIGH.
9
BASIC GATES-4
10
BASIC GATES-5
 OR GATE (A + B)
 This is a gate with 2 or more inputs.
 The output is HIGH when any input is HIGH.
11
BASIC GATES-6
12
BASIC GATES-7
 NOR GATE
 This represents an OR gate followed by an inverter.
13
BASIC GATES-8
 Universality of NOR Gate
14
BASIC GATES-9
 NAND GATE
 This represents an AND gate followed by an
inverter.
15
BASIC GATES-10
 Universality of NAND Gate
16
EXCLUSIVE-OR GATES-1
 The exclusive-OR gate has a high output only when an
odd number of inputs is high.
 OR
 Y=A B 17
18
 EX-NOR Gate
 Truth Table
A B Y
0 0 1 A
0 1 0 Y
B
1 0 0
1 1 1
 Y=A B

 or 19
20
COURSE CONTENT
Module 1
 Metal Oxide Semiconductor Field Effect
transistor(MOSFET): Structure and I-V characteristics,
MOSFET as a switch, MOSFET as an amplifier, CMOS
and its applications.
 Oscillators: Basic working and applications of RC Phase
shift oscillator, Wien Bridge oscillator, LC oscillator,
Colpitt oscillator, Crystal Oscillator.
 Linear Power Supplies: Constituents of a Linear Power
Supply, Designing Mains Transformer, Linear IC voltage
regulators, Regulated Power Supply Parameters
21
Module 2
Karnaugh maps:
Minimum forms of switching functions, two and three
variable Karnaugh maps, four variable karnaugh maps,
Quine-McClusky Method: determination of prime
implicants, The prime implicant chart, petricks method,
simplification of incompletely specified functions,
simplification using map-entered variables
22
Module 3
Combinational Circuits: Multiplexer, Decoders, Adders,
Subtractors, BCD arithmetic, carry look ahead adder, serial
adder, ALU-Design and popular MSI chips, digital
comparator, parity checker/generator, code converters,
priority encoders, decoders/drivers for display devices
23
Module 4
Flip-Flops and Registers:
Flip Flops: S-R,J-K,D and T flip flops, Edge-triggered JK
FLIP-FLOPs
Registers: Types of Registers, Serial In - Serial Out, Serial In -
Parallel out, Parallel In - Serial Out, Parallel In - Parallel
Out, Universal Shift Register, Applications of Shift
Registers.
Counters: Asynchronous Counters, Decoding Gates,
Synchronous Counters, Changing the Counter Modulus,
Decade Counters, Applications of Counters.
24
Module 5
D/A Conversion and A/D Conversion:
Digital to analog converters: weighted resistor/converter, R-
2R Ladder D/A converter, specifications for D/A converters,
examples of D/A converter lCs, sample and hold circuit.
Analog to digital converters: quantization and encoding,
parallel comparator A/D converter, successive approximation
A/D converter, counting A/D converter, dual slope A/D
converter, A/D converter using voltage to frequency and
voltage to time conversion, specifications of A/D converters,
example of A/D Converter ICs
25
INTRODUCTION
• Each gate input is labelled with a variable.
• Each appearance of a variable or its complement in
an expression will be referred to as a literal.
 The following expression, which has three variables, has 10
literals
 ab′c + a′b + a′bc′ + b′c′
A truth table (also called a table of combinations)
specifies the values of a Boolean expression for every
possible combination of values of the variables in the
expression.
26
INTRODUCTION
 An expression is said to be in sum-of-products (SOP) form when all products
are the products of single variables.
 E.g. AB′ + CD′E + AC′E′
 A sum-of-products expression can be realized using one or more AND
gates feeding a single OR gate at the circuit output.
 An expression is in product-of-sums (POS) form when all sums are the sums
of single variables.
 E.g. (A + B′)(C + D′ + E)(A + C′ + E′)
 A product-of-sums expression can be realized using one or more OR
gates feeding a single AND gate at the circuit output.
27
SOP
28
POS
29
BASICS
1. A .A = A
10:53 PM
2. A+A=A
3. A.1 =A
4. A+A =1
5. 1+A=1
30
INTRODUCTION
Redundant Terms: The Term not or no longer needed or useful.
 (A + BC)(A + D + E)
 = A + AD + AE + ABC + BCD + BCE
 = A(1 + D + E + BC) + BCD + BCE
 = A + BCD + BCE
31
INTRODUCTION
The Consensus Theorem
 Useful in simplifying Boolean expressions.
 The consensus theorem can be used to eliminate redundant
terms from Boolean expressions.
E.g. XY + X′Z + YZ
The term YZ is redundant and can be eliminated to form the

equivalent expression XY + X′Z.
The term that was eliminated is referred to as the consensus
term.
32
10:53 PM
33
 Given a pair of terms for which a variable appears in one term
and the complement of that variable in another, the
consensus term is formed by multiplying the two original
terms together, leaving out the selected variable and its
complement.
 Eg: The consensus of ab and a′c is bc;

 The consensus of abd and b′de′ is (ad)(de′) = ade′.
 The consensus of terms ab′d and a′bd′ is 0.
34
SUM-OF-PRODUCTS (SOP)
METHOD-1
 Possibleways 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.
35
METHOD-2
 ANDing two variables and their complements
36
METHOD-3
 The fundamental products are also called min-terms.
 Products are represented by m0, m1, m2

and m3 respectively.
 The suffix i of m comes from decimal equivalent of

binary values that makes corresponding product term
high.
37
METHOD-4
 Example:
 Fundamental Products for Three Inputs
38
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
39
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 A = 0, B
= 1, and C = 1. The corresponding fundamental product is .
40
10:53 PM
41
 To get the sum-of-products equation, all you have to do

is OR the fundamental products
 Alternate representation
42
 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.
43
LOGIC CIRCUIT
44
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

 45
PRODUCT-OF-SUMS METHOD-1
 Given a truth table, identify the fundamental sums
needed for a logic design. Then by ANDing these
sums, will 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. 46
 Converting a Truth Table to an Equation
47
 Logic Circuit
48
 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.
49
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) = ∏ M(1,3,5,6,7)
50
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.
51
Truth Table with Don’t-Cares
 In Minterm form
 F =Σ m(0, 3, 7) +Σ d(1, 6)
 In Maxterm form
 F =Π M(2, 4, 5)· Π D(1, 6)
52
 Truth Table with Don't-Care Conditions
 Y=F(A,B,C,D) = ∑m (9) + d(10,11,12,13,14,15)
53
KARNAUGH MAPS
 Switching functions can generally be simplified by using the
algebraic techniques.
 However, two problems arise when algebraic procedures are
used:
 1. The procedures are difficult to apply in a systematic way.
 2. It is difficult to tell when you have arrived at a minimum solution.
 The Karnaugh map method and the Quine-McCluskey procedure
used to overcome these difficulties by providing systematic
methods for simplifying switching functions.
 The Karnaugh map is useful tool for simplifying and
manipulating switching functions of three or four variables
(Literals).
54
KARNAUGH MAPS
MINIMUM FORMS OF SWITCHING FUNCTIONS
 When a function is realized using AND and OR gates, the cost of realizing
the function is directly related to the number of gates and gate inputs used.
 The Karnaugh map techniques developed that lead directly to minimum
cost two-level circuits composed of AND and OR gates.
 An expression consisting of a sum of product terms corresponds directly to
a two-level circuit composed of a group of AND gates feeding a single OR
gate.
 Similarly, a product-of-sums expression corresponds to a two-level circuit
composed of OR gates feeding a single AND gate.
 Therefore, to find minimum cost two-level AND-OR gate circuits, we must
find minimum expressions in sum-of-products or product-of-sums form.
55
KARNAUGH MAPS
A minimum sum-of-products expression for a

function is defined as a sum of product terms
which
 (a) has a minimum number of terms and
 (b) of all those expressions which have the same
minimum number of terms, has a minimum number
of literals.
56
Karnaugh Maps
Minimum Forms of Switching Functions
 The minimum sum of products corresponds directly to a

minimum two-level gate circuit which has
 (a) a minimum number of gates and
 (b) a minimum number of gate inputs.
 Unlike the minterm expansion for a function, the minimum

sum of products is not necessarily unique; that is, a given
function may have two different minimum sum-of-products
forms, each with the same number of terms and the same
number of literals.
57
KARNAUGH MAPS
 Given a minterm expansion, the minimum sum-of-products form
can often be obtained by the following procedure:
 1. Combine terms by using the uniting theorem XY′ + XY = X. Do this
repeatedly to eliminate as many literals as possible. A given term may
be used more than once because X + X = X.
 2. Eliminate redundant terms by using the consensus theorem or other
theorems.
 Note: Unfortunately, the result of this procedure may depend on the order in
which terms are combined or eliminated so that the final expression obtained
is not necessarily minimum.
58
KARNAUGH MAPS
 A minimum product-of-sums expression for a function is defined as a

product of sum terms which
 (a) has a minimum number of terms, and
 (b) of all those expressions which have the same number of terms, has a
minimum number of literals.
 Unlike the maxterm expansion, the minimum product-of-sums form of a

function is not necessarily unique.
 Minimum product of sums can often be obtained by uniting theorem (X +

Y)(X + Y′) = X is
59
KARNAUGH MAPS
 Minterms and products are represented in algebraic notation or
binary notation.
 The first four-variable example below illustrates this for
minterms and the second for products containing three literals.
The dash indicates a missing variable.
 ab′cd′ + ab′cd = ab′c
 ab′c + abc = ac
 Note that minterms only combine if they differ in one variable,
and products only combine if they have dashes in the same
position (same missing variables) and differ in one other
variable.
60
10:53 PM
61
10:53 PM
62
RULES FOR K-MAP SIMPLIFICATION
1. Groups may not contain zero.
10:53 PM
2. We can group 1, 2, 4, 8 or 2^n cells.
3. Each group should be as large as possible
4. Cells contain 1 must be grouped.
5. Groups may overlap.
6. Opposite grouping and corner grouping is
allowed.
7. There should be as few group as possible.
63
KARNAUGH MAPS
TWO- AND THREE-VARIABLE KARNAUGH MAPS
It is a two variable karnaugh map
64
KARNAUGH MAPS
• Minterms in adjacent squares of the map

can be combined since they differ in only
one variable.
• Thus, A′B′ and A′B combine to form A′,
and this is indicated by looping (Grouping)
the corresponding 1’s on the map in Figure 65
KARNAUGH MAPS
 Two-Variable Maps
 Example: Y =F(A,B)= ∑m(2,3)
66
KARNAUGH MAPS
The rows are labeled in the sequence 00, 01, 11, 10 so that values in
adjacent rows differ in only one variable.
67
KARNAUGH MAPS
 Location of Minterms on a Three-Variable

Karnaugh Map
68
KARNAUGH MAPS
 Three-Variable Maps
 Example: Y = F(A, B, C) = ∑m(2,6,7)
69
KARNAUGH MAPS
 Given the minterm expansion of a function, it can be plotted on a map by
placing 1’s in the squares which correspond to minterms of the function and
0’s in the remaining squares (the 0’s may be omitted if desired).
 E.g. Karnaugh Map of
F(a, b, c) = Σ m(1, 3, 5)
= Π M(0, 2, 4, 6, 7)
70
KARNAUGH MAPS
 Karnaugh Maps for Product Terms
71
KARNAUGH MAPS
 Simplification of a Three-Variable Function
 Terms in adjacent squares on the map differ in only one
variable and combine them.
 E.g. a′b′c and a′bc combine to form a′c, and a′b′c and ab′c
combine to form b′c,
72
KARNAUGH MAPS
 Karnaugh Maps that Illustrate the Consensus Theorem

 XY + X′Z + YZ = XY + X′Z
 Note that the consensus term (YZ) is redundant because its 1’s
are covered by the other two terms.
73
KARNAUGH MAPS
 Function with Two Minimum Forms

 Two minimum solutions for F = Σ m(0, 1, 2, 5, 6, 7).
74
10:53 PM
75
10:53 PM
76
10:53 PM
77
10:53 PM
78
10:53 PM
79
10:53 PM
80
10:53 PM
81
10:53 PM
82
10:53 PM
83
KARNAUGH MAPS
 The Karnaugh map method is easily extended to

functions with don’t-care terms.
 The required minterms are indicated by 1’s on
the map, and the don’t-care minterms are
indicated by X’s.
 When choosing terms to form the minimum sum
of products, all the 1’s must be covered, but the
X’s are only used if they will simplify the
resulting expression.
84
KARNAUGH MAPS
 Exercise Problems:
1. Given F1 =Σ m(0, 4, 5, 6) and F2 =Σ m(0, 3, 6,
7) find the minterm expression for F1 and F2
using K-map.
85
10:53 PM
86
KARNAUGH MAPS
1. Work (a) and (b) with the following truth table:
a) Find the simplest expression for F, and specify the
values of the don’t-cares that lead to this expression.
b) Repeat (a) for G. (Hint: Can you make G the same
as one of the inputs by properly choosing the values
for the don’t-care?)
87
KARNAUGH MAPS
 Find the minimum sum of products for each
function using a Karnaugh map.
 (a) f1(a, b, c) = m0 + m2 + m5 + m6
 (b) f2(d, e, f ) = Σ m(0, 1, 2, 4)
 (c) f3(r, s, t) = rt′ + r′s′ + r′s
 (d) f4(x, y, z) = M0 · M5
88
10:53 PM
89
KARNAUGH MAPS FOUR-VARIABLE KARNAUGH MAPS
 Location of Minterms on Four-Variable

Karnaugh Map
90
KARNAUGH MAPS
FOUR-VARIABLE KARNAUGH MAPS
 Example: Y= F(A,B,C,D)= ∑m(1,6,7,14)
91
KARNAUGH MAPS
 Simplification of Four-Variable Functions
• Minterms can be combined in groups of two, four, or eight to

eliminate one, two, or three variables, respectively.
92
KARNAUGH MAPS
 Simplification of an Incompletely Specified
Function
93
KARNAUGH MAPS
 A minimum product of sums can also be obtained from the map.
 Because the 0’s of f are 1’s of f′, the minimum sum of
products for f′ can be determined by looping the 0’s on a map
of f.
 The complement of the minimum sum of products for f′ is
then the minimum product of sums for f.
 The following example illustrates this procedure for
 f = x′z′ + wyz + w′y′z′ + x′y
 Then, from the 0’s,
 f ′ = y′z + wxz′ + w′xy
 and the minimum product of sums for f is
94
 f = (y + z′)(w′ + x′ + z)(w + x′ + y′)
KARNAUGH SIMPLIFICATIONS-1
 The Karnaugh map uses the following rules for the
simplification of expressions
by grouping together adjacent cells containing ones.
 After drawing a Karnaugh map,
 Encircle the octets first,
 The quads second, and
 The pairs last.
95
 Groups may not include any cell containing a zero.
 Groups may be horizontal or vertical, but not

diagonal.
96
 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.
97
 Each group should be as large as possible.
 Each cell containing a one must be in at least one group.
98
 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.
99
 Rolling the Map
100
 Always overlap groups if possible
 Use the 1s more than once to get the largest
groups you can.
101
 There should be as few groups as possible, as long as
this does not contradict any of the previous rules.
102
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.
9. Fewest number of groups possible.
103
K- MAP GROUPING EXAMPLES-1
 Rolling and overlapping
104
K- MAP GROUPING EXAMPLES-2
105
ELIMINATING REDUNDANT GROUPS-2
 A group whose 1s are already used by other groups.
106
 A group whose 1s are already used by other
groups.
107
 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
108
 A group whose 1s are already used by other groups.
109
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 groups.
110
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)
111
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)
112
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)
113
EXAMPLE-1
Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12, 13, 14, 15)
114
EXAMPLE-1
Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12, 13, 14, 15)
115
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= + +
116
117
 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.
118
 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 119
1 1 1 1 X
 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)
120
DETERMINATION OF MINIMUM EXPRESSIONS
USING ESSENTIAL PRIME IMPLICANTS
 Any single 1 or any group of 1’s which can be combined
together on a map of the function F represents a product
term which is called an implicant of F.
 A product term implicant is called a prime implicant if
it cannot be combined with another term to eliminate a
variable.
121
 In Figure, a′b′c, a′cd′, and ac′ are prime implicants because they
cannot be combined with other terms to eliminate a variable.
 a′b′c′d′ is not a prime implicant because it can be combined with
a′b′cd′ or ab′c′d′.
 Neither abc′, nor ab′c′ is a prime implicant because these terms can
be combined together to form ac′.
122
 All of the prime implicants of a function can be obtained
from a karnaugh map.
 a single 1 on a map represents a prime implicant if it is not
adjacent to any other 1’s.
 two adjacent 1’s on a map form a prime implicant if they are
not contained in a group of four 1’s;
 four adjacent 1’s form a prime implicant if they are not
contained in a group of eight 1’s, etc.
123
 The minimum sum-of-products expression for a function
consists of some (but not necessarily all) of the prime
implicants of a function.
 In other words, a sum-of-products expression containing
a term which is not a prime implicant cannot be
minimum.
 This is true because if a nonprime term were present,
the expression could be simplified by combining the
nonprime term with additional minterms.
124
 The function plotted in Figure has six prime implicants.
 Three of these prime implicants cover all of the 1’s on the
map, and the minimum solution is the sum of these three
prime implicants.
 The shaded loops represent prime implicants which are not
part of the minimum solution.
125
 All of the prime implicants of a function are generally
not needed in forming the minimum sum of products, a
systematic procedure for selecting prime implicants is
needed.
 If prime implicants are selected from the map in the
wrong order, a no minimum solution may result.
126
 For example, in Figure (a), if CD is chosen first, then
BD, B′C, and AC are needed to cover the remaining 1’s,
and the solution contains four terms.
 If the prime implicants indicated in Figure (b) are chosen
first, all 1’s are covered and CD is not needed.
127
 Note that some of the minterms on the map of Figure (a)
can be covered by only a single prime implicant, but
other minterms can be covered by two different prime
implicants.
 For example, m2 is covered only by B′C, but m5 is
covered by both B′C and CD.
128
 If a minterm is covered by only one prime implicant,
that prime implicant is said to be essential prime
implicants, and it must be included in the minimum
sum of products.
 B′C is an essential prime implicant because m2 is not
covered by any other prime implicant.
 CD is not essential prime implicant because each of the 1’s
in CD can be covered by another prime implicant.
 The only prime implicant which covers m5 is BD, so BD is
essential.
 AC is essential because no other prime implicant covers
m14. 129
 In general, in order to find a minimum sum of products from a
map, we should first loop all of the essential prime implicants.
 One way of finding essential prime implicants on a map is
simply to look at each 1 on the map that has not already been
covered, and check to see how many prime implicants cover
that 1.
 If there is only one prime implicant which covers the 1, that
prime implicant is essential.
 If there are two or more prime implicants which cover the 1, we
cannot say whether these prime implicants are essential or not
without checking the other minterms.
130
 For example, in Figure, m4 is covered only by the prime
implicant bc′, and m10 is covered only by the prime
implicant ac.
 All other 1’s on the map are covered by two prime
implicants; therefore, the only essential prime implicants
are bc′ and ac.
131
 If the given minterm and all of the 1’s adjacent to
it are covered by a single term, then that term is
an essential prime implicant.
 If all of the 1’s adjacent to a given minterm are
not covered by a single term, then there are two
or more prime implicants which cover that
minterm, and we cannot say whether these prime
implicants are essential or not without checking
the other minterms.
132
 The adjacent 1’s for
minterm m0 (10) are 11,
12, and l4.
 Because no single term
covers these four 1’s, no
essential prime
implicant is yet
apparent.
 The adjacent 1’s for 11
are 10 and 15, so the
term which covers these
three 1’s (A′C′) is an
essential prime
implicant. 133
 The only 1 adjacent to
12 is 10, A′B′D′ is also
essential.
 The only 1 adjacent to

111 is 115, ACD is
essential.
134
 The 1’s adjacent to 17 (15
and 115) are not covered by
a single term, neither
A′BD nor BCD is essential.
 To complete the minimum
solution, one of the
nonessential prime
implicants is needed. So
either A′BD or BCD may
be selected
 The final solution is
135
 The following procedure can be used to obtain a
minimum sum of products from a Karnaugh map:
1. Choose a minterm (a 1) which has not yet been
covered.
2. Find all 1’s and X’s adjacent to that minterm.
(Check the n adjacent squares on an n-variable
map.)
136
1. If a single term covers the minterm and all of the
adjacent 1’s and X’s, then that term is an essential
prime implicant, so select that term. (Note that don’t-
care terms are treated like 1’s in steps 2 and 3 but not
in step 1.)
2. Repeat steps 1, 2, and 3 until all essential prime
implicants have been chosen.
3. Find a minimum set of prime implicants which cover
the remaining 1’s on the map. (If there is more than
one such set, choose a set with a minimum number of
literals.)
137
138
PROGRAMMED EXERCISE
 Determine the minimum sum of products and
minimum product of sums for
 f = b′c′d′ + bcd + acd′ + a′b′c + a′bc′d
 First, plot the map for f.
139
10:53 PM
140
PROGRAMMED EXERCISE
 For problem on K-Map refer text book and VTU
question papers.
 Y=F(A,B,C,D)=∑m(7,9, 10, 11, 12, 13, 14, 15)
 F(w, x, y, z) = ∑m(0, 1, 2, 5, 8, 9, 10)
 Y= ∑m(1, 2, 6, 7)
 Y=F(p,q,r,s)=∑m(1, 3, 4, 10, 12, 13, 15)
 F (w, x, y, z) = ∑m (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)
 F (A, B, C, D) = ∑m(0,1, 2, 5, 8, 9,10)

141
PROGRAMMED EXERCISE –
VTU QUESTIONS
 Find the minimal SOP of the following Boolean
functions using K-Map:
 F(a,b,c,d)=∑m(6,7,9,10,13)+d(1,4,5,11)
 F(p,q,r,s)=∑m(6,7,9,10,13)+d(0,1,8,12)
 F(A,B,C,D)= ∑m(6,8,9,10,11,12,13,14,15)
 F(A,B,C,D)=∑m(1,3,5,7,8,10,12,14)
 F(a,b,c,d)=∑m(5,6,7,12,13)+d(4,9,14,15)
142
PROGRAMMED EXERCISE
 Find the minimum sum of products for each
function using a Karnaugh map.
 (a) f1(a, b, c) = m0 + m2 + m5 + m6
 (b) f2(d, e, f ) = Σ m(0, 1, 2, 4)
 (c) f3(r, s, t) = rt ′ + r′s′ + r′s
 (d) f4(x, y, z) = M0 · M5
143
PROGRAMMED EXERCISE
 Find the minimum sum-of-products expression
for each function. Underline the essential prime
implicants in your answer and tell which
minterm makes each one essential.
1. f(a, b, c, d) =Σ m(0, 1, 3, 5, 6, 7, 11, 12, 14)
2. f(a, b, c, d) =Π M(1, 9, 11, 12, 14)
3. f(a, b, c, d) =Π M(5, 7, 13, 14, 15)· Π D(1, 2,
3, 9)
4. f(a, b, c, d) =Σ m(0, 2, 3, 4, 7, 8, 14)
5. f(a, b, c, d) =Σ m(1, 2, 4, 15) +Σ d(0, 3, 14)
6. f(a, b, c, d) =Π M(1, 2, 3, 4, 9, 15)
7. f(a, b, c, d) =Π M(0, 2, 4, 6, 8) ·Π D(1, 12, 9, 15) 144
PROGRAMMED EXERCISE
 Find the minimum sum-of-products expression
for each function. Underline the essential prime
implicants in your answer and tell which
minterm makes each one essential.
1. f(a, b, c, d) =Σm (0, 1, 3, 5, 6, 7, 11, 12, 14)
2. f(a, b, c, d) =ΠM (1, 9, 11, 12, 14)
3. f(a, b, c, d) =ΠM (5, 7, 13, 14, 15)· ΠD (1, 2, 3, 9)
145
PRODUCT-OF-SUMS
SIMPLIFICATION-1
 SOP Simplification
 Complementary Circuit
146
PRODUCT-OF-SUMS
SIMPLIFICATION-2
 Using Karnaugh map by grouping zeros
147
EXAMPLE-1
 Give POS form of Y = F(A, B, C, D) = ∏M(0,3, 4,
5, 6, 7, 11, 15)
AB
CD
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
148
EXAM QUESTIONS
 Simplify the following using K-Map
 By Grouping 1’s By Grouping 0’s

A
BC
00 01 11 10 A
BC
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

149
MULTIPLE CHOICE QUESTIONS
1.The universal gate is ………………
1. NAND gate
2. OR gate
3. AND gate
4. None of the above
2. The NAND gate is AND gate followed by

…………………
1. NOT gate
2. OR gate
3. AND gate
4. None of the above
150
3.Determine the values of A, B, C, and D that make the
sum term equal to zero.
1. A = 1, B = 0, C = 0, D = 0
2. A = 1, B = 0, C = 1, D = 0
3. A = 0, B = 1, C = 0, D = 0
4. A = 1, B = 0, C = 1, D = 1
4. One of De Morgan's theorems states that . Simply

stated, this means that logically there is no difference
between:
1. NOR and an AND gate with inverted inputs
2. NAND and an OR gate with inverted inputs
3. An AND and a NOR gate with inverted inputs
4. NOR and a NAND gate with inverted inputs

151
5.How many gates would be required to implement
the following Boolean expression before
simplification? XY + X(X + Z) + Y(X + Z)
A.1
B.2
C.4
D.5
6.There are ______ cells in a 4-variable K-map.
a) 12
b) 16
c) 18
d) 8
152
7. It should be kept in mind that don’t care terms
should be used along with the terms that are
present in ___________
a) Minterms
b) Expressions
c) K-Map
d) Latches
8. An n variable K-map can have
1. n2 cells
2. 2n cells
3. nn cells
4. n2n cells
153
9. Each term in the standard SOP form is called a
1. minterm
2. maxterm
3. don’t care
4. literal
10. The main criterion in the design of a digital circuit is

reduction of
1. cost
2. size
3. weight
4. volume
154
11. Determine the number of essential prime implicants
of the function f(a, b, c, d) = Σm(1, 3, 4, 8, 10, 13) + d(2,
5, 7, 12), where m denote the minterm and d denotes
the don’t care condition.
a) 23
b) 3
c) 643
d) 128
12. How many number of prime implicants are there in
the expression F(x, y, z) = y’z’ + xy + x’z.
a) 7
b) 19
c) 3
d) 53
155
13.A Karnaugh map (K-map) is an abstract form of
____________ diagram organized as a matrix of
10:53 PM
squares.
a) Venn Diagram
b) Cycle Diagram
c) Block diagram
d) Triangular Diagram
14. There are ______ cells in a 4-variable K-map.
a) 12
b) 16
c) 18
d) 8
156
15.The K-map based Boolean reduction is based on
the following Unifying Theorem: A + A’ = 1.
a) Impact
b) Non Impact
c) Force
d) Complementarity
16.Each product term of a group, w’.x.y’ and w.y,

represents the ____________in that group.
a) Input
b) POS
c) Sum-of-Minterms
d) Sum of Maxterms
157
18.The prime implicant which has at least one
element that is not present in any other implicant is
known as ___________
a) Essential Prime Implicant
b) Implicant
c) Complement
d) Prime Complement
19.Product-of-Sums expressions can be implemented

using ___________
a) 2-level OR-AND logic circuits
b) 2-level NOR logic circuits
c) 2-level XOR logic circuits
d) Both 2-level OR-AND and NOR logic circuits
158
20.Each group of adjacent Minterms (group size in
powers of twos) corresponds to a possible product
term of the given ___________
a) Function
b) Value
c) Set
d) Word
21.Don’t care conditions can be used for simplifying
Boolean expressions in ___________
a) Registers
b) Terms
c) K-maps
d) Latches
159
22.It should be kept in mind that don’t care terms
should be used along with the terms that are
present in ___________
a) Minterms
b) Expressions
c) K-Map
d) Latches
23.Using the transformation method you can
realize any POS realization of OR-AND with only.
a) XOR
b) NAND
c) AND
d) NOR
160
24.There are many situations in logic design in
which simplification of logic expression is
possible in terms of XOR and _________________
operations.
a) X-NOR
b) XOR
c) NOR
d) NAND
25.These logic gates are widely used in
_______________ design and therefore are
available in IC form.
a) Sampling
b) Digital
c) Analog
d) Systems 161
26.In case of XOR/XNOR simplification we have to look
for the following _______________
a) Diagonal Adjacencies
b) Offset Adjacencies
c) Straight Adjacencies
d) Both diagonal and offset adjencies
27.Entries known as _______________ mapping.
a) Diagonal
b) Straight
c) K
d) Boolean
162
28.Which of the following expressions is in the
sum-of-products form?
a) (A + B)(C + D)
b) (A * B)(C * D)
c) A* B *(CD)
d) A * B + C * D
29. Which of the following is an important feature
of the sum-of-products form of expressions?
a) All logic circuits are reduced to nothing more
than simple AND and OR operations
b) The delay times are greatly reduced over other
forms
c) No signal must pass through more than two
gates, not including inverters
d) The maximum number of gates that any signal
must pass through is reduced by a factor of two 163
UNIVERSITY QUESTIONS
1.Find the SOP and POS of the following Boolean
functions using K-Map and draw the circuit diagram
F(a,b,c,d)=∑m(6,7,9,10,13)+d(1,4,5,11)
F(w,x,y,z)=πM(1,2,3,4,9,10)+d(0,1,4,15) -- L2
2. Find the minimum sum of products for each function

using a Karnaugh map (a)f1(a,b,c)= m0 + m2 + m5 + m6 .
-- L2
3. Find the minimum product of sum expression for
F(a,b,c,d) =πM(0,2,10,11,12,14,15) . πD(5,7) --L1
4.Find the minimum SOP and minimum POS expression
for the followin function using K-Map
164
F(A,B,C,D)=∑m(1,3,4,11) + ∑d(2,7,8,12,14,15) --L1
3.Find all prime implicants of the following function
and then find all minimum solutions using petrick’s
method.
 F(A,B,C,D)=∑m(9,12,13,15)+ ∑d(1,4,5,7,8,11,14) -- L2
4.Using the method of map-entered variables, use 4-

variable maps to find minimum sum of products
expression for:
 F(A,B,C,D,E)=∑m(0,4,5,7,9)+
∑d(6,11)+E(m1+m15),where the m’s represent
minterms of the variables A,B,C and D --L2
165
5.Find the minimum sum of products for each function
using a Karnaugh map
 f(a,b,c,d) =∑m (0,3,4,5,7,9,11,13)
 f(a,b,c,d) =∑m (2,4,5,6,9,10,11,12,13,15) --L2

 F(a,b,c,d)=∑m(0,1,2,5,6,7,8,9,10,14) --L2
166
INNOVATIVE PROJECT LINK
1. www.elprocus.com
2. https://www.elprocus.com/
167
CASE STUDY LINK
1. https://core.ac.uk/download/pdf/162670931.pdf
2. https://www.ijcaonline.org/archives/volume143/n
umber7/wankhade-2016-ijca-910257.pdf
168
REFERENCES
 en.wikipedia.org
 www.allaboutcircuits.com
 www.tutorialspoint.com
 https://www.wikizero.com
 www.electronicshub.org
169

Module 1 PDF

Uploaded by

Copyright:

Available Formats

Module 1 PDF

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 1 PDF

Uploaded by

Copyright:

Available Formats

An Autonomous Institute

Affiliated to VTU, Belagavi,

DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING

FACULTY : Nivedita Sahoo , Asst. Prof, Dept. of CSE

● Demonstrate the functionalities of binary logic

 A logic gate is a digital circuit with 1 or more input

 The output is HIGH when any input is HIGH.

Redundant Terms: The Term not or no longer needed or useful.

 = A + AD + AE + ABC + BCD + BCE

 = A(1 + D + E + BC) + BCD + BCE

The term YZ is redundant and can be eliminated to form the

 Eg: The consensus of ab and a′c is bc;

 The consensus of terms ab′d and a′bd′ is 0.

 Possibleways to AND two or more input signals that

A SOP expression is two or more AND functions ORed

 ANDing two variables and their complements

 The fundamental products are also called min-terms.

 Products are represented by m0, m1, m2

 The suffix i of m comes from decimal equivalent of

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

 Conversion between SOP and POS

 Identifying complementary locations,

 Maxterm to minterm conversion

 Minterm expansion of F to minterm expansion of

 Maxterm expansion of F to maxterm expansion of

 In digital systems, certain input conditions never occur during

 The X is called a don 't-care condition.

 Whenever you see an X in a truth table, you can let it equal

Truth Table with Don’t-Cares

 Truth Table with Don't-Care Conditions

 Y=F(A,B,C,D) = ∑m (9) + d(10,11,12,13,14,15)

A minimum sum-of-products expression for a

 The minimum sum of products corresponds directly to a

 Unlike the minterm expansion for a function, the minimum

 A minimum product-of-sums expression for a function is defined as a

 Unlike the maxterm expansion, the minimum product-of-sums form of a

 Minimum product of sums can often be obtained by uniting theorem (X +

1. Groups may not contain zero.

• Minterms in adjacent squares of the map

 Location of Minterms on a Three-Variable

 Karnaugh Maps for Product Terms

 Karnaugh Maps that Illustrate the Consensus Theorem

 Function with Two Minimum Forms

 The Karnaugh map method is easily extended to

 Location of Minterms on Four-Variable

• Minterms can be combined in groups of two, four, or eight to

 Groups may be horizontal or vertical, but not

 If n = 2, a group will contain four 1's since 22 = 4.

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

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

1. Enter a 1 on the Karnaugh map for each fundamental

 The only 1 adjacent to

 First, plot the map for f.

 F (A, B, C, D) = ∑m(0,1, 2, 5, 8, 9,10)

 (b) f2(d, e, f ) = Σ m(0, 1, 2, 4)

 (c) f3(r, s, t) = rt ′ + r′s′ + r′s

 By Grouping 1’s By Grouping 0’s

4. None of the above

2. The NAND gate is AND gate followed by

4. None of the above