Introduction
Simplification of Boolean functions is mainly used to reduce the gate count of a design. Less number of gates means less power consumption, sometimes the circuit works faster and also when number of gates is reduced, cost also comes down.
There are many ways to simplify a logic design, some of them are given below. We will be looking at each of these in detail in the next few pages.
· Algebraic Simplification.
o Simplify symbolically using theorems/postulates.
o Requires good skills
· Karnaugh Maps.
o Diagrammatic technique using 'Venn-like diagram'.
o Limited to no more than 6 variables.
We have already seen how Algebraic Simplification works, so lets concentrate on Karnaugh Maps or simply k-maps.
Karnaugh Maps
Karnaugh maps provide a systematic method to obtain simplified sum-of-products (SOPs) Boolean expressions. This is a compact way of representing a truth table and is a technique that is used to simplify logic expressions. It is ideally suited for four or less variables, becoming cumbersome for five or more variables. Each square represents either a minterm or maxterm. A K-map of n variables will have 2
squares. For a Boolean expression, product terms are denoted by 1's, while sum terms are denoted by 0's - but 0's are often left blank.
A K-map consists of a grid of squares, each square representing one canonical minterm combination of the variables or their inverse. The map is arranged so that squares representing minterms which differ by only one variable are adjacent both vertically and horizontally. Therefore XY'Z' would be adjacent to X'Y'Z' and would also adjacent to XY'Z and XYZ'.
Minimization Technique
· Based on the Unifying Theorem: X + X' = 1
· The expression to be minimized should generally be in sum-of-product form (If necessary, the conversion process is applied to create the sum-of-product form).
· The function is mapped onto the K-map by marking a 1 in those squares corresponding to the terms in the expression to be simplified (The other squares may be filled with 0's).
· Pairs of 1's on the map which are adjacent are combined using the theorem Y(X+X') = Y where Y is any Boolean expression (If two pairs are also adjacent, then these can also be combined using the same theorem).
· The minimization procedure consists of recognizing those pairs and multiple pairs.
o These are circled indicating reduced terms.
o Groups which can be circled are those which have two (2^{1}) 1's, four (2^{2}) 1's, eight (2^{3}) 1's, and so on.
o Note that because squares on one edge of the map are considered adjacent to those on the opposite edge, group can be formed with these squares.
o Groups are allowed to overlap.
· The objective is to cover all the 1's on the map in the fewest number of groups and to create the largest groups to do this.
· Once all possible groups have been formed, the corresponding terms are identified.
o A group of two 1's eliminates one variable from the original minterm.
o A group of four 1's eliminates two variables from the original minterm.
o A group of eight 1's eliminates three variables from the original minterm, and so on.
o The variables eliminated are those which are different in the original minterms of the group.
2-Variable K-Map
In any K-Map, each square represents a minterm. Adjacent squares always differ by just one literal (So that the unifying theorem may apply: X + X' = 1). For the 2-variable case (e.g.: variables X, Y), the map can be drawn as below. Two variable map is the one which has got only two variables as input.
Equivalent labeling
K-map needs not follow the ordering as shown in the figure above. What this means is that we can change the position of m0, m1, m2, m3 of the above figure as shown in the two figures below.
Position assignment is the same as the default k-maps positions. This is the one which we will be using throughout this tutorial.
This figure is with changed position of m0, m1, m2, m3.
The K-map for a function is specified by putting a '1' in the square corresponding to a minterm, a '0' otherwise.
Example- Carry and Sum of a half adder
In this example we have the truth table as input, and we have two output functions. Generally we may have n output functions for m input variables. Since we have two output functions, we need to draw two k-maps (i.e. one for each function). Truth table of 1 bit adder is shown below. Draw the k-map for Carry and Sum as shown below.
X | Y | Sum | Carry |
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
Grouping/Circling K-maps
The power of K-maps is in minimizing the terms, K-maps can be minimized with the help of grouping the terms to form single terms. When forming groups of squares, observe/consider the following:
· Every square containing 1 must be considered at least once.
· A square containing 1 can be included in as many groups as desired.
· A group must be as large as possible.
· If a square containing 1 cannot be placed in a group, then leave it out to include in final expression.
· The number of squares in a group must be equal to 2
· i.e. 2,4,8,.
· The map is considered to be folded or spherical, therefore squares at the end of a row or column are treated as adjacent squares.
· The simplified logic expression obtained from a K-map is not always unique. Groupings can be made in different ways.
· Before drawing a K-map the logic expression must be in canonical form.
In the next few pages we will see some examples on grouping.
Example of invalid groups
Example - X'Y+XY
In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y and XY position. Now combine two 1's as shown in figure to form the single term. As you can see X and X' get canceled and only Y remains.
F = Y
Example - X'Y+XY+XY'
In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y, XY and XY position. Now combine two 1's as shown in figure to form the two single terms.
F = X + Y
3-Variable K-Map
There are 8 minterms for 3 variables (X, Y, Z). Therefore, there are 8 cells in a 3-variable K-map. One important thing to note is that K-maps follow the gray code sequence, not the binary one.
Using gray code arrangement ensures that minterms of adjacent cells differ by only ONE literal. (Other arrangements which satisfy this criterion may also be used.)
Each cell in a 3-variable K-map has 3 adjacent neighbours. In general, each cell in an n-variable K-map has n adjacent neighbours
There is wrap-around in the K-map
· X'Y'Z' (m0) is adjacent to X'YZ' (m2)
· XY'Z' (m4) is adjacent to XYZ' (m6)
Example
F = XYZ'+XYZ+X'YZ
F = XY + YZ
Example
F(X,Y,Z) = å(1,3,4,5,6,7)
F = X + Z
4-Variable K-Map
There are 16 cells in a 4-variable (W, X, Y, Z); K-map as shown in the figure below.
There are 2 wrap-around: a horizontal wrap-around and a vertical wrap-around. Every cell thus has 4 neighbours. For example, the cell corresponding to minterm m0 has neighbours m1, m2, m4 and m8.
Example
F(W,X,Y,Z) = (1,5,12,13)
F = WY'Z + W'Y'Z
Example
F(W,X,Y,Z) = (4, 5, 10, 11, 14, 15)
F = W'XY' + WY
There are 32 cells in a 5-variable (V, W, X, Y, Z); K-map as shown in the figure below.
Inverse Function
· The 0's on a K-map indicate when the function is 0.
· We can minimize the inverse function by grouping the 0's (and any suitable don't cares) instead of the 1's.
· This technique leads to an expression which is not logically equivalent to that obtained by grouping the 1's (i.e., the inverse of X != X').
· Minimizing for the inverse function may be particularly advantageous if there are many more 0's than 1's on the map.
We can also apply De Morgan's theorem to obtain a product-of-sum expression.