|
Boolean Minimizer |
The Boolean Equation (or Boolean algebra) software minimizes and generates truth tables for one or a series of Boolean equations and/or truth tables. Operator formats are supported for ABEL, C, C++, PALASM, Verilog, VB and VHDL languages.
Boolean minimization is automated using an Espresso(© UC Berkeley) executable to implement Karnaugh map reduction.
The Input window can have one or more Boolean equations or truth tables. Data can be typed in, pasted, loaded from a file (File/Open or Examples menu), or a file can be dragged-and-dropped onto the Input window. File data must be in standard ASCII text format.
Selection - If one or more Boolean equations (or truth tables) are selected (highlighted), only the selected equation(s) will be processed. Otherwise all equations will be processed.
Minimization - Refer to the Overview (Help menu) for a comparison of Boolean (BEQ) vs. Logic Design Auto/Synthesis (SYN) minimization
Variable name Limits
a. Names - Each Boolean equation or truth table can have from 1-30 variable names
For example: F = x1 and x2 or x3 ... xor x30;
b. Output Option: PLA Truth Table - Available for 1-20 variable names
c. Output Option: Logic Design - Available for 1-10 variable names
File size Limits
Files are limited to 2 GB (2147 MB / 2,147,483,647 bytes). For 27-30 variable names, the Espresso input file (SSolver\bin\Temp\Espr_Inp.txt) may exceed this limit and result in an error.
Espresso execution time
For large Boolean equations or truth tables, Espresso minimization may take minutes, hours, or days.
If you wish to stop the minimization, wait until the Boolean Minimizer Output Data displays "Espresso working..." and an icon is added to the Windows Taskbar for the Espresso task. Then right-click on the Espresso icon and select "Close" or "Close window".
Alternative to Boolean Minimization
- Although the Boolean Minimizer can be extremely useful for many applications, in some cases - especially
when there are large numbers of variables and large Espresso input files - a table-lookup approach may be needed.
- Refer to 8. Appendix 1 - Alternate to Boolean Minimization
1. BOOLEAN EQUATION INPUT FORMAT
Each equation must consist of one variable name followed by an "=" or
":=", and then one or more variable names with Boolean operators.
Each equation must end with a semi-colon ";"
Examples: F = A or (B and C); f := (a || (!b && !c));
1.1 Compact Format
Equations can also be in a compact/terse format. However this format has a number of limitations:
a. Equation must be on one line
b. Names can only be one letter long: a-z A-Z
c. "=" must be used, ":=" is not allowed
d. The Not operator is " ' ", Or operator is "+", And operator is implied
e. Parentheses are not allowed
f. Each equation must end with a period "."
g. Comments ('comment or //comment) are allowed after the period
Examples:
F=A+BC.
// F = A or (B and C);
f = a + b' c'. // f = a or (not b and not c);
2. TRUTH TABLE INPUT FORMAT
Each truth table input must consist of a row of variable names followed
by one or more rows of logic state (1/0/x) values. ('x' may also be
represented by an 'X' or '-' character).
A semicolon (;) must follow the last row of logic states.
Input truth tables can be partial (do not specify all binary combinations) or complete.
Partial Truth Table Example:
a b c Function ' Function of (3) variables
0 0 0 1
0 1 1 0
1 1 0 1 ;
2.1 Multiple-Output Truth Table
Multiple outputs can be specified by adding a colon (:) between the input names and the output name(s).
Example: file Truth-Table-AND-OR-XOR.txt has (3) outputs F G H which are 'and', 'or', 'xor' functions
A B : F G H
0 0 0 0 0
1 0 0 1 1
0 1 0 1 1
1 1 1 1 0;
2.2 Truth Table Fill
A partial truth table such as the one above will be filled in to create
a full truth table before Minimize or Truth Table output operations.
The truth table result for each unspecified row will be set to
'0'. A warning comment at the end of these rows, "unspec",
will mark the rows that were missing in the specification.
The Truth Table output for the above "a b c" truth table is:
a b c Function ' Function of (3) variables
0 0 0 1
0 0 1 0 ' unspec
0 1 0 0 ' unspec
0 1 1 0
1 0 0 0 ' unspec
1 0 1 0 ' unspec
1 1 0 1
1 1 1 0; ' unspec
CAUTION: If the SORT TERMS option is checked, columns in the Output
window may be re-ordered relative to the Input window. When
resolving unspecified or redundant rows, de-selecting the SORT TERMS
option is recommended.
2.3 Don't care (x) Expansion
A truth table with logic state values of x will be expanded replacing each x with a 0 or a 1 to cover all implied combinations.
For example
X Y Z Function
0 x 0 1
expands to two rows:
X Y Z Function
0 0 0 1
0 1 0 1
2.4 Redundant Rows
If a truth table row has no effect on the truth table, that row is
considered to be redundant to a previous row and a warning will be
reported.
d e f Function
0 0 x 1
0 0 1 1
"Input truth table row is redundant with one or more previous rows at Line 3"
It is a good practice to eliminate all redundant rows
2.5 Conflicting Rows
If an initial or expanded truth table row specifies a different truth
table result than a previous row, an error will be reported.
g h j Function
0 0 0 1
0 0 0 0
"Line 2 in the Input truth table conflicts with "000 0" at line 3"
3. BOOLEAN EQUATION OPERATORS
Any of the following symbols can be used as Boolean equation operators:
not / !
and * & &&
or + # | ||
nand
nor
xor $ ^
xnor
Example: X = !(A*B & C) || (D && E);
4. OPERATOR PRECEDENCE
Boolean equation operators are evaluated in the following order:
Not, And, Nand, Or, Nor, Xor, Xnor
That is, all Not operations are evaluated first, then all And operations, etc.
If the same operator is used multiple times, the operators are evaluated from left to right.
Parentheses can be used to explicitly override the order of precedence.
Example:
1. If the equation is: F = A and A or B;
"A and A" is evaluated first and results in "A"
Then "A or B" is evaluated and results in "A or B"
2. If the equation is: F = A and (A or B);
"A or B" is evaluated first and results in "A or B"
Then "A and (A or B)" is evaluated and results in "A"
5. VARIABLE NAMES
Variable names can be up to 32 characters in length.
Up to 20 variables can be used in a Boolean equation or a truth table.
Names consisting only of numbers, such as "0" or "123", are not allowed; this avoids confusion with logic state (1/0) values.
Additional restrictions, which differ for Boolean equations vs. truth tables, are listed below.
5.1 Boolean Equation Names
Boolean Equation variable names cannot include operator symbols.
The following characters cannot be used in a variable name: space tab * + & | = # $ ^ / ! ; or character(s) beginning a comment: // -- ' # .
Parentheses and colon characters ( ) : have restricted usage in
variable names, but can be used as shown in the following example:
F(7:0) = A(15:8) + B(7:4)(3:0);
Parentheses must be matched and cannot be nested. For Boolean
Equation names colon ":" characters must be enclosed by parentheses.
5.2 Compact Boolean Equation Names
Compact Boolean Equation names can only be one character long and can only be a lower-case or upper-case letter: a-z A-Z
5.3 Truth Table Names
Truth tables variable names cannot include space, tab, semi-colon ";" or
character(s) beginning a comment: // -- ' # .
The colon ":" character can be used as part of a Truth table name but not a name by itself since " : " is reserved as a separator between input and output variable names - see Section 2.1 Multiple-Output Truth Table.
In addition Truth tables variable names cannot be a Boolean equation operator listed in Section 3
There are no other restrictions. However, for compatibility with Boolean equation names and the Logic Design tool, the rules of Section 5.1 are recommended.
6. CASE SENSITIVITY
Operator Format 0-2 : Not case sensitive
Operator Format 3 (C/C++/Verilog) : Variable names are case sensitive; Input operators (and/OR/nOt) are not.
7. COMMENTS
Boolean equation and Truth table comments begin with " ' " or "//" and extend to the end of the line.
Boolean equation comments may also begin with "--".
However truth table comments may not begin with "--" since the "-"
character is equivalent to an "x" (don't care) state, and truth table
sequences such as "--" or "---" may occur.
Truth table comments may also begin with "#".
However Boolean equation comments may not begin with "#" since the "#" character is a Boolean equation 'or' operator.
Hyperlinks
Hyperlinks can be included in a commented line. They will be colored blue and underlined, and can be opened with a single-click.
The following table illustrates the syntax for different hyperlink targets:
|
| Target | Hyperlink Example |
|
| File | <file:C:\Doc\Actuarial Life tables.npd> |
|
| Folder | <file:C:\Doc> |
|
| Shortcut (to Help_PE) | <file:C:\Users\Dave\Desktop\Help_PE.lnk> |
|
| NETWORK File | \\DAVE-PC\Doc\AREACODE.TXT |
|
| NETWORK Folder | \\DAVE-PC\Doc |
|
| Internet | https://www.simplesolverlogic.com/ |
| Search |
The Search box can be used to highlight signal names, numbers or text in the Output window. To search, enter the text to be found and then press the Enter key. This will highlight up to 100 instances of the Search text.
To clear all highlighting, delete all text in the Search box and press Enter.
8. OUTPUT OPTIONS
Output data and formats can be selected by the following options:
Comment Lines - Comment lines in the Input window are shown in the Output window.
Input Eqn/TT - Boolean equations or Truth Tables in the Input window are shown in the Output window.
Truth Table-Full
A complete truth table is generated for each Boolean Equation or Truth Table input.
If the number of variables is <= 10, the truth table values are aligned with their respective names.
If the number of variables is > 10, there are no spaces between
truth table 0/1 characters in order to save memory space and display time.
If the number of variables is > 20, only the output state is shown
in order to save memory/disk space.
An Input truth table with logic state values of "x" (don't care) will be expanded, replacing each x with a 0 or a 1 in all implied truth-table lines.
CAUTION: The size of the full truth table doubles with each added variable. For 21-30 variables, Truth Table-Full results are saved to one or more files on hard disk. For 30 variables the result requires 30 100-MB files.
Minimize - Each Input Equation or Truth Table is minimized
Invert & Minimize - Each Input Equation or Truth Table is inverted and then minimized
Align Minterms - Each Boolean equation minterm is printed on a separate row
PLA Truth Table - 1-20 variables
Show minimized Espresso truth table in PLA (Programmable Logic
Array) format for each Boolean Equation input or Truth
Table input. If Invert & Minimize is checked, the PLA table
will be the minimized INVERTED Input Equation or Truth Table. The
PLA format is much more compact than the Truth
Table-full format; the PLA format has no spaces between 01-
characters and it only shows truth table states in which the output is
a logic 1.
Logic Design - 1-10 variables
A truth table is generated for each Boolean
Equation input or Truth Table input in a format compatible with the
Logic Design (SYN) tool.
This truth table can be exported by copy/paste - Copy (Ctrl C) from the Boolean Output window and Paste (Ctrl V) to the Logic Design Input window - or by saving the Boolean Output to a file and then opening the file at SYN.
SYN can then:
- Reformat the Boolean truth table as a waveform or timing diagram (SYN Timing Only option)
- Minimize the Boolean equation using any mix of part types (and, or, inv, nand, nor, xor, xnor)
- Generate one or more corresponding logic circuits
CAUTION: Except for very simple Boolean expressions, SYN is much slower
than BEQ since the SYN search time increases exponentially with the
number of variables and the number of parts.
SYN has been optimized for its default and-or PARTS; other gate types,
such as nand, generally take much more time to find solutions.
For example, file "4 Variable XOR.txt" which solves in 0.03 seconds with BEQ and 33 seconds with SYN and4-or8 parts, will require SYN many hours to find a solution using nand parts. (However, since this is a special case of an XOR function, SYN is even faster than BEQ using xor/xnor parts).
Sort Terms - Variable names and Boolean equation minterms are sorted in alphabetical order
Operator Format - Numbers 0-3 select the format of Boolean NOT AND OR operators shown in the Output window:
| Number | NOT | AND | OR | Language |
| 0 | not | and | or | VHDL VB |
| 1 | / | * | + | PALASM |
| 2 | ! | & | # | ABEL |
| 3 | ! | && | || | C C++ Verilog |
9. APPENDIX 1 - Alternative to Boolean Minimization
Although the Boolean Minimizer can be extremely useful for many applications, in some cases - especially when there are large numbers of variables and large Espresso input files - a table-lookup approach may be needed.
Example: 20-variable Truth Table
A full 20-variable Truth Table has 1,048,576 lines, or can be an array of output states from
0-1048575.
A text file with one output (shown as a 0 except for the last line), and with no spaces between 1's and 0's needs 24,117,246 bytes including newlines.
000000000000000000000
000000000000000000010
000000000000000000100
...
111111111111111111010
111111111111111111100
111111111111111111111
A byte array needs only 1,048,576 bytes (one byte per line). Only the output state (1 or 0) is needed since the input-variable pattern (converted from binary to decimal) is the index to the array. Note also that since there are 8 bits to a byte, up to 8 outputs could be encoded in a byte array, which would provide further savings.
The byte array approach could be applied to 30+ variable arrays as long as the 2-GB file limit is not exceeded.