”;
In this chapter, we will discuss the minimization of Boolean expressions using a tabular method also known as Quine-McCluskey method.
The Quine-McCluskey method is more beneficial in minimization of Boolean functions of more than six variables. This minimization technique overcomes the issues associated with K-Map for more than six variables.
Another major advantage of Quine-McCluskey method is that it is equally suitable both hand computation and machine computation, as it is programmable.
Theory of Quine-McCluskey Method
The Quine-McCluskey method is a systematic technique of minimizing complex Boolean expressions. It becomes a suitable method to perform minimization of Boolean expressions of large number of variables. It is also known as tabular method.
This minimization technique is based on the repeated use of the combining theorem (i.e., $\mathrm{XA \: + \: X\bar{A} \: = \: X}$, where X is a set of literals) on all adjacent pairs of terms. This process gives a set of all prime implicants, from which we can select a minimal sum.
Quine-McCluskey Method Procedure
The step-by-step procedure for minimizing a Boolean function by using the Quine McCluskey method is explained below −
Step 1 − List all the minterms of the given Boolean expression.
Step 2 − Group the minterms. In this step, we arrange all the minterms in groups according to the number of 1s in their binary form. For example, arrange all the minterms with no 1s together, all the minterms with only one 1s together, and so on. The number of 1s in a minterm is called the index of the minterm. Write these grouped minterms in the column 1 of the table.
Step 3 − Combine minterms. In this step, compare each minterm of the lowest index group with every minterm in the succeeding group. Whenever possible, combine two minterms in adjacent groups that differ by only 1-bit and replace the differing bit by a dash (-). This represents a don’t care condition. Also, place a check mark (✓) in front of the every minterm that has been combined with at least one minterm. Repeat this process until all possible minterm combinations are made. Write all the combined minterms in the column 2 of the table.
Step 4 − Compare and combine the minterms generated in the above step in the same manner. In this step, we combine two minterms which differ by only 1-bit and whose dashes are in the same position. We cannot combine two minterms having dashes in different positions.
Write the newly generated terms in the column 3 and put a check mark (✓) next to each term that has been combined in the column 2. Continue this process with terms in column 3, 4, and so on until no further combination is possible. At the end, the terms that are not combined are called the prime implicants.
Step 5 − List all the prime implicants and create a prime implicant chart. If there is any don’t care, it should not appear in the prime implicant chart.
Step 6 − Select the essential prime implicants which are the prime implicants that cover a minterm which is not covered by any other prime implicant.
Step 7 − Combine the essential prime implicants to obtain the final minimized expression.
Important Terms Related Quine-McCluskey Method
In the Quine-McCluskey method of Boolean expression minimization, several terms are used to convey information. Some key terms related to the Quine-McCluskey method are defined below −
Minterm − A minterm is a combination of Boolean variables that has 1 for true value and 0 for false value.
Maxterm − A maxterm is a combination of Boolean variables in which true values are designated by 0s and false values are designated by 1s.
Index − The number of 1s in a minterm is called its index.
Prime Implicant − A minterm that cannot be combined with any other minterm is called a prime implicant.
Essential Prime Implicant − A prime implicant that covers at least one minterm which is not covered by any other prime implicant is called an essential prime implicant.
Prime Implicant Chart − The graphical representation showing the relationship between the prime implicants and the minterms of the Boolean expression is called the prime implicant chart.
Don’t Care Condition − A don’t care condition is a bit or variable that can be ignored during minimization of the function. In Quine-McCluskey method, it is represented by a dash (-).
These are some important terms essential to work with the Quine-McCluskey method.
Let us now understand the application of Quine-McCluskey method to minimize a Boolean function through an example.
Example Based on Quine-McCluskey Method
Using the Quine-McCluskey technique minimize the following Boolean function.
$$\mathrm{f(A, B,C,D) \: = \: \sum \: m(0,1,5,7,10,14)}$$
Solution
The minimization of given Boolean function using the Quine-McCluskey method is explained below.
Step 1 − Grouping the given minterms in terms of number of 1s in ascending order and writing their binary form in column 1.
| Column 1 | |||||
|---|---|---|---|---|---|
| Index | Min Term | Binary Form | |||
| A | B | C | D | ||
| I0 | 0 | 0 | 0 | 0 | 0 |
| I1 | 1 | 0 | 0 | 0 | 1 |
| I2 | 5 | 0 | 1 | 0 | 1 |
| 10 | 1 | 0 | 1 | 0 | |
| I3 | 7 | 0 | 1 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | |
Step 2 − Comparing and combining minterms of the column 1.
| Column 1 | Column 2 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Index | Min Term | Binary Form | Pairs | A | B | C | D | |||||
| A | B | C | D | |||||||||
| I0 | 0 | 0 | 0 | 0 | 0 | ✓ | 0, 1 (1) | 0 | 0 | 0 | – | P |
| I1 | 1 | 0 | 0 | 0 | 1 | ✓ | ||||||
| I2 | 5 | 0 | 1 | 0 | 1 | ✓ | 1, 5 (4) | 0 | − | 0 | 1 | Q |
| 10 | 1 | 0 | 1 | 0 | ✓ | 5, 7 (2) | 0 | 1 | − | 1 | R | |
| I3 | 7 | 0 | 1 | 1 | 1 | ✓ | ||||||
| 14 | 1 | 1 | 1 | 0 | ✓ | 10, 14 (4) | 1 | − | 1 | 0 | S | |
We can see there is no term that can be combined with any other term in the column 2 between two adjacent groups. Thus, all of them are prime implicants.
Step 3 − Creating the prime implicant chart.
| PI | Minterms | 0 | 1 | 5 | 7 | 10 | 14 |
| P | 0, 1 (1) | x | x | ||||
| Q | 1, 5 (4) | x | x | ||||
| R | 5, 7 (2) | x | x | ||||
| S | 10, 14 (4) | x | x |
We can see from the prime implicant chart that the minterms m10 and m14 are covered by S only. Hence, S is an essential prime implicant. It can also be observed that the remaining minterms of the function are covered by the minimal set of prime implicants P and R.
Therefore, the minimal expression will be,
$$\mathrm{f_{min} \: = \: P \: + \: R \: + \: S \: = \: (000 \: − \: ) \: + \: (01 \: − \: 1) \: + \:(1 \: − \: 10)}$$
$$\mathrm{\Rightarrow f_{min} \: = \: \overline{ABC} \: + \: \overline{A}BD \: + \: AC\overline{D}}$$
This is minimal Boolean expression for the given Boolean function and it can be realized using AND, OR, and NOT gates.
Advantages of Quine-McCluskey Method
The Quine-McCluskey method offers several advantages over other minimization techniques such as Karnaugh Map. Some of the key advantages of the Quine-McCluskey method are listed below −
- The Quine-McCluskey method provides a systematic minimization process to find a minimal version of a complex Boolean expression.
- It can be applied to Boolean functions of large number of variables where, the K-map technique becomes impractical.
- It is suitable for both hand computation and computerized computation.
- The Quine-McCluskey method is based on a systematic algorithm that helps to reduce human errors.
- It can also be applied to Boolean functions with don’t care conditions, i.e., incomplete Boolean functions.
Disadvantages of Quine-McCluskey Method
However, the Quine-McCluskey method is a powerful simplification technique to minimize Boolean functions having several advantages over other minimization techniques.
But, it also has certain disadvantages, some of which are listed below −
- The primary disadvantage of the Quine-McCluskey method is computational complexity. It is because, we have to check all the possible combinations of minterms.
- Although the Quine-McCluskey method is better than K-Map for large number of variables. But it also becomes impractical for vary large number of variables, typically more than 7 variables.
- The Quine-McCluskey method involves extensive manual computation that makes it tedious and prone to human error.
- The Quine-McCluskey method is not much effective for certain types of Boolean functions.
- As the Quine McCluskey method involves an algorithmic approach for minimization rather than graphical approach. This makes it less intuitive.
Applications of Quine-McCluskey Method
The Quine-McCluskey method is one of the most effective minimization techniques in Boolean algebra. It provides a systematic approach to minimized complex Boolean functions of large number of variables. Some major applications of the Quine-McCluskey method are given below −
- Quine-McCluskey method is used to design and optimize digital circuits and systems. It helps reducing the number of logic gates used in the digital circuits.
- It is also used in computer programming to optimize conditional logics for better efficiency and faster speed.
- In digital signal processing, the Quine-McCluskey method is used to simplify Boolean expressions to develop efficient processing algorithms.
- Quine-McCluskey method is used to design efficient state machine.
Conclusion
In conclusion, the Quine-McCluskey method is a systematic and algorithmic approach for simplifying complex Boolean expressions. It is an effective minimization technique for Boolean functions of large number of variables.
The greatest advantage of the Quine-McCluskey method is that it supports both hand computation and machine computation, i.e., it is programmable. However, this method involves relatively complex computation which makes it tedious.
”;