Karnaugh map • Hacker News Board

Re: Karnaugh map

#21

Post by mud_dauber » Sun, Dec 24, 2017, 2:39 PM UTC

filereaper wrote: post #11

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?

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

Re: Karnaugh map

#22

Post by laszlokorte » Sun, Dec 24, 2017, 2:50 PM UTC

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)

Re: Karnaugh map

#23

Post by dreamcompiler » Sun, Dec 24, 2017, 5:17 PM UTC

metahost wrote: post #4

AceJohnny2 wrote: post #2

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.

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

Re: Karnaugh map

#24

Post by dreamcompiler » Sun, Dec 24, 2017, 5:21 PM UTC

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.

Re: Karnaugh map

#25

Post by meh2frdf » Sun, Dec 24, 2017, 10:05 PM UTC

praneshp wrote: post #6

schemathings wrote: post #3

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.

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.

Re: Karnaugh map

#26

Post by AKifer » Mon, Dec 25, 2017, 9:54 AM UTC

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.

Re: Karnaugh map

#27

Post by hulkisdumb » Mon, Dec 25, 2017, 10:01 AM UTC

setoptimizer wrote: post #10

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?

Re: Karnaugh map

#28

Post by dekhn » Mon, Dec 25, 2017, 2:39 PM UTC

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...