Minimize Boolean expressions instantly — click cells to toggle minterms and don't-cares, and see the minimized SOP with color-coded prime implicant groups. Supports 2, 3, and 4 variables.
Each cell in the K-map corresponds to one minterm — a unique input combination. Click to set a cell to 1 (function outputs true), 0 (false), or X (don't-care). You can also type minterm numbers directly in the fields below the map and click Load.
② Form Maximal Groups
The solver finds all prime implicants — the largest possible rectangles of 1s and Xs with a power-of-2 cell count (1, 2, 4, 8, 16). Groups wrap around all four edges. A larger group means fewer literals: a group of 4 eliminates 2 variables from the product term.
③ Find Essential Prime Implicants
An essential prime implicant (EPI) is the only group covering a particular minterm. EPIs are always included in the minimal solution. After locking in EPIs, remaining uncovered minterms are covered greedily with the largest available prime implicants.
④ Read the SOP Expression
Each selected group becomes one AND-term. Variables fixed at 0 appear complemented (A'), variables fixed at 1 appear uncomplemented (A), variables that change within the group are eliminated. The terms are OR-ed to form the final SOP.
Group Size
Variables Eliminated
Literals in Term
Example (4-var)
1 cell
0
4
A'B'C'D'
2 cells
1
3
A'B'C'
4 cells
2
2
A'B'
8 cells
3
1
A'
16 cells
4
0
1 (always true)
Frequently Asked Questions
What is a Karnaugh map and why is it used?
A Karnaugh map (K-map) is a graphical tool for simplifying Boolean expressions. It arranges all truth table rows in a grid where adjacent cells differ by exactly one variable (Gray code ordering). Grouping adjacent 1s in the grid corresponds to factoring shared variables out of a product term, directly giving the minimized Sum of Products (SOP). K-maps are universally taught in digital electronics and asked in VLSI/ASIC interviews because they build intuition for logic minimization.
How do I solve a 4-variable Karnaugh map step by step?
① Fill the 4×4 grid with your truth table values (0, 1, or X). The rows represent AB (in Gray code 00→01→11→10) and columns represent CD. ② Circle all maximal groups of 1s and Xs — start with the largest possible groups (16, 8, 4, 2, 1). Groups wrap around all edges. ③ Identify essential prime implicants — any minterm covered by only one group makes that group essential. ④ Cover remaining minterms with the fewest additional groups. ⑤ Write one AND-term per group: include only variables that are constant within the group. OR all terms together for the final SOP.
What are don't-care conditions (X) in K-maps?
Don't-care conditions (marked X) are input combinations that either cannot occur in the real system or whose output value doesn't matter. In a BCD digit detector, for example, binary values 10–15 are invalid and can be marked X. In K-map minimization, don't-cares act as wildcards — they can be included in groups to form larger rectangles and eliminate more variables. However, a group made entirely of don't-cares is never selected, since it doesn't contribute to covering any actual minterm.
Why must K-map groups be powers of 2?
The Gray code ordering of the K-map ensures that any rectangular group of 2ⁿ adjacent cells (1, 2, 4, 8, …) has exactly n variables that change across the group. Those n changing variables cancel out, leaving a product term with (total_variables − n) literals. If a group size is not a power of 2, the variables cannot be cleanly eliminated, so you'd end up with a more complex or incorrect expression. The power-of-2 constraint is what makes K-maps a sound minimization method.
What is the difference between POS and SOP simplification?
Sum of Products (SOP) groups the 1s in the K-map to produce AND terms OR-ed together — implementing a two-level NAND-NAND network. Product of Sums (POS) instead groups the 0s (maxterms) and applies De Morgan's law to get OR terms AND-ed together — implementing a NOR-NOR network. This solver uses SOP. For some functions, POS gives fewer gates, but in practice, synthesis tools evaluate both and choose the more economical form automatically.
Can K-maps solve 5 or 6 variable functions?
Yes, but they require two overlapping 4-variable K-maps side by side. For 5 variables (ABCDE), one map covers E=0 and the other E=1; a group is valid only if the same pattern of 1s appears in both maps. At 6 variables, four 4-variable maps are needed, making the visual method very unwieldy. Beyond 6 variables, the Quine-McCluskey (tabulation) algorithm or the ESPRESSO heuristic are used by synthesis tools. For VLSI interview purposes, 4-variable K-maps are the most commonly tested form.
Boolean Minimization in Modern VLSI Design
How Synthesis Tools Minimize Logic
Modern VLSI synthesis tools (Synopsys Design Compiler, Cadence Genus) do not use K-maps internally — they use the ESPRESSO heuristic algorithm or BDD (Binary Decision Diagram) based methods that scale to hundreds of variables. But the goal is identical to K-map minimization: find the minimum set of product terms (prime implicants) that covers all required minterms. ESPRESSO works by iteratively expanding, irredundifying, and reducing cover sets. BDDs represent Boolean functions as directed acyclic graphs where the path from root to leaf encodes a variable assignment; minimizing the BDD minimizes the logic. Understanding K-map minimization gives you a precise mental model of what the synthesizer is doing, which lets you structure RTL to give the tool the best starting point — for example, writing an always_comb block with a complete case statement allows the synthesizer to identify don't-care states and exploit them for logic reduction.
Don't-Cares in Synthesis: Output vs Input
K-maps distinguish two kinds of don't-cares. Output don't-cares (ODCs) are input combinations that can never occur in the real circuit — the output value for these minterms is irrelevant and the synthesizer may assign 0 or 1 to minimize logic. In RTL, these appear as default branches in a case statement inside an always_comb block: the synthesizer treats unassigned output bits in the default as don't-cares. Input don't-cares (IDCs) arise when a signal combination genuinely cannot occur due to upstream logic constraints. Synthesis tools use both to reduce gate count. A common mistake is using casex or casez to create implicit don't-cares without understanding that the synthesizer will use them aggressively — which may produce incorrect behavior if the "impossible" combination later becomes reachable due to a protocol change. Always use explicit don't-care assignments (out = 'x;) rather than relying on casex wildcards, because the former documents the designer's intent while the latter obscures it.
Two-Level vs Multi-Level Logic and Delay
K-map minimization produces two-level SOP expressions (AND-OR or equivalently NAND-NAND). Two-level logic has a predictable maximum delay: one gate level for the AND plane, one for the OR plane, regardless of the number of inputs. This makes timing analysis straightforward. However, two-level implementations are not always area-optimal. Consider the function F = ABC + ABD + ACD + BCD — two-level SOP requires 4 AND gates and 1 OR gate. Factored form F = AB(C+D) + CD(A+B) requires 2 OR gates, 2 AND gates, and 1 OR gate — fewer gates total. Modern synthesis tools automatically explore multi-level implementations by applying algebraic factoring and decomposition techniques. The K-map gives you the two-level optimal starting point; the synthesizer then decides whether further factoring saves area at the cost of adding gate levels (and thus delay). Understanding this trade-off explains why synthesis tool constraints (area, timing) directly affect the number of logic levels in the output netlist.
K-Maps in FPGA vs ASIC Context
In ASIC synthesis, minimizing the number of literals (input variables) in each product term minimizes the number of gate inputs, which reduces area and often improves timing. In FPGA synthesis, the optimization target is different: a 6-input LUT can implement any function of up to 6 variables with identical delay, so minimizing literal count within 6 inputs provides no benefit — the LUT delay is the same whether the function uses 3 or 6 variables. FPGA synthesis instead focuses on minimizing the number of LUTs by packing multiple related functions into a single LUT, exploiting the LUT's ability to represent any truth table. A 4-variable K-map result directly maps to a 4-LUT with one cell; a 5-variable result requires two 4-LUTs and an additional MUX LUT. This explains why FPGA tools sometimes produce "suboptimal" SOP expressions that look more complex but use fewer LUT resources — they are optimizing for a different cost function than literal count.