Digital Logic · AI215

Karnaugh Map (K-Map) Simplification Step by Step

Digital Logic Study guides

A Karnaugh map is a grid that shows a truth table so that adjacent cells differ in exactly one variable. Grouping adjacent 1s gives a minimal sum-of-products expression.

A K-map for n variables has 2^n cells: 4 cells for 2 variables, 8 for 3 and 16 for 4. Rows and columns are labelled in Gray code order (00, 01, 11, 10), so neighbouring cells, including the wrap-around edges, differ in one bit. Each cell is a minterm: for F(x,y,z) = Sum m(0, 1, 6, 7), put 1 in cells 0, 1, 6 and 7.

To simplify: group the 1s in rectangles whose size is a power of two (1, 2, 4, 8, 16), as large as possible, and cover every 1 with as few groups as possible. Groups can overlap and can wrap around the edges. For each group, keep the variables that do not change across the group and drop the ones that do; write the kept variables as a product term and OR the terms. Don't-care conditions (X) can be treated as 1 when they make a group larger, and ignored otherwise. For POS, group the 0s instead.

Bigger groups remove more variables: a group of 2 removes one variable, a group of 4 removes two, a group of 8 removes three.

Key points

  • 2^n cells for n variables; Gray code labelling.
  • Groups are powers of two: 1, 2, 4, 8, 16.
  • Largest possible groups, fewest groups, overlap and wrap-around allowed.
  • Keep unchanged variables, drop changing ones.
  • Don't-cares may join groups only when useful.

Worked example

F(x, y, z) = Sum m(0, 1, 6, 7). Cells 0 (000) and 1 (001) form a group where x = 0 and y = 0 stay fixed, giving x'y'. Cells 6 (110) and 7 (111) form a group with x = 1 and y = 1 fixed, giving xy. So F = x'y' + xy.

Common questions

How many cells does a 3-variable K-map have?

8 cells, since 2^3 = 8.

Why use Gray code order on a K-map?

So adjacent cells differ by only one variable, which lets grouping eliminate that variable.

Practice questions on this topic

Try these, then open the app to check your answers with explanations.

  1. The K-Map is just a different form of the truth table
    • A. TRUE
    • B. FALSE
  2. A Karnaugh map (K-map) is an abstract form of diagram organized as a matrix of squares.
    • A. Venn
    • B. cycle
    • C. block
    • D. triangular
  3. A K-Map of 3 variables contains ....... cells.
    • A. 8
    • B. 3
    • C. 9
    • D. 12
  4. Minimizing such functions can be achieved by converting them into standard forms such as ____, then making the k-map and obtaining the minimized function.
    • A. SOP
    • B. POS
    • C. Both A and B
    • D. None of the above
  5. a K-map is a collection of squares
    • A. true
    • B. false
  6. Using a Karnaugh map, F(x,y,z) = Σm(0, 2, 6, 7) is minimized to:
    • A. F = x'z' + y
    • B. F = x'z' + xyz'
    • C. F = x'z' + xy
    • D. F = xz' + xy