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 here: qm.py and the line_profiler output here: qm_line_profiler_output.txt.

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