K-Map

Karnaugh Map (K-Map)
A Karnaugh Map is a method of mapping truth tables onto a matrix that identifies places where two or more different combination of the input variables yield the same result. In addition to identifying redundant terms, the K map also cancels them, leaving only the minimized Boolean algebra expressions that will yield the same truth table outputs as the unreduced terms. The best way to understand K maps is to go through an actual simplification process using a K map.

We will start with a three variable truth table. Three variables have 2 to the 3'd, or 8 possible combination of 1’s and 0's. This means that the K map must have 8 cells, one for even possible combination of input variables. The input variables can be mapped in any order on the K map, but it must follow the same organization as the truth table being mapped. We will assign the letters R, S, & T to the input variables of our truth table, and X to the output.

The Karnaugh map is laid out so that from cell to cell and from edge to edge, there is only a one bit change in the variables at any given time. This accounts for the column to column and row to row order of 00 01 11 10 (Gray Code). The column variables are assigned across the top of
the map, and the row variables are assigned to the left side of the map. Each cell contains the result of the variables for the binary combination given by the intersecting row and column. If the column variables are R S and the row variables are T U for a 16 cell or four variable map, the combination 0 1 1 0 is the same as (not R S T not U) or cell 6. If the truth table shows a 1 for the output at the position 0 1 1 0, then the Karnaugh map will contain a 1 in that particular cell.

As an example, Let's simplify the 3 bit K map above. Notice the four three variable expressions reduce down to three two variable expressions. This is a substantial savings in circuitry, and the equation will do exactly the same thing as the original unsimplified expression from the truth table.

The same method applies to larger K maps of 4, 5, and 6 variables. Four variable K maps have sixteen cells, since 2 to the 4 is 16. Five variable K maps are mapped as two, sixteen cell maps side by side. It is like mapping one map above the other, with the same numbered cells being redundant. Six variable K maps result in four, sixteen cell maps together in a square pattern. Top to bottom and side by side, redundancies are cancelled in the same numbered cells. More than four variable K maps are rarely used because they are more difficult to follow without getting lost.

Posted in: Digital Electronics