Quine–McCluskey algorithm
From Wikipedia, the free encyclopedia
The Quine–McCluskey algorithm is a method used for minimization of boolean functions. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.
The method involves two steps:
- Finding all prime implicants of the function.
- Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.
Contents |
[edit] Complexity
Although more practical than Karnaugh mapping when dealing with more than four variables, the Quine-McCluskey algorithm also has a limited range of use since the problem it solves is NP-hard: the runtime of the Quine-McCluskey algorithm grows exponentially with the input size. It can be shown that for a function of n variables the upper bound on the number of prime implicants is 3n/n. If n = 32 there may be over 6.5 * 1015, prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods.
[edit] Example
[edit] Step 1: finding prime implicants
Minimizing an arbitrary function:
A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 X
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 X
m15 1 1 1 1 1
One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms) where the function evaluates to one:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD
Of course, that's certainly not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table, so they can be combined with minterms:
Number of 1s Minterm Binary Representation
--------------------------------------------
1 m4 0100
m8 1000
--------------------------------------------
2 m9 1001
m10 1010
m12 1100
--------------------------------------------
3 m11 1011
m14 1110
--------------------------------------------
4 m15 1111
At this point, one can start combining minterms with other minterms. If two terms vary by only a single digit changing, that digit can be replaced with a dash indicating that that digit doesn't matter. Terms that can't be combined any more are marked with a "*". When going from Size 2 to Size 4, treat '-' as a third bit value. Ex: -110 and -100 or -11- can be combined, but not -110 and 011-. (Trick: Match up the '-' first.)
Number of 1s Minterm 0-Cube | Size 2 Implicants | Size 4 Implicants
------------------------------|-------------------|----------------------
1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--*
m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0*
------------------------------| m(8,10) 10-0 |----------------------
2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-*
m10 1010 |-------------------|
m12 1100 | m(9,11) 10-1 |
------------------------------| m(10,11) 101- |
3 m11 1011 | m(10,14) 1-10 |
m14 1110 | m(12,14) 11-0 |
------------------------------|-------------------|
4 m15 1111 | m(11,15) 1-11 |
| m(14,15) 111- |
[edit] Step 2: prime implicant chart
None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated, and along the top go the minterms specified earlier. The don't care terms are not placed on top - they are omitted from this section because they are not necessary inputs.
| 4 | 8 | 10 | 11 | 12 | 15 | ||
| m(4,12)* | X | X | -100 | ||||
| m(8,9,10,11) | X | X | X | 10-- | |||
| m(8,10,12,14) | X | X | X | 1--0 | |||
| m(10,11,14,15)* | X | X | X | 1-1- |
Here, each of the essential prime implicants has been starred - the second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and is thus neither an essential. If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more systematic way is Petrick's Method. In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, one can combine the essential implicants with one of the two non-essential ones to yield one of these two equations:
Both of those final equations are functionally equivalent to this original (very area-expensive) equation:
[edit] See also
[edit] External links
- Karma (Karnaugh Map Viewer) – A CAD tool for Karnaugh map manipulation with didactic features in logic circuit synthesis. Uses Quine-McCluskey algorithm to generate a minimal sum of products.
- Lecture on the Quine–McCluskey algorithm
- Boolean function simplifier
- Java applet to display all the generated primes.
- Python Implementation
- Quinessence, an open source implementation written in Free Pascal.
- A literate program written in Java implementing the Quine-McCluskey algorithm.
- minBool a Matlab implementation.
- [1] , a Java program to display the boolean expresssion ..... by Manoranjan Sahu
- [2], an applet for a step by step analyze of the QMC- algorithm by Chritian Roth
- [3] SourceForge.net C++ program implementing the algorithm.
The C++ source code for the McCluskey algorithm is:
#include<iostream>
/*
Author: Liviu Gheorghisan, liviu.gheorghisan@gmail.com
Date: 20 Martie 2007
Purpose: Implements the decimal version of the McCluskey algorithm !
*/
using namespace std;
int pow(int base, int exp)
{
int res=1;
for(int i=0; i<exp; i++)
res*=base;
return res;
}
bool isPowerOfTwo(int nr)
{
bool este=false;
for(int i=0; i<=nr/2; i++)
if(pow(2,i)==nr)
{
este=true;
break;
}
return este;
}
int countBits(int nr) // numara bitii din nr !
{
int count=0;
while(nr != 0)
{
count+=nr&1;
nr=nr>>1;
}
return count;
}
class Function
{
private:
int terms[1000], mask[1000], tickedOff[1000]; //holds the decimal indicator for each term
int nVars, nTerms, pi, ps;
public:
Function(int nv);
void addTerm(int decIndicator, int msk);
void printTerms();
void printPrimeImplicants();
void computeZSpace();
void printUntickedTerms();
void tickOffIdenticalTerms(); //decat unu din ei, nu pe amandoi !;
void printUntickedTermsReloaded();
};
Function::Function(int nv)
{
nVars=nv;
nTerms=0;
}
void Function::addTerm(int decIndicator, int msk)
{
terms[nTerms]=decIndicator;
mask[nTerms]=msk;
nTerms++;
}
void Function::printTerms()
{
for(int i=0; i<nTerms; i++)
cout<<"termenul "<<terms[i]<<" cu maska "<<mask[i]<<endl;
}
void Function::computeZSpace()
{
pi=0;
ps=nTerms;
int diff, addedTerms, i, j;
for(int k=0; k<nVars*15; k++)
{
tickedOff[k]=0;
}
while(pi<ps)
{
addedTerms=0;
for(i=pi; i<ps-1; i++)
for(j=pi+1; j<ps; j++)
if((mask[i] == mask[j]) && isPowerOfTwo(diff=terms[j]-terms[i]) && (abs(countBits(terms[i])-countBits(terms[j]))==1))
{
tickedOff[i]=1;
tickedOff[j]=1;
addTerm(terms[i], mask[i]+diff);
addedTerms++;
}
pi=ps;
ps+=addedTerms;
}
}
void Function::tickOffIdenticalTerms()
{
for(int i=0; i<nTerms-1; i++)
for(int j=i+1; j<nTerms; j++)
if(mask[i]==mask[j] && terms[i]==terms[j])
tickedOff[j]=1;
}
void Function::printUntickedTerms()
{
for(int i=0; i<nTerms; i++)
if(!tickedOff[i])
cout<<"termenul "<<terms[i]<<" cu maska "<<mask[i]<<endl;
}
void Function::printUntickedTermsReloaded()
{
for(int i=0; i<nTerms; i++)
{
if(!tickedOff[i])
{
for(int j=nVars-1; j>=0; j--)
{
if(mask[i]&pow(2,j)) cout<<"-"; //adica variabila lipseste.
else if(terms[i]&pow(2,j)) cout<<"1";
else cout<<"0";
}
cout<<endl;
}
}
}
int main(int argc, char *argz[])
{
int nMinterms, i, decInd, nVars;
cout<<"numarul de variabile ale functiei este? "; cin>>nVars;
cout<<"dati numarul de mintermeni: "; cin>>nMinterms;
cout<<"Atentie, indicii mintermenilor se dau in ordine crescatoare!!!"<<endl;
Function func(nVars);
for(i=0; i<nMinterms; i++)
{
cout<<"dati indicele zecimal al mintermenului "<<i<<" :"; cin>>decInd;
func.addTerm(decInd,0); //initial, un termen nou are masca 0, adica contine toate variabilele!
}
cout<<"initial, functia arata"<<endl;
func.printTerms();
func.computeZSpace();
func.tickOffIdenticalTerms();
// func.printUntickedTerms(); // ii printeaza in format nashpa, nu se intelege nimic
cout<<"\n\n Spatiul Z este: \n\n";
func.printUntickedTermsReloaded();
return 0;
}
