5 ms·
Karnaugh map
- AceJohnny2 9y agoThanks! 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 :\
- metahost 9y agoQuine–McCluskey algorithm might be of help to you.
- wiz21c 9y agoahhh memories...
- dreamcompiler 9y agoQM is not as satisfyingly elegant as a Karnaugh map, but more practical in most cases. QM scales while Karnaugh maps do not.
- schemathings 9y agoLearned 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.
- praneshp 9y agoMorris Mano, ha! Thanks for reminding me of that author, it's been a long time.
- vishnugupta 9y agoCame 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
- B4TMAN 9y agoI think it was supposed to minimize the number and kind of logic gates that would be required to build function.
- deleted 9y ago[deleted]
- lb1lf 9y agoI 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.
- manojlds 9y agoOne 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.
- setoptimizer 9y agoI'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.
- hulkisdumb 9y agoCould you make the problem you were solving into a non-copyright infringing question and post it on here please?
- filereaper 9y agoQuestion 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?
- gchadwick 9y agoIt 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_minimizer 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.
- mud_dauber 9y agoNot 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 http://www.gsitechnology.com/node/123377
- martyvis 9y agoI 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.
- djaychela 9y agoYeah, 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.
- kbwt 9y agoKarnaugh 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.
- stefanpie 9y agoOh 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.
- laszlokorte 9y agoAs 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 https://thesis.laszlokorte.de/demo/kvd-editor.html (click on the question mark icon at the top to get some brief usage instructions)
- dreamcompiler 9y agoIf 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.
- AKifer 9y agoThat 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.
- dekhn 9y agoI 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...