Quine-McClusky Method-數位邏輯設計筆記

一定愛配王俊堯教授開放課程食用:課程連結

Quine-McClusky Method

Overview

What is Quine-McClusky Method?

• A systematic simplification procedure.
• You input a minterm expansion, you will get a minimum sum of product.

Steps to Do Quine-McClusky Method

1. Generate all prime implicants.
   • Eliminate as many literals as possible from each term with .
2. Find the minimum solution.
   • Use a "prime implicant chart" to select a minimum set of prime implicants that contains a minimum number of literals.

Determination of Prime Implicants

Steps to Determine Prime Implicants

1. Represent each minterm with binary code.
2. Find decimal number for each binary code.
3. List all the binary numbers.
   • Group them according to the number of 1's.
     • Ex: Group 5 => 5 1's.
   • List all groups in a column in a ascending oder.
4. Start to eliminate terms with adjacnt group by doing .
5. Check off all the terms that is combinable.
6. The leftovers are "prime implicants".

Finding the Minimum Solution(The Prime Implicant Chart)

Steps to Find the Minimum Solution

1. Construct the prime implicant table.
2. Make a cross under each decimal number that is a term contained in the prime number implicant at that row.
3. Find all the columns that contain only one cross and circle them. Place a star at the left of those rows in which you circle.
4. Repeat Step 1-3.
5. The rows marked with a star are the essential prime implicants.

Cyclic Prime Implicant Table

• The minimum form can be more than one.

Petrick's Method

What is Petrick's Method?

• Petrick's method is a technique to determine "all" minimum sum of product from a prime implicant table.
• Before applying Petrick's method, all essential prime implicants and the minterms they cover should be "removed" from the chart.

Steps to Do Petrick's Method

1. Lable the rows of the table.
2. Form a logic function P, which is true when all of the minterms in the table have been covered.
3. Reduce P to minimum sum using and .
4. Select one solution that has the minimum number of prime implicant, minimum number of literals.

Simplification of Incompletely Specified Functions

How to simplify incompletely specified functions(functions with "don't care")?

• When finding the prime implicants. => Treat the don't care terms as if they were "required minterms".
• When formimg the prime implicant table. => The don't cares are "not" listed at the top of the table.