Quine-McCluskey logic algorithm in CF

One of my courses this semester (only one more semester to go, yay!) is on Digital Logic. It’s a fun course, as it essentially boils down to doing a whole bunch of repeatable procedures and optimization. If you’ve ever sat in an airport with a book of logic puzzles, you’d do well in the course.

Of course, the primary focus of the first half of the course has been on small circuit optimization. You are given a function table that describes the set of outputs for every possible given input, like so:

Input AInput BOutput F
000
011
101
110

Given a basic set of AND, OR, and NOT gates/operators, there’s a function F that describes that set of inputs and outputs. Not only that, but in most cases there’s a single minimum cost function — one with the least number of operations.

Circuits with up to 4 inputs are easily and quickly done by hand with pencil and paper with Karnaugh maps. Beyond 4 and it starts to get tricky, eventually becoming soul-crushingly complex.

But it turns out that you can cheat. A pair of really smart guys came up with an algorithm for solving it procedurally: the Quine-McCluskey Algorithm. There are really only three steps to the algorithm, which you repeat over and over until your problem space stops getting smaller. It turns out that it still doesn’t quite give perfect answers, so if you don’t want to do the last bit of grunt work by hand, there’s another algorithm for the last part: Petrick’s Method.

While Petrick’s method is tricky to code, it turns out that QMC is dead simple. Notice how that thing above looks an awful lot like a query result set? Yeah. It’s solvable with set math — meaning that you can use SQL queries to do it.

I spent some time today hacking together a working ColdFusion version of the QMC algorithm and it turns out that you can do it without a single line of iterating code. That is, it’s just a bunch of SQL queries in a loop. Better yet, even with QoQ’s limited vocabulary, you can do it all in QoQ. So, in theory, you could use ColdFusion to build digital circuits!

I’ll post some code soon, but I figured the real propellerheads among you might appreciate that.

Published by

Rick Osborne

I am a web geek who has been doing this sort of thing entirely too long. I rant, I muse, I whine. That is, I am not at all atypical for my breed.