Standard forms for Karnaugh maps?

A -----\

A -----\

=A0/- B -\

I didn't think that anyone still used Karnaugh maps for programmable logic.

Leon

Is this homework ? The design is not usually going to stay on paper, it has to end up in silicon. That makes most of this irrelevent.

-jg

I did my last "homework", as you put it, 28 years ago, in Quantum Mechanics.

There's a common misconception that K-maps are/were only used for minimisation, so they're now irrelevant. Actually, K-maps are probably the most fundamental tool for the design, specification, and analysis of combinatorial logic. They're also independent of the implementation, which makes them ideally suited for verification of the same circuits. They're about 'what', not 'how'. An HDL description, on the other hand, is exactly the opposite - 'how', not 'what'. As I said originally, this is about verification. The fact that the K-map may or may not end up in silicon is "irrelevant".

Leon asked whether anyone still used K-maps for programmable logic; a good question, without being condescending. I don't imagine many people use them to fill up FPGAs. On the other hand, I'm sure there are still people in this NG who do digital logic design, and some of them may occasionally even do non-trivial combinatorial logic.

I'm still trying to get a handle on the 'why' ?

Do you mean actual FET level logic ? Even at the lowest combinatorial logic, I still look at the tools output, and often they do eqn invert, or do D/T/XOR synthesis swapping in order to pack things more efficently.

-jg

The last time I did Karnaugh maps was in an attempt to get 8b10b encoding into a CPLD. In this case I also had more than 4 inputs and I have to say that human interaction with such maps is not easy no matter how you slice it. This is like trying to envisage objects with more than 3 dimensions. However to answer the original question, the fact that 'B' lines up left in one map and right in the other is useful if you view them side-by-side as in your post, rather than stacked up as in a 3D viewer.

Still an explanation of the end use of this would be interesting...

Regards, Gabor

It's been 30 years since I've used Karnaugh maps, they were useful when the 7400 was state of the art and every gate counted. In that era logic was necessarily simple so a tool that could minimize a four input equation was helpful. However as you must have figured out by now, Karnaugh maps don't scale well. When the first widely used programmable logic was introduced, PALs, the Karnaugh maps largely disappeared. PALs had to many terms, 20, for a Karnaugh map to be usable. When FPGAs were introduced they were based on 4 input LUTs. The LUT is universal logic so there is no point in doing any minimization on the scale that Karnaugh maps are useful. What's more modern synthesis tools handle logic minimization on a scale that is simply not possible by a human being. The kinds of optimizations that are still done by hand are also in a class that is outside of the domain of Karnaugh maps, to be specific the kind of things that are done by hand are deciding what terms can be moved to a synchronous set or reset instead of the main equation, or figuring out what portion of an equation can be calculated in an earlier pipeline stage. Those are time optimizations not logic optimizations, i.e. they require knowledge of what's known when and what's nearby and what's far away.

All very true, but Evan's question was explicitly targetted toward people who USE K-maps ("If you use K-maps, which version do you prefer..." from the original post) and his reasons had to do with verification not design (later post).

I don't think he was looking for responses from people who don't use K-maps while they are not doing verification.

KJ

To answer that question, the Logic minimisation I use, is that built into the tools, which will include the tools version of K-Maps, and others as well. ie the REPORT files are closely scrutinised.

It is common to look at the tool output, and recode the source, and sometimes we have taken one tools output, and pasted into another as source code.

Sometimes, the choices made within the tools surprises, and sometimes it disappoints....

Where the tools have a blind spot is in 'node creation' to reduce total mapped logic (at the expense of some speed). Understandable, as that is a LOT more variables in the air.

Sometimes the designer has to help there.

It's a matter of matching the degrees of freedom, to the tools IQ.

In Xilinx flows, fastest and smallest switches sometimes seem to work backwards :)

-jg

Evan, In John F. Wakerly's "Digital Design, Principles and Practices",

4th Edition, pgs 235-236,564 (there is also a 5th edition) uses your second version (the historical one) of 5/6-variable map for logic minimization exercises and FSM synthesis. Of course, mathematically, either one works. alan

I rarely use a K map for "logic minimization". Once I got out of school (some 22 years ago), about the only thing I used them for was for state-code assignments in state machines with unsynchronized inputs (guaranteeing gray-code state transitions on those inputs), and for P-term minimization when using PALs (choosing state assignments to minimize branches into states with bits set). With modern FPGAs in most cases, if you are designing at the k-map level, you are not taking maximum advantage of the tools. Specifying design behavior at higher levels of abstraction often leads to correspondingly higher levels of optimization. But not always...

Another advantage of using higher levels of abstraction is in debugging and verification. State transition optimization to avoid an extra register for input synchronization may have been a good idea when an entire device had only 8 or 10 registers. But when extra registers are so darn cheap in an FPGA, it is foolhardy, and not nearly as easily verified by inspection as simply burning another register to synchronize the input.

Andy

Thanks. And thanks to those who gave me an opinion without an accompanying lecture on logic minimisation.

The 'why' is not very interesting - basically feature creep. I have a verification tool which allows usage of multi-dimensional arrays. It occurred to me that, with a couple of hours fiddling, I could modify the array indexing so that you could convert an array initialiser into a K-map:

// f is a 5D array, but the 'kmap' declaration handles the complexity

kmap f = 0 1 1 0 1 0 1 0 // uses reflected-binary addressing, 1 1 0 0 0 0 1 1 // not "C-style" addressing 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0; ... x = f[A,B,C,D,E]; // compute a function of 5 vars

Not Earth-shattering, but potentially useful to people who still do combinatorial logic design, although there can't be many of them left. Nothing to do with minimisation, but presumably those people will have a preferred array layout which was originally derived from minimisation principles. I didn't want to impose reflected-binary addressing on them if another form was preferable.

-Evan

Yes, my copy of Lewin ("Logical Design of Switching Circuits") does the same. I suspect that teaching material does this because it's easier to visualise, where the more academic approach may be the reflected-binary version.

Thanks

Evan

That may have been true at one time, but it's not true any longer. Aside from my own experience, I know quite a few digital designers, and most have not used a K-map since school.

That entirely depends on how you write the HDL. It's possible and not even all that uncommon to write behavioral HDL that specifies what is desired, and let the synthesizer decide how to implement it.

In VHDL one way to do that is to use conditional assignment statements, e.g.,

Q