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:
        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

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

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: