VLSI & Adv Digital Dsgn
VLSI & Adv Digital Dsgn ECE 3060
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 0 page Class Notes was uploaded by Cassidy Effertz on Monday November 2, 2015. The Class Notes belongs to ECE 3060 at Georgia Institute of Technology - Main Campus taught by Sung Lim in Fall. Since its upload, it has received 9 views. For similar materials see /class/233855/ece-3060-georgia-institute-of-technology-main-campus in ELECTRICAL AND COMPUTER ENGINEERING at Georgia Institute of Technology - Main Campus.
Reviews for VLSI & Adv Digital Dsgn
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
1 5 UNIT 7 71 Determination of Prime Implicants In order to apply the Quine McCluskey procedure to determine a minimum sumofproducts expression for a function the function must be given as a sum of minterms If the function is not in minterm form the minterm expansion can be found by using one of the techniques given in Section 53 In the first part of the QuineMcCluskey procedure all of the prime implicants of a function are system atically formed by combining minterms The minterms are represented in binary notation and combined using XYXY39X 71 where X represents a product of literals and Y is a single variable Two minterms will combine if they differ in exactly one variable The examples given below show both the binary notation and its algebraic equivalent AB39CD39 AB39CD AB39C 1 0 l 0 l 0 l 1 l 0 l the dash indicates a missing variable X Y X Y39 X A 39BC39D A 39BCD39 won t combine 0 1 0 l O l 1 0 won t combine In order to find all of the prime implicants all possible pairs of minterms should be compared and combined whenever possible To reduce the required number of comparisons the binary minterms are sorted into groups according to the number of 1 s in each term Thus fa b c d 2m0 1 2 56 7 8 91014 is represented by the following list of minterms 72 group0 0 0000 l 0001 groupl 2 0010 8 1000 S 0101 6 11 gm 9 100 10 1010 7 0111 gr p3l14 1110 In the above list the term in group 0 has zero l s the terms in group 1 have one 1 those in group 2 have two 1 s and those in group 3 have three 1 s Two terms can be combined if they differ in exactly one variable Com parison of terms in nonadjacent groups is unnecessary since such terms will always differ in at least two variables and cannot be combined using X Y X Y39 X Sim ilarly comparison of terms within a group is unnecessary since two terms with the same number of 1 s must differ in at least two variables Thus only terms in adjacent groups must be compared 4 Wm W wt VT QUINEMcCLUSKEY METHOD 141 First we will compare the term in group 0 with all of the terms in group 1 Terms 0000 and 0001 can be combined to eliminate the fourth variable which yields 000 Similarly O and 2 combine to form 00 0a39bquotd and 0 8 combine to form 000 b39c39dp39 The resulting terms are listed in column II of Table 71 Whenever two terms combine the corresponding decimal numbers differ by a power of 2 l 2 4 8 etc This is true because when the binary representa tions differ in exactly one column if we subtract these binary representations we get a 1 only in the column in which the difference exists and a binary number with a l in exactly one column is a power of 2 Since comparison of group 0 with groups 2 and 3 is unnecessary we pro ceed to compare terms in groups 1 and 2 Comparing term i with all terms in group 2 we find that it combines with 5 and 9 but not with 6 or 10 Similarly term 2 combines only with 6 and 10 and term 8 only with 9 and 10 The resulting terms are listed in column II Each time a term is combined with another term it is checked off A term may be used more than once since X X X Even though two terms have already been combined with other terms they still must be com pared and combined if possible This is necessary since the resultant term may be needed to form the minimum sum solution At this stage we may generate redun dant terms but these redundant terms will be eliminated later We nish with column I by comparing terms in groups 2 and 3 New terms are formed by combining terms 5 and 7 6 and 7 6 and 14 and 10 and 14 Table 71 Determination of Prime lmplicants Column I Column 11 Column III groupO 0 OOOOJ 01 OOOJ 0189 00 l OOOIJ 02 OOOJ 02810 O0 groupl 2 OOIOJ 08 000J W 8 lOOOJ 15 061 W 5 OlOlJ 19 OOI 261014 10 6 OIIOJ 26 O lOJ WW gm 9 room 210 010 10 lOlOJ 89 lOOJ 7 011w 810 100 gr up3l14 111w 57 01 1 67 Oll 614 llOJ 1014 1 1o Note that the terms in column II have been divided into groups according to the number of 1 s in each term Again we apply X Y X Y39 X to combine pairs of terms in column II in order to combine two terms the terms must have the same variables and the terms must differ in exactly one of these variables Thus it is only necessary to compare terms which have dashes missing variables in corresponding places and39which differ by exactly one in the nmber of 1 s m UNIT 7 Terms in the rst group in column II need only be compared with terms in the second group which have dashes in the same places Term 000 0 l combines only with term loo 89 to yield OO This is algebraically equivalent to a b c ab c39 b39c The resulting term is listed in column III along with the desig nation 0 l 8 9 to indicate that it was formed by combining minterms 0 l 8 and 9 Term 0 2 combines only with 8 IO and term 0 8 combines with both 1 9 and 2 10 Again the terms which have been combined are checked off Comparing terms from the second and third groups in column II we find that 2 6 combines with 10 14 and 2 IO combines with 6 14 Note that there are three pairs of duplicate terms in column III These duplicate terms were formed in each case by combining the same set of four min terms in a different order After deleting the duplicate terms we compare terms from the twolgroups in column III Since no further combination is possible the process terminates In general we would keep comparing terms and forming new groups of terms and new columns until no further terms could be combined 39 The terms which have not been checked off because they cannot be com bined with other terms are called prime implicants Since every minterm has been included in at least one of the prime implicants the function is equal to the sum of its prime implicants In this example we have f a c39d a39bd a39bc b c b39d cd39 73 1 5 5 7 67 01 8 9 0 2 810 2 61014 In the above expression each term has a minimum number of literals but the number of terms is not minimum Using the consensus theorem to eliminate redundant terms yields f a39bd b39c39 cd39 74 which is the minimum sumofproducts expression for f Section 72 discusses a better method of eliminating redundant prime implicants using a prime implicant chart Next we will de ne implicant and prime implicant and relate these terms to the Quine McCluskey procedure described above De nition Given a function F of n variables a product term P is an implicant of F iff for every combination of values of the n variables for which P 1 F is also equal to 1 In other words if for some combination of values of the variables P l and F 0 then P is not an implicant of F For example consider the function F a b c a39b39c39 ab39c39 ab39c abc b c39 ac 75 Ifa b39c39 1 then F lifac 1 then F letc Hence the terms a39b39c39 ac etc are implicants of F In this example be is not an implicant of F because bc l and F 0 when a 0 and b c 1 In general if F is written in sumofproducts form every product term is an implicant Every minterm of F is also an implicant of F and so is any term formed by combining two or more minterms For example in Table 71 all of the terms listed in any of the columns are implicants of the func tion given in Equation 72