JQM - Java Quine McCluskey Copyright (C) <2016-2026> Luis Paulo Laus, laus@utfpr.edu.br
This is another implementation of the Quine McCluskey algorithm. Additionally, Petrick's Method is used to select the optimal (or minimum) solution when there are multiple options. The motivations for writing this program were that, despite the existence of many other implementations, none fulfilled 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 minimisation 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. As truth tables can be extensive, the save/reload feature prevents the need to re-enter data after modifications.
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.
The truth table can describe a Finite State Machine (FSM). JQM can analyse this FSM automatically looking for transitions that really can take place, race conditions and loops. The transitions table for the FSM is generated. Booth Mealy and Moore model are supported.
How to use it
Please follow this workflow:
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 separate threads, so you will be able to save after starting the minimisation process, even if something goes wrong… probably.
4- Select the output (result) format and other options.
5- Click on MINIMISE and wait patiently.
6- Export the result, or select other options and click on MINIMISE again. Note that any change you make will only affect the result after you click on MINIMISE.
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 (like "̅x̅t" or "x̅t̅ "), the straight line may look broken, depending on the font, giving 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)".
Prefix notation: a list of expressions in standard notation where the operator is placed before the operands, resembling a function call.
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".
QM 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 corresponding to ones (or zeros) covered by essential prime implicants are shown with a light blue background and non-essential ones with a light green background. Petrick's Method is applied only to non-essential prime implicants.
Time report: shows the processing time spent: assembling and sorting the truth table, generating the prime implicants, and the total time.
Ladder Diagram (LD): a list of expressions formatted 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 sub-expressions are represented first.
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 overlap 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 corresponding sub-expression. The order in which the variables appear in the Karnaugh Map can be modified by pressing the “KM ORDER” button. This is important when verifying an exercise, for instance.
Exporting
After minimising, 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 has not minimised 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 variable as a comment to 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 sub-expressions, and, if you are a teacher, you can generate exams. If you have not yet minimised 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 names of the input and output variables and separate 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 where 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 set 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 input 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 input 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 human 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", a 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" bits were introduced (from 16 to 31) because this function does not depend on x_5 (originally, there are only two "don't care" bits, 9 and 14). Also, I took the liberty of changing function z_9 from ones to zeros just to provide a map of zeros.
Boolean expressions in standard notation can be input, and the truth table is automatically generated. This mode is triggered by the ".e" command. Each output variable is described by its full expression type in a row. For example:
.e
a,b,c,,X,Y,Z
X = (a ^ b)'
Y = ̅a.(b + a.̅c)
Z = a*(b + a'*(b' + c + 1'))
Note that the variable declaration is mandatory. The operator available in this mode are: + and | (or); *, & and . (and); ^ (exlusive-or); ', ~, ! and character 773 (complement). The complement can be placed after or before operand. Character 773 (U+0305) is supported so the results can be copied and paste in a new CSV file. Constants 0 and 1 are supported. The parser's ability to detect errors is limited, so double-check your expression.
Finally, the input file can contain commands for Finite State Machine analysis, a new feature loosely related to logic synthesis. Command ".s" defines the initial transition (the starting point of the branching algorithm), ".f" declares the number of input variables which are inputs of the FSM, the remaining input variables are the state variables. The states can be labelled using the command ".n". The new CSV file can be saved (you do not need to minimise it first). In the “File” menu, the item “Analyse FSM...” presents some options:
Timers: If the FSM features timers, these can be included in the analysis. TON (Timer On Delay), TOF (Timer Off Delay), and TP (Pulse) types are supported. The timer output is connected to an FSM input variable and is controlled by an FSM output variable. Two evolution rules are applied: if the timer is reset, a new transition is generated; if the timer is invalid (output is on but input control is off in the last transition), the output is corrected accordingly. A timer is created in the input file using the .t command, followed by the input variable connected to the timer's output, the output variable that controls the timer, and the type (TON, TOF, TP).
Stable only: Inhibits timer activation when spreading from unstable states. The timer triggers strictly within stable states.
Follow races: follows race conditions if more than one state variable changes. Important for asynchronous FSM.
Non-critical races: besides critical race conditions, non-critical ones can also be enlisted;
Full stable spread: completely spreads all stable states. Can be useful if not all states were found (implies that more than one input are changed in a stable state). Important for synchronous FSM.
Unstable spread: spreads all unstable states. Can be misleading, mainly employed in relay command analyses;
Full unstable spread: completely spreads all unstable states. Important for synchronous FSM.
Omit transitions to DC: omit invalid transitions that contain don’t care (multiple destinations);
Hamming distance: includes the Hamming distance in the transition table.
The input and output variables must be declared as follows:
| input | output |
| FSM inputs | FSM current state | FSM next state | output |
The current and next state variables must be listed in the same order. A simple example is:
% Flip-flop toggle
.f 1
.n OFF 0,0 0 2 % off
.n ON 1,1 2 0 % on
.n PON 1,0 2 2 % pre-on, on immediately after I activates
.n POFF 0,1 0 0 % pre-off, off immediately after I activates
.s 0,0,0,0, 0,0,0,0,0,0
I, N,M,,M,M, Q
0, 0,0,,0,0, 0
1, 0,0,,1,0, 0
1, 1,0,,1,0, 1
0, 1,0,,1,1, 1
0, 1,1,,1,1, 1
1, 1,1,,0,1, 1
1, 0,1,,0,1, 0
0, 0,1,,0,0, 0
0, 0,0,,0,0, 0
where I is the input, N and M are the current state variables, N* and M* are the next state variables and Q is the output. Command ".n" labels a state N=M=0 as OFF, N=M=1 as ON and so on. It is also possible to specify the state coordinates (x,y) for the state diagram and include comment. Use the format ".n name state x y % some state comment" where "state" is something like "0,0,1,1", no spaces because the parser uses the white space as field separator. The output file shall contain the analysis in which the following transition table can be found:
I,,OFF,PON,ON,POFF
0,,OFF/0,ON/1,ON/1,OFF/0
1,,PON/0,PON/1,POFF/1,POFF/0
The first row is the table header (input I, current states FF,PON,ON and POFF), and the following rows contain the next state for every combination of inputs. The algorithm starts at transition I=0, N=M=0 to N*=M*=0, and tries to find every possible transitions, but constraining the guesses to a Hamming distance of one (unless options full spread are checked).
Command-line parameters
You can specify the truth table file (CSV) to be opened 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 (odd) character.
GNOME Wayland users may experience strange behaviour when moving columns around. The solution depends on fixing the java.awt.Robot library. Try: WAYLAND_DISPLAY= java -jar JQM-QuineMcCluskey.jar. Also, use dconf-editor to change /org/gnome/mutter/wayland/xwayland-disable-extension to blanc; by default 'Xtest' is disable.
Acknowledgements
I would like to thank many people who, by placing their work in the public domain or collaborating with forums, helped, even unintentionally, with this project. The interface is inspired by, 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's Quine-McCluskey-Petrick minimiser. 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 (494.3 kB)
