Learn › Topic 4

Karnaugh maps for 2, 3 and 4 variables with don't-care conditions

7 min read · bitGateLab Team

Simplifying with Boolean algebra works, but it depends on you "seeing" which law to apply. The Karnaugh map turns that search into a visual exercise: it arranges the truth table in a grid where neighboring cells differ in a single variable, and simplifying becomes a matter of circling groups of ones. Here you will learn to build maps of 2, 3 and 4 variables, to group correctly (including the edges that "wrap around") and to take advantage of don't-care conditions.

The idea: neighboring cells, one variable apart

The adjacency law says that AB + AB = A: two terms that differ in a single variable merge, and that variable disappears. The Karnaugh map arranges the minterms so that any pair of cells sharing a side meets that condition. To achieve this, the row and column headings do not follow the binary order 00, 01, 10, 11, but the Gray code: 00, 01, 11, 10. Only one bit changes between two consecutive values, and also between the last and the first (10 and 00). That is why the map behaves as if its opposite edges were glued together.

Maps of 2 and 3 variables

The two-variable map has 4 cells: A on the rows and B on the columns. The three-variable map has 8 cells: A on the rows and BC on the columns, in Gray order. The number inside each cell shows the minterm it corresponds to:

Notice that m3 and m2 appear in that order: it is the effect of the Gray code, and the cause of many mistakes when filling in the map by hand.

Grouping rules

• Groups may contain only ones (or X's, as you will see later), never zeros.
• The size of each group must be a power of 2: 1, 2, 4, 8 or 16 cells.
• Groups are rectangles of adjacent cells, including adjacency across the edges. Diagonals do not count.
• Make each group as large as possible: a group of 2^k cells eliminates k variables.
• Use the smallest number of groups that covers all the ones. Groups may overlap.

To read a group, check each variable: if it keeps the same value in every cell of the group, it appears in the term (without a bar if it is 1, with a bar if it is 0); if it changes, it is eliminated.

The 4-variable map and adjacency at the edges

With four variables the map has 16 cells: AB on the rows and CD on the columns, both in Gray order.

The left column is a neighbor of the right one, and the top row is a neighbor of the bottom one. As a result, the four corners (m0, m2, m8, m10) form a valid group of 4 cells: in all of them B = 0 and D = 0, so they read as BD.

Don't-care conditions (X)

Sometimes certain input combinations never occur, or their output has no consequences. For example, in a BCD digit the codes 1010 to 1111 do not exist. Those rows are marked with an X (known as a don't care) and listed separately as d(...). When grouping, each X may be taken as a 1 if it helps you form a larger group, or ignored if it does not. An X never needs to be covered.

Common mistakes

• Ordering the headings in binary (00, 01, 10, 11) instead of Gray. The map no longer has neighbors that differ in a single variable, and the groups come out wrong.
• Forming groups of 3 or 6 cells. Only powers of 2 are allowed.
• Forgetting the adjacency of the edges and of the four corners, which leaves groups smaller than necessary.
• Adding a group whose cells are all already covered by others. It is redundant and adds gates.
• Forcing yourself to cover the X's. They are used only when they enlarge a group.

Try it in the simulator

The Karnaugh map module arranges the function in Gray order, marks the groups and writes the minimal expression, so you can compare your grouping with the one the tool proposes.

1. Create a four-variable function and enter the ones from example 2.
2. Group them yourself on paper first and write down your result.
3. Look at the groups the map marks and the resulting expression; if it differs from yours, check which of your groups was not as large as possible.
4. Enter example 3, marking cells 0, 2 and 5 as X, and watch how the simplification changes when you remove those X's.
5. Convert the result to a circuit and toggle the inputs to confirm that it matches the table.

Exercises

1. Simplify F(A, B, C) = Σm(0, 2, 4, 6).
   Answer

   The columns BC = 00 and BC = 10 are neighbors across the edge and both are full. In all four cells C = 0: F = C.

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

   Corners: BD. Center block m5, m7, m13, m15: BD. F = BD + BD, which is the XNOR of B and D.

3. Simplify F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Answer

   The rows AB = 01 and AB = 11 form a group of 8; only B stays at 1. F = B.

4. A BCD digit (A is the most significant bit) must turn on an output when its value is 5 or more. Simplify F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Answer

   With the X's, the rows AB = 11 and AB = 10 form a group of 8: A. The block m5, m7, m13, m15 gives BD and the block m6, m7, m14, m15 gives BC. F = A + BD + BC = A + B(C + D).

With more than four or five variables the map becomes hard to read; for those cases there is a tabular procedure, the Quine-McCluskey method.