SmartEng Tools

Digital logic · Simplification

Simplifying with a Karnaugh map

A Karnaugh map rearranges the truth table so that the cells that can be combined sit next to each other. First we solve an example in seven steps; then you practise and check it with the minimizer.

Guided example

1. The function

F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15)

2. The minterms in binary

m0 = 0000 · m2 = 0010 · m5 = 0101 · m7 = 0111 · m8 = 1000 · m10 = 1010 · m13 = 1101 · m15 = 1111

Before drawing anything a pattern is already visible: in all of them, bit B equals bit D.

3. The map

Rows AB and columns CD in Gray order (00, 01, 11, 10). Each cell shows its minterm number in the corner.

AB \ CD00011110
0010010312
0104151706
11012113115014
101809011110

4. Group

Look for the largest possible rectangles of 1, 2, 4 or 8 cells. Here there are two groups of 4: the centre (m5, m7, m13, m15) and the four corners (m0, m2, m8, m10). The corners form a group because the map “wraps”: the first and last columns are neighbours, and so are the first and last rows.

AB \ CD00011110
0010010312
0104151706
11012113115014
101809011110

5. Read each group

Inside a group, the variables that change disappear and those that stay constant form the product. In the centre, A and C take both values but B = 1 and D = 1: the term is BD. In the corners, A and C change again and B = 0, D = 0: the term is B'D'.

6. The solution

F = B'D' + BD

From eight 4-literal minterms to two 2-literal terms. The expression confirms the pattern from step 2: F is 1 when B and D are equal, i.e. F is the XNOR of B and D. A and C have no effect.

7. Check

Load the example into the minimizer (or mark the cells by hand below) and compare the result and the AND-OR diagram.

Karnaugh minimizer

Click a cell to go from 0 to 1 to X (don’t care). You can change the number of variables and their names, view the truth table and add up to 8 outputs.

AB \ CD00011110
00
01
11
10
Minimized Expression (SOP)
OUT: F1
F1 = 0
CIRCUITO RTL UNIFICADO
OR
F1

Practise

Place the minterms on the map

Mark the cells of F(A,B,C,D) = Σm(3, 6, 11, 12, 14) on the 4-variable map. Rows are AB and columns are CD, both in Gray code.

AB \ CD00011110
00
01
11
10
Open in the tool

Minimize using don’t cares

Write a minimal sum of products for F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5). Use A, B, C, D and an apostrophe for NOT (for example A'B).

Syntax: products side by side (AB), sum with +, NOT with an apostrophe (A') or a leading !.

Open in the tool

Check someone else’s solution

A classmate proposes F = A'B' + BC' + AB for F(A,B,C) = Σm(0, 1, 2, 5, 6, 7). Is it correct? If not, mark a minterm where it fails.

F = A'B' + BC' + AB

Is the expression correct?
Open in the tool

How the minimizer computes

  1. It finds every prime implicant with the Quine-McCluskey tabular method: it repeatedly combines terms that differ in a single bit, including don’t cares.
  2. It takes the essential prime implicants (the only ones covering some 1).
  3. It covers the remaining 1s with a backtracking search that minimizes the number of terms. Among covers with the same number of terms it keeps the first one found, which is not necessarily the one with fewest literals.
  4. If the search exceeded 10,000 iterations, it would use a greedy cover and flag it with an “Approximate” warning.

Limitations

  • 2 to 4 variables.
  • It only produces a sum of products (SOP). For a product of sums you have to group the zeros by hand (or minimize the complemented function).
  • With several outputs, each one is minimized separately; the diagram marks the products they have in common, but it does not search for the optimal multi-output solution.
  • When there are several minimal solutions it shows one. In the don’t-care exercise above there are two equally good ones.
GuideHow Karnaugh maps workWhy Gray order, essential prime implicants and cyclic cases.GuideBCD to 7-segment decoderSeven 4-variable functions with don’t cares, solved and checked.

References

  • M. Karnaugh, “The Map Method for Synthesis of Combinational Logic Circuits”, Transactions of the AIEE, Part I, vol. 72, no. 5, 1953 — original paper describing the map method
  • W. V. Quine, “The Problem of Simplifying Truth Functions”, The American Mathematical Monthly, vol. 59, no. 8, 1952 — prime implicants and function simplification
  • E. J. McCluskey, “Minimization of Boolean Functions”, Bell System Technical Journal, vol. 35, no. 6, 1956 — tabular method the minimizer uses to find prime implicants