Karnaugh Map (K-map): Introduction

Computers use 1’s and 0’s to read and run programs. We, as engineers or scholars, sometimes need to double check “computer language.” It’s easy to get lost in 1’s and 0’s. The K-map is a useful tool to help make sense of boolean functions. This is K-maps, explained.

To understand K-maps, Let’s take a look at truth tables. Truth tables are tables that have inputs and outputs. We’ll use a simple 2-input, 1-output function as an example.

You might recognize this as an XOR function

Here, a and b are inputs, and f is an output. f outputs 1 if either a or b are 1, but not both. Let’s translate this truth table to a K-map.

In K-maps, the inputs are the rows and columns of the table. The outputs are the 0’s and the 1’s in the table. For example, it’s easy to see that when a is 1 and b is 0, the output is 1 (marked in red).

It’s easy to see from the output of the function that this is an Exclusive OR function (XOR function), which we can write as a⊕b. So why do we need K-maps? Let’s take a look at a slightly more complex example, a 4-input function.

Here, it’s difficult to tell exactly how to represent this function. If we try writing it out in the boolean function as it is now, it would be a’b’c’d’ + a’b’cd’ + a’b’cd + a’bcd + ab’c’d’ + ab’c’d + ab’cd’ + ab’cd + abc’d + abcd = f.

Let’s try translating the truth table into a K-map. To draw the K-map, we need to draw our rows and columns inputs only 1 bit apart. In other words, we can’t just “jump” from drawing 01 to 10. We go in the order of 00, 01, 11, 10.

Then, we can just populate the K-map. (When you’re doing this, be careful of the order. Again, the order of the rows and columns are 00, 01, 11, 10.)

Now comes the useful part of K-maps. We can “cover” the largest chunks of the K-map by circling out the largest areas of 1’s. Note that the regions must be in powers of 2. So here, a region has to be a size of 1, 2, 4, or 8.

Each colored region marks a different circled region. The largest regions are in groups of 4. Additionally, some of the regions can “wrap around”: note the orange and blue regions.

Then, we can remove the “extra” blue and red regions.

Finding the right regions Reduce-Expand-Irredundant Loop method. There is a famous tool called ESPRESSO that can calculate this two-level minimization. The specifics are beyond this guide, but for most 4-input functions, the regions are relatively easy to spot.

We can then extrapolate a simpler boolean function: b’d’ + cd + ad = f. This is a much simpler representation of our function from before.