
Simplified Methods for Prime Implicants in Digital Function Systems
Explore the Quine-McCluskey method for determining prime implicants in digital systems. Learn to find essential prime implicants, simplify functions, and derive minimum sum-of-products expressions efficiently. Utilize Petrick's method and map-entered variables for simplification. Programmed exercises and practical examples included.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
UNIT 6 QUINE-McCLUSKEY METHOD Objectives Study Guide Determination of Prime Implicants The Prime Implicant Chart Petrick s Method Simplification of Incompletely Specified Functions Simplification Using Map-Entered Variables Conclusion Programmed Exercises Problems 6.1 6.2 6.3 6.4 6.5 6.6
Objectives 1. Find the prime implicants of a function by using the Quine-McCluskey method. 2. Define prime implicants and essential prime implicants 3. Given the prime implicants, find the essential prime implicants and a minimum sum-of-products expression for a function, using a prime implicant chart and using Petrick method 4. Minimize an incompletely specified function, using the Quine-McCluskey method 5. Find a minimum sum-of-products expression for a function, using the method of map-entered variables
Quine-McCluskey Method Quine-McCluskey Method Used when the number of variables is large Provides systematic simplification procedure which can be readily programmed for a digital computer. Reduction Procedure Eliminate as many literals as possible from each term by systematically applying the theorem XY + XY = X The resulting terms are called prime implicants Use a implicant chart to select a minimum set of prime implicants
6.1 Determination of Prime Implicants Convert the given function into a sum-of minterms form The minterms are represented in binary notation and combined using X XY XY = + ' if two terms differ in exactly one variable.
6.1 Determination of Prime Implicants Example 1 + = ' ' ' ' CD 1 0 1 AB CD 1 1 0 1 + AB AB 1 C = 0 1 0 The dash(-) indicates a missing variable - - ' X Y X Y X Example 2 + ' ' ' ' A BC D A BCD Two terms differ in two variables, so it cannot be combined. 1 1 0 + 1 0 1 0 0
6.1 Determination of Prime Implicants Given binary minterms are sorted into groups according to the number of 1 s in each term. group 0 0 0000 Example 1 0001 ? ?,?,?,? = ?(0,1,2,5,6,7,8,9,10,14) group 1 2 0010 8 1000 5 0101 6 0110 group 2 9 1001 10 1010 7 0111 group 3 14 1110
6.1 Determination of Prime Implicants Determination of Prime Implicants Column I Column II Column III 0, 1 0, 2 0, 8 1, 5 1, 9 2, 6 2,10 8, 9 8,10 5, 7 6, 7 6,14 10,14 000- 00-0 -000 0-01 -001 0-10 -010 100- 10-0 01-0 011- -110 1-10 0, 1, 8, 9 0, 2, 8,10 0, 8, 1, 9 0, 8, 2,10 2, 6,10,14 2,10, 6,14 -00- -0-0 -00- -0-0 --10 --10 group 0 0 1 2 8 5 6 9 0000 0001 0010 1000 0101 0110 1001 1010 0111 1110 group 1 group 2 10 7 14 group 3
6.1 Determination of Prime Implicants The function is equal to the sum of its prime implicants = + + + + + ' ' ' ' ' ' ' ' ' f a (1,5) (5,7) (6,7) (0,1,8,9) (0,2,8,10) (2,6,10,14) c d a bd a bc b c b d cd Apply consensus theorem to eliminate redundant terms + + = + Consensus theorem: ' ' XY X Z YZ XY X Z = + + + + + ' ' ' ' ' ' ' ' ' f a c d a bd a bc b c b d cd + + ' b + + ' ' ' ' ' ' ' ' ' ba d c a dc b c d c b d + + ' ' ' a bd cd a bc = + + ' ' ' ' f a bd b c cd Minimum sum-of-products
6.1 Determination of Prime Implicants Definition of Implicant Given a function F of n variables, a product term P is an implicants of F iff for every combination of values of the n variables for which P=1, F is also equal to 1. Emaxple = + ' + ' = + ' ( , , ) ' ' ' ' ' F a b c a b c ab c ab c b c ac Every term in the equation is an implicant, but bc is not.
6.1 Determination of Prime Implicants Definition of Implicant: A Prime Implicants of a function F is a product term implicant which is no longer an implicant if any literal is deleted from it. Emaxple = + ' + ' = + ' ( , , ) ' ' ' ' ' F a b c a b c ab c ab c b c ac Implicant a b c is not a Prime Implicants because b c is still an implicant. b c and ac are Prime Implicants.
6.2 The Prime Implicant Chart Prime Implicant Chart (Table 6-2) Select Essential Prime Implicants 0 1 2 5 6 7 8 9 10 14 ? ? ? ? x x x x x x x x (0,1,8,9) x x x x x x x x (0,2,8,10) x x x x x x x x (2,6,10,14) ?? ? ? ? ? ?? ? ?? x x x x (1,5) x x x x (5,7) x x x x (6,7)
6.2 The Prime Implicant Chart Prime Implicant Chart (Table 6-2) Select Essential Prime Implicants 0 1 2 5 6 7 8 9 10 14 ? ? ? ? x x x x x x (0,1,8,9) x x x x x x x x (0,2,8,10) x x x x x x (2,6,10,14) ?? ? ? ? ? ?? ? ?? x x x x (1,5) x x x x (5,7) x x x x (6,7)
6.2 The Prime Implicant Chart Prime Implicant Chart (Table 6-2) Select Essential Prime Implicants 0 1 2 5 6 7 8 9 10 14 ? ? ? ? x x x x x x (0,1,8,9) x x x x x x x x (0,2,8,10) x x x x x x (2,6,10,14) ?? ? ? ? ? ?? ? ?? x x x x (1,5) x x x x (5,7) x x x x (6,7)
6.2 The Prime Implicant Chart Prime Implicant Chart (Table 6-2) Select Essential Prime Implicants 0 1 2 5 6 7 8 9 10 14 ? ? ? ? x x x x x x (0,1,8,9) x x x x x x x x (0,2,8,10) x x x x x x (2,6,10,14) ?? ? ? ? ? ?? ? ?? x x x x (1,5) x x x x (5,7) x x x x (6,7) ? = ? ? + ?? + ? ?? The resulting minimum sum of products is
6.2 The Prime Implicant Chart Example: cyclic prime implicants(two more X s in every column in chart) m F = (0, 1, 2, 5, 6, 7) Derivation of prime implicants 0 000 0,1 00 - 1 001 0,2 0 - 0 2 010 1,5 - 01 5 101 2,6 - 10 6 110 5,7 1 - 1 7 111 6,7 - 1 1
6.2 The Prime Implicant Chart The resulting prime implicant chart (Table 6-4) 0 1 2 5 6 7 (0, 1) ' ' x x a b (0,2) ' ' x x a c (1,5) ' x x b c (2,6) ' x x bc (5,7) x x ac (6,7) x x ad = + ' + ' ' F a b bc ac One solution:
6.2 The Prime Implicant Chart Again starting with the other prime implicant that covers column 0. The resulting table (Table6-5) b 0 1 2 5 6 7 P (0, 1) ' x ' x a 1 P (0,2) ' x ' x a c 2 P (1,5) ' c x x b 3 P (2,6) ' x x bc 4 P (5,7) ad x x ac 5 P (6,7) x x 6 = + + ' ' ' . F a c b c ab Finish the solution and show that
6.3 Petricks Method - - A technique for determining all minimum SOP solution from a PI chart b 0 1 2 5 6 7 P (0, 1) ' x ' x a 1 P (0,2) ' x ' x a c 2 P (1,5) ' c x x b 3 P (2,6) ' x x bc 4 P (5,7) ad x x ac 5 P (6,7) x x 6 Because we must cover all of the minterms, the following function must be true: )( ( 1 2 1 + = P P P P + + + + + = )( )( )( )( ) 1 P P P P P P P P P 3 2 4 3 5 4 6 5 6 minterm0 minterm1
6.3 Petricks Method - Reduce P to a minimum SOP First, we multiply out, using (X+Y)(X+Z) = X+YZ and the ordinary Distributive law = + + + ( )( P )( ) P P P P + P P P P P P P 1 1 1 1 P 1 P 1 P 1 1 1 = + + + ( P )( ) P P P + P P P P P P 1 P + 4 P 1 P 2 P 6 P + 2 + 3 P 4 P 2 P 3 + 6 P 5 P 3 + 6 P = P P + P P P P P 1 4 5 1 2 5 6 2 3 4 5 2 3 5 6 1 3 4 6 P P P P P P P P P P P 1 2 3 6 2 3 4 6 2 3 6 Use X+XY=X to eliminate redundant terms from P = + + + + P P P P P P P P P P P P P P P P P P P 1 4 5 1 2 5 6 2 3 4 5 1 3 4 6 2 3 6 - Choose P1,P4,P5 or P2,P3,P6 for minimum solution = + ' + ' = + + ' ' ' ' . F a c b c ab F a b bc ac or or
6.4 Simplification of Incompletely Specified Functions , 9 , 7 , 3 , 2 ( ) , , , ( m D C B A F = + 11 13 , ) , 1 ( d 10 15 , ) Example: Don t care terms are treated like required minterms 3) (1, 0001 1 1 - 00 11) 9, 3, (1, - 1 - 0 2 0010 (1, 9) - 001 (2, 3, 10, 11) - 01 - 3 0011 (2, 3) 001 - (3, 7, 11, 15) - -11 9 1001 (2, 10) - 010 (9, 11, 13, 15) - 1 -1 1010 10 (3, 7) 0 - 11 7 0111 (3, 11) - 011 1011 11 (9,11) 10 1 - 1101 13 (9, 13) - 1 01 1111 15 (10, 11) 101 - (7, 15) - 111 (11, 15) - 1 11 (13, 15) 11 1 -
6.4 Simplification of Incompletely Specified Functions Don t care columns are omitted when forming the PI chart 2 3 7 9 11 13 11) 9, 3, (1, x x x x 11) 10, 3, (2, * x x = ' + + F B C CD AD (3, * 7, 11, 15) x x x * (9, 11, 13, 15) x x x Replace each term in the final expression for F + + + = + + + + + + + + ( ) ( ) ( ) F m m m m m m m m m m m m 2 3 10 11 3 7 11 15 9 11 13 15 The don t care terms in the original truth table for F = = = = 0001 , ; 0 1010, for ; 1 1111, for 1 for ABCD F F F
6.5 Simplification Using Map-Entered Variables Using of Map-Entered Variables (Figure 6-1) The map represents the 6-variable function = + + + + + + + ( , , , , , ) G A B C D E F m m m Em Em Fm m m 0 2 3 5 7 9 11 15 + ( don' care t terms)
6.5 Simplification Using Map-Entered Variables Use a 3-variable map to simplify the function: = + + + + ( , , , ) ' ' ' ' ' ( ' ) F A B C D A B C A BC A BC D ABCD AB C Simplification Using a Map-Entered Variable (Figure 6-2)
6.5 Simplification Using Map-Entered Variables From Figure 6-2(b), A F ' = + + = + + C ( ' ) ' ' C D A B A C CD A BD Find a sum-of-products expression for F of the form = + + + + ... F MS P MS P MS 0 1 1 2 2 MS0: minimum sum obtained by P1=P2= =0 MS1: minimum sum obtained by P1=1, Pj=0(j=/ 1) and replacing all 1 s on the map with don t cares(X) MS2: . The resulting expression is a minimum sum of products for G(Fig. 6-1) : = + ' + + ' ' G A B ACD EA D FAD