K-maps: Supplementing From Nand2tetris

This geeky philomath, always hungry to learn more, is currently tackling the From Nand to Tetris course to learn about building computers from first principles. Being highly curious and from a non-traditional background, this course has been highly recommended by a number of mentors and peers to gain a deeper understanding of how computers are built and work. During Project One, I was struggling with some of the more complex gates, namely Mux. The additional input(s) were hard for me to wrap my head around. Then my mentor and colleague introduced me to K-maps.

K-maps or Karnaugh maps are tools for simplifying boolean (true/false) logic. They take advantage of our ability to recognize patterns and quickly find the minimum logic gate (and/or/not) solutions that implement the function. It works by identifying truth-y values that can be anded together into groups which can be ored together to implement our solutions. It is another tool similar in use to a truth table. There are many fields that utilize boolean logic, but this article is written with a focus on how it is used in the field of computer science. If you’d like an overview of these topics, you can read more about boolean logic and logic gates here, or read chapter one from the From Nand to Tetris book, The Elements of Computing Systems¹.

The structure of setting up a Karnaugh map is pretty straightforward. The number of rows/columns needed are dependent on the number of variables. K-maps lend themselves most usefully to 3–4 variables or inputs. It is possible to create K-maps with more variables, but we will start with simple examples for understanding the basics first.

Let’s say we have a function with 3 inputs: a, b, s. The function might be something like:

if s == 0
  out = a
else
  out = b

The truth table for that would be:

|   a   |   b   |   s   |  out  |
|-------|-------|-------|-------|
|   0   |   0   |   0   |   0   |
|   0   |   0   |   1   |   0   |
|   0   |   1   |   0   |   0   |
|   0   |   1   |   1   |   1   |
|   1   |   0   |   0   |   1   |
|   1   |   0   |   1   |   0   |
|   1   |   1   |   0   |   1   |
|   1   |   1   |   1   |   1   |

The K-map for this will condense this rather large truth table and help us see the patterns that will allow us to simplify the logic of this function by showing us grouped truth-y results that we can or together to get the outputs we want.

The set up of the K-map will group the aand b inputs together as the rows, the s variable will be the columns:

The 3 variable K-map structure

A few notes on the structure:

• There are two columns for s, and four rows for a and b, because each of these variables can be true (1) or false (0). So, the columns read from left to right as not s , s and the rows read from top to bottom as not a and not b , not a and b , a and b , a and not b
• When counting in binary, the count would normally be 00 , 01 , 10 , and 11 however, for the K-map, we want our truth-y values for each input adjacent to each other, so we switch the ordering of the last two.
• The variables are logically anded together to create the output.

Then we will fill in the table with the outputs. The outputs can be read from the truth table:

The 3 variable K-map with outputs

The top left output grid is the output for when a is 0 (false, or not a), b is 0 (false or not b) and s is 0 (false or not s). The top right grid is also when a and b are 0 (false or not a, and not b), but s is 1 (true, s). Can you see the patterns already?

Now, we group the truth-y values that are next to one another.

The 3 variable K-map with truth-y value groups circled

Somethings to note:

• The table wraps, so if there would have been a truth-y value for the output of the top left cell of the grid (top of the s0 column), that would have wrapped to join the group created at the bottom left cell (bottom of the s0 column).
• These groups are ored together for the final solution.
• I represented the truth-y value groups in two colors — blue and purple. Only the purple ones will need to be written for the implementation, as the blue group is overlapped by the purple groups, so including the blue grouping would be redundant. We can even check the logic of this and see that two of the results would be repeated².
• I represent negated values with a !, anded values are placed adjacent to each other, and ored values have a | between them.

All together the long notation for the results would look something like:

!a b s  |  a b s  |  a b !s  |  a !b !s

but if we look at that closely, and know our logic laws, we can see that this could be simplified. Taking the left two values, !a b s | a b s , the a and !a cancel each other out, leaving just b s and likewise for the second two, the b cancels out leaving just a !s. So, our final and simplified implementation solution is: notated as b s | a !s , or (b and s) or (a and not s) or !

We can double check this by proving it with a truth table and comparing the original output values (out, in the middle of the table) to the kmap’s ored groups. This is done by anding b and s in one column, and anding a and not s in another column and then oring them in the last column:

|   a   |   b   |   s   |  out  |  b s   |  a !s  |  b s | a !s  | 
|-------|-------|-------|-------|--------|--------|--------------|
|   0   |   0   |   0   |   0   |   0    |   0    |      0       |
|   0   |   0   |   1   |   0   |   0    |   0    |      0       |
|   0   |   1   |   0   |   0   |   0    |   0    |      0       |
|   0   |   1   |   1   |   1   |   1    |   0    |      1       |
|   1   |   0   |   0   |   1   |   0    |   1    |      1       |
|   1   |   0   |   1   |   0   |   0    |   0    |      0       |
|   1   |   1   |   0   |   1   |   0    |   1    |      1       |
|   1   |   1   |   1   |   1   |   1    |   0    |      1       |

We now have a nice, clean and reduced equation for this function. This is important for computer science because simpler equations translate into simpler circuits which use fewer wires and are more efficient.

1. There is also a coursera course for the first half of the book.

1. “not a, and b, and s”, which can be notated as: !a b s (purple row 2, col 2),

2. “a and b and s”, which can be notated as: a b s (purple row 3, col 2 and blue row 3 col 2) which means this is repeated,

3. “a and b and not s”, which can be notated as: a b !s (purple row 3, col 1 and blue row 3 col 1) which means this is repeated,

4. “a and not b and not s”, which can be notated as: a !b !s (purple row 4 col 1),