Chapter-3
Gate-Level Minimization
Outline of Chapter 3
● Karnaugh Map
● 2- variable with examples
● 3- variable with examples
● 4- variable with examples
● Don’t cares with examples
● Multiple outputs with examples
● More logic gates
● Parity generators
● Even parity
● Odd parity
ITEC-252 Ch1-0
Karnaugh Map
● Also called K-map for short
● The Karnaugh map is a diagram made up of squares
● It is a reorganized version of the truth table
● Each square in the Karnaugh map represents a minterm
● Adjacent squares differ in the value of one variable
● Simplified expressions can be derived from the Karnaugh map
● By recognizing patterns of squares
● Simplified sum-of-products expression (AND-OR circuits)
● Simplified product-of-sums expression (OR-AND circuits)
Two-Variable Karnaugh Map
Two-variable K-map
y0 1 y0 1
x x
0 m0 m1 0 x' y' x' y
1 m2 m3 1 x y' xy
From a Truth Table to Karnaugh Map
● Given a truth table, construct the corresponding K-map
● Copy the function values from the truth table into the K-
map
● Make sure to copy each value into the proper K-map
square
Truth Table K-map
y0 1
xy f x
00 1
0 1 0
01 0
10 1
1 1 1
11 1
K-Map Function Minimization
K-map
y0 1
x
0 1 0
1 1 1
Three-Variable Karnaugh Map
● Have eight squares (for the 8 minterms), numbered 0 to 7
● The last two columns are not in numeric order: 11, 10
● Remember the numbering of the squares in the K-map
● Each square is adjacent to three other squares
● Minterms in adjacent squares can always be combined
● This is the key idea that makes the K-map work
● Labeling of rows and columns is also useful
00 01 11 10 00 01 11 10
0 0
1 1
Simplifying a Three-Variable Function
00 01 11 10
0 0 0 1 0
1 1 1 1 0
Simplifying a Three-Variable Function (2)
00 01 11 10
0 0 0 1 0
1 1 0 1 1
Combining Squares on a 3-Variable K-Map
● By combining squares, we reduce number of literals in
a product term, thereby reducing the cost
● On a 3-variable K-Map:
● One square represents a minterm with 3 variables
● Two adjacent squares represent a term with 2 variables
● Four adjacent squares represent a term with 1 variable
● Eight adjacent square is the constant ‘1’ (no variables)
Example of Combining Squares
0 0 1 1
0 1 1 0
0 0 0 1 1
1 0 1 1 1
Minimal Sum-of-Products Expression
00 01 11 10
0 1 1 0 1
1 1 0 1 1
Four-Variable Karnaugh Map
Notice the order of Rows 11 and 10
and the order of columns 11 and 10
0 0 1 1
0 1 1 0
0
0
0
1
1
1
1
0
Combining Squares on a 4-Variable K-Map
● On a 4-variable K-Map:
● One square represents a minterm with 4 variables
● Two adjacent squares represent a term with 3 variables
● Four adjacent squares represent a term with 2 variables
● Eight adjacent squares represent a term with 1 variable
● Combining all 16 squares is the constant ‘1’ (no variables)
Combining Eight Squares
00 01 11 10
00
01
11
10
Combining Four Squares
00 01 11 10
00
01
11
10
Combining Two Squares
00 01 11 10
00
01
11
10
Simplifying a 4-Variable Function
00 01 11 10
00 1 0 0 1
01 1 1 1 1
11 1 0 0 0
10 1 0 0 0
Don't Cares
● Sometimes, a function table may contain entries for which:
● The input values of the variables will never occur, or
● The output value of the function is never used
● In this case, the output value of the function is not defined
● The output value of the function is called a don't care
● A don't care is an X value that appears in the function table
● The X value can be later chosen to be 0 or 1
● To minimize the function implementation
Example of a Function with Don't Cares
Truth Table
abcd f
0000 0
0001 0
0010 0
0011 0
0100 0
0101 1
0110 1
0111 1
1000 1
1001 1
1010 X
1011 X
1100 X
1101 X
1110 X
Minterms Don't Cares 1111 X
Minimizing Functions with Don't Cares
0 0 1 1
0 1 1 0
00 0 0 0 0
The don't care values can be 01 0 1 1 1
selected to be either 0 or 1, to
produce a minimal expression 11 X X X X
10 1 1 X X
Minimizing Functions with Don't Cares (2)
0 0 1 1 0 0 1 1
00 0X 1
1 1
1 0
X 00 0X 1
1 1
1 0
X
01 0 X 1 0 01 0 X 1 0 Not all don't
11 0 0 1 0 11 0 0 1 0 cares need
be covered
10 0 0 1 0 10 0 0 1 0
Multiple Outputs
One circuit with
Two separate circuits Two Outputs
Multiple Outputs: Example 1
One
circ
uit
0 0 1 1 per
0 1 1 0 func
0 1 0 0 1
tion
1 0 0 1 1
One
circ
0 0 1 1 uit
0 00 11 11 00 with
two
1 0 0 1 1 Out
puts
Multiple Outputs: Example 2
0 0 1 1 0 0 1 1
0 1 1 0 0 1 1 0
0 1 0 1 1
0 0
0 1 1 0 1 1
1 1
1 1 1 1 1
1 1
1 1 1 1 1
0 0
Common Terms Shared Gates
One Circuit
NO Shared Two Shared
Gates Gates
More Logic Gates
• NAND and NOR Gates
– NAND and NOR circuits
– Two-level Implementations
– Multilevel Implementations
• Exclusive-OR (XOR) Gates
– Odd Function
– Parity Generation and Checking
Gate Level Minimization
More Logic Gates
• We can construct any combinational circuit with
AND, OR, and NOT gates
• Additional logic gates are used for practical reasons
Gate Level Minimization
BUFFER, NAND and NOR
Gate Level Minimization
NAND Gate
• Known as a “universal” gate because ANY
digital circuit can be implemented with NAND
gates alone.
• To prove the above, it suffices to show that
AND, OR, and NOT can be implemented
using NAND gates only.
Gate Level Minimization
NAND Gate Emulation
F = (X•X)’ X F = X’
X
= X’+X’
= X’
X X F X•Y
F = ((X•Y)’)’
Y Y
= (X’+Y’)’
= X’’•Y’’
= X•Y
X X
F = (X’•Y’)’ F = X+Y
= X’’+Y’’
Y Y
= X+Y
Gate Level Minimization
NAND Circuits
• To easily derive a NAND implementation of a
boolean function:
– Find a simplified SOP
– SOP is an AND-OR circuit
– Change AND-OR circuit to a NAND circuit
– Use the alternative symbols below
Gate Level Minimization
AND-OR (SOP) Emulation
Using NANDs
Two-level implementations
• Original SOP
• Implementation with NANDs
Gate Level Minimization
AND-OR (SOP) Emulation
Using NANDs (cont.)
Verify:
G = WXY + YZ
G = ( (WXY)’ • (YZ)’ )’
= (WXY)’’ + (YZ)’’ = WXY + YZ
Gate Level Minimization
SOP with NAND
• Original SOP
• Double inversion and grouping AND-NOT
• Replacement with NANDs NOT-OR
Gate Level Minimization
Two-Level NAND Gate
Implementation - Example
F (X,Y,Z) = m(0,6)
• Express F in SOP form:
F = X’Y’Z’ + XYZ’
• Obtain the AND-OR implementation for F.
• Add bubbles and inverters to transform
AND-OR to NAND-NAND gates.
Gate Level Minimization
Example (cont.)
Two-level implementation with NANDs
F = X’Y’Z’ + XYZ’
Gate Level Minimization
NOR Gate
• Also a “universal” gate because ANY digital
circuit can be implemented with NOR gates
alone.
• This can be similarly proven as with the
NAND gate.
Gate Level Minimization
NOR Circuits
• To easily derive a NOR implementation of a boolean
function:
– Find a simplified POS
– POS is an OR-AND circuit
– Change OR-AND circuit to a NOR circuit
– Use the alternative symbols below
Gate Level Minimization
Two-Level NOR Gate
Implementation - Example
F(X,Y,Z) = m(0,6)
• Express F’ in SOP form:
• F’ = m(1,2,3,4,5,7)
= X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XY’Z + XYZ
• F’ = XY’ + X’Y + Z
• Take the complement of F’ to get F in the POS
form: F = (F’)' = (X'+Y)(X+Y')Z'
• Obtain the OR-AND implementation for F.
• Add bubbles and inverters to transform OR-AND
implementation to NOR-NOR implementation.
Gate Level Minimization
Example (cont.)
Two-level implementation with NORs
F = (F’)' = (X'+Y)(X+Y')Z'
Gate Level Minimization
XOR and XNOR
X Y F=X Y
XOR: “not-equal” gate 0 0 0
0 1 1
X F 1 0 1
Y 1 1 0
X Y F=X Y
XNOR: “equal” gate 0 0 1
0 1 0
X F
1 0 0
Y 1 1 1
Gate Level Minimization
Exclusive-OR (XOR) Function
• XOR denoted by the symbol
• XOR (also ) : the “not-equal” function
• XOR(X,Y) = X Y = X’Y + XY’
• Identities:
– X 0=X
– X 1 = X’
– X X=0
– X X’ = 1
• Properties:
– X Y=Y X
– (X Y) W = X (Y W)
Gate Level Minimization
XOR function implementation
• We are going to implement Parity Generation and
Checking by using XOR function.
• Exclusive-OR functions are very useful in systems
requiring error detection and correction codes.
• Parity bit is used for the purpose of detecting errors
during the transmission of binary information.
• Definition: The circuit that generates the parity bit
in the transmitter is called a parity generator.
• Definition: The circuit that checks the parity bit in
the receiver is called a parity checker.
Gate Level Minimization
Parity Generation Types
• There are two types of Parity generators as
below
1. Even Parity
2. Odd Parity
[Link] parity: An even parity bit generator
generates an output of 0 if the number of 1’s in
the input sequence is even and 1 if the number
of 1’s in the input sequence is odd.
Gate Level Minimization
Odd parity
2. Odd parity: An odd parity bit generator
generates an output of 1 if the number of 1’s in
the input sequence is even and 0 if the number
of 1’s in the input sequence is odd.
Therefore , P can be expressed as a three-
variable exclusive-OR function:
P= X Y Z
Gate Level Minimization
Logic diagram of Even Parity
generator
Gate Level Minimization
Even parity generator Truth table
Gate Level Minimization
Logic diagram of odd Parity
Gate Level Minimization
Odd parity generator Truth table
Gate Level Minimization
Even & Odd parity Truth table
Gate Level Minimization