Quine-McCluskey in (mostly) SQL with CF QoQ

I promised in my previous post that I would go into detail on how to implement the Quine-McCluskey algorithm in ColdFusion using QoQ (Queries of Queries). I’ll try to explain QMC as I go, but it probably wouldn’t kill you to make sure you understand QMC beforehand. The QMC wikipedia article is a good introduction, but this paper by Prof. Nowick at Columbia is a more thorough explanation with better examples.

Oh, and this is going to take a while. Grab some popcorn or carrots or something.

Problem Statement:

Given a truth table, or at least the outputs of a standard truth table, generate a minimum cost boolean function (using only AND, OR, and NOT operators) that defines the outputs.

You’ll generally start off with one of two things:

Truth table: Karnaugh map:
ABCF
0000
0010
0101
0111
1000
1011
1101
1111
 AB
00011110
C00110
10111

Our first goal is to turn this into something that we can understand. If we take just the outputs of the truth table we get:

F(A,B,C) = [ 0, 0, 1, 1, 0, 1, 1, 1 ]

Or, in QMC form we can just count the positions of the 1s, starting at position zero. This will come in handy later.

F(A,B,C) = m(2,3,5,6,7)

Step 1: Generate a truth table

Our first task is to generate a truth table. We could do this iteratively, but we can also do it in SQL. Start with a single column and two rows, each for a 0 and 1. Self-join until you have enough columns. For simplicity, instead of using ABC for the column names, we’ll number them.

S1
0
1
S1S2
00
01
10
11
S1S2S3
000
001
010
011
100
101
110
111

If we add a column for our outputs (via queryAddColumn) we’ve made our truth table into a query. We really only care about the rows of the truth table that output a 1, so we can eliminate the 0 rows. We can also express each of them as a boolean expression. For each term, a 0 represents a NOT modification to the term, which we express with an apostrophe.

S1S2S3Fterm
0101A’ B C’
0111A’ B C
1011A B’ C
1101A B C’
1111A B C

Step 2: Find the prime implicants

We could use that boolean term as a primary key for the rest of the row, as each set of bits is only going to able to be represented one way. We could … but we aren’t going to. For simplicity, we’re going to cheat. We’re going to add another column to the table where the value is the current row number, and use that as the primary key.

S1S2S3Ftermrow
0101A’ B C’1
0111A’ B C2
1011A B’ C3
1101A B C’4
1111A B C5

To find the implicants, we start combining rows where there is a single bit of difference. Doing this in SQL is straightforward: join the table with itself. This is a little convoluted due to QoQ restrictions, so we actually do it 3 times and UNION the results together.

SELECT a.row AS M1, b.row AS M2, '-' AS S1, a.S2, a.S3
FROM truth AS a, truth AS b
WHERE (a.row < b.row) AND (a.S1 != b.S1) AND (a.S2 = b.S2) AND (a.S3 = b.S3)
UNION ALL
SELECT a.row AS m1, b.row AS m2, a.S1, '-' AS S2, a.S3
FROM truth AS a, truth AS b
WHERE (a.row < b.row) AND (a.S1 = b.S1) AND (a.S2 != b.S2) AND (a.S3 = b.S3)
UNION ALL
SELECT a.row AS m1, b.row AS m2, a.S1, a.S2, '-' AS S3
FROM truth AS a, truth AS b
WHERE (a.row < b.row) AND (a.S1 = b.S1) AND (a.S2 = b.S2) AND (a.S3 != b.S3)

We use M to prefix our row numbers, as we are now using them to represent a minterm. Where that one bit has changed, we mark it with a “-” instead of a 1 or 0. We’re effectively taking our binary system and turning it into a trinary system. For our truth table above, this yields:

M1M2S1S2S3
1201
1410
2511
3511
4511

Now what if we repeated the process? We’d do the exact same self-join, adding in more M columns as necessary. This time, we get:

M1M2M3M4S1S2S3
12451

Obviously we can’t go any further. We do need to back up a step, though. You can see that terms (1,2) and (4,5) were used to generate that last row. We need to go back and mark the other three rows in the first query as prime implicants — implicants that couldn’t be further combined. We’d also mark that last (1,2,4,5) implicant as prime, as it also could not be combined any further. If we threw out everything but the prime implicants we’d have:

M1M2M3M4S1S2S3term
14  10BC’
25  11BC
35  11AC
12451B

For simplicity, let’s replace all of those term references with just row numbers again:

M1M2M3M4S1S2S3R
14  101
25  112
35  113
124514

If we were to build a proper prime implicants table, it would look like the following. There’s no point in doing this in SQL, it’s just for illustration and visualization.

term M1
BC’
2
BC
3
AC
4
B
1X  X
2 X X
3  X 
4X  X
5 XXX
Query X
MR
11
41
22
52
33
53
14
24
44
54

It also turns out that the rest of the problem is much easier to solve if you flatten that query so that you have a simple list of the row references R paired with the minterms M that are part of them. I call this query “X” because it corresponds to the X marks on the prime implicants table.

We now effectively have a link table — no real meaning, just references to other data.

Step 3a: Reduce essentials

The first of the three repeatable steps is to find the essential implicants. An implicant is essential if it is the only one to reference a given minterm. That is, in our above flattened query, we want to find any cases where there is only a single M.

SELECT M
FROM x
GROUP BY M
HAVING COUNT(*) = 1
Query x
MR
11
41
22
14
24
44

This yields a single result: M=3. We’ll mark that implicant (R=3) as essential, then remove it from our working set. But there’s a trick — we want to remove not just the singled-out minterm, but also any other minterms referenced by that implicant row. That is, not just where M=3, but also anwhere R=3. In our example, that also drops the M=5 minterm, leaving us with:

Or, in prime implicants format:

term M1
BC’
2
BC
4
B
1X X
2 XX
4X X

Step 3b: Reduce row dominance

Row dominance occurs when one minterm is “covered” by another. That is, in our example above, since M=1 and M=4 are covered by the same terms, they can be said to dominate each other. Row dominance works a little backwards, in that we need to eliminate the row that has the X marks in it. In this case, however, they have the same number of X marks, so we can arbitrarily choose one to eliminate.

Really, we are looking for the row M with the highest R count where each of its R values is shared with at least one other M. In SQL, this is a multi-step process.

First, we need to get a count of the number of X marks, or R values, for each minterm, or M value. Easy:

SELECT M, COUNT(*) AS RC
FROM x
GROUP BY M
Count1
MRC
12
22
42

For our particular example, this isn’t very exciting. It just tells us that every row has two X marks. We’ll call this query Count1.

Next we need to figure out how many R coverings there are for each M. We can do this by joining our x table with itself, matching up different M values with the same R values. This yields the Count2 query:

SELECT x1.M AS leftM,
  x2.M as rightM, COUNT(*) AS RC
FROM x AS x1, x AS x2
WHERE (x1.M < x2.M) AND (x1.R = x2.R)
GROUP BY x1.M, x2.M
Count2
leftMrightMRC
121
142
241

You can interpret this as: Minterms 1 and 2 share 1 X-mark, while 1 and 4 share 2 X-marks, and 2 and 4 share 1 X-mark. We can then join this Count2 query with our Count1 query, which hold the number of X marks for each minterm M. Where the numbers match up, we know that one minterm dominates another. That is, if minterm M=1 has 2 X-marks and minterm M=4 shares 2 X-marks with minterm M=1 then minterm M=4 must dominate minterm M=1. Of course, we can see that the two actually dominate each other, so we arbitrarily pick the minterm with the highest X-count, or the highest-numbered minterm to eliminate.

SELECT Count2.rightM
FROM Count1, Count2
WHERE (Count1.M = Count2.leftM)
  AND (Count1.RC = Count2.RC)
ORDER BY Count2.RC DESC, Count2.rightM DESC
domCount
rightM
4

But here’s the tricky thing — we don’t want to eliminate too many rows at a time, because we might eliminate rows that depend on each other. To be safe, we want to only eliminate the first dominating row, then repeat this step from the beginning until we don’t find any more dominating rows. In QoQ SQL:

SELECT *
FROM x
WHERE (M != #domCount.rightM[1]#)
Query x
MR
11
22
14
24

Or, in prime implicants format:

term M1
BC’
2
BC
4
B
1X X
2 XX

Step 3c: Reduce column dominance

As you can imagine from the title, this step is pretty similar to the last one, but transposed. The only trick is that this time instead of eliminating the dominating rows, we will be eliminating the dominated columns. The queries are pretty much the same, though.

First, get our counts:

SELECT R, COUNT(*) AS CC
FROM x
GROUP BY R
Count1
RCC
11
21
42

Then get a count of intersections:

SELECT x1.leftR, COUNT(*) AS CC
FROM x AS x1, x AS x2
WHERE (x1.M = x2.M) AND (x1.R > x2.R)
GROUP BY x1.R, x2.R
Count2
leftRCC
21
41
41

Then figure out dominated columns:

SELECT Count2.leftR
FROM Count1, Count2
WHERE (Count1.R = Count2.R)
  AND (Count1.CC = Count2.CC)
ORDER BY Count2.CC DESC, Count2.R DESC
domCount
leftR
2

Again, we want to do this one at a time, then repeat the entire step until we stop reducing our working set. The first iteration eliminates R=2, then the second eliminates R=1, as both are dominated by R=4.

SELECT *
FROM x
WHERE (R != #domCount.leftR[1]#)
Query x
MR
14
24

Or, in prime implicants format:

term M4
B
1X
2X

Step 4: Repeat step 3

The series of three reductions we do in Step 3 should be repeated until you are out of X-marks. That is, until your working set X is out of records.

In our specific example, the next round of Step 3a (essentials) will catch that R=4 is the only solution to both M=1 and M=2, will mark it as essential, and leave our working set empty.

Step 5: Combine essentials

Our first iteration of Step 3 marked R=3 as essential, then the second iteration caught R=4. If we go back and look at our implicants table, we find that these translate to the terms AC and B, respectively. All we have to do now is logically-OR them together to get our minimum cost solution:

F(A,B,C) = m(2,3,5,6,7) = ((A and C) or B) = AC+B

We can double-check this with our original truth table or K-map. In this one I’ve marked the AC terms as red, the B terms as blue, and the terms covered by both as purple.

 AB
00011110
C00110
10111

Conclusions and Source Code

I think it’s pretty clear that this is a problem that is made much easier to solve through the use of sets, tables, and SQL. While ColdFusion QoQ is a little underpowered in its limitations (such as only being able to join two tables at a time, not having CASE statement support, etc) it can still get the job done. Looking at the source code for the algorithm in other languages, I find that they aren’t nearly as elegant.

I’ve posted the source code on Google Code here:

http://code.google.com/p/nowrists/source/browse/trunk/NoWriSts/logic/quinemccluskey.cfm

It’s under a Mozilla Public License, so you are welcome to do what you will with it.

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.