(Logic Minimization)

Check a 64 bits input file and its resulting output file...

A simple 5 input/5 output example is available to show the different ways of using the

*bfunc*for MSDOS: bfunc.zip - Boolean functions simplification (logic minimization) programs using Quine-McCluskey and BDD methods. This ZIP archive contains 32 bit executables that run on Linux or MS-Windows systems. It also includes input files, table generators, some documentation, etc.*espresso*for MSDOS: espres23.zip - a MSDOS version of the well known logic minimization program (version 2.3).- "How Stuff Works" about boolean logic (nice introductory stuff)
- Quine-McCluskey algorithm (in Wikipedia.org)
- Logic design
- KVD Demo (nice Java applet about
*Karnaugh Maps*) Quine McCluskey minimization - Information - Information about
*bfunc*parameters and constants

It can be considered an alternative to the Karnaugh Map method of simplifying boolean functions, etc.

This software package was originally written in Pascal (1986), but after
translated to C using the `p2c` program (1989). This development started in my
last year in the Engineering Faculty of Porto and was continued at INESC-Porto.

The code is available to everybody. Please send a message to
António Costa if interested...

Available implementations are:

**Global**- Boolean Simplification of all the output functions simultaneously (multi-level), using the Quine-McCluskey method, and generation of:- Truth Table (optional);
- Symbolic Equations (optional);
- General Statistics (optional).

**Local**- Boolean Simplification of each output function (two-level), independently of the others, using the Quine-McCluskey method, and generation of:- Truth Table (optional);
- Symbolic Equations (optional);
- General Statistics (optional).

- Boolean Simplification of each output function, using the Binary Decision Diagram method (two-level), and generation of:*Quasi-optimal*Local- Binary Decision Tree (optional);
- Symbolic Equations (optional);
- General Statistics and Tree Evaluation Statistics (optional).

7 Segment Decoder 18-MAY-1988 ############# Inputs ############ B3 HIGH Code MSBit B2 HIGH Code 2nd MSBit B1 HIGH Code 3rd MSBit B0 HIGH Code LSBit ############ Outputs ############ A HIGH 0 Segment 1 B HIGH 0 Segment 2 C HIGH 0 Segment 3 D HIGH 0 Segment 4 E HIGH 0 Segment 5 F HIGH 0 Segment 6 G HIGH 0 Segment 7 ############ Options ############ Read Mode =0 Table/Tree=0 Equations =3 Statistics=0 ########## Truth table ########## 0000 1111110 '0' 0001 0110000 '1' 0010 1101101 '2' 0011 1111001 '3' 0100 0110011 '4' 0101 1011011 '5' 0110 1011111 '6' 0111 1110000 '7' 1000 1111111 '8' 1001 1111011 '9' 1010 1110111 'A' 1011 0011111 'b' 1100 1001110 'C' 1101 0111101 'd' 1110 1001111 'E' 1111 1000111 'F'This input file defines all data for a 7 Segment Decoder. Things to notice:

- there are 4 input signals, all active high (binary code);
- there are 7 output signals, all active high (one for each segment);
- we want the NOT SUM OF PRODUCTS form of equations, for all outputs;
- we only want the equations;
- we describe how the inputs affect the outputs through the truth table, with 1 term per line (in this example, each term is equal to a minterm).

##### Boolean Functions Total Terms : 15 Total Prime Imps : 22 1st reduced Prime Imps: 14 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 1 <Redundant> Prime Imps: 0 <Essential> Prime Imps: 15 ##### Boolean Equations TERM_1=/B2*/B1*B0 TERM_2=/B3*B1*B0 2 Term Common Expressions PRIME_1=/B3*B2*/B1*/B0 PRIME_2=TERM_1*/B3 PRIME_3=B3*B2*/B1*/B0 PRIME_4=B3*/B2*B1*B0 PRIME_5=B3*B2*/B1*B0 PRIME_6=B3*B2*B1 PRIME_7=/B3*B2*/B1*B0 PRIME_8=/B3*/B2*B1*/B0 PRIME_9=TERM_2 9 Prime Imps Common Expressions /A=PRIME_1 +PRIME_2 +PRIME_4 +PRIME_5 /B=PRIME_3 +PRIME_4 +PRIME_6 +PRIME_7 +B2*B1*/B0 /C=PRIME_3 +PRIME_6 +PRIME_8 /D=PRIME_1 +PRIME_2 +B2*B1*B0 +B3*/B2*B1*/B0 /E=PRIME_1 +PRIME_7 +PRIME_9 +TERM_1 /F=PRIME_2 +PRIME_5 +PRIME_8 +PRIME_9 /G=PRIME_3 +/B3*/B2*/B1 +TERM_2*B2

##### Boolean Functions Total Terms: 15 ##### Function A Total Local Terms : 4 Total Prime Imps : 4 1st reduced Prime Imps: 4 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 4 ##### Boolean Equation /A=B3*/B2*B1*B0 +B3*B2*/B1*B0 +/B3*/B2*/B1*B0 +/B3*B2*/B1*/B0 ##### Function B Total Local Terms : 6 Total Prime Imps : 5 1st reduced Prime Imps: 4 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 4 ##### Boolean Equation /B=B3*B1*B0 +B2*B1*/B0 +B3*B2*/B0 +/B3*B2*/B1*B0 ##### Function C Total Local Terms : 4 Total Prime Imps : 3 1st reduced Prime Imps: 3 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 3 ##### Boolean Equation /C=B3*B2*B1 +B3*B2*/B0 +/B3*/B2*B1*/B0 ##### Function D Total Local Terms : 5 Total Prime Imps : 4 1st reduced Prime Imps: 4 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 4 ##### Boolean Equation /D=B2*B1*B0 +B3*/B2*B1*/B0 +/B3*/B2*/B1*B0 +/B3*B2*/B1*/B0 ##### Function E Total Local Terms : 6 Total Prime Imps : 3 1st reduced Prime Imps: 3 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 3 ##### Boolean Equation /E=/B3*B0 +/B2*/B1*B0 +/B3*B2*/B1 ##### Function F Total Local Terms : 5 Total Prime Imps : 4 1st reduced Prime Imps: 4 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 4 ##### Boolean Equation /F=/B3*B1*B0 +/B3*/B2*B0 +/B3*/B2*B1 +B3*B2*/B1*B0 ##### Function G Total Local Terms : 4 Total Prime Imps : 3 1st reduced Prime Imps: 3 2nd reduced Prime Imps: 0 3rd reduced Prime Imps: 0 <Essential> Prime Imps: 3 ##### Boolean Equation /G=/B3*/B2*/B1 +/B3*B2*B1*B0 +B3*B2*/B1*/B0There is also a small amount of information about the simplification, but the equations are slightly different from each method, because in GLOBAL mode, the program searches for partial logical products (first) and global logical products (after), and then shares them between the output functions (this is the multi-level phase).

A third possibility is to generate a Binary Decision Tree, which is converted to standard Sum of Products (this conversion step also reduces the number of literals, and, in some special cases, the number of logical products). Please note that the equation's set obtained may be, sometimes, not as fully optimized as if generated in LOCAL mode. Although, these particular cases are very rare and tend to disappear if the number of input variables grows (more than 7).

##### Boolean Functions Total Minterms: 15 ##### Function A Tree Compression: 0.0 % Tree Density : 89.47 % Tree Depth : 5 Total Nodes : 11 Total Leaves : 4 ##### Boolean Equation /A=/B3*/B2*/B1*B0 +/B3*B2*/B1*/B0 +B3*/B2*B1*B0 +B3*B2*/B1*B0 Total Prime Imps: 4 ##### Function B Tree Compression: 17.2 % Tree Density : 87.18 % Tree Depth : 5 Total Nodes : 10 Total Leaves : 5 ##### Boolean Equation /B=/B3*B2*/B1*B0 +B2*B1*/B0 +B3*B1*B0 +B3*B2*/B0 +B3*B2*B1 Total Prime Imps: 5 ##### Function C Tree Compression: 25.81 % Tree Density : 82.61 % Tree Depth : 5 Total Nodes : 7 Total Leaves : 3 ##### Boolean Equation /C=/B3*/B2*B1*/B0 +B3*B2*/B0 +B3*B2*B1 Total Prime Imps: 3 ##### Function D Tree Compression: 19.5 % Tree Density : 91.18 % Tree Depth : 5 Total Nodes : 10 Total Leaves : 4 ##### Boolean Equation /D=/B2*/B1*B0*/B3 +/B2*B1*/B0*B3 +B2*/B1*/B0*/B3 +B2*B1*B0 Total Prime Imps: 4 ##### Function E Tree Compression: 50.0 % Tree Density : 86.36 % Tree Depth : 5 Total Nodes : 7 Total Leaves : 3 ##### Boolean Equation /E=/B3*B2*/B1 +/B3*B0 +B0*/B2*/B1 Total Prime Imps: 3 ##### Function F Tree Compression: 20.0 % Tree Density : 87.50 % Tree Depth : 5 Total Nodes : 9 Total Leaves : 4 ##### Boolean Equation /F=/B3*/B2*B0 +/B3*/B2*B1 +/B3*B1*B0 +B3*B2*/B1*B0 Total Prime Imps: 4 ##### Function G Tree Compression: 24.24 % Tree Density : 88.0 % Tree Depth : 5 Total Nodes : 8 Total Leaves : 3 ##### Boolean Equation /G=/B3*/B2*/B1 +/B3*B2*B1*B0 +B3*B2*/B1*/B0 Total Prime Imps: 3

xyz + x~yz = x(y + ~y)z = x(TRUE)z = xz

Thus the two minterms can be simplified to one term with one fewer character. The Quine-McCluskey method gives us a systematic way of selecting the pairs that we use for this simplification.

We illustrate the Method with an example. Suppose we are given the
logical expression

xyz + ~x~yz + x~yz + ~x~y~z + ~xyz

to simplify. We convert each minterm to its bit string form and arrange them in a table ordered according to the number of 1's that appear in the bit string. The minterm with the largest number of 1's in its bit string appears first and the rest appear in order of decreasing numbers of 1's in the bit strings.

No. Minterm Bit String Number of 1's 1 xyz 111 3 2 x~yz 101 2 3 ~xyz 011 2 4 ~x~yz 001 1 5 ~x~y~z 000 0

#'s Used| Term | Bit String | # of 1's | --------|--------|------------|----------| 1 | xyz | 111 | 3 | 2 | x~yz | 101 | 2 | 3 | ~xyz | 011 | 2 | 4 | ~x~yz | 001 | 1 | 5 | ~x~y~z | 000 | 0 | --------|--------|------------|----------| 1,2 | xz | 1-1 | 2 | 1,3 | yz | -11 | 2 | 2,4 | ~yz | -01 | 1 | 3,4 | ~xz | 0-1 | 1 | 4,5 | ~x~y | 00- | 0 | ------------------------------------------The new terms all contain two literals. We next apply the same procedure to eliminate those terms that have bit strings differing in one bit. Looking at the list of bit strings in the last column, we see that the strings in rows marked 1,2 and 3,4 differ in one bit, and the strings in rows marked 1,3 and 2,4 differ by one bit. Using rows marked 1,2 and 3,4, we get a new row for which the bit string is --1, the corresponding term is z, and we now used 1,2,3,4 (having combined 1,2 and 3,4). Thus we have the new entry

REDUCTION TABLE #'s Used |Term | Bit String | # of 1's | ---------|--------|------------|----------| 1 | xyz | 111 | 3 | 2 | x~yz | 101 | 2 | 3 | ~xyz | 011 | 2 | 4 | ~x~yz | 001 | 1 | 5 | ~x~y~z | 000 | 0 | ---------|--------|------------|----------| 1,2 | xz | 1-1 | 2 | 1,3 | yz | -11 | 2 | 2,4 | ~yz | -01 | 1 | 3,4 | ~xz | 0-1 | 1 | 4,5 | ~x~y | 00- | 0 | ---------|--------|------------|----------| 1,2,3,4 | z | --1 | 1 | -------------------------------------------Combining rows marked 1,3 and 2,4 uses the same terms, and gives the same term, z, so we do not write it in our table. In general, if we have reached the point where the terms contain N literals, we combine those terms, where possible, to obtain terms containing N-1 literals. This continues until no more eliminations can be made. We have finished the reduction step.

|(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z | --------------------------------------------------------------We look at the Reduction Table and take the term with the fewest number of literals (in the last row). In our case, that is z. We see that minterms 1,2,3,4 were used to obtain it. The term z is now the label for the first row of the new table. We also put an asterisk under each minterm that was used.

|(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z | -------------------------------------------------------------- z | * | * | * | * | |We then go up the Term column of the Reduction Table from the term we have already selected to get to the first row that contains the number of a term that is missing from the list so far obtained. Notice that 5 was missing and this occurs in the row marked 4,5. Thus we write the term ~x~y as the next row label and put asterisks in the columns for minterms 4 and 5.

SELECTION TABLE |(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z | -------------------------------------------------------------- z | * | * | * | * | | ~x~y | | | | * | * | --------------------------------------------------------------We continue this process until we have asterisks in all columns or until we have no more terms in the Term column of the reduction table. We now form the expression obtained by taking the disjunction of all terms that appear as row labels in the Selection Table. Thus our simplified expression is

z + ~x~y

This method works for expressions with any number of literals.

Here is another example using four literals. Simplify

wxyz + wx~yz + wx~y~z + w~xy~z + w~x~y~z

REDUCTION TABLE #'s Used |Term | Bit String | # of 1's | ----------|-----------|------------|----------| 1 |wxyz | 1111 | 4 | 2 |wx~yz | 1101 | 3 | 3 |wx~y~z | 1100 | 2 | 4 |w~xy~z | 1010 | 2 | 5 |w~x~y~z | 1000 | 1 | ----------|-----------|------------|----------| 1,2 | wxz | 11-1 | 3 | 2,3 | wx~y | 110- | 2 | 3,5 | w~y~z | 1-00 | 1 | 4,5 | w~x~z | 10-0 | 1 | ----------------------------------------------- SELECTION TABLE |(1)wxyz |(2) wx~yz |(3) wx~y~z |(4) w~xy~z |(5) w~x~y~z | ------------------------------------------------------------------- w~x~z | | | | * | * | wx~y | | * | * | | | wxz | * | * | | | | -------------------------------------------------------------------w~y~z + wx~y + wxy

This is one possible answer, but we could just as well have chosen w~y~z instead of wx~y, to get the Selection Table

SELECTION TABLE |(1)wxyz |(2) wx~yz |(3) wx~y~z |(4) w~xy~z |(5) w~x~y~z | ------------------------------------------------------------------- w~x~z | | | | * | * | w~y~z | | | * | | * | wxz | * | * | | | | -------------------------------------------------------------------w~x~z + w~y~z + wxz

Thus there are several correct simplifications that are minimal.

Here is the last example.

xyz + x~yz + ~x~y~z

REDUCTION TABLE #'s Used | Term | Bit String | # of 1's | -----------|---------|------------|----------| 1 | xyz | 111 | 3 | 2 | x~yz | 101 | 2 | 3 | ~x~y~z | 000 | 0 | -----------|---------|------------|----------| 1,2 | xz | 1-1 | 2 | SELECTION TABLE |(1) xyz |(2) x~yz |(3) ~x~y~z | ----------------------------------------- xz | * | * | | ~x~y~z | | | * | -----------------------------------------xz + ~x~y~z

Last update: 7-7-2009

António Costa