\n"); } else { header("Content-type: text/html; charset=utf-8"); } ?> Minimizing Boolean Functions

Minimizing Boolean Functions

Introduction

This document describes graphical and algebraic ways to minimize boolean functions. It includes a Java program that you can use to experiment with the algebraic algorithm outlined below. The subject of minimization is also covered in many textbooks, articles, and other web sites. Here are a few references:

Some Minimization Resources
  1. Interactive Karnaugh Map from the Technische Universität Ilmenau (Germany). The applet web page linked to from here is part of a large set of tutorial pages on logic design written in German, including several other excellent Java applets in addition to this one. Most of the applets have an option for interacting with the user in English, but the text material on the web site is all in German.
  2. Karnaugh, M. "The Map Method for Synthesis of Combinational Logic Circuits", Trans. AIEE, pt. I, vol. 72, no. 9, pp. 593-599, 1953. As cited in the Kohavi and McCluskey books listed below.
  3. Kohavi, Z. Switching and Finite Automata Theory, New York: McGraw-Hill, 1970.
  4. McCluskey, E. J., Introduction to the Theory of Switching Circuits, New York: McGraw-Hill, 1965

Why Minimize?

All the datapath and control structures of a digital device can be represented as boolean functions, which take the general form:

y = Σ(x, … )

where “(x, … )” is a set of boolean variables (variables that may take on only the values zero and one). These boolean functions must be converted into logic networks in the most economical way possible. What qualifies as the “most economical way possible” varies, depending on whether the network is built using discrete gates, a programmable logic device with a fixed complement of gates available, or a fully-customized integrated circuit. But in all cases, minimization yields a network with as small a number of gates as possible, and with each gate as simple as possible.

To appreciate the importance of minimization, consider the two networks in Figures 1 and 2. Both behave exactly the same way! No matter what pattern of ones and zeros you put into a, b, and c in Fig. 1, the value it produces at y will be exactly matched if you put the same pattern of values into the corresponding inputs in Fig. 2. Yet the network in Fig. 2 uses far fewer gates, and the gates it uses are simpler (have smaller fan-ins) than the gates in Fig. 1. Clearly, the minimized circuit should be less expensive to build than the unminimized version. Although it is not true for Fig. 2, it is often the case that minimized networks will be faster (have fewer propagation delays) than unminimized networks.

Full sum of products logic network

Figure 1

Minimized logic network for the function implemented in Figure 1.

Figure 2

Background and Terminology

Karnaugh Maps

A Karnaugh Map is a graphical way of minimizing a boolean expression based on the rule of complementation. It works well if there are 2, 3, or 4 variables, but gets messy or impossible to use for expressions with more variables than that.

The idea behind a Karnaugh Map (Karnaugh, 1953) is to draw an expression’s truth table as a matrix in such a way that each row and each column of the matrix puts minterms that differ in the value of a single variable adjacent to each other. Then, by grouping adjacent cells of the matrix, you can identify product terms that eliminate all complemented literals, resulting in a minimized version of the expression.

Figure 3 shows how the minterms in truth tables are placed in a Karnaugh Map grid for both 3 and 4 variable expressions.

line drawing

Figure 3

Looking at the 3 variable map on the left in Fig. 3, note that minterm 0 (0002) is just above minterm 4 (1002). This arrangement means that if both minterms 0 and 4 occur in a function, the first variable (the one named a in Fig. 3) appears in both its true and complemented form, and can be eliminated. The top row of the Karnaugh Map is labeled with a' and the lower row with a: Any minterms appearing in the top row have the literal a' in them, and any minterms in the bottom row have the literal a in them. At the same time, note that each column has the same values for the variables b and c. Also, the columns are arranged in an order so that only one variable changes value as you go from one column to the next. Thus, the first two columns differ in the value of c, the second and third columns differ in the value of b, and the third and fourth columns differ in the value of c again. Furthermore, the first and fourth columns are “next to” each other as well, because they differ from each other just in the value of b.

The right side of Figure 3 shows that this same pattern (adjacent columns differ by the value of a single variable) applies to the rows of a Karnaugh map too: The first and second rows of that map differ in the value of b, the second and third differ in the value of a, the third and fourth differ in the value of b, and the first and fourth differ in the value of a.

Figure 4 shows our sample function drawn as a Karnaugh Map. Minterms 1 and 2 are in the second and fourth columns of the top row, while minterms 4, 5, 7, and 6 appear from left to right in the four columns of the bottom row.

Truth table and Karnaugh Map

Figure 4

A Karnaugh Map is used to produce a minimal sum of products implementation of an expression by drawing rectangles around groups of adjacent minterms in the map; each rectangle will correspond to one product term, and the full expression will be constructed as the OR (sum) of all the product terms. The goal is to have as few product terms as possible, which implies that each product term will account for as many minterms as possible.

Here are the rules for drawing the rectangles:

Figure 5 shows the rectangles for our sample function, following the procedure outlined above:

Karnaugh Map for sample function

Figure 5

The largest rectangle (the bottom row) corresponds to the product term a. By enclosing four minterms, two variables have been eliminated resulting in a single product term with a single variable. The rectangle in the second column encloses two minterms, eliminating one variable (a) from that product term. Similarly, the rectangle in the fourth column eliminates a from that product term. The resulting sum of products function is:

y = a + b'c + bc'

If you examine Fig. 2, you will see that that logic network implements exactly this function.

Every time you double the number of minterms inside a rectangle, you eliminate one variable from the resulting product term. Every doubling corresponds to applying the rule of complementation again. The next section shows how to do the same thing algebraically.

The Interactive Karnaugh Map mentioned at the beginning of this page is a very nice way to see how to draw the rectangles. You can enter the function you want to process algebraically, by editing a truth table, or just by clicking on cells in the Karnaugh Map itself. Figure 6 is a screen shot of the applet showing how it displays our sample function:

Karnaugh Map applet screen shot

Figure 6

Algebraic Minimization

Minimizing an expression algebraically involves repeatedly applying the rule of complementation, starting with the disjunctive normal form of the function, and ending with a set of product terms called prime implicants. A prime implicant is a product term that will generate ones only for combinations of inputs that are minterms of the disjunctive normal form of the function, and which cannot be further reduced by combining with any other term. They correspond to the rectangles in a Karnaugh Map.

We will call each step in this process a “pass.” It takes two passes to minimize our sample function. The following chart shows the original disjunctive normal form of the function as “Pass 0” and shows what reductions are performed for the other two passes.

--------------------------------------------------------------- | Pass 0: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc | --------------------------------------------------------------- --------------------------------------------------------------- | Pass 1: a'b'c + ab'c reduces to b'c | | a'bc' + abc' reduces to bc' | | ab'c + ab'c' reduces to ab' | | abc' + abc reduces to ab | --------------------------------------------------------------- | b'c + bc' + ab' + ab | --------------------------------------------------------------- --------------------------------------------------------------- | Pass 2: ab' + ab reduces to a | --------------------------------------------------------------- | a + b'c + bc' | ---------------------------------------------------------------

The rules to follow for each pass are:

The rule about reusing terms in a pass corresponds to circling some minterms more than once in a Karnaugh Map. The two minterms that are reused in Pass 1 above are exactly the same two that are circled twice in the Karnaugh Map of Figure 5.

Once the prime implicants of an expression have been determined, a minimal subset of them has to be selected. Picking a minimal subset of prime implicants relies on the notion of minterms being “covered” by prime implicants. For our sample function, the prime implicant a covers minterms 4, 5, 6, and 7; the prime implicant b'c covers minterms 1 and 5, and and the prime implicant bc' covers minterms 2 and 6. In this example, we need all three prime implicants in order to cover all the minterms at least once, and the expression shown at the end of Pass 2 is the minimized form for our sample function.

But whenever there is more than one minimal form for an expression, the different forms will correspond to different subsets of the complete set of prime implicants. For any one of the minimal forms there will be extra prime implicants that have to be discarded.

The following procedure describes a way to determine one minimal form of an expression after all the prime implicants have been determined.

Disclaimer! The algorithm given here is based on the Quine-McClusky “chart” method described in (McClusky, 1965) and in (Kohavi, 1970). But it is not exactly the same as the procedure given in those references, and may not produce the same results. It should, however, produce a fully minimized function.

Minimization Program

There are two version of the minimization program available. The first was developed in 2000. It must be invoked from a command prompt such as a Windows "DOS Window" or a L/Unix shell prompt. The second version was developed in 2005, and can still be run from a command prompt, but also can be run with a graphical user interface. Both versions require a Java runtime environment (JRE), available from Sun Microsystems' Java web site. The first version of the program will work with JRE version 1.3 or later, and probably works with some older JRE's as well. The second version definitely needs JRE version 1.5 or later.

Download either version of the program:

The program allows you to enter either a boolean expression or a list of minterm numbers, and displays a series of messages that show the steps it followed to perform the minimization. Some expressions can be minimized more than one way, but the program shows just one minimization even if others are possible.

Running the Program

Current Version

If you are running Windows and have the proper JRE installed, you can run the program by double-clicking on it’s icon.

You may enter either a boolean expression or a list of minterm numbers in the entry field in the upper left corner of the window, and the minimized version of the expression will appear immediately below it. Do not use quotes for either type of input. Use single-letter variable names (case sensitive), * or nothing for AND, + for OR, ^ for XOR, and ' for postfix NOT. You may also use the boolean constants 0 and 1, and you may use parentheses to control evaluation order. When entering minterm numbers instead of an expression, use either spaces or commas to separate the numbers.

When you enter an expression or minterm list, the minimized result of the algorithm appears immediately below the entry field. This string is automatically copied to the system clipboard and can be pasted into another application if desired. (There is no visual indication that the result string has been selected, but it can be pasted.)

The Minterm Table immediately below the minimized result shows the minterms for the sum of products form of the expression you entered. The left column shows the product terms as truth table row numbers, and the right column shows the product terms algebraically. The Prime Implicant Table below that shows each minimized product term in the first column, and a list of the full product terms that each minimized term “covers” (implies) in the second column.

The right side of the window shows the processing steps the program went through to do the minimization. (Or an error message if you entered an invalid expression.) This is the information that is written to the console when you run either version of the program from the command line.

Use the “New Window” button if you want to have multiple minimizations visible at the same time. The size, shape, and interior divisions of the last window you exit will be reused if you run the program again.

You can also launch the graphical interface from the command line using the command, java -jar Minimize.jar. If you want to run the command line version, the command is:

java -cp Minimize.jar MinimizedTable <expression or minterm list>
.

See the description of the older program version below for the syntax of <expression or minterm list>.

Previous Version

Open a command line window on your computer, and change to the directory where you downloaded Minimize.zip. The command to run the program is:

java -cp Minimize.zip Minimize <expression or minterm list>

The boolean expression you enter on the command line must use the following syntax:

Alternatively, you may write a list of minterm numbers on the command line. There must be spaces but no commas between numbers. The largest minterm number you supply will determine the number of variables in the expression and the number of rows in the resulting truth table. For example:

java -cp Minimize.zip Minimize 4 6

There have to be three variables and 8 rows in the truth table to include these two minterms. The variables will automatically be named a, b, and c.

Sample Output (First Version of the Program)

$ java -cp Minimize.zip Minimize "a+b^c" Finding One Minimization Minterm Numbers: [1,2,4,5,6,7] Reduced ab'c and a'b'c to b'c in pass 1. Reduced abc' and a'bc' to bc' in pass 1. Reduced ab'c and ab'c' to ab' in pass 1. Reduced abc' and ab'c' to ac' in pass 1. Reduced abc and ab'c to ac in pass 1. Reduced abc and abc' to ab in pass 1. Unable to reduce b'c in pass 2 Unable to reduce bc' in pass 2 Reduced ab and ab' to a in pass 2. Unable to reduce b'c in pass 3 Unable to reduce bc' in pass 3 Unable to reduce a in pass 3 Minterm 1 is covered by 1 prime implicant. Minterm 2 is covered by 1 prime implicant. Minterm 4 is covered by 1 prime implicant. Minterm 5 is covered by 2 prime implicants. Minterm 6 is covered by 2 prime implicants. Minterm 7 is covered by 1 prime implicant. Expression: a+b^c Sum of products: a'b'c + a'bc' + ab'c' + ab'c + abc' + abc Prime implicants: [ a: ab'c', ab'c, abc', abc ], [ b'c: a'b'c, ab'c ], [ bc': a'bc', abc' ] Minimized: b'c + bc' + a $ java -cp Minimize.zip Minimize "aa'+b1" Finding One Minimization Minterm Numbers: [1,3] Reduced ab and a'b to b in pass 1. Unable to reduce b in pass 2 Minterm 1 is covered by 1 prime implicant. Minterm 3 is covered by 1 prime implicant. Expression: a*a'+b*1 Sum of products: a'b + ab Prime implicants: [ b: a'b, ab ] Minimized: b $