Quine Mccluskey Method : Algorithm, Example, Advantages & Its Applications

In digital electronics, Boolean function simplification is a significant method. Earlier, the K-map technique is used to reduce Boolean functions up to five variables. However, by using this technique, it is complex to shorten the Boolean functions for the above five variables. So, the Quine-McClukey tabular method is a very helpful and suitable technique for Boolean functions simplification above 4 variables. This is a tabular method that uses the prime implicants concept. So, the prime implicant is a sum term or product, which cannot be reduced further by merging with any other sum terms or products of the specified Boolean function. So this article discusses an overview of a quine mccluskey method, its advantages, and its applications.

What is Quine Mccluskey Method?

The tabulation method which is used for minimizing the Boolean functions is known as the Quine McCluskey method. This method simplifies the expression of Boolean with prime implicants. So this method is very helpful in simplifying boolean expressions for the above 4 input variables. This method was developed in 1952 by Willard V. Quine & extended in 1956 by Edward J. McCluskey.

Terminologies used in Quine Mccluskey Method are; implicant, prime implicant, and essential prime implicant.

• Implicant can be defined as a collection of one’s for minterm.
• Prime implicant can be defined as the main possible group of one’s for minterm.
• An essential prime implicant is a group that covers as a minimum single minterm that cannot be enclosed with other applicants. So this technique utilizes decimal (D) to binary (B) representation.

Quine–Mccluskey Algorithm

The step-by-step procedure of the Quine-McCluskey Method of minimization is discussed below.

First, the given min terms need to arrange in an ascending order & make the groups depending on the number of 1s available in their binary representations. Thus, there will be ‘n+1’ groups nearly if there are ‘n’ Boolean variables within a Boolean function otherwise n-bits within the binary equivalent of min terms.

Next, the present min terms need to be compared in succeeding groups. If there is a change within the 1-bit position only, then get the two min terms pair. Put this ‘_’ symbol within the changed bit position & as it is maintain the remaining bits.

After that, the above step need to repeat through newly created terms till we obtain all prime implicants.
Create a table for prime implicants with a set of rows & columns. In this table, prime implicants can be arranged in rows & min terms can be arranged in columns. Place ‘one’ within the cells equivalent to the min terms that are enclosed in every prime implicant.

Discover the essential prime implicants by monitoring every column. If the min term is enclosed with only a single prime implicant, then the essential prime implicant will be the element of the shortened Boolean function.

Decrease the table of prime implicant by simply removing every fundamental prime implicant in the row & the columns equivalent to the min terms that are enclosed in that fundamental prime implicant. Now, repeat the above step for decreased prime implicant table. Once given the Boolean function’s all min terms are over then this process needs to be stopped.

Example of Quine Mccluskey Method Solved

Simplify the Boolean function like f (PQRS) =∑ m(2, 6, 8, 9, 10, 11, 14, 15) with Quine-McClukey tabular technique. This Boolean function has four variables which are represented with P,Q,R & S and minterms are; 2, 6, 8, 9, 10, 11, 14 & 15. Based on the number of one’s available in the binary equivalent, these are arranged in ascending order like 2, 8, 6, 9, 10, 11, 14 & 15. The table below provides min terms with corresponding binary representations.

In the below table, these min terms are divided into four groups depending on the number of 1s available within binary equivalents and which differ by one bit.

The below table provides the possible min terms merging from nearby groups. The min terms are merged which are changed in 1-bit position only from nearby groups. The changed bit is signified with this ‘-‘symbol. So there are 3 groups where every group includes combinations of 2 min terms.

The table below shows the achievable min term merging pairs from neighboring groups.

The min term pairs successive groups are changed in single bit position are only merged. So the differed bit is signified with the ‘-‘symbol. So there are mainly two groups in this case where every group includes 4-min terms combinations which are accessible in 2-rows. Thus, we can eliminate the rows which are repeated. After eliminating the unnecessary rows, the reduced table is shown below.

Further from nearby groups, the combinations of min terms merging are impossible, as they are changed above the single-bit position. In the above table, there are mainly three rows where every row provides a single prime implicant. So, RS’, PQ’, and PR are the prime applicants. Here, the table of prime implicants is given below.

Here, the prime implicants in the above table are arranged row-wise whereas min terms are arranged column-wise. In the table above, 1s are arranged within the prime implicant rows of common cells & the equivalent min term columns.

The 2 & 6 min terms are covered by a single prime implicant only like RS’’. Thus, it is a fundamental prime implicant and it will be a part of a simplified Boolean function. Now in the table, eliminate the prime implicant row as well as the equivalent min term columns. So, the table of reduced prime implicant is given below.

The 8 & 9 min terms in the above table are covered by only a single PQ’s prime implicant. Thus, it is a significant prime implicant and it will be an element of a reduced Boolean function. So now eliminate the row of prime implicant & the equivalent min term columns. Finally, the table for simplified prime implicant is given below.

The 15 min term in the above table is covered simply by a single PR prime implicant which is an important prime implicant in the reduced Boolean function. So in this example, we got mainly 3 significant prime implicants. So, the reduced Boolean function is

f (PQRS) = RS’ + PQ’ + PR

Advantages and Disadvantages

The advantages of the quine mccluskey method include the following.

• Quine–McCluskey technique is used for a large number of inputs like the above 4.
• It does not need pattern identification.
• This method overcomes the drawback of Karnaugh maps that is, pattern recognition is impossible and tedious in K-map with more inputs.
• The k-map method is used to reduce Boolean functions up to five variables.
• As compared to the K-map method, the quine mccluskey method is very faster.

The disadvantages of the quine mccluskey method include the following.

• To find the minimized Boolean expression, we need to tabulate four to five tables, so these are complex.
• This method’s computational complexity is high.

Applications

The applications or uses of the quine mccluskey method include the following.

• A quine-McClukey tabular method is a tabular method based on the concept of prime applicants.
• The Quine–McCluskey algorithm is the same as Karnaugh mapping functionally, although the tabular form of this will make it very efficient to utilize in computer algorithms.
• This method is helpful in simplifying boolean expressions with the above five input variables
• The Quine-McCluskey method presents a systematic approach to programming easily into a computer mainly for digital simplification.
• The Quine-McCluskey algorithm is used in the computer science field & electrical engineering.
• This method is used to simplify logical expressions for representing the digital logic circuits behavior like in cell phones, computers & different electronic devices.
• A quine-McCluskey algorithm is used in digital circuit design that executes Boolean functions.
• The Quine-McCluskey algorithm is used wherever logical expressions play a significant role like formal hardware & software system verification and in proving an automated theorem.
• This algorithm is utilized to decrease the circuit’s complexity to attain a similar performance as the more challenging & original expressions.

Thus, this is all about an overview of the Quine Mccluskey Method – algorithm, example, and its applications. This method also called the tabulation technique is mainly used to reduce the Boolean functions. Here is a question for you, what is K-map?