My favorites | Sign in
Project Logo
Project Home
  
Downloads
  
Wiki
  
Issues
  
Source
    
Checkout | Browse | Changes |
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
 
<cfsetting enablecfoutputonly="Yes" requesttimeout="15">
<!---
	logic/quinemccluskey.cfm
	Use the Quine-McCluskey algorithm to generate a boolean expression for a set of function outputs.
	Original Code by Rick Osborne, Oct/Nov 2008.
	Based on algorithms described in:
	  http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
	  http://www1.cs.columbia.edu/~cs4861/handouts/quine-mccluskey-handout/
	
	The contents of this file are subject to the Mozilla Public License
	Version 1.1 (the "License"); you may not use this file except in
	compliance with the License. You may obtain a copy of the License at
	http://www.mozilla.org/MPL/
	Software distributed under the License is distributed on an "AS IS"
	basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
	License for the specific language governing rights and limitations
	under the License.

	DO NOT USE THIS CODE IF YOU DO NOT UNDERSTAND THE LICENSE.
--->

<cfparam name="URL.f" default="">
<cfset f=reReplace(lCase(URL.f),"[^01x]+","","ALL")>

<cfoutput><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html lang="en">
<head>
<title>Digital Logic</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
</head>
<body>
<h1>Digital Logic</h1>
<form action="#cgi.script_name#" method="get">Enter your function outputs (0,1,x): <input type="text" size="32" maxlength="255" name="f" id="f" value="#htmlEditFormat(f)#"/></form>
<p>Examples: 0x11000101x1010x, 0110, 000010001x1110x1, 1010011110101111, 10101011101111101011000000000110</p>
</cfoutput>

<cffunction name="bitTable" output="true" returntype="query" description="Make a query/table of every possible binary combination of the given number of inputs">
	<cfargument name="inputCount" type="numeric" required="true">
	<cfargument name="outputs" type="array" required="true">
	<cfset var i=0>
	<cfset var j=0>
	<cfset var bits="">
	<cfset var twoRows=queryNew("M1,S1","CF_SQL_INTEGER,CF_SQL_VARCHAR")>
	<!--- Start with a 2-row table: one for 0 and one for 1 --->
	<cfset queryAddRow(twoRows)>
	<cfset queryAddRow(twoRows)>
	<cfset querySetCell(twoRows, "S1", "0", 1)><!--- S columns are strings, as the might end up being "x" (don't care) --->
	<cfset querySetCell(twoRows, "S1", "1", 2)>
	<cfset querySetCell(twoRows, "M1", 0, 1)><!--- M columns are numbers, and become the number of the minterm --->
	<cfset querySetCell(twoRows, "M1", 1, 2)>
	<cfset bits=twoRows>
	<cfloop from="2" to="#Arguments.inputCount#" index="i">
		<!--- Repeatedly join our result table (b) with our 2-row table (twoRows) --->
		<cfquery name="bits" dbtype="query">
		SELECT
		  <cfloop from="1" to="#decrementValue(i)#" index="j">bits.S#j# AS S#incrementValue(j)#,</cfloop><!--- New S column for each input/output --->
		  twoRows.S1 AS S1,
		  (twoRows.M1 * #int(2^(i-1))#) + bits.M1 AS M1 <!--- Through the magic of math, this counts from 0 to (inputs-1), or, equals (currentRow-1) --->
		FROM twoRows, bits
		</cfquery>
	</cfloop>
	<!--- Tack on our function outputs --->
	<cfset queryAddColumn(bits,"F","CF_SQL_VARCHAR",arguments.outputs)>
	<cfreturn bits>
</cffunction>

<cffunction name="getImplicants" returntype="query" description="Given a set of function inputs and outputs, figure out which are the implicants (necessary)">
	<cfargument name="originalImplicants" type="query" required="true">
	<cfargument name="varCount" type="numeric" required="true">
	<cfargument name="recursionLevel" type="numeric" required="false" default="1">
	<cfset var ret=""><!--- Our return variable --->
	<cfset var originalRef=originalImplicants><!--- A reference so that we can self-join --->
	<cfset var implicants=""><!--- The result of a recursive call --->
	<cfset var i=0>
	<cfset var j=0>
	<cfset var comboSize=arguments.recursionLevel>
	<cfset var bitCount=comboSize*2>
	<cfset var nonprime="">
	<cfset var colNames="">
	<cfset var result="">
	<cfset var mCount=0>
	<!---
	Yay for recursion!
	Long story short:
	Given the short list of minterms that we care about (F=1 or F=x), find
	  prime implicants by combining minterms that are a single-bit different.
	For example: combine 1000 and 1010 to yield 10-0.
	The dash essentially becomes a third bit type. ("trit"?)
	Repeat this until no more combinations are possible.
	--->
	<cfif not isNumeric(comboSize)><cfset comboSize=1></cfif>
	<!--- 
	We join the implicant table with itself, looking for a single mismatch.
	We loop over each position, looking for a mismatch in that position and a
	  match in all others, then UNION them all together.
	--->
	<cfquery name="ret" dbtype="query">
	<cfloop from="1" to="#arguments.varCount#" index="i">
	<cfif i gt 1>UNION ALL</cfif>
	SELECT
	  #comboSize# AS L, originalImplicants.F,
	  <cfloop from="1" to="#comboSize#" index="j">originalImplicants.m#j# AS m#int((2*j)-1)#, originalRef.m#j# AS m#int(2*j)#, </cfloop>
	  <cfloop from="1" to="#arguments.varCount#" index="j"><cfif j eq i>'-'<cfelse>originalImplicants.S#j#</cfif> AS S#j#<cfif j lt arguments.varCount>, </cfif></cfloop>
	FROM originalImplicants, originalRef
	WHERE
	  <cfloop from="1" to="#arguments.varCount#" index="j"><cfif j gt 1> AND </cfif> (originalImplicants.S#j#<cfif j eq i>!</cfif>= originalRef.S#j#)</cfloop>
	</cfloop>
	</cfquery>
	<!---
	We'll get results like (1,2,3,4) and (4,3,2,1), which are the same,
	  so filter it down to just the ones in increasing sequence.
	--->
	<cfquery name="ret" dbtype="query">
	SELECT *
	FROM ret
	WHERE (m1 < m2) <cfloop from="3" to="#bitCount#" index="i">AND (m#int(i-1)# < m#i#)</cfloop>
	ORDER BY m1 <cfloop from="2" to="#bitCount#" index="i">, m#i#</cfloop>
	</cfquery>
	<!--- We use each row number as a primary key to make the joins less hairy --->
	<cfset ret=makeRowNumbers(ret)>
	<cfif ret.recordCount gt 0>
		<!--- If we are able to combine implicants, try to further combine them --->
		<cfset implicants=getImplicants(ret,arguments.varCount,bitCount)>
		<cfif implicants.recordCount gt 0>
			<!---
			We need to mark which implicants were NOT able to be further combined.
			These are "prime" implicants, which we'll keep later.
			--->
			<cfset colNames="implicants." & listChangeDelims(reReplaceNoCase(implicants.columnList,"^[^m,]+|,[^m,]+","","ALL"),", implicants.")>
			<cfset mCount=listLen(colNames)>
			<!--- Look for implicant row numbers that WERE combined (have all minterms in a result row) --->
			<cfquery name="nonprime" dbtype="query" result="result">
			SELECT DISTINCT ret.r
			FROM ret, implicants
			WHERE <cfloop from="1" to="#bitCount#" index="i"><cfif i gt 1> AND </cfif>(ret.m#i# IN (#colNames#))</cfloop>
			</cfquery>
			<cfset colNames=listChangeDelims(reReplaceNoCase(ret.columnList,"^P,|,P","","ALL"),", ret.")>
			<!--- All of the matching non-prime rows are marked P=0, and the others are marked P=1  --->
			<cfquery name="ret" dbtype="query">
			SELECT ret.#colNames#, 0 AS P
			FROM ret, nonprime
			WHERE (ret.r = nonprime.r)
			UNION
			SELECT ret.#colNames#, 1 AS P
			FROM ret
			WHERE (r NOT IN (0#valueList(nonprime.r)#))
			</cfquery>
			<!--- We're going to want to return both our own implicants, and the ones we got recursively, in a single result --->
			<cfset colNames=reReplaceNoCase(ret.columnList,"^[RP],|,[RP]","","ALL")>
			<cfquery name="ret" dbtype="query">
			SELECT #colNames#, P <cfloop from="#incrementValue(bitCount)#" to="#mCount#" index="i">, -1 AS m#i#</cfloop>
			FROM ret
			UNION ALL
			SELECT #colNames#, <cfif not isDefined("implicants.p")>1 AS</cfif> P <cfloop from="#incrementValue(bitCount)#" to="#mCount#" index="i">, m#i#</cfloop>
			FROM implicants
			</cfquery>
		</cfif>
	<cfelseif comboSize eq 1>
		<!--- If we couldn't combine anything, and we never got further in, just return the original dataset, all marked as prime --->
		<cfset colNames=reReplaceNoCase(originalImplicants.columnList,"^P,|,P","","ALL")>
		<cfquery name="ret" dbtype="query">
		SELECT #colNames#, 1 AS P
		FROM originalImplicants
		</cfquery>
	</cfif>
	<cfif comboSize eq 1>
		<!--- If we are just about to return the final result set to the original caller, eliminate all of the stuff we added, and return only the prime, do-care rows --->
		<cfset colNames=reReplaceNoCase(ret.columnList,"^[PR],|,[PR]","","ALL")>
		<cfquery name="ret" dbtype="query">
		SELECT #colNames#
		FROM ret
		WHERE <cfif listFind(ret.columnList,"P") gt 0>(P = 1)
		  AND </cfif>(F = '1')
		</cfquery>
	</cfif>
	<cfreturn ret>
</cffunction>

<cffunction name="reduceImplicants" returntype="query" description="Progressively reduce our implicant set via QMC.">
	<cfargument name="implicants" type="query" required="true">
	<cfargument name="varCount" type="numeric" required="true">
	<cfargument name="minTerms" type="query" required="true">
	<cfset var ret=makeRowNumbers(arguments.implicants)>
	<cfset var c=arguments.varCount>
	<cfset var t=arguments.minTerms>
	<cfset var colNames="ret." & listChangeDelims(reReplaceNoCase(arguments.implicants.columnList,"^[^m,]+|,[^m,]+","","ALL"), ", ret.")>
	<cfset var x="">
	<cfset var e="">
	<cfset var essential="">
	<cfset var essentialCount=0>
	<cfset var retCount=0>
	<cfset var xCount=0>
	<!--- We want to flatten our implicant table to just pairs of minterms (T) and inputs/outputs (R) --->
	<cfquery name="x" dbtype="query">
	SELECT t.#t.columnList# AS T, ret.R
	FROM t, ret
	WHERE (t.#t.columnList# IN (#colNames#))
	</cfquery>
	<!--- We want to start with an empty list of essential implicants --->
	<cfquery name="essential" dbtype="query">
	SELECT *
	FROM ret
	WHERE (1 = 0)
	</cfquery>
	<cfloop condition="((x.recordCount neq xCount) or (essential.recordCount neq essentialCount) or (ret.recordCount neq retCount)) and (ret.recordCount GT 0)">
		<!--- This is a 3-step process that we repeat as it continues to reduce our outputs and terms. --->
		<cfset essentialCount=essential.recordCount>
		<cfset xCount=x.recordCount>
		<cfset retCount=ret.recordCount>
		<!--- Step 1: Extract any essential prime implicants (outputs that are the only ones to own a term) --->
		<cfset e=reduceEssentials(x)>
		<cfset x=e.x>
		<cfset e=e.e>
		<cfif e.recordCount gt 0>
			<!--- Add the returned essentials to our running table ... --->
			<cfquery name="essential" dbtype="query">
			SELECT #essential.columnList#
			FROM essential
			UNION ALL
			SELECT #essential.columnList#
			FROM ret
			WHERE (R IN (#valueList(e.r)#))
			</cfquery>
			<!--- ... then remove them from the working set. --->
			<cfquery name="ret" dbtype="query">
			SELECT *
			FROM ret
			WHERE (R NOT IN (#valueList(e.r)#))
			</cfquery>
		</cfif>
		<!--- Step 2: Trim off any terms that dominate any other terms --->
		<cfif (x.recordCount gt 0)>
			<cfset x=reduceRows(x)>
		</cfif>
		<!--- Step 3: Trim off any outputs that are dominated by other outputs --->
		<cfif (x.recordCount gt 0)>
			<cfset x=reduceCols(x)>
		</cfif>
	</cfloop>
	<cfreturn essential>
</cffunction>

<cffunction name="reduceCols" returntype="query" description="Disqualify any outputs that are dominated by other outputs">
	<cfargument name="x" type="query" required="true">
	<cfset var termCount="">
	<cfset var intCount="">
	<cfset var domCount="">
	<cfset var retCount=0>
	<cfset var ret=arguments.x>
	<cfset var ret2=ret>
	<cfloop condition="(retCount neq ret.recordCount)">
		<cfset retCount=ret.recordCount>
		<cfset ret2=ret>
		<!--- Get a count of terms for each output --->
		<cfquery name="termCount" dbtype="query">
		SELECT R, COUNT(*) AS C
		FROM ret
		GROUP BY R
		</cfquery>
		<!--- Get a count of intersections --->
		<cfquery name="intCount" dbtype="query">
		SELECT ret.R, COUNT(*) AS C
		FROM ret, ret2
		WHERE (ret.T = ret2.T) AND (ret.R > ret2.R)
		GROUP BY ret.R, ret2.R
		</cfquery>
		<!--- Figure out which outputs are dominated by others (number of terms matches count) --->
		<cfquery name="domCount" dbtype="query" maxrows="1">
		SELECT intCount.R, termCount.C
		FROM intCount, termCount
		WHERE (intCount.R = termCount.R)
		  AND (intCount.C = termCount.C)
		ORDER BY termCount.C DESC, intCount.R DESC
		</cfquery>
		<cfif domCount.recordCount gt 0>
			<cfquery name="ret" dbtype="query">
			SELECT *
			FROM ret
			WHERE (R != #domCount.R[1]#)
			</cfquery>
		</cfif>
	</cfloop>
	<cfreturn ret>
</cffunction>

<cffunction name="reduceRows" returntype="query" description="Disqualify any minterms that dominate other minterms.">
	<cfargument name="x" type="query" required="true">
	<cfset var outCount="">
	<cfset var intCount="">
	<cfset var domCount="">
	<cfset var retCount=0>
	<cfset var ret=arguments.x>
	<cfset var ret2=ret>
	<cfloop condition="(retCount neq ret.recordCount)">
		<cfset retCount=ret.recordCount>
		<cfset ret2=ret>
		<!--- Get a count of the outputs for each minterm --->
		<cfquery name="outCount" dbtype="query">
		SELECT T, COUNT(*) AS C
		FROM ret
		GROUP BY T
		</cfquery>
		<!--- Get a count of intersections --->
		<cfquery name="intCount" dbtype="query">
		SELECT ret.T AS leftT, ret2.T AS rightT, COUNT(*) AS C
		FROM ret, ret2
		WHERE (ret.T < ret2.T) AND (ret.R = ret2.R)
		GROUP BY ret.T, ret2.T
		</cfquery>
		<!--- Figure out which terms are dominated by others (number of outputs matches count) --->
		<cfquery name="domCount" dbtype="query">
		SELECT intCount.rightT, intCount.C
		FROM intCount, outCount
		WHERE (intCount.leftT = outCount.T)
		  AND (intCount.C = outCount.C)
		ORDER BY intCount.C DESC, intCount.rightT DESC
		</cfquery>
		<!--- Figure out which are the dominating terms, then get the biggest --->
		<!--- <cfquery name="domCount" dbtype="query" maxrows="1">
		SELECT domCount.rightT, outCount.C
		FROM domCount, outCount
		WHERE (domCount.rightT = outCount.T)
		ORDER BY outCount.C DESC, domCount.rightT DESC
		</cfquery> --->
		<cfif domCount.recordCount gt 0>
			<cfquery name="ret" dbtype="query">
			SELECT *
			FROM ret
			WHERE T != #domCount.rightT[1]#
			</cfquery>
		</cfif>
	</cfloop>
	<cfreturn ret>
</cffunction>

<cffunction name="reduceEssentials" returntype="struct" description="Identify any minterms that have only one corresponding output.">
	<cfargument name="x" type="query" required="true">
	<cfset var ret=structNew()>
	<cfset var termCount="">
	<cfset var loseTerms="">
	<cfset var newX="">
	<!--- Find all terms that have exactly one output --->
	<cfquery name="termCount" dbtype="query">
	SELECT T
	FROM x
	GROUP BY T
	HAVING COUNT(*) = 1
	</cfquery>
	<!---
	Find all output/term combinations that match those 1-output terms.
	We want to remove any terms referenced by any outputs we remove,
	  not just the 1-output terms.
	--->
	<cfquery name="termCount" dbtype="query">
	SELECT x.T, x.R
	FROM x, termCount
	WHERE (x.t = termCount.t)
	</cfquery>
	<cfif termCount.recordCount gt 0>
		<cfquery name="loseTerms" dbtype="query">
		SELECT DISTINCT T
		FROM x
		WHERE (R IN (#valueList(termCount.R)#))
		</cfquery>
		<cfquery name="newX" dbtype="query">
		SELECT *
		FROM x
		WHERE x.T NOT IN (#valueList(loseTerms.T)#)
		</cfquery>
		<cfset ret.x = newX>
	<cfelse>
		<cfset ret.x=x>
	</cfif>
	<!--- We need to keep those outputs we removed, so we send them back --->
	<cfset ret.e = termCount>
	<cfreturn ret>
</cffunction>

<cffunction name="makeKeys" returntype="query" description="Add/replace a column that stores the human-readable version of a function input/output.">
	<cfargument name="q" type="query" required="true">
	<cfargument name="varCount" type="numeric" required="true">
	<cfset var ret=arguments.q>
	<cfset var i=0>
	<cfset var kk="">
	<cfset var a=Asc('A')-1>
	<cfset var notMark="´">
	<!--- 
	Turn a bit set such as "01-1" into something human readable, like "A´BD".
	Work each bit, where the first bit becomes "A", then "B", etc.
	For each bit:
	  a "0" means "not", so add a notMark: A´, B´, etc.
	  a "1" means just the bit name itself: A, B, etc.
	  a "-" is not applicable, so ignore it.
	--->
	<cfif not isDefined("ret.K")>
		<cfset queryAddColumn(ret, "K", "CF_SQL_VARCHAR", listToArray(repeatString("-,",ret.recordCount)))>
	</cfif>
	<cfloop query="ret">
		<cfset kk="">
		<cfloop from="1" to="#arguments.varCount#" index="i">
			<cfswitch expression="#ret['S' & i][currentRow]#">
				<cfcase value="0"><cfset kk=kk & Chr(a+i) & notMark></cfcase>
				<cfcase value="1"><cfset kk=kk & Chr(a+i)></cfcase>
			</cfswitch>
		</cfloop>
		<cfset querySetCell(ret,"K",kk,currentRow)>
	</cfloop>
	<cfreturn ret>
</cffunction>

<cffunction name="makeRowNumbers" returntype="query" description="Add a column to a query equal to each row number.">
	<cfargument name="q" type="query" required="true">
	<cfset var ret=arguments.q>
	<cfif not isDefined("ret.r")>
		<cfset queryAddColumn(ret, "R", "CF_SQL_INTEGER", listToArray(repeatString("0,",ret.recordCount)))>
	</cfif>
	<cfloop query="ret">
		<cfset querySetCell(ret, "R", currentRow, currentRow)>
	</cfloop>
	<cfreturn ret>
</cffunction>

<cffunction name="quine" output="true" returntype="any" description="Use the Quine-McCluskey algorithm to convert a set of function outputs into a minimum logic equation.">
	<cfargument name="outputs" type="string">
	<cfset var outString=reReplace(lCase(arguments.outputs),"[^01x]+","","ALL")>
	<cfset var varCount=0>
	<cfset var outArray=arrayNew(1)>
	<cfset var i=0>
	<cfset var bits="">
	<cfset var implicants="">
	<cfset var terms="">
	<cfif len(outString) lte 0><cfthrow message="You must enter a list of outputs."></cfif>
	<cfset varCount=log(len(outString)) / log(2)>
	<cfif int(varCount) neq varCount><cfthrow message="The number of function outputs should be a power of 2.  You entered #len(outString)# outputs."></cfif>
	<cfloop from="1" to="#len(outString)#" index="i"><cfset outArray[i]=mid(outString,i,1)></cfloop>
	<cfset bits=bitTable(varCount,outArray)>
	<cfquery name="implicants" dbtype="query">
	SELECT *
	FROM bits
	WHERE (F IN ('1','x'))
	</cfquery>
	<cfquery name="terms" dbtype="query">
	SELECT DISTINCT m1
	FROM bits
	WHERE F = '1'
	</cfquery>
	<!--- Get the list of implicants, reduce it, then make it human-readable. --->
	<cfset implicants=makeKeys(reduceImplicants(getImplicants(implicants,varCount),varCount,terms),varCount)>
	<cfreturn valueList(implicants.k,"+")>
</cffunction>

<cfif len(f) gt 0>
	<!--- <cftry> --->
		<cfdump var="#quine(f)#">
	<!--- <cfcatch>
		<cfoutput><p><strong>#cfcatch.message#</strong></p></cfoutput>
	</cfcatch>
	</cftry> --->
</cfif>

<cfoutput>
</body>
</html>
</cfoutput>

<cfsetting enablecfoutputonly="No">
Show details Hide details

Change log

r47 by deliver8r on Nov 01, 2008   Diff 
MPL v1.1 License added.
Go to: 
Project members, sign in to write a code review

Older revisions

r46 by deliver8r on Nov 01, 2008   Diff 
Initial QMC check-in
All revisions of this file

File info

Size: 18903 bytes, 466 lines
Hosted by Google Code