Okay, Quine-McKluskey is the name of an algorithm taught in Digital Logic.

Electronics Engineers prolly should remember it... it is sometimes called the 'tabulation method.'

Basically, it gets a set of 'minterms', and tabulates it and eventually comes up with the 'best' digital logic function to generate it - best as in least number of gates (assuming, anyway, that your gates are only AND and OR gates, no XOR gates).

This was put together in a few days by me 'cause I needed to use this for a project.... it was 7 bit inputs, 14 bit outputs.... no WAY I would do that by hand...

(minterms - in digital logic, a minterm is a condition in which your function outputs a 1. For a ridiculously simple example, let us say that your function needs to see if a number is odd. So your function gets a 1 at 1, 3, 5, 7, etc. So there are minterms there.)
Posted on 2003-03-25 04:20:09 by AmkG
is this ECE421?? i forgot :grin:
Posted on 2003-03-25 20:24:36 by flotsam
Fun fun,

I've actually had to do a few dozen of these by hand over the past few weeks... sure beats the heck out of trying to do > 5 variable k-maps... although I never gave much thought to what sort of logic would be required to implement this in a algorithm...


Anyhow, was there supposed to be code accompanying this post? Or did I miss something?

-----
Domain
Posted on 2003-03-25 23:17:11 by Domain
Ah, crick.

I musta forgot to attach it.

Can't attach it now, I'm at univ.
Posted on 2003-03-25 23:47:26 by AmkG
This is an interesting problem and also a version including XOR would be awesome for parallel bit processing with MMX registers. He are some links I'm reading:

http://www2.ele.ufes.br/~ailson/digital2/cld/CLD.html (section 2.4)
http://logik.phl.univie.ac.at/~chris/qmo-uk.html (cool solver script :))
http://www.seattlerobotics.org/encoder/200106/qmccmin.htm (BASIC source code)
Posted on 2003-03-26 00:30:20 by bitRAKE
Here it is AT LAST!

Oh and yeah flotsam: it's Comp 421/304 to us... the curriculum has been changing....
Posted on 2003-03-26 19:01:14 by AmkG