Boolean simplifier: Karnaugh map solver, minimal SOP and POS
Type a Boolean expression or a minterm list and get its Karnaugh map, its minimal SOP and POS in SystemVerilog, and a live two-level circuit where one fits.
- Limit
- 6 variables
- Published
- Authorship
- Drafted with AI assistance, reviewed by İsmail
SystemVerilog operators ~ & | ^, parentheses, 1 to 6 names of up to 8 characters.
y has 3 inputs. Minimal SOP: 2 terms, 4 literals; minimal POS: 2 terms, 4 literals.
Karnaugh map
| 00 | 01 | 11 | 10 | |
Minimal SOP
y = ~b & c | a & b
not b and c, or a and b
Minimal POS
y = (b | c) & (a | ~b)
b or c, and a or not b
written Your expression
minimum Minimal SOP
Run plays this scenario from the start; driving an input continues from here.
Two circuits driven by the same inputs, written and minimum, under one waveform. Inputs: a, b, c. Outputs: y. It is built from 1 inverter, 3 AND gates, 1 OR gate. The waveform shows a, b, c, y [written], y [minimum].
Figure 1. Your SOP as written, against the minimum. Press Run: the inputs walk the truth table in Gray order, and both outputs agree on every row.
// minimal_sop: a minimal sum of products from alwaysff.com, cover 1 of 1.
module minimal_sop (
input logic a,
input logic b,
input logic c,
output logic y
);
assign y = ~b & c
| a & b;
endmoduleHow to read the result
Each cell of the Karnaugh map is one row of the truth table, and its button says which: its
value, its row number and each variable's value. Rows and columns run in Gray order, 00, 01,
11, 10, so two cells side by side differ in exactly one variable, and so do the first and the
last cell of a row or a column: the map wraps around at its edges. Five variables take two maps,
one for each value of the first variable; six take four.
A group is one term of the cover on screen: a rectangle of 1, 2, 4 or more cells, drawn in ink
with a dash and a number of its own, and broken into open pieces where it wraps around an edge.
The legend under the map lists the groups in the order the form prints its terms, each with its
number and its term. Point at a legend button to light its group, or press it to keep the group
lit. The map is an input too: click a cell, or press 0, 1 or - on it, and the function on
screen becomes the map's.
Both minimal forms are printed. The sum of products (SOP) is an OR of AND terms; the product of
sums (POS) is an AND of OR terms. Each is written as SystemVerilog, which pastes back into the
field, and under it in textbook notation, with a bar over a complemented name and + for OR. A
function can have several minimum covers of the same cost. "1 of 2" says so, and Previous and Next
step through them. “Map, code and circuit show” chooses the form that the map's groups, the code
and the circuit follow.
The code is one assign, a term to a line, and each first-level gate of the circuit lights its
line. Press Run and the inputs walk the truth table in Gray order, one input changing a step, while
the output is checked against the table on every row the table decides; five and six variables walk
one map a scenario. A sum of products or a product of sums you typed, unless it is already a
minimum, is drawn against its minimum on one waveform, so you can watch the two outputs agree.
The method
The tool finds the prime implicants by the Quine–McCluskey method: it merges rows that differ in one variable into larger groups until no two merge, and the groups left over are the primes. Don't-cares help to form a group but never have to be covered. Choosing the fewest primes that cover every 1 is a covering problem, which the tool solves exactly, by branch and bound: fewest terms first, then fewest literals. Its answers were checked against an independent reference on every function of up to four variables, and on 20,000 random functions of five variables and 2,000 of six, each sample again with don't-cares.
The minimal POS is the minimal SOP of the complement, with the same don't-cares, read back by De Morgan's law, so its groups are groups of 0s. Of several minimum covers, the first is the one that holds the earliest group the other lacks, and of two groups the earlier is the one that holds the earliest row of the truth table the other lacks.
The minimum is not always the circuit you want
The default expression, a & b | ~b & c | a & c, is the covered form of the static-1 hazard
reference page. Its minimum drops the term a & c, because the other two
terms already cover every row it covers. In a circuit with gate delays that term matters: when b
falls while a and c are high, ~b & c rises a moment after a & b falls, and without a & c
the output dips. A minimum is the cheapest correct expression, not a circuit without hazards.
Limits
The tool reads up to 6 variables, with names of at most 8 characters: lowercase letters, digits
and _, starting with a letter or _. A SystemVerilog keyword is refused, and so is a name a lint
tool rejects, because the code would not lint, or one the highlighter colours as a keyword. Expressions use SystemVerilog's operators ~ ! & ^ ~^ | && || and parentheses, with its precedence.
A circuit is drawn where it fits the figure: every minimum of up to three variables, every four-variable minimum of at most 25 literals, five-variable minima of at most 4 terms or 16 literals, and six-variable minima of at most 3 terms or 13 literals, with larger ones when they fit. Past that the page says how large the circuit would be, and the map, the forms and the code are complete without it. The hardest six-variable functions take a moment on a slow phone, and the status line says so while the tool works. A printed form is one completion of the don't-cares, and it leaves out a variable the minimum does not need: the minterm list and the map carry the whole function.