JQM - Java Quine McCluskey Copyright (C) <2016-2022> Luis Paulo Laus, laus@utfpr.edu.br
This is another implementation of the Quine McCluskey algorithm. Also, Petrick's Method is used to select the best (minimum) solution when there are many. The motivations for writing this program were: even though there are many other implementations around, none fulfil my requirements. So, you must be asking yourself what the requirements are? Well, first I need several output variables (functions). Second, I need an easy to use interface that allows for a variable name change, column rearrangement, and saving and reloading of the truth table. Column rearrangement is very important when inputting data and it can save you a lot of time if used wisely. Third, I need to present the results in several formats including ladder diagrams (LD) which are used in PLC programming and are very uncommon in this kind of software. Also, I need the equations and drawings formatted in LaTeX so I can use them in my documents, usually presentations. This includes of course the ladder diagram (LD). Fourth, I need to control the minimization criterion for research purposes. Fifth, I need both result formats: disjunctive normal form (sum of products, or OR of ANDs) and conjunctive normal form (product of sums, or AND of ORs).
Other reasons include: some implementations produce the wrong output, mainly regarding the concept of minimal solution; frequently, there is no way of saving the truth table for future or continued work. Note that sometimes those truth tables are very big, re-entering them every time you change your mind or detect a mistake is a drag.
For input, this implementation uses a CSV (Comma-separated values) file format so one can edit or create the truth table using other software like a spreadsheet or Computer-Aided Engineering (CAE). The results can be exported in HTML (HyperText Markup Language), then opened in a browser, edited, or converted into other formats, and LaTeX for high-quality typesetting.
How to use it
The software design aims for usability, but you must follow some steps:
1- Start a new truth table and adjust the number of input and output variables (function).
2- Fill in the truth table according to the logic function you need to perform. You can change the variable names by double-clicking on them. You can change the position of the input and output variables by dragging and dropping one of them. This is very useful when one variable takes precedence over the others: you can place it on the left-most side (most significant bit) and, after filling in the output accordingly, you can place it back. Note that when you change the input variable order, the output changes to preserve the overall function defined by the truth table so far.
3- Save your truth table. Though it is not mandatory, it is highly recommended. The interface and the solver run as separated threads, so you will be able to save after starting the minimization process even if something goes wrong… probably.
4- Select the output (result) format and other options.
5- Click on MINIMIZE and wait patiently.
6- Export the result, or select other options and clique on MINIMIZE again. Note that any change you made will only affect the result after you click on MINIMIZE.
Result (output) format
Boolean expressions: a list of expressions in standard notation. Complemented variables are shown with a straight line over them. Underscore in variable names, e.g., "x_2", indicates index. Therefore, only the part of the variable name before the first underscore receives a straight line over it when the respective variable is complemented. Refrain from mixing high and low letters in a variable name, e.g., "xt", because, if this variable is complemented, the straight line will be broken given the impression that it is the AND of two different and complemented variables. The essential prime implicants are shown first and in blue, then non-essential prime implicants in green. Note that, inside the essential and non-essential prime implicants list, the implicants are sorted according to a criterion explained next.
Boolean expressions (sorted): a list of expressions each of which is sorted according to the following criterion: shorter prime implicants (smaller number of terms) first; the presence of a term of the most significant variable (according to the truth table column order); the term is the complement or not of the variable (not complemented variable first, then complemented). Note that, following traditional nomenclature widely adopted in this field, "term" means a single variable complemented or not. In Mathematics, a term is either a single number or variable, or the product of several numbers and variables separated from another term by a + or - sign, e.g., in the expression 3 + 4x + 5yzw, the 3, the 4x and the 5yzw are all separate terms. Here, in the expression A' B + A C, the terms are A, A', B, and C, not A' B and A C (here, due to pure text limitations, the complement is indicated by ').
Structured Text (ST): a list of expressions formatted in ST (a PLC language) suited to be copied and pasted into a PLC system. The prime implicant order is the same as in "Expressions (sorted)".
Truth Table: the truth table was obtained from the list of expressions. In the case of multiple solutions, the order of the columns for a given output variable (function) is the same as in the expressions (if "Expressions", or order format, is selected). Inconsistencies between the input truth table and the generated truth table are shown in red. One should expect those inconsistencies whether the input truth table contains any "don't care".
Quine McCluskey internals: shows the internal details of Quine McCluskey namely the implicant table, the prime implicant chart, and the logic expressions that represent multiple solutions. In the implicant table, the prime implicants are marked with an asterisk. In the implicant chart, the columns respective to ones (or zeros) covered by essential prime implicants are shown with light blue background and non-essential ones with light green background. Petrick's Method is applied only to non-essential prime implicants.
Time report: shows the processing time spend: assembling and sorting the truth table, generating the prime implicants, and the total time.
Ladder Diagram (LD): a list of expressions format as a ladder diagram (a PLC programming language where terms are represented as contacts). AND and OR operations appear as serial and parallel connections, respectively. Each variable is placed in a column (or row if "Product of sums" has been selected) which is not mandatory but improves readability. The prime implicant order is such that bigger subexpressions are represented firstly.
Karnaugh Map: the Karnaugh Map was obtained from the truth table with the prime implicants marked with different background colours (HTML). This is very cool if you are learning (or teaching) Karnaugh Maps because you can check your exercises quickly. Unfortunately, it is a bit difficult to figure out the mapping if there is too much overlapping between the prime implicants. LaTeX exporting produces a much cleaner result. A colour code has been used to match the prime implicant (rectangle or set of rectangles) in the map and the correspondent subexpression. The order in which the variables appear in the Karnaght Map can be modified by pressing the bottom “KM ORDER”. This is important when verifying an exercise, for instance.
Exporting
After minimizing you can export the result in two formats: HTML and LaTeX. LaTeX produces a much better quality result but requires some extra effort. You can generate a complete document or just inserts to be input into another document. HTML export saves the output shown in the interface straight to a file.
The options for LaTeX export are:
Boolean expressions: a list of expressions in a latex AMS align environment. Note that complemented single character variables are printed with \bar{} and longer strings with \overline{}. Also, the underline (_) indicates an index and it is formatted accordingly. The order is the same as in "Expressions" shown in the output.
Boolean expressions (sorted): same as above, but the order in which the prime implicants appear is the same as in "Expressions (sorted)".
Truth Table: the truth table obtained from the list of expressions similar to the one you see in the output. If the truth table was not minimized yet, the input truth table is formatted.
Ladder Diagram (LD): a list of expressions formatted as a ladder diagram to be printed using TikZ and tikz-ladder packages. Naturally, to see the actual diagram you will need to generate the PDF and for this, you will need a LaTeX distribution and the packages tikz-ladder and TikZ (both widely available). You can add the output var as a comment at the right of each rung. This serves as a placeholder for more insightful information.
Karnaugh Map: a list of commands to produce the Karnaugh Map from the truth table with the prime implicants represented as semi-transparent rectangles. Naturally, to see the actual Karnaugh Map you will need to generate the PDF and for this, you will need a LaTeX distribution and the packages tikz-karnaugh and TikZ (both widely available). You can generate colour-coded expressions to relate the implicants and the subexpressions and, if you are a teacher, you can generate exams. If you have not yet minimized the truth table, you can still export the map without the solution on it.
Input format (file)
The input file is formatted in CSV (comma-separated values) where each line contains a true table row. Lines beginning with "%" are considered comments and do not affect the output. Before the data itself, it is necessary to inform the name of the input and output variables and separated them by commas. The input and output variables are separated by two commas. If you use non-ASCII characters in comments or variable names, save your file as UTF-8 encoded. It is possible to force the order in which the input variables will appear in Karnaugh Maps using the ".i" command followed by the list of input variables in the desired order. This order can be changed using a graphical interface triggered by the "KM Order" button and this method is preferable.
You can use wildcards in the input values to automatically generate the values to reduce the amount of work of generating the lines. If a line appears a second time with different output values, a warning will be displayed.
Example:
.i x_7,x_3,x_6,x_2,x_5,x_1,x_4,x_0
x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,,z
0,-,-,-,0,-,-,-,,-
0,-,-,-,1,-,-,-,,0
1,-,-,-,0,-,-,-,,0
1,-,-,-,1,-,-,-,,-
0,1,0,0,0,1,0,0,,1
1,1,0,0,1,1,0,0,,1
0,1,0,0,1,1,0,0,,-
1,1,0,0,0,1,0,0,,-
The first four lines generate 256 rows in the truth table. The last four lines change the value of four rows which produces four warnings that can be ignored, in this case.
When inputting more than one function (output variable) it makes sense to use a special symbol "?" at the lines you do not want to touch a particular output variable.
Example:
B1,SM,SO1,SO2,M,C,,M,C
-,-,-,-,-,-,,0,0 % the whole table is set to zero
-,1,-,0,-,-,,?,1 % SM & NOT(SO2)
-,-,-,0,-,1,,?,1 % C & NOT(SO2)
1,-,0,0,-,-,,1,? % B1 & NOT(SO1) & NOT(SO2)
-,-,0,0,1,-,,1,? % M & NOT(SO1) & NOT(SO2)
-,-,1,1,-,-,,-,- % SO1 & SO2 are never activated simultaneously
The first line sets all functions (M and C) to zero for all input values. The second and third lines set the true values for function C, but do not touch the values of function M. The fourth and fifth lines sets the true value for function M, but do not touch function C. The sixth line sets the "don't care" values for both variables. Many warnings are issued, but all of them can be disregarded.
Sometimes you want to verify an exercise extracted from a book (or somewhere else) that is presented as a Karnaugh Map. Normally, you would need to read the Karnaugh Map decoding every cell address to transform the Karnaugh into a linear truth table. This is a very difficult, time-consuming, and error-prone task. To solve this problem, a new input mode was introduced. In this mode, called "Karnaugh Map mode", each row of the Karnaugh Map is typed in the input file in the same way they appear in the map. The mode is triggered by the ".k" command. The input variables must be typed in order from the most significant to the least significant and first all variables associated with the rows (variables that appear at the side of the map) then the variables associated with the columns (variables that appear on the top of the map). Several functions (output variables) can be inputted in the same file, but they must depend on the same set of variables and in the very same order. It is possible, however, to introduce "don't care" to complete the map of functions that depend on a subset of variables.
Examples: suppose you found these three Karnaugh Maps in a book:
z_2
\ x_2, x_1, x_0
x_5, x_4, x_3 \ 000 001 011 010 110 111 101 100
+---+---+---+---+---+---+---+---+
000 | | | | - | | | | |
+---+---+---+---+---+---+---+---+
001 | | 1 | - | | | | 1 | |
+---+---+---+---+---+---+---+---+
011 | | | | | | | | |
+---+---+---+---+---+---+---+---+
010 | | | | 1 | 1 | | | |
+---+---+---+---+---+---+---+---+
110 | 1 | | | 1 | 1 | | | - |
+---+---+---+---+---+---+---+---+
111 | 1 | | | 1 | 1 | | | - |
+---+---+---+---+---+---+---+---+
101 | | - | | | | | 1 | |
+---+---+---+---+---+---+---+---+
100 | | | | | | | | |
+---+---+---+---+---+---+---+---+
z_3
\ x_2, x_1, x_0
x_4, x_3 \ 000 001 011 010 110 111 101 100
+---+---+---+---+---+---+---+---+
00 | | | 1 | | - | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
01 | - | - | | 1 | 1 | 1 | | - |
+---+---+---+---+---+---+---+---+
11 | 1 | 1 | | 1 | 1 | - | - | 1 |
+---+---+---+---+---+---+---+---+
10 | | 1 | 1 | - | 1 | 1 | | 1 |
+---+---+---+---+---+---+---+---+
z_4
\ x_2, x_1, x_0
x_5, x_4, x_3 \ 000 001 011 010 110 111 101 100
+---+---+---+---+---+---+---+---+
000 | | | | | | | | |
+---+---+---+---+---+---+---+---+
001 | | 1 | - | 1 | 1 | | | |
+---+---+---+---+---+---+---+---+
011 | | 1 | - | 1 | 1 | - | 1 | |
+---+---+---+---+---+---+---+---+
010 | | | | | | | | |
+---+---+---+---+---+---+---+---+
110 | - | | | | | | | - |
+---+---+---+---+---+---+---+---+
111 | | 1 | | | | - | | |
+---+---+---+---+---+---+---+---+
101 | | - | | | | - | - | |
+---+---+---+---+---+---+---+---+
100 | 1 | | | | | | | 1 |
+---+---+---+---+---+---+---+---+
They can be inputted as:
.k
x_5,x_4,x_3,x_2,x_1,x_0,,z_2,z_3,z_4
000- 0000
01-0 0010
0000 0000
0001 1000
1001 100-
1001 100-
0-00 0010
0000 0000
0010 -111
--01 110-
1101 1--1
011- 11-1
---- ----
---- ----
---- ----
---- ----
0000 0000
01-1 1000
01-1 1-10
0000 0000
-000 000-
0100 0-00
0-00 0--0
1000 0001
Since all three maps have to be the same size, it was necessary to insert four additional lines so that z_3 depends on six, not just five, variables. Alternatively, z_3 could be input in a separate file. Note that the spaces, line breaks, and commas are ignored in this mode. Spaces and the empty line between maps were added to improve readability.
In some books and technical articles, it is common to specify the function by a list of implicants expressed in decimal. This type of list can be entered using the graphical interface without bigger problems, but it may be more convenient simply to copy and paste the list. For this, the "list mode" was created in which it is possible to specify a list of ones, zeros and possibly "don't care". In this mode, triggered by the ".l" command, each row of the input file represents a function (output variable). A list of ones starts with "s", list of zeros starts with "z". A list of "don't care" is inserted in the same row by placing a "d" character to mark the end of the ones/zeros list and the start of the "don't care".
Example: In Edward McCluskey's original article you find the following functions (Tables II, V, IX, and XIV):
.l
x_5, x_4, x_3, x_2, x_1,, z_2, z_5, z_9, z_14
s, 0, 2, 4, 6, 7, 8, 10, 11, 12, 13, 14, 16, 18, 19, 29, 30
s, 0, 1, 2, 3, 7, 14, 15, 22, 23, 29, 31
z, 0, 1, 2, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30
s, 5, 6, 13, d, 9, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
Spaces are ignored. Note that in the last function (z_14) sixteen additional "don't care" were introduced (from 16 to 31) because this function does not depend on x_5 (originally there are only two "don't care", 9 and 14). Also, I took the liberty of changing function z_9 from ones to zeros just to provide a map of zeros example.
Command-line parameters
You can specify the truth table file (CSV) to be open and an XML (eXtensible Markup Language) configuration file. See "JQMdefaults.xml" in the jar file for the defaults used in this package. You can save a copy of this file, say with a different name like "JQMconfig.xml", and modify the parameters. Then, you can execute with the new configuration in place using "-c" to specify the configuration file:
java -jar .\JQM-QuineMcCluskey.jar example.csv -c JQMconfig.xml
This loads the configuration file and opens example.csv. The order is not important, so, "java -jar .\JQM-QuineMcCluskey.jar -c JQMconfig.xml example.csv" does the same.
Probably, the two most important parameters are the number of variables that can be used without the risk of getting out of memory and the don’t care symbol.
Known issues
Even though, in general, the software works flawlessly, it is under development, and so you may experience some glitches.
One known problem is that sometimes the interface does not show. In this case, place the jar file on your desktop and try again. It happens when the jar path contains a special (odds) character.
Acknowledgements
I would like to thank many people that, by placing their work in the public domain or collaborating with forums, helped even unintentionally with this project. The interface is inspired in, not to say "copied from", Truth Table Solver 1.2 Beta, by Sherif Ahmed. The mechanism for editing variable names (column headings) was adapted from a hint by splungebob at http://stackoverflow.com. The Petrick's Method was adapted from Marcos Jimenez' Quine-McCluskey-Petrick minimizer. I do apologise if I left anyone out.
Processing time (on my computer):
660.602407640s 13 variables
70.914030554s 12 variables
9.280402119s 11 variables
106h (estimated) 16 variables
Download Latest Version
JQM-QuineMcCluskey.zip (352.4 kB)
