#### Read 734_n_8580.pdf text version

EGR 277 Digital Logic File: N277Lsu6

Lecture #6

Reading Assignment: Chapter 3 in Digital Design, 3rd Edition by Mano Handout: Quine McCluskey computer program (example). The program is only 27 kB in size! Minimization Methods:

Recall that this chapter deals with three methods for minimizing Boolean expressions: 1. Boolean algebra 2. Karnaugh maps 3. Tabulation methods primarily the Quine McCluskey method

Quine-McCluskey Method

The Quine McCluskey method is a systematic, tedious method for minimizing logic functions that are originally expressed in sum of minterms form. The method is well-suited to computer implementation. The method uses bit-by-bit comparisons or minterms or groups until all prime implicants have been identified. Then the method identifies the essential prime implicants and determine which of the other prime implicants can be best used to express the function.

Procedure:

1. 2. List all minterms in binary form by weight with the smallest weight at the top. Call this LIST #1. Compare terms in adjacent weight groups. If two terms differ in only one bit position, put the term in LIST #2 with a "-" in the position of the differing bit. List the minterms that were combined to form the new term next to it and check the minterms (they are now covered by the new term, so they are no longer needed and are not prime implicants). Continue in the same manner, comparing terms in LIST #2 to form LIST#3 (and checking off the terms that were combined), comparing terms in LIST#3 to form LIST#4, etc. Note: To relate this to Karnaugh maps: LIST #1 corresponds to all minterms LIST #2 corresponds to all possible groups of two minterms LIST #3 corresponds to all possible groups of four minterms LIST #4 corresponds to all possible groups of eight minterms All unchecked terms are prime implicants (PI). Number them PI1, PI2, PI3, etc. Construct a prime implicant chart (PI Chart) listing all PI's versus all minterms and place X's in the chart to indicate which minterms are covered by each PI.

3.

4. 5.

Page 2 6. Select a minimum number of PI's to cover all minterms as follows: A) If a minterms is only covered by one PI, it is an essential PI. Save the PI off to the side to be a part of the final solution. Remove the PI and all minterms covered by it from the PI Chart. You might now draw a "reduced PI Chart". B) Look for and eliminate any PI's that are completely contained within another PI (i.e., the smaller PI can be eliminated if the larger PI contains all of the smaller PI's minterms). You might now draw a "reduced PI Chart". C) Repeat steps A and B until all minterms in the PI Chart have been covered by PI's removed in steps A and proceed to step 7. If steps A and B could not be used to completely reduce the PI Chart, then the chart is cyclic and there are multiple possible equivalent solutions. Proceed to step D. D) Cyclic PI Charts: Randomly pick any of the remaining PI's and treat it as essential (i.e., save it off to the side to be a part of the final solution). Remove the PI and all minterms covered by it from the PI Chart. You might now draw a "reduced PI Chart". Go back to steps A and B to finish reducing the PI Chart. Note: Different random choices yield different solutions. You could go back and try other choices of PI's to be treated as essential to find other solutions. The function f can now be expressed by the sum of the PI's that were set aside as essential to the solution. Treat the 1's in a PI as uncomplemented variables, the 0's as complemented variables, and the dashes ("-") as unnecessary variables.

7.

Don't cares: Treat don't cares as normal minterms in steps 1 - 4 as the PI's are determined, but leave the don't cares out of the PI Chart since they do not need to be covered. POS expressions: Begin with the terms that correspond to the 0's in function f and using the method above will yield a SOP expression for f . Apply DeMorgan's theorem to find the POS expression for f.

Example: Use the Quine-McCluskey method to find a minimal SOP expression for

f(A,B,C,D) = (2,4,6,8,9,10,12,13,15). 1. LIST #1 Minterm 2 4 8 6 9 10 12 13 15 ABCD 0010 0100 1000 0110 1001 1010 1100 1101 1111 covered() or PI?

weight = 1

weight = 2

weight = 3 weight = 4

Page 3 2. LIST #2 Minterms 2, 6 2, 10 4, 6 4, 12 8, 9 8, 10 8, 12 9, 13 12, 13 13, 15 3. LIST #3 Minterms 8,9,12,13 4. 5. PI's labeled in the charts above PI Chart: Minterm 9 10 X X X X X X X X X X ABCD 1-0covered() or PI? PI1 ABCD 0-10 -010 01-0 -100 10010-0 1-00 1-01 11011-1 covered() or PI? PI2 PI3 PI4 PI5 PI6 PI7

2 PI1 PI2 PI3 PI4 PI5 PI6 PI7 X X

4

6 X

8 X

12 X

13 X

15

6A. PI1 is essential (only PI1 covers minterm 9). Save PI1. PI7 is essential (only PI7 covers minterm 15). Save PI7. Remove the saved PI's and the minterms covered from the chart.

Page 4 Reduced PI Chart: Minterm 4 6 X X X X X

PI2 PI3 PI4 PI5 PI6

2 X X

10 X

6B. PI5 is eliminated since it is completely contained within PI4. PI6 is eliminated since it is completely contained within PI3. Reduced PI Chart: Minterm 2 4 6 X X PI2 X PI3 X X PI4

10 X

6A. PI3 is essential (only PI3 covers minterm 10). Save PI3. PI4 is essential (only PI4 covers minterm 4). Save PI4. Remove the saved PI's and the minterms covered from the chart. When we do so, all columns in the chart have been eliminated, so PI2 was unnecessary. 7. f(A,B,C,D) = Sum of essential (saved) PI's. f(A,B,C,D) = PI1 + PI3 + PI4 + PI7 f(A,B,C,D) = 1 - 0 - + - 0 1 0 + 0 1 - 0 + 1 1 - 1 f(A,B,C,D) = AC + BCD + ABD + ABD (minimal SOP solution)

Example: Use the Quine-McCluskey method to find a minimal SOP expression for

f(A, B, C, D) = (1, 3, 4, 6, 7, 9, 13, 15).

Page 5

Implementing SOP expressions using NAND gates

· NAND gates are "universal gates" and thus any circuit could be constructed using only NAND gates. · Illustrate how NAND's could be used to replace NOT, OR, AND, NOR, and XOR gates. · NAND gates are commonly represented using two symbols:

7400

·

7400

NAND gates with their inputs tied together act like inverters. This is true of any number of inputs, so we often represent a NAND tied as an inverter as having only one input as shown below.

7400

·

7400

SOP circuits can be easily converted to NAND circuits by "balancing bubbles". Examples: Implement each expression using only 2-input NAND gates. 1. f(A,B,C) = AB' + BC' 2. f(A,B,C,D) = AB' + BC' + CD' 3. f(A,B,C,D) = A + BC' + CD' + BD

Implementing POS expressions using NOR gates

· NOR gates are "universal gates" and thus any circuit could be constructed using only NOR gates. · Illustrate how NOR's could be used to replace NOT, OR, AND, NAND, and XOR gates. · NOR gates are commonly represented using two symbols:

7402

·

7402

NOR gates with their inputs tied together act like inverters. This is true of any number of inputs, so we often represent a NOR tied as an inverter as having only one input as shown below.

7402

·

7402

POS circuits can be easily converted to NOR circuits by "balancing bubbles". Examples: Implement each expression using only 2-input NAND gates. 1. f(A,B,C) = (A+B')(B+C') 2. f(A,B,C,D) = (A+B')(B+C')(C+D') 3. f(A,B,C,D) = A(B+C')(C+D')(B+D)

#### Information

5 pages

#### Report File (DMCA)

Our content is added by our users. **We aim to remove reported files within 1 working day.** Please use this link to notify us:

Report this file as copyright or inappropriate

606832