Quine-McCluskey algorithm implementation in Python

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:
      elif b & 1:
      a >>= 1
      b >>= 1
  return result

14 Responses to “Quine-McCluskey algorithm implementation in Python”

  1. Terry Says:

    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.

    • prekageo Says:

      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!

      • terry Says:

        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.

      • prekageo Says:

        That’s great! If you need any help to adapt this piece of code to your own code, please let me know.

  2. Henry Gomersall Says:

    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.

  3. Henry Gomersall Says:

    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! 🙂

  4. ysangkok Says:

    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)

  5. Henry Gomersall Says:

    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 .

  6. Another un-productive weekend | CS Meanderings Says:

    […] found an optimized version of QM, but I’m already onto the next Possible […]

  7. B Says:

    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?

  8. How much does Boolean expression minimization shorten? Says:

    […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: