Quine-McCluskey Simplification Algorithm Introduction. Using K-maps to find the minimized two-level form of a function is difficult for functions of more than 4 variables and nearly impossible for functions of more than 6 variables because it's hard to visualize and spot patterns in multidimensional space. The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of Boolean functions that was developed by Willard V. Quine and extended by Edward J. 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.
Quine-McCluskeyCode for Quine McCluskey method of minimization of boolean expression.LANGUAGE USED: JAVAHOW TO COMPILE AND RUN: Open the source file using any java IDE (BlueJ, eclipse,etc). Compile the code and run.There is primarily one input the number of variables. The number of minterms and the mintermsare randomly generated.( Code tested in BlueJ IDE and eclipse on Windows 8 )ABOUT THE CODE: The given JAVA code implements the Quine Mccluskey method for simplifying boolean expressions.
I haveused mainly 2D arrays mainly to implement the method along with some function calls. A simple overview of how the codeworks is given below:-HOW IT WORKS:- First store the number of variables and number of minterms. Accordingly declare 2 two dimensional arrayseach of size (NumberOfMinterms)C2 X NoOfVariables. While the first one holds the binary forms of the minterms entered theother one hold the binary forms of the minterms with bit difference of 1. Each time the contents of second matrix iscopied to the first keeping track of the minterms which are not carried forward to next pass. Such minterms/combinationsare stored in another matrix which is meant for storing the Prime Implicants.After storing the prime implicants the PI coverage chart is made, using yet another 2D array.
The dimension of thismatrix is (No. Of PI )X(No of minterm). Initialise the matrix with 0 symbolising empty. For each PI put 1(meaning across - X) under the correct minterm. We now check columnwise and presense of single 1 in a column symbolises anessential PI which is marked. All the columns of an essential PI is deleted ( -1 to symbolise deleted spaces ).Repeatedchecking is made to remove row and column dominance.
After that the row which has a 1 is taken in final expression forthe simplified expression.METHOD DESCRIPTIONS:- Descriptions of the method/function used in my code is as follows1. Initialise(int a,int val) - initialise matrix a with the value in val2.
Initialisesingle(int a,int val) - initialise array a with the value in val3. Decode(int a,int row,int nvar,char bitvar)-will convert the final essential pi and pi into switching variables4. Match(int min,int a,int row,int nvar) - this method identifies the decimal notation of the PI and essential PIfrom their binary notations5. The main method takes all input computes PI and essential PI, removes row and column dominance and outputs theminterms in final expression.LIMITATIONS OF THE CODE:1. The primary limitation of the code is that it does not consider semi-cyclic conditions in the PI coverage chart.2. The use of array has a restriction on the number of minterms we can consider according to number of variables in theproblem.EXAMPLE: If we are working on 8 varables the code can give results with upto a maximum of 210 minterms, for 10variables it works fine for 700 minterms.
Beyond a certain limit the code can throw a ArrayIndexOutOfBoundsException.Explanation:. Random rand=new Random(32); = The use of roll number (ie, 32 ) while creating the Random object rand has a limitationof generation of identical integers every time you run the code, that is, every timeyou give 10 variable as input you get the same set of minterms. To remove this situationsimply remove the argument (ie, 32) while creating the Random object.
![Methode Methode](http://www.groupes.polymtl.ca/circuits-logiques/help/Chapitre04_fichiers/image045.jpg)
![Methode De Quine-mc Cluskey Methode De Quine-mc Cluskey](https://electronics-council.com/electronics-img/news/800/everything-about-quine-mccluskey-method.png)
nmin=(int)rand.nextInt((int)(.75.(Math.pow(2,nvar)-1))); = Generates number of minterm within the limit set bythe argument. The limit is 75% of permitted value to prevent ArrayIndexOutOfBoundsException.PLEASE NOTE:- I have commented out the portions of the code that display the binary forms of the minterms entered,the tables generated, the binary forms of PIs,essential PIs and the PI coverage chart before and after removingdominance. This has been done to keep a cleaner output terminal.
If you wish to display them you can do so un-commenting the following lines:-LINES 72-79: Displays the binary forms of the mintermsLINES 141-155: Displays the table in every passLINES 163-175: Displays the binary forms of the PILINES 189-203: Displays the PI coverage chartLINES 223-238: Displays the binary forms of essential PILINES 260-274: Displays the PI chart after removing essential PILINES 361-375: Displays the PI chart after removing row and column dominance.
Quine-McCluskey Simplification Algorithm Quine-McCluskey Simplification Algorithm IntroductionUsing K-maps to find the minimized two-level form of a function isdifficult for functions of more than 4 variables and nearly impossible for functions ofmore than 6 variables because it's hard to visualize and spot patterns in multidimensionalspace.An alternative to using K-maps is the Quine-McCluskey algorithm. TheQuine-McCluskey algorithm provides a systematic approach for finding the prime implicantsand selecting a minimum cover. Because the algorithm is tedious it is better suited tomachine implementation.
Quine-McCluskey AlgorithmWith both the K-map method and Quine-McCluskey algorithm you aretrying to find a minimum number of terms that cover all of the minterms in the function.For example, the two minterms AB'CD' and ABCD' are covered by the term ACD'Both the K-map method and Quine-McCluskey algorithm go through thefollowing 3 phases:Step 1: find prime implicants.Step 2: find essential prime implicantsStep 3: select a minimal set of remaining prime implicants thatcovers the on-set of the functionExample 1. Use the Quine-McCluskey algorithm to find the minimalsum-of-products form of the following function:F = (0,9,13,15) d(7,12)The following image shows the first step of theQuine-McCluskey algorithm where we identify prime implicants.Figure 1. Using the Quine-McCluskey algorithmto find prime implicants.Column 1 shows the indices of the minterms in the givenfunction. Indices for don't-care values are marked with a (d).
We use the don't-carevalues here while identifying prime implicants, but won't use them later when searchingfor a minimal subset of prime implicants that covers the minterms of the function.Column 2 shows the minterm value written as a binarynumber. For example, 1001 = AB'C'DColumn 3 shows minterms in binary form grouped inascending order by the number of 1's in the binary form of the minterm. The first grouphas 0 1's. The second group has 2 1's, etc.Column 4 has an entry for every pair of terms that canbe combined in the previous column. For example, 1001 can be combined with 1101 whichresults in 1-01. Or in Boolean algebra:AB'C'D + ABC'D =AC'D(B' + B) =AC'D(1)AC'DWhenever a term is combined to create a smaller term weput a check beside the terms that were combined. This is so we can identify primeimplicants at the end.
The prime implicants are all terms that don't have a check. (Primeimplicants are circles in the above image.)Here we stop at column 4 because there are no terms incolumn 4 that can be combined.The next step is to identify essential prime implicantsand select a minimal subset of prime implicants that covers the on-set of the function. Tofind essential prime implicants first create a table. The columns are labeled with theminterms in the on-set of the function. (Notice, don't care values are not included.) Therows are labeled with the prime implicants found above. For each prime impilcant mark an Xat the intersection of the row for the prime implicant and the column for all mintermscovered by the prime implicant.
Are there any columns with only 1 X? If so, the primeimplicant that covers the minterm for the column is an essential prime implicant.Figure 2. Selecting essential primeimplicants with the Quine-McCluskey algorithm.Essential prime implicants must be included in thefinal minimized form of the function:F = A'B'C'D' + AC'D +???The final step is to select a minimal subset ofremaining prime implicants that cover the remaining uncovered minterms in the on-set.
Inour example we could select either: -111 (BCD) or 11-1 (ABD). If we select BCD, the finalanswer is:F = A'B'C'D' + AC'D + BCD ConclusionThe Quine-McCluskey algorithm has it's practical limitstoo. Both the K-map method and the Quine-McCluskey algorithm find the guaranteed two-levelminimized form of a function. The K-map method doesn't work well for functions of morethan 4 variables because there is a limit on our ability to spot visual patterns inmultidimensional space. The Quine-McCluskey algorithm has it's practical limits alsobecause the algorithm is NP-Complete. In other words the runtime of the Quine-McCluskeyalgorithm grows exponentially with the input size.
For example, it can be shown that for afunction of n variables the upper bound on the number of prime implicants is 3 n/n.So, when n=25 there may be 3.0. 10 10, or 30 billion prime implicants. If youhave to minimize functions with a large number of variables and can accept less than theguaranteed minimum form of the function there are algorithms that follow heuristics toarrive at a close to optimal solution.