Recently, I had to minimize some boolean functions using Karnaugh maps. The functions were part of a state machine, which I would like to optimize, so I had to repeat the process using Karnaugh maps over and over until, finally, I decided it would be much more productive, if I could write a program that could do the trick. So, here it is; an implementation of the Quine-McCluskey algorithm written in Python. Before writing the code, I had studied the implementation of Robert Dick, which can be found here: http://pypi.python.org/pypi/qm/0.2.
I improved the performance of the above mentioned implementations by:
- using bitwise operations,
- eliminating uses of strings and
- using Petrick’s method for determining all minimum sum-of-products solutions from a prime implicant chart.
I have also run line_profiler in order to pinpoint the lines of code that might need optimization if necessary.
You can find the Python module and the line_profiler output on GitHub: prekageo/optistate. The source code is distributed under the MIT license.
Update 2011/05/19: I have improved the complexity calculation method. Before this change the complexity of a NOT gate was the same as the complexity of a 2-input OR gate, so instead of the minimal function NOT B, the function A OR C was produced. I have also written a function that provides an interface in case you would like to use this implementation instead of Robert Dick’s. The interface translates the output to match that of Robert Dick’s implementation.
def t(x,n): x = x[1] if x == '1': return ['X'*n] if x == '0': return ['X'*n] result = [] for a,b in x: tmp = [] for i in xrange(n): if a & 1: tmp.append('1') elif b & 1: tmp.append('X') else: tmp.append('0') a >>= 1 b >>= 1 tmp.reverse() result.append(''.join(tmp)) return result
November 17, 2011 at 1:58 am |
Is this code licensed under the Python license? I was thinking about trying to use this code in some test code that I’m writing that would include some GPL code as well.
November 17, 2011 at 8:58 am |
You can use whatever license you want. The code provided here is under public domain. It would be interesting to know what project you are working on!
November 17, 2011 at 3:07 pm
I work on the Asterisk project (asterisk.org). I am writing a test that loops through all combinations of a lot of configuration options and records certain failure cases. Being able to minimize the cases to a function describing the configuration options is quite helpful.
November 17, 2011 at 4:24 pm
That’s great! If you need any help to adapt this piece of code to your own code, please let me know.
July 10, 2012 at 2:59 pm |
The QM class is great! Thanks! Would you mind putting a formal copyright declaration at the top of the code? It would be very helpful to me.
July 10, 2012 at 6:19 pm |
Thank you very much Henry! What license would you suggest?
July 10, 2012 at 7:08 pm |
I’m planning on using it with some code which uses the apache license… http://www.apache.org/licenses/LICENSE-2.0.txt – it’s pretty liberal. Alternatively, you might just want to use something like the original license that Robert Dick used (which is virtually public domain). So much choice! 🙂
July 11, 2012 at 7:37 pm |
Hi Henry! I have uploaded the project on GitHub under the MIT license. Hope it is OK for you. If not, do not hesitate to contact me.
July 11, 2012 at 9:28 pm
Fantastic! Thanks! 🙂
December 12, 2012 at 10:25 pm |
here’s a function to transform the old input to the new function
from newqm import QM
def qm(**kwargs):
n = ceil(log2(max(kwargs[“ones”])))
q = QM([chr(code) for code in range(ord(‘A’),ord(‘A’)+n)])
return t(q.solve(kwargs[“ones”],[]),n)
November 15, 2013 at 10:45 am |
I should have come back ages ago, but I wrote a parsing front end (based on pyparsing) for user input of boolean expressions. In combination with your qm.py it generates quite a nice pairing for handling boolean expressions: https://github.com/hgomersall/python-boolean .
March 17, 2014 at 9:16 am |
[…] found an optimized version of QM, but I’m already onto the next Possible […]
October 5, 2017 at 11:09 am |
Hi, I’m working on some Functional Decomposition (ashenhurst/curtis) type methods for ML (karnaugh maps are really useful for this), I would like to use non-binary inputs, the idea is to use more wires on the input to create larger numbers of possibilities per variable. My question is how many variables (binary) do you suppose this algorithm can handle?
November 19, 2020 at 2:15 pm |
[…] this would take over a year on my laptop. The qm module could be made more efficient, and in fact someone has done that. But even if you made the code a billion times faster, six variables would still be […]