K-Maps: Boolean Algebra Simplification Made Easy

2024-02-02 | By Antonio Velasco

License: Public Domain

Throughout the world of electrical engineering, one of the most prominent concepts and fundamentals you'll need to be adept at is Boolean algebra and simplification within it. In digital design, simplification is the name of the game. Logical expressions need to be simplified in order to minimize the complexity of logic circuits. K-maps are an essential and simple way to do so.

What Are K-Maps?

Karnaugh Maps, abbreviated K-Maps, are named after Indian mathematician Maurice Karnaugh. They're used as a graphical tool to simplify Boolean expressions. The visual representation makes it a lot easier to understand and will allow anybody to deal with long, complex expressions. A simplified expression means fewer gates and more efficiency with less cost for the manufacturer.

K-Map

K-Maps are organized in a grid structure like so, where each row/column represents every possible combination for the allotted variables.

For example, a Boolean function with 2 variables, A and B, will be arranged in a 2x2 grid, where each row will represent a 0 and a 1, and each column will represent a 0 and a 1. This is to show every possible combination, with A' (or A-not) and A, along with B' and B.

2x2

Moreover, if we were to have 4 variables, ABCD, we would be able to represent it in a 4x4 grid, with AB and CD representing the columns and rows. The reason for there being 4 columns and rows is to, once again, represent every combination AB, A'B, AB', A'B' for the columns, and CD, C'D, CD', C'D' for the rows.

4x4

The way that K-maps work is through utilizing common ground. We can group together certain values in order to make our Boolean expression much simpler.

For example, say that we have the expression y=AB + AB'.

kmap

We can then display it as such, with AB' and AB outputting 1's. We can now "group" the 1's, since they're representative of the same row.

example

Since we can group it, we can simply represent the expression as just that row. We end up with the expression y=A since that entire "group" can be represented with just A alone.

Let's take a look at an example with 4 variables. Let's say y = ABC' + ABC + A'BD + ABD

ex2

With this example, we can see multiple groupings. The most obvious is the group of AB, which represents an entire row. The second is the A'B and CD grouping.

ex3

Now, we just make an expression with the groups, which results in y= AB + A'BC'D + A'BCD, which can be further simplified into y= AB + A'BD. We essentially remove the C' and C from the first two expressions, and remove ABD since it can be represented with the prior.

You can also do larger groupings and overlapping groupings. We can group the entire middle 4 with this strategy.

ex4

This allows us to represent more numbers with fewer variables. With the groupings, we can now represent it as y= AB + BD. This utilizes much fewer variables and a smaller input gate for the latter. As you can see, the name of the game here is essentially to make as big of a group as possible to allow for less variables.

Variables are only "groupable" if they are directly adjacent to each other. The 4 in the middle are groupable because they fit this description, however, we cannot make an even larger group including the other two as they do not meet the requirement, nor can they be represented with a Boolean expression.

Conclusion

As the number of variables increases, k-maps become increasingly less efficient. They are extremely efficient and important, however, when working with a low amount of variables. They've revolutionized the way that we look at digital design and optimize our circuits. It's extremely intuitive and allows for anybody to streamline the process.