SE COMPUTER SEM-I

210245
DIGITAL ELECTRONICS AND LOGIC DESIGN
UNIT –I
MINIMIZATION TECHNIQUE

Prof.P.C.Patil
Department of Computer Engg
Guru Gobind Singh College of Engineering , Nasik
pcpatil.webs.com
 Analog Versus Digital
• Analog = Continuous waves
• Digital = Discrete waves

• Example:
– An analog clock, whose hands move smoothly and
continuously.
– A digital clock, whose digits jump from one value to the
next.
2
‘Analog to Digital’ or ‘Digital to Analog’

• Example: A typical CD player accepts digital data

from the CD drive and converts it to an analog
signalfor amplification.

3
 What is DigitalElectronics?
• Digital electronics is a field of electronics
involving the study of digital signals and the
engineeringof devicesthatuseor produce them.

• Digital electronics is a branch of electronics which

deals with digital formatof data and codes.

4
• Digital stand for digit, digital electronics basically
has two conditions which are possible, 0 (low
logic) and 1 (high logic).

• "1" as true and "0" as false are called bit and the
group of bits are namedbyte.

• Digital electronic circuits are usually made from

large assemblies of logicgates.

• Digital describes electronic technology that

generates, stores, and processes data in terms of
two states: 1 and number0.
5
 History of Digital Electronics
• Prior to digital technology, electronic transmission was limited to
Analog Technology, which conveys data as electronic signals of
varying frequency or amplitude.

• In the 1930's the prototypes of the computer were constructed

from mechanical switches ( Vacuum Tubes ) and relays. These were
comparatively slow, large, and produced a great deal ofheat.

• The next stage in the 1940's was the use ofElectronic Diodes, and
while these were better but they were unreliable.

• The next stage was the result of the development in 1947 of the
Transistor which was much smaller, faster and cooler. Simple
transistors were replaced by Integrated Circuits (IC’s) and that got
smaller and smaller and finally deposited on silicon to be put into a
"chip". Chips are further converted to Microprocessors and etc.
6
 Advantages of Digital Electronics
• Computer-controlled digital systems can be
controlled by software, allowing new
functions to be added without changing
hardware.

• Information storage can be easier in digital

systems than in analog ones.

• The noise-immunity of digital systems permits

data to be stored and retrieved without noise.
7
• Digital system are easier to design and more
precise representation of a signal can be
obtained by using more binary digits to represent
it.

• More digital circuitry can be fabricated on IC

chips.

• Error management method can be inserted into

the signal path. To detect errors, and then either
correct the errors, or at least ask for a new copy
of the data. Eg.Parity, Hamming codesetc.
8
 Disadvantages of Digital Electronics
• Conversion to digital format and re-conversion to
analog format is needed, which always include
the lost ofinformation.

• In some cases, digital circuits use more energy

than analog circuits and produce more heat and
need heat sinks.

• Digital circuits are sometimes more expensive,

especially in small quantities.
9
 Number Systems and
Representation, Data Types
 Agenda
• Number Systems

• Number Representation

• Data Types

• Arithmetic Operations
 Number System
• Many number systems are used

– Decimal 53710
– Binary 1010012
– Octal 1488
– Hexadecimal 4BAF16
• Octal, Decimal, hexadecimal

– Octal Uses 8 symbols/digits: 0, 1, 2, 3, 4, 5, 6,7;

– Decimal Uses 10 symbols/digits: 0, 1, 2, 3, 4, 5, 6,
7, 8, 9;
– Hexadecimal Uses 16 symbols/digits: 0, 1, 2, 3, 4,
5, 6, 7, 8, 9,A,B,C,D,E,F;

MSD: Most SignificantDigit

LSD: Least Significant Digit
• Binary

– Uses 2 symbols/digits: 0, 1

B B

MSB: Most Significant Bit

LSB: Least Significant Bit
Binary Octal

Decimal Hexadecimal
• BINARY CODED DECIMAL (BCD)

– Representation Technique
– On the BCD (Binary Coded Decimal) system the
digits are grouped in 4/8 bits nibbles, each nibble
representing a decimal digit;

– Packed BCD 1 Digit= 4 bits

• Eg. 12 == 0001 0010
– UnPacked BCD 1 Digit= 8 bits
• Eg. 12 == 00000001 00000010
 Integer Representation
• Only have 0 & 1 to represent everything.

• Positive numbers stored in binary.

– e.g. 41=00101001

• No minus sign.

• Two ways to represent negative numbers:

– Sign Magnitude
– Two’s Complement
Number representation: Binary
 Sign-Magnitude
• Left most bit (Most Significant Bit) is signbit.
– 0 means Positive.
– 1 means Negative.
• +18 = 00010010
• -18 = 10010010
• Problems
– Need to consider both sign and magnitude in
arithmetic.
– Two representations of zero (+0 and -0).
 Two’s Compliment
• +3 = 00000011
• +2 = 00000010
• +1 = 00000001
• +0 = 00000000
• -1 = 11111111
• -2 = 11111110
• -3 = 11111101
 Benefits of 2’s Complement
• One representation of zero.

• Arithmetic works easily.

• Negating is fairly easy

– 3 =00000011
– Boolean complement gives11111100
– Add 1 to LSB 11111101
Geometric Depiction of Twos
Complement Integers
 Solve

What is range for 8 bit and 16 bitnumber?

 Range of Numbers
• 8 bit 2scompliment
– +127 = 01111111 = 27 -1
– -128 = 10000000 = -27

• 16 bit 2scompliment
– +32767 = 011111111 11111111 = 215 - 1
– -32768 = 100000000 00000000 = -215
 Floating Point Representations:
IEEE Standards
Two Types

1. Single Precision (bias of 127)

2. Double Precision (bias of 1023)

 Arithmetic Operations
• Following Arithmetic Operations can be
performed:

– Addition
– Subtraction
– Multiplication  Booth’s Algorithm, Add & Shift
Algorithm
– Division  Restoring DivisionAlgorithm
Rules: Addition and Subtraction
 Solve
• 19 + 7
 General concept: Addition

• Decimal addition • Binary addition

(carry) 1_ ( carry) 111_
19 10011
+ 7 + 111
26 11010
• 16+8+2 = 26
 Solve
• -8 +6
 Signed and unsignedadditions

• Unsigned addition • Signed

in 4-bit arithmetic addition in 4-
( carry) 11_ bit arithmetic
1011 ( carry) 11_
+ 0011 1011
+ 0011
1110 1110
• 11 + 3 = 14 • -8 + 6 = -2
(8 + 4 + 2)
 Solve
• 2-7
• 5–3
• -5 – 2
• 5 +2
• 7 +7
• -6 - 4
Subtraction
Fundamental Data Types
Byte Integer
Word Integer
BCD
Packed BCD
String
Pointers
 Defaults (Intel Processors)
• Number System: Hexadecimal

• Number Representation: Packed BCD

• Byte Ordering: Little endian

• 1 Address in memory can store= 1 Byte

 Byte Ordering in ComputerMemory
(Data definition)
1.Little endian machine
• Stores data little-endfirst
• Least significant byte at smallest address
• Example: Intel processors (all x86processors)
eg. 1234 (One thousand two hundred thirty four)

2.Big endian machine

• Stores data big-endfirst
• Most significant byte at smallestaddress
• Example: IBM processors (Power PC)
eg. 4321 (One thousand two hundred thirty four)
Qnumber: dq 12345678A95CCDFE h
ASCII to HexTable
Logic Gates
 Boolean Logic
• BOOLEAN LOGIC (or Boolean algebra) is a
complete system for logical mathematical
operations.

• BINARY DIGITS are used to represent LOGIC STATES

like “true” (1) or “false”(0).

• Boolean logic has many applications in electronics,

computer hardware and software, and is the
foundation of all modern digital electronics.
 What is Logicgates?
• Digital gate is a Digital Device used to perform the logic
operation.

• Logic gates (or simply gates) are the fundamental building

blocks of digitalcircuitry.

• Electronic gates require a powersupply.

– Gate INPUTS are driven by voltages having two nominal values, e.g.
0V and 5V representing logic 0 and logic 1 respectively.
– The OUTPUT of a gate provides two nominal values of voltage only,
e.g. 0V and 5V representing logic 0 and logic 1 respectively.

• In general, there is only one output to a logic gate except in

some special cases.
 Truth tables
• Truth table are used to show the function of a logic
gate.
• Relation between outputs and inputs.
• Number system used in Binary.
• Number of entries in table =2number_of_inputs
– Eg.No of input =1, then number of entries in table are2.
• Digital circuits are built from simple on/off switches
called GATES. These gates have two states: logic high
(ON or 1) and logic low (OFFor 0).
• TRUTH TABLES are used to analyse all the possible
alternative states of a digital circuit.
Types of Logic Gate
AND & ORGates
 NOT Gate
• The NOT gate is an electronic circuit that
produces an inverted version of the input at its
output. It is also known asaninverter.

• If the input variable is X, the inverted output is

known as NOTX. This is also shown as X', or X with
a bar over the top, as shown at the outputs.
 OR Gate
• The ORgate is an electronic circuit that gives a high
output (1) if one or more of its inputs are high. A
plus (+) is used to show the ORoperation.
 AND gate
• The AND gate is an electronic circuit that gives a
high output (1) only if all its inputs are high. A dot
(.) is used to show the AND operation (X.Y), Bear in
mind that this dot is sometimes omitted (XY).
 NOR Gate
• This is a NOT-OR gate which is equal to an OR gate
followed by a NOT gate. The outputs of all NOR
gates are low if any of the inputs are high. The
symbol is an OR gate with a small circle on the
output. The small circle represents inversion.
 NAND Gate
• This is a NOT-AND gate which is equal to an AND
gate followed by a NOT gate. The outputs of all
NAND gates are high if any of the inputs are low.
The symbol is an AND gate with a small circle on the
output. The small circle represents inversion.
 XOR Gate
• The 'Exclusive-OR' gate is a circuit which will
give a high output if its two inputs are
different.
 XNOR Gate
• The 'Exclusive-NOR' gate circuit does the
opposite to the XOR gate. It will give a low
output when its two inputs are different. The
symbol is an EXOR gate with a small circle on
the output. The small circle represents
inversion.
 Relation: Boolean Algebra andLogic
• Boolean algebra is based on
these logical operations:
• Conjunction x ∧y(AND)
• Disjunction x ∨y(OR)
• Complement or negation
¬x (NOT).
• In electronics, the AND is
represented as a multiplication,
the OR is represented as an
addition, and the NOT is
represented with anoverbar.
https://circuitverse.org/simulator
Boolean Algebra
 Boolean Algebra
• The digital circuit can be made up of several logicgates.

• The Boolean algebra is mainly used for simplifying and

analyzing the complex Boolean expression.

• It is used when number of variables are less. For more

number of variables K-map method is used.

• It is also known as Binary algebra because we only use

binary numbers in this. George Boole developed the
binary algebra in 1854.
• “To perform the logical operation with minimum
logic gates, a set of rules were invented, known as
the Laws of Boolean Algebra” or “It is a set of rules
used to simplify the given logic expression without
changing its functionality”
• Both equations must have same functionality.
• Truth tables can be used to check whether they
have same functionality or not.
• Less number of gates means: Less time, Less
Power.
Rules of Boolean Algebra
Complement
Law
B.B' = 0
B+B' = 1
 Properties of Boolean algebra or Rules of BooleanAlgebra
4) Distributive Law (IMP)
A+(B.C) = (A+B).(A+C)
A.(B+C) = (A.B)+(A.C)

5) Commutative Law
A.B = B.A
A+B = B+A
Commutative law states that changing the sequence of the
variables does not have any effect on the output of a logic
circuit.

6) Associative Law
(A.B).C = A.(B.C)
(A+B)+C =A+(B+C)
This law states that the order in which the logic operations
are performed is irrelevaR.nV.tBidawse,PtIChT,ePuinre.effectis the same. 75
7) De Morgan Law (ComplementLaw)

The operation of an ORand AND logic circuit

will remain same if we invert all the inputs,
change operators from AND to ORand ORto
AND, and invert the output.

(A.B)' =A'+B'

(A+B)' =A'.B'
 Other Laws
• Double Negation (Inversion)
Identity Law
Law
•B.1 = B
• ((A)')' =A •B+0 = B

• Absorption Law Idempotent Law

• B+(B.A) = B •B.B = B
•B+B = B
• B.(B+A) = B

Annulment Law
• B.0 = 0
• B+1 = 1
 Priorities
• When you are solving problems then solve

1. NOT

2. AND

3. OR
Y= (A + B). C’
 Problems
1. AB+AB’

2. AB+ AB’C+AB’C’
Problems
 Solve
X’Y’+XYZ+X’Y
Few more problems
Examples
Sum of Product (SOP),
Product of Sum (POS),
Minterm and Maxterm
 Overview
• Sum of Product (SOP)

• Product of Sum(POS)

• Standard SOPand POSForms

• Minterms and Maxterms

 Sum of Product(SOP)
• The sum-of-products (SOP) form is a method (or form) of
simplifying the Boolean expressions of logic gates.

• Sum and product derived from the symbolic representationsof

the OR and ANDfunctions.

• OR(+) , AND ( . ) , addition and multiplication.

• Expression is written for value“1”.
 Product of Sum (POS)
• When two or more “Sum” terms are multiplied (Product) by a
Boolean AND operation.

• Sum terms are defined by using ORoperation and the product

term is defined by using ANDoperation.

• Expression is written for value“0”.

 Canonical or Standard SOP/ POS
Forms
• The canonical forms are the special cases of
SOPand POSforms.

• These are also known as standard SOP and

POS forms.

• These forms can be minimized using Boolean

Algebra. It is called as Minimized form.
 Minterm and Maxterm
• Each individual term in the SOPform is calledMinterm.
• Each individual term in the POSform is calledMaxterm.

• In Minterm, we look for the functions where theoutput

results is “1”.
• While in Maxterm we look for function where the
output results is“0”.

• We perform Sum of Minterm also known as Sum of

Products (SOP).
• We perform Product of Maxterm also known as Product
of Sum(POS).
 Minterms
• Minterms are AND terms with every variable present in
either normal or complementedform.

• Given that each binary variable may appear normal (e.g. X)

or complemented (e.g. X’), there are 2(power)n=m total
terms.

• Example: Two variables (X and Y) produce 2 x 2 = 4

combinations:
XY (both normal)
XY’ (X normal, Ycomplemented)
X’Y (X complemented, Ynormal)
X’Y’ (both complemented)

Thus there are four minterms of two variables.

 Minterm from values
Using variable values, we can write the minterms as:
1) If the variable value is 1, we will take the variable without its complement.
2) If the variable value is 0, take itscomplement.

[0  A’ (Complement), 1  A (Normal)]
Example
1) Let's assume that we have three Boolean variables A, B, and C havingvalues
A=1
B=0
C=0

Now, we will take the complement of the variables Band Cbecause thesevalues
are 0 and will take A without complement. So, the minterm will be:

2) Let's take another example in which we have two variables Band Chaving the
value
B= 0
C= 1
 Minterm from values
Example
1) Let's assume that we have three Boolean variables A, B, and Chaving
values
A=1
B=0
C=0

Now, we will take the complement of the variables Band Cbecausethese

values are 0 and will take A without complement. So, the minterm willbe:
Minterm= AB'C’

2) Let's take another example in which we have two variables B and Chaving
the value
B= 0
C= 1
Minterm= B'C
 Sum of Product (SOP)example
A canonical sum of products is a boolean expression that entirely consists ofmin
terms.

The Boolean function Fis defined on two variables XandY.

F=The truth table for Boolean expression Fis asfollows:
Here we are interested in the Minterms for which output is 1.

Term X Y F
Index

0 0 0 0

1 0 1 1

2 1 0 1

3 1 1 1
 Sum of Product (SOP)example
A canonical sum of products is a boolean expression that entirely consists ofmin
terms.

The Boolean function Fis defined on two variables Xand Y.

F=The truth table for Boolean expression Fis asfollows:
Here we are interested in the Minterms for which output is 1.

Term X Y F Min Short hand

Index Term Notation;
X’Y’=(00)2 = m0
0 0 0 0 X’Y’
X'Y = (01)2 = m1
1 0 1 1 X’Y XY' = (10)2 = m2
XY=(11)2 =m3
2 1 0 1 XY’
F in SOP Form (minterms)
3 1 1 1 XY

F = X’Y + XY’ + XY
F= ∑(1,2,3)
m0

m1 Canonical FormSOP:
m2

m3

m4

m5

m6 Minimal FormSOP:
m7

F in SOP Form (minterms)

99
m0

m1 Canonical FormSOP:
m2

m3

m4

m5

m6 Minimal FormSOP:
m7

F= A+BC’

F in SOP Form (minterms)

100
 NOTE: SOP
• In Canonical/ Standard SOP form: Each minterm is
having all the variables in normal or complimented
form.

• In Minimal SOP form: Each minterm is not have all

the variables in normal or complimented form.

F= A+BC’

101
 Examples
1. Y(A,B)= ∑(1,3)

2. Y(A,B)= ∑(0,2,3)

3. Y(A,B,C)= ∑(0,2,3,6,7)

102
 Solution
1. Y=B

2. Y=A+B’

3. Y=B+A’C’

103
 Maxterm
• Maxterms are OR terms with every variable in
true or complementedform.

• Given that each binary variable may appear

normal (e.g. X) or complemented (e.g. X’), there
are 2(power)n=m total terms.

• Example: Two variables (X and Y) produce 2x2=4

combinations:
X+Y (both normal)
X+Y’ (x normal, y complemented)
X’+Y (x complemented, y normal)
X’+Y’ (both complemented)
104
 Max term fromvalues
Rule: [0  A (Normal), 1  A’ (Complement)]
Example:

1) Maxterm from values if wehave,

A=1
B=0
C=0

2) Maxterm from values if wehave,

A=0
B=1
C=0

2) Maxterm from values if wehave,

A=0
B=0
C=1
 Max term fromvalues
Example:

1) Maxterm from values if wehave,

A=1
B=0
C=0
Maxterm=A’ + B+ C

2) Maxterm from values if wehave,

A=0
B=1
C=0
Maxterm=A + B’+ C

2) Maxterm from values if wehave,

A=0
B=0
C=1
Maxterm=A + B+ C’
 Product of Sum (POS)
A canonical product of sum is a boolean expression thatentirely
consists of maxterms.

Here we will observe the Maxterms for which output is 0.

Term X Y F
Index
0 0 0 0
1 0 1 1
2 1 0 1
3 1 1 0
 Product of Sum (POS)
A canonical product of sum is a boolean expression thatentirely
consists of maxterms.
Here we will observe the Maxtermsfor which output is0.

Term X Y F Max Short hand Notation;

Inde Ter X‘+Y’ =(00)2 = M0
x m X’+Y = (01)2 = M1
0 0 0 0 X+Y X+Y' = (10)2 = M2
1 0 1 1 X+Y’ X+Y=(11)2 =M3

2 1 0 1 X’+Y
F in POS Form (Maxterms)
3 1 1 0 X’+Y’

F = (X+Y).(X’+Y’)
F=∏(0,3)
m0

m1 Canonical FormPOS:
m2

m3

m4

m5

m6 Minimal FormPOS:
m7

F in POS Form (Maxterms)

109
m0

m1 Canonical FormPOS:
m2

m3

m4

m5

m6 Minimal FormPOS:
m7

F= (A + B). (A + C’)

F in POS Form (Maxterms)

F (A,B,C)= M0 + M1 +M3
F=∏ ( 0, 1,3)

110
 NOTE: POS
• In Canonical/ Standard SOP form: Each minterm is
having all the variables in normal or complimented
form.

• In Minimal SOP form: Each minterm is not have all

the variables in normal or complimented form.

F= (A + B). (A + C’)

111
 Examples
1. Y(A,B)=∏(1,3)

2. Y(A,B,C)=∏(1,4,5)

112
 Solution
1. Y=B’

2. Y=B+A’C’

113
 Where to use SOP ndPOS?
• If you wish to use more AND gates: UseSOP

• If you wish to use more ORgates: UsePOS

114
Minimization with Karnaugh
Maps
 Overview
• K-maps: an alternate approach to representing Boolean
functions.

• K-map representation can be used to minimize Boolean

functions.

• Easy conversion from truth table to K-map to minimized

SOP representation.

• Simple rules (steps) used to perform minimization.

• Leads to minimized SOPrepresentation.

• Much faster and more efficient than previous minimization

techniques with Booleanalgebra.
116
Two Variable map
Three Variable map

Four Variable map

117
 Karnaugh maps
• Alternate way of representing Booleanfunction
– All rows of truth table represented with a square
– Each square represents a minterm

• Easy to convert between truth table, K-map, and SOP

– Unoptimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
– Optimized form: reduced number of minterms
– RULE: [0  A’ (Complement), 1  A(Normal)]

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

118
 Karnaugh maps
• Alternate way of representing Booleanfunction
– All rows of truth table represented with a square
– Each square represents a minterm

• Easy to convert between truth table, K-map, and SOP

– Unoptimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
– Optimized form: reduced number of minterms
– RULE: [0  A’ (Complement), 1  A(Normal)]

x y F y
0 0 1 y y
x 0 1 x 0 1
0 1 1 0 x’y’ x’y 0 1 1
1 0 0
x 1 xy’ xy 1 0 0
1 1 0

119
 Karnaugh maps
• Alternate way of representing Booleanfunction
– All rows of truth table represented with a square
– Each square represents a minterm

• Easy to convert between truth table, K-map, and SOP

– Unoptimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
– Optimized form: reduced number of minterms
– RULE: [0  A’ (Complement), 1  A(Normal)]

F= Σ(m0,m1) = x’y’ + x’y

x y F y
0 0 1 y y
x 0 1 x 0 1
0 1 1 0 x’y’ x’y 0 1 1
1 0 0
x 1 xy’ xy 1 0 0
1 1 0

120
 Karnaugh Maps
• A Karnaugh map is a graphical tool for assisting in the
general simplification procedure.
• Two variable maps.
B B
0 1 0 1
A A
0 0 1 0 0 1
1 1 0 1 1 1
A B C F
° Three variablemaps. 0 0 0 0
0 0 1 1
BC 0 1 0 1
A
00 01 11 10 0 1 1 0
0 0 1 0 0 1
1 0 1 1 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1

121
 Karnaugh Maps
• A Karnaugh map is a graphical tool for assisting in the
general simplification procedure.
• Two variable maps.
B B
0 1 0 1
A A
0 0 1 0 0 1 F=AB +AB+AB 
F=AB +A’B
1 1 0 1 1 1
A B C F
° Three variablemaps. 0 0 0 0
0 0 1 1
BC 0 1 0 1
00 01 11 10 0 1 1 0
A
0 0 1 0 0 1
1 0 1 1 0 1 1
1 1 1 1 1 1 1 0 1
1 1 1 1
F=AB’C’ +AB C+ABC +ABC + A’B’C +A’BC’
122
 Rules for K-Maps
 We can reduce functions by circling 1’s in the K-map
 Each circle represents minterm reduction
 Following circling, we can deduce minimized AND-ORform.

Rules to consider
1. Every cell containing a ‘1’ must be included at least once.
2. The largest possible “Power of 2 rectangle” must be
enclosed
[Pairing of two 1’s, four 1’s, eight 1’s or sixteen 1’s (Highest
Priority)].
3. The 1’s must be enclosed in the smallest possible number of
rectangles.
4. Diagonal pairing is notallowed, adjacent pairing is allowed.

123
 Karnaugh maps
• Alternate way of representing Booleanfunction
– All rows of truth table represented with a square
– Each square represents a minterm

• Easy to convert between truth table, K-map, and SOP

– Unoptimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
– Optimized form: reduced number of minterms
– RULE: [0  A’ (Complement), 1  A(Normal)]

F= Σ(m0,m1) = x’y’ + x’y

x y F y
0 0 1 y y
x 0 1 x 0 1
0 1 1 0 x’y’ x’y 0 1 1
1 0 0
x 1 xy’ xy 1 0 0
1 1 0

124
 Karnaugh maps
• Alternate way of representing Booleanfunction
– All rows of truth table represented with a square
– Each square represents a minterm

• Easy to convert between truth table, K-map, and SOP

– Unoptimized form: number of 1’s in K-map equals number of
minterms (products) in SOP
– Optimized form: reduced number of minterms
– RULE: [0  A’ (Complement), 1  A(Normal)]

F= Σ(m0,m1) = x’y’ + x’y

y
= x’
x y F
0 0 1 y y
x 0 1 x 0 1
0 1 1 0 x’y’ x’y 0 1 1
1 0 0
x 1 xy’ xy 1 0 0
1 1 0

125
 Karnaugh Maps
• A Karnaugh map is a graphical tool for assisting in thegeneral
simplification procedure.
• Two variable maps.
B B
0 1 0 1
A A F=AB +AB+AB 
00 1 Optimized 00 1
11 0 form: 11 1
F=AB +A’B
° Three variablemaps.
BC
00 01 11 10
A
00 1 0 1
11 1 1 1

Unoptimized form: F=AB’C’ +AB C+ABC +ABC + A’B’C + A’BC’

126
 Karnaugh Maps
• A Karnaugh map is a graphical tool for assisting in thegeneral
simplification procedure.
• Two variable maps.
B B
A 0 1 A 0 1
F=AB +AB+AB
00 1 Optimized 00 1
form: Optimized
11 0 11 1
F=AB +A’B form:
° Three variablemaps. F=A+B
BC
00 01 11 10
A
00 1 0 1
11 1 1 1

Unoptimized form: F=AB’C’ +AB C+ABC +ABC + A’B’C + A’BC’

127
 Karnaugh Maps
• A Karnaugh map is a graphical tool for assisting in thegeneral
simplification procedure.
• Two variable maps.
B B
A 0 1 A 0 1
F=AB +AB+AB
00 1 Optimized 00 1
form: Optimized
11 0 11 1
F=AB +A’B form:
° Three variablemaps. F=A+B
BC
00 01 11 10
A
00 1 0 1 Optimized form: F=A+B C+BC 
11 1 1 1

Unoptimized form: F=AB’C’ +AB C+ABC +ABC + A’B’C + A’BC’

128
 More Karnaugh Map Examples
a
0 1 a
b
• Examples 0 0 1
1 0 1
b 0 1
0 1 1
1 0 0

ab ab
c 00 01 11 10 c 00 01 11 10
0 0 0 1 0 0 0 0 1 1
1 0 1 1 1 1 0 0 1 1

1. Circle the largest groupspossible.

2.Group dimensions must be apower 1 1 1
of 2. 1 1
3. Remember what circling means!
129
 More Karnaugh Map Examples
a
0 1 a
b 0 1
0 0 1 b
• Examples 1 0 1 0 1 1
1 0 0
f =a
f =b'
ab ab
c 00 01 11 10 c 00 01 11 10
0 0 0 1 0 0 0 0 1 1
1 0 1 1 1 1 0 0 1 1
f = ab + bc +ac
f =a
ab
00 01 11 10
c
0 1 1 1
f = a’c+b
1 1 1
130
 More Examples
• f1(x, y, z) = ∑m(2,3,5,7)

• f2(x, y, z) = ∑m (0,1,2,3,6)

• f3(x1,x2) = ∑m (0,1,2)

• y=A’B’C’+A’BC’+AB’C+ABC

PJF- 131
 Solution
yz
X 00 01 11 10

• f1(x, y, z) = ∑m(2,3,5,7) 0 1 1
1 1 1
 f1(x, y, z) = x’y + xz

• f2(x, y, z) = ∑m (0,1,2,3,6)
1 1 1 1
 f2(x, y, z) = x’+yz’
1

PJF- 132
• f3(x1,x2) = ∑m (0,1,2) x2
f3(x1,x2)= x1’ +x2’ x1 0 1
0 1

0 1 1
2 3

1 1 0

133
Y=AC+A’C’

134
 Example
• Simplify the followingBoolean function

• f(A,B,C,D) = ∑m(0,1,2,4,5,7,8,9,10,12,13).

PJF- 135
 Solution
• Simplify the following Boolean function(A,B,C,D) =
∑m(0,1,2,4,5,7,8,9,10,12,13).
• First put the function g( ) into the map, and then
group as many 1s as possible.
cd
ab 00 01 11 10
1 1 1 1 1 1
00
01 1 1 1 1 1 1

11 1 1 1 1

10 1 1 1 1 1 1

g(A,B,C,D) = c’+b’d’+a’bd
PJF- 136
Example

137
138
f =y f = x’y +xy’ f = x’ +y’

139
140
141
Answers

142
 Example
• f(A,B,C,D) = ∑m(6,8,9,10,11,12,13,14).

143
144
145
 Summary
• Application: One bit adder.
• Karnaugh map allows us to represent
functions with new notation.
• Representation allows for logic reduction.
– Implement same function with less logic
• Each square represents one minterm
• Each circle leads to one product term
• Not all functions can be reduced
• Each circle represents an application of:
– Distributive rule -- x (y + z) = xy + xz
– Complement rule – x + x’ = 1
146
147
148
149
150
151
KMap using Don’t care
 Don’t Care Conditions
• Adon’t care condition, marked by (X) in the truth table,
indicates a condition where the design doesn’t care if
the output is a (0) ora (1).

• A don’t care condition can be treated as a (0) or a (1) in

a K-Map.

• Treating a don’t care as a (0) means that you do not

need to groupit.

• Treating a don’t care as a (1) allows you to make a

grouping larger, resulting in a simpler term in the SOP
equation.
153
154
155
156
Quine-McCluskey Minimization
Technique (Tabular Method)
 Quine-McCluskey (Tabular)
Minimization
• The Q-K method reduces the minterm
expansion of a function to obtain a minimum
SOP.
• IMP terms:
– Implicants: Group of 1’s
– Prime Implicants: Largest possible group of1’s.
– Essential Prime Implicants: It is a prime implicant
which contains atleast one minterm which can not
be combined in any other way.
158
 Quine-McCluskey (Tabular)
Minimization
• All work is done in tabular form
– Number of variables is not alimitation
– Basis for many computer implementations
– Don’t cares are easily handled

• Proper organization and term identification

are key factors for correct results

159
 Steps
1. Make a groups according to number of ‘1’s’
present.

2. Find Prime Implicants

3. Find Essential Prime Implicants

160
161
162
163
164
Prime
Implicants

165
166
 Example 1
• f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15)

167
Solution

168
169
F=YZ’ + WX’ + WY.

170
 Example 2
• f(A, B, C, D) = (0,1,2,3,5,7,8,10,12,13,15)

171
Solution

172
173
Example 3

174
Solution

f = a’bd + b’c’ + cd’

175
176
177