Karnaugh Map (K-Map): Rules and Examples

A Karnaugh map (K-map) is a visual method for simplifying Boolean expressions. Instead of grinding through algebraic identities, you plot a function’s output on a specially ordered grid and then read the minimal expression straight off it by circling groups of adjacent 1s. Invented by Maurice Karnaugh in 1953, the technique turns tedious Boolean manipulation into a pattern-matching exercise that most engineers can do faster and with fewer mistakes. This guide covers what a Karnaugh map is, why it beats raw Boolean algebra, how to build and read 2-, 3-, and 4-variable maps, the grouping rules for pairs, quads, and octets, extracting both SOP and POS forms, and how to exploit don’t-care conditions.

Why Use a Karnaugh Map Instead of Boolean Algebra?

Boolean algebra can simplify any expression, but it has two weaknesses. First, there is no mechanical procedure: deciding which identity to apply next relies on experience and luck, and it is easy to miss a reduction. Second, algebra gives no guarantee that the result is actually minimal. A Karnaugh diagram fixes both problems. The map is arranged so that physically adjacent cells differ by exactly one variable, which means any adjacent pair of 1s represents a term where one variable can be eliminated. By circling the largest legal groups, you are guaranteed a minimal (or near-minimal) sum-of-products expression.

The payoff is practical: fewer logic gates, lower area, and shorter critical paths in the final circuit. Karnaugh mapping is one of the first tools taught in any digital-design course precisely because it builds the intuition you later apply when writing synthesizable RTL and reasoning about a combinational circuit.

The Gray-Code Ordering

The single most important feature of a K-map is that rows and columns are labelled in Gray code (00, 01, 11, 10) rather than binary counting order (00, 01, 10, 11). Gray code ensures that moving one square horizontally or vertically changes only one bit. This is what makes “adjacency” on the map correspond to a valid Boolean simplification. The map also wraps around: the leftmost and rightmost columns are adjacent, and the top and bottom rows are adjacent, because their labels also differ by a single bit.

Building 2-, 3-, and 4-Variable Maps

A function of n variables needs a map with 2ⁿ cells. A 2-variable map has 4 cells, a 3-variable map has 8 cells, and a 4-variable map has 16 cells. Each cell corresponds to one minterm, and you write a 1 in it when the function is true for that input combination.

Consider the two-variable function below, defined by its truth table:

Plotted on a 2-variable map (rows = A, columns = B):

The left column (B=0) holds two 1s, giving the term B’. The bottom row (A=1) holds two 1s, giving A. The minimal result is F = A + B’, reached in seconds.

Grouping Rules: Pairs, Quads, and Octets

All the power of the method lives in how you circle the 1s. The rules are strict and worth memorising:

• Groups must be rectangular and contain only 1s (and don’t-cares, discussed later).
• Group size must be a power of two: 1, 2, 4, 8, or 16 cells. A group of 2 is a pair, a group of 4 is a quad, and a group of 8 is an octet.
• Make groups as large as legally possible. A larger group eliminates more variables: a pair removes one variable, a quad removes two, and an octet removes three.
• Groups may overlap if sharing a 1 lets you form a larger group elsewhere.
• Groups may wrap around edges and corners, because of Gray-code adjacency.
• Use as few groups as possible, but every 1 must be covered by at least one group.

To read a group’s term, keep the variables that stay constant across every cell in the group and drop the ones that change. A variable that is constant at 1 appears uncomplemented; a variable constant at 0 appears complemented.

Worked Example 1: Three-Variable SOP

Take F(A, B, C) = Σm(1, 3, 4, 5, 7). The truth table is:

The 3-variable map uses A for the rows and BC (in Gray order) for the columns:

Two groups cover every 1 cleanly:

• The two middle columns (BC = 01 and BC = 11) are full in both rows — a quad of minterms 1, 3, 5, 7. Across this quad only C stays at 1, so the term is C.
• Minterm 4 is left over. Pairing it with the adjacent minterm 5 (bottom row, BC = 00 and 01) gives a pair where A = 1 and B = 0 are constant: the term AB’.

The minimal sum-of-products result is F = C + AB’.

Reading POS From the Same Map

A Karnaugh map also yields the product-of-sums (POS) form directly — you simply group the 0s instead of the 1s. This gives you the complement F’, which you then invert. In Example 1 the zeros sit at minterms 0, 2, and 6.

• Pair of 0s at minterms 0 and 2 (A = 0, C = 0 constant): term A’C’.
• Pair of 0s at minterms 2 and 6 (B = 1, C = 0 constant): term BC’.

So F’ = A’C’ + BC’. Applying DeMorgan’s theorem and the rule that a constant-0 variable becomes uncomplemented in a sum term, the maxterm form is F = (A + C)(B’ + C). Expanding this product confirms it reduces back to C + AB’, so the SOP and POS forms describe the same function — a useful self-check.

Worked Example 2: Four-Variable Map With Edge and Corner Groups

Four-variable maps are where K-maps shine, and where wrap-around adjacency becomes essential. Take F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15). Rows are AB (Gray order) and columns are CD (Gray order):

Two quads cover the whole function:

• The four corner cells (minterms 0, 2, 8, 10) form one quad thanks to wrap-around in both directions. Across these cells B = 0 and D = 0 stay constant, giving the term B’D’.
• The central block (minterms 5, 7, 13, 15) forms the second quad, where B = 1 and D = 1 are constant, giving BD.

The result is F = B’D’ + BD — which is simply the XNOR of B and D. The corner grouping is the classic trap that catches students relying on pure binary intuition; Gray-code adjacency makes it perfectly legal.

Don’t-Care Conditions

In many real designs some input combinations can never occur — for example, the codes 1010 through 1111 in a BCD (binary-coded decimal) system. For these the output is irrelevant, and we mark the cell with an X (a don’t-care). The simplification rule is powerful: treat each X as whatever value (0 or 1) helps form a larger group, but never create a group made entirely of Xs.

Consider F(A, B, C, D) = Σm(1, 3, 7) + d(0, 2, 5), where d marks don’t-cares:

If we ignored the don’t-cares, the required 1s (minterms 1, 3, 7) would need two groups: A’B’ (covering 1 and 3) plus A’CD (covering 3 and 7), giving F = A’B’ + A’CD. But by treating the X at minterm 5 as a 1, minterms 1, 3, 5, and 7 form a single quad in which A = 0 and D = 1 are constant. The whole function collapses to F = A’D — one term, one two-input gate. This illustrates why don’t-cares are so valuable: they frequently cut gate count dramatically.

Common Mistakes to Avoid

• Forgetting Gray code. Labelling columns 00, 01, 10, 11 breaks every adjacency and produces wrong answers.
• Making groups too small. Always extend a group to the largest legal power-of-two size before committing.
• Leaving a 1 uncovered. Every 1 must belong to at least one group.
• Grouping only Xs. A don’t-care may join a group but must never form one on its own.
• Ignoring wrap-around. Edges and the four corners are adjacent; check them on every map.

Beyond five or six variables the map becomes hard to read, and engineers switch to the Quine-McCluskey algorithm or let a synthesis tool handle minimisation. In practice, modern RTL-to-gates flows optimise logic automatically, but the Karnaugh map remains the clearest way to understand what that optimisation is doing — knowledge you carry into writing clean Verilog or SystemVerilog for combinational blocks.

Learn Digital Logic the Right Way

Mastering Karnaugh maps is the foundation for everything from FSM design to timing-aware RTL. If you want structured, project-driven training in digital logic and VLSI design, explore ChipXpert’s VLSI courses for UG and PG students, where K-map simplification, combinational and sequential design, and hands-on tool flows are taught step by step.

Frequently Asked Questions

What is a Karnaugh map used for?

A Karnaugh map is used to simplify Boolean expressions into their minimal sum-of-products or product-of-sums form. By plotting a function’s outputs on a Gray-coded grid and grouping adjacent 1s (or 0s), you can eliminate redundant variables and design a circuit with fewer logic gates.

How is Karnaugh mapping different from a truth table?

A truth table simply lists every input combination and its output. Karnaugh mapping takes that same information and arranges it on a grid where adjacent cells differ by one variable, so patterns of adjacent 1s reveal simplifications that a flat truth table cannot show at a glance.

What are pairs, quads, and octets in a K-map?

These are the legal group sizes. A pair is two adjacent 1s and removes one variable; a quad is four adjacent 1s and removes two variables; an octet is eight adjacent 1s and removes three variables. Larger groups always give simpler terms, so you form the biggest legal group possible.

How do don’t-care conditions help in a Karnaugh diagram?

Don’t-care conditions are input combinations that never occur, marked with an X. You may treat each X as a 1 or a 0 — whichever lets you form a larger group — which often reduces the number of terms and gates. You must never build a group made up only of don’t-cares.

Can a Karnaugh map give both SOP and POS expressions?

Yes. Grouping the 1s produces the minimal sum-of-products (SOP) form. Grouping the 0s produces the complement, which when inverted with DeMorgan’s theorem gives the minimal product-of-sums (POS) form. Both describe the same function and can be used to cross-check your result.