Karnaugh map | Hacker News Reader

Karnaugh map

en.wikipedia.org

66 pointslainon24 comments

Learned those in undergrad .. was in Chapter 1 of our textbook .. Computer System Architecture, Morris Mano. Have used it twice with great results in my career.

Morris Mano, ha! Thanks for reminding me of that author, it's been a long time.

This and Albert Paul Malvino are two of my personal favorites!

Likewise, one of the most satisfying books/subjects at uni! Thanks for giving me the name, I had wanted to revisit the book but forgot the name and author.

Came here to say exactly this, Moris Mano is a very well written book. The subject was "Logic Design". Though I now don't recall what it was for, Karnaugh Map was one of my favourite pen and paper exercises. Fond memories indeed

Thanks! I remember learning this in introductory circuit design 15 years ago, but forgot about it since. I actually needed it a few weeks ago, when I was trying to simplify a complex boolean expression in my C code :\

Quine–McCluskey algorithm might be of help to you.

ahhh memories...

QM is not as satisfyingly elegant as a Karnaugh map, but more practical in most cases. QM scales while Karnaugh maps do not.

As part of my bachelor thesis I build a tool for editing Karnaugh maps showing the map and the resulting circuit side by side:

https://thesis.laszlokorte.de/demo/kvd-editor.html

(click on the question mark icon at the top to get some brief usage instructions)

One of the things in the minority in college syllabus that gives you joy and also the realization that you are learning what you like learning.

Karnaugh maps are often made out as something special, but it's nothing more than a graphical brute-force method. Thus, useful for pen-and-paper up to 5-6 bit logic functions but no better than exhaustive testing for a computer. There seems to be little emphasis on the "why" in Computer Architecture courses.

Question for folks here who've worked on these 1 Billion+ transistor chips. How relevant is stuff like K-Maps in your day-to-day work? Is this stuff done by tools like Mentor-Graphics and Synopsis or do folks still lay this out by hand?

It depends on what you're doing. Certainly for standard design you won't be looking at Karnaugh maps. You trust the implementation tool to deal with the logic minimisation for you.

In certain cases say a piece of logic on the critical path that's preventing your design clock as fast as you want or something complex that you know requires lots of effort to meet your ppa (power, performance, area) targets, say an ALU or part of an FP unit, you'll be doing more manual optimisation. However even then you're probably not using a Karnaugh map, instead using more sophisticated techniques and then using specialised programs to do these for you (Espresso being the classic example https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_min...).

There's also things that simple logic minimisation doesn't take into account like fan out (how many things you have hanging off a particular output) and wire distance (a significant proportion of the clock cycle can be taken up in waiting for signals to propagate if the logic is spread across the chip). A hand crafted piece of logic is likely to use a mix of 'pure logic' type optimization techniques (that are simply trying to minimise logical operations) and the engineer using their judgment to work out what arrangement of minimised functions leads to the best implementation result.

Not that it's day-to-day, but my previous co is still working on a GPU-like design that uses associative memory (with KMs as basic principle) as the core processing engine. It took me forever to wrap my head around the idea.

http://www.gsitechnology.com/node/123377

I've used these together with Quinn McCluskey and Petrick's method for finding the minimal set cover of some of the problems I was facing.

Could you make the problem you were solving into a non-copyright infringing question and post it on here please?

I remember Karnaugh diagrams fondly; they were pretty much the first thing covered in my circuit design class which really made sense - and gave me the boost I needed to try to wrap my head around the rest of the curriculum, too.

Haven't designed any circuits in my career, but have on occasion used them to simplify my horribly inelegant boolean expressions before committing them to Siemens' S7 SCL.

I only took one CS class in my life, "Cybernetics" taught by David Huffman. I clearly remember karnaugh maps (25 years later) because on the final, he gave an example where you had to find a collection of 4 1s in the corners of the map (the map is symmetric on the edges/corners), and I got that one wrong. Sigh...

That was my first encounter with computers world even before I touched a real computer, playing with these maps and drawing combinatorial circuits with gates, under the guidance of an old soviet book of Mir publishers.

I remember it being quite a revelation as to how discrete digital circuits can be optimised Our Uni class execise revolved around designing a drink vending machine operation with a minimum number of logic gates.

Yeah, I have a similar recollection of lectures at college 30 years ago, and what seemed to be a hugely complex system being reduced drastically in complexity by the realisations contained within the maps. It was obviously a contrived situation that the lecturer had thought of, but there were many 'lightbulb' moments across the room in that hour.

If you visualize a Karnaugh map (more generally, a truth table) as a small tabular chunk of static RAM, that's essentially the fundamental logic gate building block of an FPGA.

Oh I remember this form my Digital Electronics course but I have never used them since then Because I haven't used actual pure combination logic since that course either.

Reply on news.ycombinator.com