Geek Answers Handbook

Quine-McCluskey Algorithm in Python

I am trying to write a Quine-McCluskey algorithm in python, but I wanted to see if there are any versions there that I can use instead. A Google search showed some useful results. I am looking for a 4x4 map abbreviation, not 2x2 or 3x3. Any ideas or links?

+3
source share
2 answers

On Wikipedia, in which you indicated the link, there are some “external links” below, among which they are interesting regarding your project:

  • " Python Implementation by Robert Dick "

    Wouldn't that fit your need?

  • " A series of articles describing the algorithm (s) implemented in R: the first article and the second article . The implementation of R is comprehensive and offers complete and accurate solutions. It processes up to 20 input variables. "

    You can use the rpy Python interface for the R language to run the Quine-McCluskey algorithm R code. Note that there is a rewrite of rpy: rpy2

    Also, why not, write yourself a new Python script using an improvement to the algorithm made by Adrian Soul in 2007, which is in the second article

+4
source 
def combine(m, n): a = len(m) c = '' count = 0 for i in range(a): if(m[i] == n[i]): c += m[i] elif(m[i] != n[i]): c += '-' count += 1 if(count > 1): return None else: return c def find_prime_implicants(data): newList = list(data) size = len(newList) IM = [] im = [] im2 = [] mark = [0]*size m = 0 for i in range(size): for j in range(i+1, size): c = combine( str(newList[i]), str(newList[j]) ) if c != None: im.append(str(c)) mark[i] = 1 mark[j] = 1 else: continue mark2 = [0]*len(im) for p in range(len(im)): for n in range(p+1, len(im)): if( p != n and mark2[n] == 0): if( im[p] == im[n]): mark2[n] = 1 for r in range(len(im)): if(mark2[r] == 0): im2.append(im[r]) for q in range(size): if( mark[q] == 0 ): IM.append( str(newList[q]) ) m = m+1 if(m == size or size == 1): return IM else: return IM + find_prime_implicants(im2) minterms = set(['1101', '1100', '1110', '1111', '1010', '0011', '0111', '0110']) minterms2 = set(['0000', '0100', '1000', '0101', '1100', '0111', '1011', '1111']) minterms3 = set(['0001', '0011', '0100', '0110', '1011', '0000', '1000', '1010', '1100', '1101']) print 'PI(s):', find_prime_implicants(minterms) print 'PI2(s):', find_prime_implicants(minterms2) print 'PI3(s):', find_prime_implicants(minterms3)
+5
source

More articles:


All Articles