Facebook
Google
GitHub
LinkedinDigital Circuits
Karnaugh Mapping
17 questions By Tony R. Kuphaldt
-
Question 7 of 17
One of the essential characteristics of Karnaugh maps is that the input variable sequences are always arranged in Gray code sequence. That is, you never see a Karnaugh map with the input combinations arranged in binary order:
The reason for this is apparent when we consider the use of Karnaugh maps to detect common variables in output sets. For instance, here we have a Karnaugh map with a cluster of four 1’s at the center:
Arranged in this order, it is apparent that two of the input variables have the same values for each of the four “high” output conditions. Re-draw this Karnaugh map with the input variables sequenced in binary order, and comment on what happens. Can you still tell which input variables remain the same for all four output conditions?
Reveal answer
Looking at this, we can still tell that B = 1 and D = 1 for all four “high” output conditions, but this is not apparent by proximity as it was before.
Notes:You could simply tell your students that the input variables must be sequenced according to Gray code in order for Karnaugh mapping to work as a simplification tool, but this wouldn’t explain to students why it needs to be such. This question shows students the purpose of Gray code sequencing in Karnaugh maps, by showing them the alternative (binary sequencing), and allowing them to see how the task of seeking noncontradictory variables is complicated by it.
-
Question 8 of 17
Examine this truth table and corresponding Karnaugh map:
Though it may not be obvious from first appearances, the four “high” conditions in the Karnaugh map actually belong to the same group. To make this more apparent, I will draw a new (oversized) Karnaugh map template, with the Gray code sequences repeated twice along each axis:
Fill in this map with the 0 and 1 values from the truth table, and then see if a grouping of four “high” conditions becomes apparent.
Reveal answer
Follow-up question: what does this problem tell us about grouping? In other words, how can we identify groups of “high” states without having to make oversized Karnaugh maps?
Notes:The concept of bit groups extending past the boundaries of a Karnaugh map tends to confuse students. In fact, it is about the only thing that tends to confuse students about Karnaugh maps! Simply telling them to group past the borders of the map doesn’t really teach them why the technique is valid. Here, they should see with little difficulty why the technique works.
And, if for some reason they just can’t visualize bit groups past the boundaries of a Karnaugh map, they know they can just draw an oversized map and it will become obvious!
-
Question 9 of 17
A student is asked to use Karnaugh mapping to generate a minimal SOP expression for the following truth table:
A B C Output
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Following the truth table shown, the student plots this Karnaugh map:
“This is easy,” says the student to himself. “All the ‘1’ conditions fall within the same group!” The student then highlights a triplet of 1’s as a single group:
Looking at this cluster of 1’s, the student identifies C as remaining constant (1) for all three conditions in the group. Therefore, the student concludes, the minimal expression for this truth table must simply be C.
However, a second student decides to use Boolean algebra on this problem instead of Karnaugh mapping. Beginning with the original truth table and generating a Sum-of-Products (SOP) expression for it, the simplification goes as follows:
$$\overline{A}BC+A\overline{B}C+ABC$$
$$BC(\overline{A}+A)+A\overline{B}C$$
$$BC+A\overline{B}C$$
$$C(B+A\overline{B})$$
$$C(B+A)$$
$$AC+BC$$
Obviously, the answer given by the second student’s Boolean reduction (AC BC) does not match the answer given by the first student’s Karnaugh map analysis (C).
Perplexed by the disagreement between these two methods, and failing to see a mistake in the Boolean algebra used by the second student, the first student decides to check his Karnaugh mapping again. Upon reflection, it becomes apparent that if the answer really were C, the Karnaugh map would look different. Instead of having three cells with 1’s in them, there would be four cells with 1’s in them (the output of the function being “1” any time C = 1:
Somewhere, there must have been a mistake made in the first student’s grouping of 1’s in the Karnaugh map, because the map shown above is the only one proper for an answer of C, and it is not the same as the real map for the given truth table. Explain where the mistake was made, and what the proper grouping of 1’s should be.
Reveal answerProper grouping of 1’s in the Karnaugh map:
Notes:The purpose of this question is to illustrate how it is incorrect to identify clusters of arbitrary size in a Karnaugh map. A cluster of three, as seen in this scenario, leads to an incorrect conclusion. Of course, one could easily quote a textbook as to the proper numbers and patterns of 1’s to identify in a Karnaugh map, but it is so much more informative (in my opinion) to illustrate by example. Posing a dilemma such as this makes students think about why the answer is wrong, rather than asking them to remember seemingly arbitrary rules.
I am studying for my midterms, and this helped me a lot. The author is trying to share the information through pure comprehension, explaining the origin and target of each and every rule, which most teachers tend not to do… Thank you so much !!
question 16 circuit is not fully simplified