Since we have 1s in the 0, 1, 14, 8, and 9 entries, we could present this truth table as f(A,B,C,D) = ∑m(0, 1, 8, 9, 14). This simple line conveys the entire truth table without having to draw it out. We can also use this equation to fill out our KMap. Since each cell can be referred to by its value just as the truth table rows can, we can place 1’s into the cells of our matrix as told by our minterm equation:

At this point all we have done is change how we are representing the exact same truth table. Nothing has changed, just a new way of looking at the information. We can actually derive the exact same complex equation from the introduction by simply looking at this matrix. Encode each cell who’s value is 1 as the four variables in that state, then OR the equations together. However, the Gray coding we have used allows us to do something extremely cool. We can wrap up our KMap into a torus, as any square can be warped in three dimensions:

And that gives us some extremely cool adjacency side effects. Take a look at this graphic below that shows how a KMap wrapped into a torus allows us to go around edges and still obey that only a single bit changes between adjacent cells:

From here we can start grouping similar outputs to minimize our equation. We can think about this like grouping 1’s with similar requirements. Let’s look at the 1’s in position 8 and 9 for now. We can see that they share A = 1, B = 0, and C = 0, but D can be 0 or 1! Since they are adjacent, we can actually turn that into an equation:

Think about this like constraining a box around those cells described by AB = 10 and CD = 0X, where X can be 0 or 1. This makes a box surrounding the two 1’s in 8 and 9. We can see two other easy boxes we can make, one surrounding 0 and 1, and one around 14:

The first group is represented by numbers in (), the second by numbers in [], and the third by numbers in \{}. Let’s do the same 'what’s in common' exercise from above to write out all three equations:

However, this is only part of how far KMaps can go. Since we are dealing with a torus, we can actually include the 1’s in the 0 and 1 position in the map, as they are actually adjacent via the join on the left/right edge. Because of the nature of our binary numbers and how the variables only change by 1 bit between each adjacent cells, we can draw boxes of any size where area is a power of 2. That means we can do 1, 2, 4, 8, etc square area boxes. Boxes of size 4 can be 1x4 or 2x2, as long as there are only four contained cells. The same is true of all other sizes.

This gives us many choices to circle our cells. We could actually just do 5 groups of 1 and get the same equations with the naive solution. But this obviously hasn’t simplified our equations any, and we spent all this time for nothing. So, we should follow a few simple rules:

With this knowledge in hand, let’s see if we can improve the equations we get from this KMap. We can see that the groups () and [] can actually join into one! Indeed, just looking at their equations, and using the properties of digital equations, we can see that () and [] actually eliminate the A term when OR’d together. This is supported by the KMap, as if we draw a box that wraps around the left/right edges, we see that the equations have !B and !C in common. That leaves us with the following equations:

Wow, not only are we down from five equations down to two, one of those equations only has two terms in it! Go ahead, try this yourself, these two equations, when OR’d together, yield the exact same truth table as our naive implementation at the start.

Note: It is convention that the most significant bits of your variable will appear on the columns, and the least significant bits as the rows. HOWEVER this is not required. Your equations will still be completely correct even if you transpose the table.

So we briefly touched on minterms in the previous section. We described the truth table with the equation: f(A,B,C,D) = ∑m(0, 1, 8, 9, 14). There’s an alternative way to represent a truth table, and that is to encode the location of the 0`s instead if `1`s. This is called the maxterm equation, and would appear like so for our truth table: `f(A,B,C,D) = ΠM(2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 15). We can use this to fill in the table with zeros, and all other cells have a 1. Obviously, this technique would be better used on logic equations that have more ones than zeros. Let’s take a quick peek at what this might look like:

In this case, we would have f(A,B,C,D) = ΠM(5, 7, 13, 15). Let’s put this into a KMap:

Now, if we see a KMap like this, we can either spend the time to circle all the 1’s together, which would look like this:

Which gives us three equations. But… what if we just inverted the whole thing?

This would let us derive the following equation:

Which we could invert again:

Then, using De Morgan’s law:

I know this seems a bit crazy, but try it. Use the three equations from above and the single equation we just derived. They will yield exactly the same results. Now, let’s cover the shortcut to getting here if you see a KMap with more ones than zeros. We can do the maxterm version instead, where we group zeros in the exact same way as we group ones, but instead of making sums of products (groups of AND equations OR’d together), we make products of sums (groups of OR equations AND’d together) using De Morgan’s law. Let’s try on yet another KMap:

We can circle two groups in this KMap. The () group shares B = 1 and D = 1. The [] group has A = 1, B = 0, C = 0, D = 1. However, since we are circling zeros, we must invert each of these terms and use De Morgan’s law to expand them:

Notice now how each of the smaller equations is only OR, and they are AND’d together to get our output equation. This is how you derive the Sum of Products equation from a KMap.