The variables X and Y are Boolean. Each of the terms that contain all variables of the function are referred to as minterms. The + represents OR, no symbol between the variables is an AND, and the single quote represents a NOT. The expression above can be written in English as: (X AND Y) OR (NOT X AND Y) OR (X AND NOT Y). Notice that it is possible to factor out Y from the first two terms and X from the first and third terms. In doing these simplifications it is perfectly okay to reuse terms since XY + XY is just XY [Mano93]. Remember that Boolean variables and terms can only have two values: 1 and 0 (no 2's allowed). Returning to the above expression we have:
F(X,Y) = XY + X'Y + X'Y
= (XY + X'Y) + (XY + XY')
= Y(X + X') + X(Y + Y')
However (X + X') is just 1. This is the same thing as saying something is true or it isn't true which is obviously always true. Substituting in a 1 for both of the parenthesized expressions gives a simplification of:
F(X,Y) = X + Y
The original expression requires 7 gates (2 OR's, 3 AND's, and 2 NOT's) while the simplified version requires only 1 OR gate. The simplified version will be much easier to implement for a laboratory.
Now look at this simplification using a Karnaugh map. This map would look like that shown in Figure 1 [Mano93].
For instance the minterm X'Y occurs in the upper right hand corner of the map at the intersection of the X' row and the Y column. It is now possible to pair up the 1's in the right hand column leading to the term Y. The two 1's in the bottom row lead to the X term. These pairings have been shown by circling the appropriate cells. For three and four variables you would need a map with 8 and 16 squares. It is possible to join cells together in groups of 2, 4, 8, or higher order powers of two. Each time the next power of two cells is joined, another variable falls out of the term representing those cells.
The Algorithm:
There are two possible approaches to solving this problem. The approach that is usually used by humans is to find the largest number of cells that can be joined and move down to smaller groupings. After some consideration it was concluded that for the computer algorithm, starting with the smallest groupings (pairs) and moving up toward larger groupings would be easier. Once an algorithm is established for pairing minterms then higher order terms can be obtained by joining terms of the previous level grouping. Here then are the basics steps for the algorithm.One: Where possible, pair up all minterms or cells that contain ones . You must obtain all legal pairs even though this may lead to extra terms . All pairs are required because it is not possible to tell at this stage which pairs may join together to make groups of four.
Two: Remove those single cells that are incorporated into the pairings. Without this, some terms would unnecessarily be included as minterms and also in pair terms.
Three:Group four pairs to obtain groups of four. Again you must obtain all groups of four for the same reasons as given above.
Four: Once all groups of four have been obtained, drop out of the pair list those that have been included in the groups of four. No need to include something in the pairs list that has already been handled in the groups of four.
Five:Continue to try to group together previous groupings essentially repeating steps three and four above until you reach 2 raised to the power of the number of variables.
Six:Output results by displaying the terms for the minterms that weren't joined into higher order groupings, groupings of two cells, groupings of four cells, . . . until all the terms are displayed.
There is one problem that occurs in performing the algorithm as described above. The easiest way to show this is with an example.
The Karnaugh map on the right has four variables and the four minterms should simplify to:
W'XY' + WXZ
These two terms are the circled ones shown on the diagram. However using the algorithm steps above will lead to an extra term: XY'Z, which is shown with the dotted circle. This is because in the first step above, the algorithm obtains all pairings which will include the extra term XY'Z. Most redundant pairs are eliminated if they are included in a higher order group. Notice however this extra term is not a part of a higher order grouping. To eliminate this problem, add one extra step after the fifth operation above. Go through all the pairs temporarily dropping out one pair at a time and check to see if the results of this new expression mark the same cells. If this is so, then the term is redundant and can be removed.
You should notice the unusual ordering of the variables in the rows and columns in the Figure 2 map. This is necessary so that adjacent cells differ in only one variable. With this order of variables, adjacent cells can be paired together because they differ in only one variable.
Algorithm Example:
To make the algorithm clearer, use it to simplify the following function:F(W,X,Y,Z) = W'X'YZ'+W'XY'Z'+W'XY'Z+WXY'Z '+WXY'Z+WX'Y'Z+WX'YZ
The Karnaugh map for this function is shown in Figure 3. The circling shows how terms should be combined to simplify the function. Step one: The algorithm requires the pairing of all possible minterms. This pairing list will be:
W'XY', XY'Z', XY'Z, WXY', WY'Z, WX'Z.
Step two: Remove from the minterm list those cells that have been included in the pairing list. The minterm list after removing all those cells that have been paired is:
W'X'YZ'.
Step three: The algorithm attempts to group the pairs. The pairs list terms, W'XY', XY'Z', XY'Z, WXY', can be combined to give a group of four:
XY'.
Step four: Remove from the pairs list all terms that are included in the groups of four. This leaves the pairs list as:
WY'Z, WX'Z.
Step five: The algorithm requires checking for groups of eight and sixteen. There are none in this example.
Step five and a half: The algorithm generates the results of the simplification so far:
W'X'YZ' + WY'Z + WX'Z + XY'.
It then removes the paired terms one at a time and see if each is necessary to maintain the original function. In this case, the WY'Z is redundant and is removed.
Step six: Display the final answer as:
F(W,X,Y,Z) = W'X'YZ' + WX'Z + XY'.
Implementation:
The representation of a minterm could be accomplished in at least two ways. For example if there are four variables (W, X, Y, Z) the variables can be thought of as holding binary positions 8, 4, 2, 1. A term such as W'XY'Z as shown on the Karnaugh map on the right would have binary value 01012 = 0 + 4 + 0 + 1 = 510 .Notice this is a nice approach because a term that can be combined with it must differ in only one binary place. In the original term a binary position that is zero would become one and a binary poSition that is one would become zero. For this example these adjacent minterms or cells have binary values moving from 8's place to 1's place of
11012 = 1310
00012 = 110
01112 = 710
01002 = 4 10
corresponding to the four adjacent cells.
Another nice feature of this representation is that two cells that are adjacent when XOR-ed together should give only a single position that has a one (i.e., 8, 4, 2, 1 in decimal). For instance the terms W'XY'Z and WXY'Z when XOR-ed would give the following:
01012 = W'XY'Z
XOR 11012 = WXY'Z
------
10002 = 810 => the 8's place variable drops out and the answer becomes => XY'Z
Unfortunately there is a problem with this representation. To be able to display the results of a grouping, it must be possible to determine which variable has been removed. For the example above it would be the W since it has the one after the XOR operation. However how can this new term be represented using the binary notation? A zero in a binary position indicates the variable is primed, not that it is missing from the term. The paired term in the example would be *1012, where the * is the variable that is to be dropped out when the paired term is displayed. Notice that you can not replace the * with a 0 since that would represent W'.
To avoid this, each minterm/cell was represented as a character array. Each position in the array represented a variable. The characters at each position can be a 0', 1' or 2', where the 2' is used to represent a variable that has been dropped out because of pairing of two minterms or groupings. This makes the XOR-ing of terms not as convenient. A function was written to accomplish this instead of being able to use built in bitwise operations. As a part of the data structure for each term, a variable representing whether a term has been paired was included as a separate field in a structure.
For the algorithm, create a list of all minterms in the Boolean function. Place these in a singly linked list or an array of size 2N, where N is the number of variables in the function.
Next obtain all the pairings of the minterms using two nested for loops. Start with the first minterm in the list and try to pair it up with the remaining minterms. Now move to the second minterm and check it against the remaining minterms. Continue this process until all minterm pairings have been considered. As a pairing is obtained, add it to the pairs list. When two terms are paired, the fields of both terms are marked indicating that they are included in the pairing list.
The pairs list is saved as an array or linked list where the maximum number of pairs is (Nm/2)(Nm-1) where Nm is the number of terms in the minterm list. Go through the minterm list and remove all terms that have been paired as indicated by a 1 or true in the field representing whether it was paired.
The next step is to group the pairs (groups of four), again using two nested for loops going through the pairs list. Save this in a list of groups of four. Once this is accomplished go back through the pairs list and remove those pairs that are included in the group of fours.
The next step is to try to group together groups of four to obtain groups of eight. Continue this process until grouping up to the maximum size group 2N is considered, where N is the number of variables.
Go through and mark all minterms using the groups of four, the unpaired terms, and all pairs except the first paired term. See if this marks the same minterms as the original function. If so, remove the first paired term since it is redundant. If not keep this paired term. Repeat this process removing the second paired term and going through the entire paired term list.
Finally go through each of the lists: singles, pair, fours, eights, . . . and display the terms for the simplified function.
Conclusion:
This program has been written in C++ as a DOS program with the boolean function input as a text string. The next step is to rewrite it in Java as an applet. The program will have three methods for input: a list of terms written as a text string as in the C++ program, a truth table and a Karnaugh map. With this on the World Wide Web the program should be available to many students.Bibliography:
[Scot97] Terry A. Scott, "Digital Logic Laboratories for a Computer Organization Course", The Journal of Computing in Small Colleges, Volume 13, Number 2, November 1997.[Mano91] Mano, M. Morris, Digital Design, Second Edition. Chapter 11, Englewood Cliffs, NJ, Prentice-Hall, Inc.
[Mano93] M. Morris Mano, Computer System Architecture, Englewood Cliffs, NJ: Prentice Hall, 1993.
Date Page last modified and links checked: September 13, 1998
© 1996 The University of Northern Colorado - All Rights Reserved.
Contact for information or Technical Questions on this page: tscott@fisher.unco.edu