What is a Karnaugh Veitch map?

170 views

[ad_1]

I’m studying computer science and this is one thing I can’t wrap my head around.

In: Technology
[ad_2]

So in a truth table, you’ll have something like

A | B | C | Result
—|—|—|—
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 0
1 | 1 | 1 | 1

Our goal is to come up with the simplest possible Boolean expression for describing the relationship between A, B, C, and the result. Simpler expressions require fewer conditional checks to come up with a result. In programming, that means fewer lines of code and faster processing, and in chip design, it (usually) means fewer transistors and thus a cheaper to produce chip. Simply taking each row as-is, we can write this as

Result = (A^(c)B^(c)C) | (AB^(c)C) | (ABC).

That’s 3 NOTs, 6 ANDs, and 2 ORs. Can we make this expression any shorter?


Note that, as we go from row 1 to row 2, only C is flipping its value, while A and B keep their same values. On the other hand, when switching from row 2 to row 3, both B and C flip their respective values. When multiple things change at the same time, it can be difficult to see what the underlying pattern is.

A Karnaugh map is essentially just a truth table where you’ve rearranged the rows so that only one column changes values at a time. Rearranging things in this way helps to highlight some patterns that could help us simplify the expression. For instance, we can change the previous truth table into a Karnaugh map by just exchanging a few rows:

A | B | C | Result
—|—|—|—
0 | 0 | 0 | 0
0 | 0 | 1 | 1
1 | 0 | 1 | 1
1 | 1 | 1 | 1
0 | 1 | 1 | 0
0 | 1 | 0 | 0
1 | 1 | 0 | 0
1 | 0 | 0 | 0

Now, when we move from any row to the next (even wrapping around from the last row back to the first), only one column is flipping its value at a time. Since only one element is shifting at a time, rows that rely on the same things get grouped together. For instance, this table makes it easy to see that the common factor between all of the rows with a result of 1 is that C is 1. It seems that C = 1 is necessary (though not sufficient, see row 5) to make the result 1. This tells us that we can simplify the expression down to

Result = (?)C

Now that we’ve figured out that C must be 1, we can rule out all the rows where C is 0 and look for more patterns to fill in that (?) in the expression:

A | B | Result2
—|—|—
0 | 0 | 1
1 | 0 | 1
1 | 1 | 1
0 | 1 | 0

Here, the result is always 1, except for the case A^(c)B, that is,

Result2 = (A^(c)B)^(c)

= A | B^(c), by DeMorgan’s law.

So our expression has been simplified from

Result = (A^(c)B^(c)C) | (AB^(c)C) | (ABC)

to

Result = (A | B^(c))C.

That’s an improvement from 3 NOTs, 6 ANDs, and 2 ORs to just 1 NOT, 1 AND, and 1 OR. Not bad at all.

It’s a way of deriving an expression that gives you the output you want for given inputs.

If you have a small truth table, like for an AND gate, then it is easy to deduce the Boolean expression. AB = Y

But if you have a very large truth table, it may be too difficult to determine the Boolean expression without a K map.

If you meant though that you do not understand how to use a K map, let me know and I will explain.