73
Chapter 3 
Gate-Level Minimization     
3.1    INTRODUCTION 
Gate-level minimization  is the design task of finding an optimal gate-level implementa-
tion of the Boolean functions describing a digital circuit. This task is well understood, 
but is difficult to execute by manual methods when the logic has more than a few inputs. 
Fortunately, computer-based logic synthesis tools can minimize a large set of Boolean 
equations efficiently and quickly. Nevertheless, it is important that a designer understand 
the underlying mathematical description and solution of the problem. This chapter serves 
as a foundation for your understanding of that important topic and will enable you to 
execute a manual design of simple circuits, preparing you for skilled use of modern 
design tools. The chapter will also introduce a hardware description language that is used 
by modern design tools.  
3.2    THE MAP METHOD 
The complexity of the digital logic gates that implement a Boolean function is directly 
related to the complexity of the algebraic expression from which the function is imple-
mented. Although the truth table representation of a function is unique, when it is expressed 
algebraically it can appear in many different, but equivalent, forms. Boolean expressions may 
be simplified by algebraic means as discussed in Section 2.4. However, this procedure of 
minimization is awkward because it lacks specific rules to predict each succeeding step in 
the manipulative process. The map method presented here provides a simple, straightforward 
procedure for minimizing Boolean functions. This method may be regarded as a pictorial 
form of a truth table. The map method is also known as the  Karnaugh map  or  K-map . 
How to convert pdf to powerpoint slides - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
changing pdf to powerpoint; convert pdf to powerpoint online for
How to convert pdf to powerpoint slides - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf to powerpoint slides; convert pdf file to powerpoint presentation
74    Chapter 3  Gate-Level Minimization
A K-map is a diagram made up of squares, with each square representing one minterm 
of the function that is to be minimized. Since any Boolean function can be expressed as a 
sum of minterms, it follows that a Boolean function is recognized graphically in the map 
from the area enclosed by those squares whose minterms are included in the function. In 
fact, the map presents a visual diagram of all possible ways a function may be expressed 
in standard form. By recognizing various patterns, the user can derive alternative algebraic 
expressions for the same function, from which the simplest can be selected. 
The simplified expressions produced by the map are always in one of the two standard 
forms: sum of products or product of sums. It will be assumed that the simplest algebraic 
expression is an algebraic expression with a minimum number of terms and with the 
smallest possible number of literals in each term. This expression produces a circuit 
diagram with a minimum number of gates and the minimum number of inputs to each 
gate. We will see subsequently that the simplest expression is not unique: It is sometimes 
possible to find two or more expressions that satisfy the minimization criteria. In that 
case, either solution is satisfactory. 
Two-Variable K-Map 
The two-variable map is shown in  Fig.   3.1   (a). There are four minterms for two variables; 
hence, the map consists of four squares, one for each minterm. The map is redrawn in 
(b) to show the relationship between the squares and the two variables  x  and  y . The 0 
and 1 marked in each row and column designate the values of variables. Variable  x  
appears primed in row 0 and unprimed in row 1. Similarly,  y  appears primed in column 
0 and unprimed in column 1.  
If we mark the squares whose minterms belong to a given function, the two-variable 
map becomes another useful way to represent any one of the 16 Boolean functions of 
two variables. As an example, the function  xy  is shown in  Fig.   3.2   (a). Since  xy  is equal to 
m
3
,    a 1 is placed inside the square that belongs to    m
3
.    Similarly, the function    xy    is 
represented in the map of  Fig.   3.2   (b) by three squares marked with 1’s. These squares 
are found from the minterms of the function:  
m
1
m
2
+m
3
xyxy′ + xy xy   
m
0
m
1
m
2
m
3
(a)
0
1
0
1
y
x
y
x
xy
m
0
xy
m
1
xy
m
2
xy
m
3
(b)
FIGURE 3.1 
Two-variable K-map       
C# PowerPoint - How to Process PowerPoint
Microsoft PowerPoint Document Processing Control in Visual C#.NET of RasterEdge .NET Imaging SDK is a reliable and professional PowerPoint slides/pages editing
pdf picture to powerpoint; add pdf to powerpoint presentation
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
add image to slide, extract slides and merge library SDK, this VB.NET PowerPoint processing control powerful & profession imaging controls, PDF document, image
pdf to powerpoint converter; how to convert pdf to powerpoint
Section 3.2  The Map Method    75
The three squares could also have been determined from the intersection of variable 
x  in the second row and variable  y  in the second column, which encloses the area 
belonging to  x  or  y . In each example, the minterms at which the function is asserted are 
marked with a 1.  
Three-Variable K-Map 
A three-variable K-map is shown in  Fig.   3.3   . There are eight minterms for three binary 
variables; therefore, the map consists of eight squares. Note that the minterms are 
arranged, not in a binary sequence, but in a sequence similar to the Gray code ( Table   1.6   ). 
The characteristic of this sequence is that  only one bit changes in value from one adjacent 
column to the next.  The map drawn in part (b) is marked with numbers in each row and 
each column to show the relationship between the squares and the three variables. For 
example, the square assigned to    m
5
corresponds to row 1 and column 01. When these two 
numbers are concatenated, they give the binary number 101, whose decimal equivalent 
is 5. Each cell of the map corresponds to a unique minterm, so another way of looking at 
square    m
5
xyz    is to consider it to be in the row marked  x  and the column belonging 
to    yz    (column 01). Note that there are four squares in which each variable is equal to 1 
and four in which each is equal to 0. The variable appears unprimed in the former four 
0
1
0
1
x
y
1
m
0
m
1
m
2
m
3
x
y
0
1
0
1
x
y
1
1
1
y
x
x
y
(a)xy
(b)x+ y
m
0
m
1
m
2
m
3
FIGURE 3.2 
Representation of functions in the map       
(a)
m
0
m
1
m
3
m
2
m
4
m
5
m
7
m
6
0
1
00
01
11
10
z
y
x
yz
x
xyz
xyz
xyz
xyz
xyz′ xyz
xyz
xyz
m
0
m
1
m
3
m
2
m
4
m
5
m
7
m
6
(b)
FIGURE 3.3 
Three-variable K-map       
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
clip art or screenshot to PowerPoint document slide large amount of robust PPT slides/pages editing powerful & profession imaging controls, PDF document, image
add pdf to powerpoint slide; convert pdf to powerpoint with
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
Besides, users also can get the precise PowerPoint slides count as soon as the PowerPoint document has been loaded by using the page number getting method.
converting pdf to powerpoint; how to add pdf to powerpoint presentation
76    Chapter 3  Gate-Level Minimization
squares and primed in the latter. For convenience, we write the variable with its letter 
symbol under the four squares in which it is unprimed.  
To understand the usefulness of the map in simplifying Boolean functions, we must 
recognize the basic property possessed by adjacent squares:  Any two adjacent squares 
in the map differ by only one variable,  which is primed in one square and unprimed in 
the other. For example,    m
5
and    m
7
lie in two adjacent squares. Variable  y  is primed in 
m
5
and unprimed in    m
7
,    whereas the other two variables are the same in both squares. 
From the postulates of Boolean algebra, it follows that the sum of two minterms in 
adjacent squares can be simplified to a single product term consisting of only two liter-
als. To clarify this concept, consider the sum of two adjacent squares such as    m
5
and    m
7
:    
m
5
m
7
xyxyz xz(y′+y) = xz   
Here, the two squares differ by the variable  y , which can be removed when the sum of 
the two minterms is formed. Thus, any two minterms in adjacent squares (vertically or 
horizontally, but not diagonally, adjacent) that are ORed together will cause a removal 
of the dissimilar variable. The next four examples explain the procedure for minimizing 
a Boolean function with a K-map. 
EXAMPLE3.1 
Simplify the Boolean function 
F (x, y, z) = ∑(2,3,4, 5)   
First, a 1 is marked in each minterm square that represents the function. This is shown 
in  Fig.   3.4   , in which the squares for minterms 010, 011, 100, and 101 are marked with 1’s. 
The next step is to find possible adjacent squares. These are indicated in the map by two 
shaded rectangles, each enclosing two 1’s. The upper right rectangle represents the area 
enclosed by    xy.    This area is determined by observing that the two-square area is in row 
0, corresponding to    x′,    and the last two columns, corresponding to  y . Similarly, the lower 
left rectangle represents the product term    xy′.    (The second row represents  x  and the 
two left columns represent    y′.   ) The sum of four minterms can be replaced by a sum of 
0
1
00
01
11
10
x
yz
m
0
m
1
1
m
3
1
m
2
1
m
4
1
m
5
m
7
m
6
xy
xy
z
y
x
FIGURE 3.4 
Map for  Example   3.1   ,    (x,y,z) = = ∑(2, , 3, , 4, , 5) = xxy          
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
want to combine these extracted slides into a please read this VB.NET PowerPoint slide processing powerful & profession imaging controls, PDF document, image
how to change pdf to powerpoint slides; how to change pdf to powerpoint on
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
of the split PPT document will contain slides/pages 1-4 code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
convert pdf slides to powerpoint online; change pdf to powerpoint on
Section 3.2  The Map Method    77
only two product terms. The logical sum of these two product terms gives the simplified 
expression 
x+xy    
In certain cases, two squares in the map are considered to be adjacent even though 
they do not touch each other. In  Fig.   3.3   (b),    m
0
is adjacent to    m
2
and    m
4
is adjacent to 
m
6
because their minterms differ by one variable. This difference can be readily verified 
algebraically: 
m
0
m
2
=xyz′ +xyz′ =xz′(y′ + y) =xz   
m
4
m
6
=xyz′ +  xyz′   =  xz  ′ +(y′ ′ + y) = xz   
Consequently, we must modify the definition of adjacent squares to include this and 
other similar cases. We do so by considering the map as being drawn on a surface in 
which the right and left edges touch each other to form adjacent squares. 
EXAMPLE3.2 
Simplify the Boolean function 
F(xyz) = = ∑(3, , 4,6,7)   
The map for this function is shown in  Fig.   3.5   . There are four squares marked with 1’s, 
one for each minterm of the function. Two adjacent squares are combined in the third 
column to give a two-literal term  yz . The remaining two squares with 1’s are also adja-
cent by the new definition. These two squares, when combined, give the two-literal term 
xz′.    The simplified function then becomes 
yz xz    
0
1
00
01
11
10
z
y
x
yz
x
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
1
1
1
1
yz
xyz
xyz
Note: xyz′+ xyz′= xz
FIGURE 3.5 
Map for  Example   3.2   ,    F(x,y,z) =∑(3,4,6,7) ) = yz +xz          
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
VB.NET PowerPoint Conversion Control to render and convert target PowerPoint document to various image or document formats, such as PDF, BMP, TIFF
convert pdf pages to powerpoint slides; conversion of pdf to ppt online
VB.NET PowerPoint: Convert & Render PPT into PDF Document
Using this VB.NET PowerPoint to PDF converting demo code below, you can easily convert all slides of source PowerPoint document into a multi-page PDF file.
online pdf converter to powerpoint; copying image from pdf to powerpoint
78    Chapter 3  Gate-Level Minimization
Consider now any combination of four adjacent squares in the three-variable map. 
Any such combination represents the logical sum of four minterms and results in an 
expression with only one literal. As an example, the logical sum of the four adjacent 
minterms 0, 2, 4, and 6 reduces to the single literal term    z′:    
m
0
m
2
+m
4
m
6
xyz′ + xyz′ + xyz′+ xyz
=xz′(y′+ y) + xz′(y′ + y)
xz′ + xz′= z′(x′ +x) = z   
The number of adjacent squares that may be combined must always represent a 
number that is a power of two, such as 1, 2, 4, and 8. As more adjacent squares are com-
bined, we obtain a product term with fewer literals. 
One square represents one minterm, giving a term with three literals. 
Two adjacent squares represent a term with two literals. 
Four adjacent squares represent a term with one literal. 
Eight adjacent squares encompass the entire map and produce a function that is 
always equal to 1. 
EXAMPLE3.3 
Simplify the Boolean function 
F (x, y, z) = ∑(0, 2, 4, 5, 6)   
The map for  F  is shown in  Fig.   3.6   . First, we combine the four adjacent squares in the 
first and last columns to give the single literal term    z′.    The remaining single square, 
representing minterm 5, is combined with an adjacent square that has already been used 
once. This is not only permissible, but rather desirable, because the two adjacent squares 
give the two-literal term    xy′    and the single square represents the three-literal minterm 
xyz.    The simplified function is 
=z′+ xy    
Note: yz′+ yz′= z
0
1
00
01
11
10
z
y
x
yz
x
1
1
1
1
1
xy
yz
yz
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
FIGURE 3.6 
Map for  Example   3.3   ,    F (x, y, z)= ∑(0, 2, 4, 5, 6) ) =z′+ xy          
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
insert or delete any certain PowerPoint slide without methods to reorder current PPT slides in both powerful & profession imaging controls, PDF document, tiff
table from pdf to powerpoint; pdf to powerpoint converter online
C# PowerPoint: C# Guide to Add, Insert and Delete PPT Slide(s)
file and it includes all slides and properties to view detailed guide for each PowerPoint slide processing & profession imaging controls, PDF document, tiff
create powerpoint from pdf; pdf page to powerpoint
Section 3.2  The Map Method    79
If a function is not expressed in sum-of-minterms form, it is possible to use the map to 
obtain the minterms of the function and then simplify the function to an expression with a 
minimum number of terms. It is necessary, however, to make sure that the algebraic expres-
sion is in sum-of-products form. Each product term can be plotted in the map in one, two, 
or more squares. The minterms of the function are then read directly from the map. 
EXAMPLE3.4 
For the Boolean function 
=A+ABABBC   
(a)   Express this function as a sum of minterms.  
(b)   Find the minimal sum-of-products expression.   
Note that F is a sum of products. Three product terms in the expression have two literals 
and are represented in a three-variable map by two squares each. The two squares cor-
responding to the first term,    AC,    are found in  Fig.   3.7    from the coincidence of    A′    (first 
row) and  C  (two middle columns) to give squares 001 and 011. Note that, in marking 
1’s in the squares, it is possible to find a 1 already placed there from a preceding term. 
This happens with the second term,    AB,    which has 1’s in squares 011 and 010. Square 
011 is common with the first term,    AC,    though, so only one 1 is marked in it. Continu-
ing in this fashion, we determine that the term    ABC    belongs in square 101, correspond-
ing to minterm 5, and the term  BC  has two 1’s in squares 011 and 111. The function has 
a total of five minterms, as indicated by the five 1’s in the map of  Fig.   3.7   .  The minterms 
are read directly from the map to be 1, 2, 3, 5, and 7. The function can be expressed in 
sum-of-minterms form as  
F (A, B, C) = = ∑(1, 2, 3, 5, 7)   
The sum-of-products expression, as originally given, has too many terms. It can be 
simplified, as shown in the map, to an expression with only two terms: 
AB      
0
1
00
01
11
10
C
B
A
BC
A
1
1
1
1
AB
C
1
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
FIGURE 3.7 
Map of  Example   3.4   ,    AA  AB BC  AB          
80    Chapter 3  Gate-Level Minimization
3.3  FOUR-VARIABLE K-MAP 
The map for Boolean functions of four binary variables (wxy, z) is shown in  Fig.   3.8   . 
In Fig. 3.8(a) are listed the 16 minterms and the squares assigned to each. In Fig. 3.8(b), 
the map is redrawn to show the relationship between the squares and the four variables. 
The rows and columns are numbered in a Gray code sequence, with only one digit 
changing value between two adjacent rows or columns. The minterm corresponding to 
each square can be obtained from the concatenation of the row number with the column 
number. For example, the numbers of the third row (11) and the second column (01), 
when concatenated, give the binary number 1101, the binary equivalent of decimal 13. 
Thus, the square in the third row and second column represents minterm    m
13
.     
The map minimization of four-variable Boolean functions is similar to the method 
used to minimize three-variable functions. Adjacent squares are defined to be squares 
next to each other. In addition, the map is considered to lie on a surface with the top 
and bottom edges, as well as the right and left edges, touching each other to form adja-
cent squares. For example,    m
0
and    m
2
form adjacent squares, as do    m
3
and    m
11
.    The 
combination of adjacent squares that is useful during the simplification process is easily 
determined from inspection of the four-variable map: 
One square represents one minterm, giving a term with four literals. 
Two adjacent squares represent a term with three literals. 
Four adjacent squares represent a term with two literals. 
Eight adjacent squares represent a term with one literal. 
Sixteen adjacent squares produce a function that is always equal to 1. 
No other combination of squares can simplify the function. The next two examples 
show the procedure used to simplify four-variable Boolean functions. 
m
0
m
1
m
3
m
2
m
4
m
5
m
7
m
6
m
12
m
13
m
15
m
14
m
8
m
9
m
11
m
10
(a)
(b)
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
m
14
m
15
m
13
m
12
m
10
m
11
m
9
m
8
00
01
11
10
00
01
11
10
x
y
wx
yz
w
z
wxyz′ wxyz wxyz z wxyz
wxyz′ wxyz wxyz wxyz
wxyz′ wxyz
wxyz
wxyz
wxyz′ wxyz wxyz wxyz
FIGURE 3.8 
Four-variable map       
Section 3.3  Four-Variable K-Map    81
EXAMPLE3.5 
Simplify the Boolean function 
F (w, x, yz) = = ∑(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)   
Since the function has four variables, a four-variable map must be used. The minterms 
listed in the sum are marked by 1’s in the map of  Fig.   3.9   . Eight adjacent squares marked 
with 1’s can be combined to form the one literal term    y′.    The remaining three 1’s on the 
right cannot be combined to give a simplified term; they must be combined as two or 
four adjacent squares. The larger the number of squares combined, the smaller is the 
number of literals in the term. In this example, the top two 1’s on the right are combined 
with the top two 1’s on the left to give the term    wz′   . Note that it is permissible to use 
the same square more than once. We are now left with a square marked by 1 in the third 
row and fourth column (square 1110). Instead of taking this square alone (which will 
give a term with four literals), we combine it with squares already used to form an area 
of four adjacent squares. These squares make up the two middle rows and the two end 
columns, giving the term    xz′.    The simplified function is  
y′+ wz′+ xz    
Note: wyz′+ wyz′= wz
xyz′+ xyz′= xz
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
m
12
m
8
m
13
m
9
m
15
m
14
m
10
m
11
00
01
11
10
00
01
11
10
x
y
wx
yz
w
z
1
1
1
1
1
1
1
1
1
1
1
wyz
xyz
wyz
xyz
y
FIGURE 3.9 
Map for  Example   3.5   ,    F(w, x, y, z)   ∑(0,1, 2, 4, 5, 6, 8, 9, 12, 13, 14) ) 
y′wz′ xz          
EXAMPLE3.6 
Simplify the Boolean function 
ABC′+ BCD′ + ABCD′ + ABC   
The area in the map covered by this function consists of the squares marked with 1’s in 
Fig.   3.10   . The function has four variables and, as expressed, consists of three terms with 
82    Chapter 3  Gate-Level Minimization
three literals each and one term with four literals. Each term with three literals is repre-
sented in the map by two squares. For example,    ABC′    is represented in squares 0000 
and 0001. The function can be simplified in the map by taking the 1’s in the four corners 
to give the term    BD′.    This is possible because these four squares are adjacent when the 
map is drawn in a surface with top and bottom edges, as well as left and right edges, 
touching one another. The two left-hand 1’s in the top row are combined with the two 
1’s in the bottom row to give the term    BC′.    The remaining 1 may be combined in a two-
square area to give the term    ACD′.    The simplified function is 
BD′ + BC′+ ACD    
Prime Implicants 
In choosing adjacent squares in a map, we must ensure that (1) all the minterms of the 
function are covered when we combine the squares, (2) the number of terms in the 
expression is minimized, and (3) there are no redundant terms (i.e., minterms already 
covered by other terms). Sometimes there may be two or more expressions that satisfy 
the simplification criteria. The procedure for combining squares in the map may be made 
more systematic if we understand the meaning of two special types of terms.  A   prime 
implicant   is a product term  obtained by combining the maximum possible number of 
adjacent squares in the map. If a minterm in a square is covered by only one prime 
implicant, that prime implicant is said to be  essential.  
Note: ABCD′+ ABCD′= ABD
ABCD′+ ABCD′= ABD
ABD′+ ABD′= BD
ABC′+ ABC′= BC
m
0
m
1
m
3
m
2
m
6
m
7
m
5
m
4
m
12
m
8
m
13
m
9
m
15
m
14
m
10
m
11
00
01
11
10
00
01
11
10
B
C
AB
CD
A
D
1
1
1
1
1
ABCD
ABCD
ABCD
ABCD
1
ABC
ABC
ACD
1
FIGURE 3.10 
Map for  Example   3.6   ,    ABC′ ′ BCD′ ABCD′ ABC′BD′ BC′ ACD          
Documents you may be interested
Documents you may be interested