Subtopics to cover within Karnaugh Maps

Question

I'm adding a bit about k-maps to my processors course, but being unfamiliar with them until now, I want to check that I am covering the correct things. Here is what I am currently covering:

1. How k-maps can be created and read (up through 4 variables -- I have decided to skip the 5th variable for now)
2. The importance of the funny ordering in the axis ($00$, $01$, $11$, $10$) as a way to ensure that only one bit must be transformed to arrive at any neighboring position
3. To derive expressions from k-maps, rectangles of 1s can be of size 1, 2, 4, or 8 only.
4. How to actually derive an expression from a k-map
5. How to derive expressions from k-maps when there are undefined regions within the k-map.
6. Using k-maps to derive a Sum of Products (a.k.a. Disjunctive Normal Form) and a Product of Sums (Conjunctive Normal Form)
7. The inverse relationship between the size of a rectangle and the number of variables that define it.
8. Spotting xor values (perhaps I don't need this? It doesn't seem much emphasized in materials I've found, since they mostly focus on finding SoP and PoS)
9. k-maps wrap around, so you can make a rectangle that starts on the left edge and wraps leftwards to the right edge, or from the top and wrap upwards to the bottom.

So, should I skip xor? Is there something I should add? Am I covering the right things?

Answer 1

I am teaching part of a Maths module that includes boolean logic- the assessment included creating digital circuits, labelling each point to derive the final expression, applying boolean logic (De Morgens etc) to the expression to minimise the term (which is by far the most difficult part for learners), creating the truth table, SOP and POS, creating the K-Map and deriving the expressions, and creating the minified circuit.

After explaining the logic of each of the gates, they build some circuits using an emulator of sorts. As it happens two of the circuits are equivalent, and they result in an XOR function. Learning point 1- XOR is useful as it can replace a bunch of other gates.

As an aside, XOR could be used to rebuild a drive bit level

HD1: 0110
HD2: 1100
HD3: 1010 (HD1 Xor HD2)

so if any one drive is destroyed, the data can be rebuilt- e.g. HD2 gets fried- rebuild new drive H4

HD1: 0110
HD3: 1010 
HD4: 1100

It's an interesting and pretty cool application of XOR.

In practise XOR can yield some nice circuit reduction but learners do tend to find it difficult using XOR in minimising.

In terms of the importance if minimising, I look at the reduction in complexity and the real-life reduction in cost- number of gates and thus the number of chips, board space and layout time.

Here is a completed labelled circ from a previous assignment completed in Logisim:

Now, this can be reduced to 2 NOT gates and one OR. I should 'warn' that Logisim can generate the minified (SOP or POS) term, the K-Map and terms and generate circuits as well- which might be more than you want it to do. At worst you could use it for creating some useful examples.

Here's a board from the 1970s. It's hard to make out any gates but there is a 74LD274 (3-input NOR gates) on there- hard to read. Given that the hardware "is" the software to a large degree here, the importance of reducing complexity and chip count was important. As already pointed out- it's not as important these days, but application of logical thought is just as important in software design. An appreciation of the complexity implemented in hardware design is important, I think.

I hope this might help with linking these elements together with K-Maps, since I suspect that you also cover these other topics. As to how much focus you place on each part, you'll have to decide how much importance you place on each. I think the outline of sub-topics is pretty good.

Answer 2

What should I cover re Karnaugh maps in my processor course?

Some more context perhaps about logic minimization??

To convey the general sense and idea of minimization, karnaugh maps are fine.

But pragmatically beyond 4-5 variables they're useless. At which point you begin to need the more program oriented Quine McCluskey method

Even that runs out of steam rapidly due to combinatorial explosion — a 32 variable minimization would result in hundreds of billions on min-terms!

Leads to Espresso : strictly speaking heuristic not optimization though generally found good enough.

Should xor spotting be covered?

Dijkstra / Gries have some zany stuff on an equivalence-centered approach to logic. And equivalence is just the negation of xor. That's book length in itself!