Supplement to Logic and Computer Design Fundamentals 3rd Edition 1 MORE OPTIMIZATION elected topics not covered in the third edition of Logic and Computer Design Fundamentals are provided here for optional coverage and for self study if desired This material fits well with the desired coverage in some programs but not may not fit within others due to time constraints or local preferences This supplement provides two optimization algorithms for finding a minimum cost two level circuit The first algorithm selects prime implicants for a minimum cost implementation of a two level sum of products circuit The second algorithm replaces K maps with tabular representations that permit the handling of more that the six variables possible using K maps Unfortunately the latter algorithm is difficult to execute manually and the prime implicant generation approach is not the best for program implementation The prime implicant selection step is more useful for both manual computation for simple problems and computer implementation for more complex ones Overall the material in this supplement provides a more rigorous perspective for the cost optimization for two level circuits and shows some of the potential computational difficulties of rigorous optimization problem solutions for digital circuits S Both sections require the study of sections 2 4 and 2 5 of the textbook Coverage of the tabular algorithm is optional but has as it prerequisite coverage of the prime implicant selection algorithm A PRIME IMPLICATION SELECTION ALGORITHM In Chapter 2 of Logic and Computer Design Fundamentals by Mano and Kime a selection rule for choosing non essential prime implicants for a sum of products expression for a function is given Recall this selection rule Minimize the overlap among prime implicants as much as possible In particular in the final solution make sure each prime implicant selected includes at least one minterm not included in any other prime implicant While it often gives good results the selection rule does not guarantee a minimum literal or gate input cost solution The alternative approach given here is systematic and guarantees a minimum cost solution 1 Pearson Education 2004 All rights reserved 1 C 00 01 11 00 01 10 1 1 1 1 1 1 B 11 1 A 10 1 1 ACD BD D FIGURE 1 Example 1 Need for Prime Implicant Selection Algorithm Why Is a Prime Implicant Selection Algorithm Needed Figure 1 illustrates the need for a prime implicant selection algorithm that goes beyond the selection rule In this example the essential prime implicants have been selected and the minterms covered by these prime implicants have been checked off The minterm without a check ABCD must be included in a prime implicant in the sum of products expression The two prime implicants that include this minterm are ACD and BD Applying the selection rule we pick ACD since this overlaps other prime implicants in only one minterm In contrast BD overlaps other prime implicants in three minterms But is this the best choice The answer is clearly no since ACD has three literals and BD has only two Selection of BD clearly gives a smaller literal cost demonstrating that the selection rule is inadequate for achieving the minimum literal cost goal The question we need to answer is How can we construct a systematic algorithm for prime implicant selection This example gives two hints at what is lacking in the selection rule First of all we need to take into account the number of literals required to implement the product term corresponding to a prime implicant Second we need a more systematic way of determining the overlap between prime implicants The algorithm we will give accomplishes both of these goals This algorithm solves what is generally referred to as a minimum covering problem hence we will refer to its solution which covers minterms of the function with prime implicants as a minimum prime implicant cover Two additional concepts related to the goals above and essential to the algorithm appear in the next section Less Than PIs and Secondary Essential PIs For simplicity we abbreviate the term prime implicant using PI For multiple prime implicants we add an s to give PIs In seeking a minimum PI cover we want to exclude those PIs that at the given stage of the algorithm execution would not be 2 C 00 00 01 11 1 1 1 10 1 BCD A CD 01 1 11 1 B 1 1 A 10 1 1 D FIGURE 2 Example 2 Less Than and Secondary Essential PIs included in the PI cover we are forming The less than PI concept permits us to do this Once one or more PIs have been excluded then some other PIs must be included in the PI cover and hence become essential These are called secondary essential PIs We will illustrate the concept of a less than relationship between two PIs and then proceed to definitions of less than a less than PI and equivalent PIs Consider the function represented on the K map in Figure 2 The essential PIs are A B and B D The minterms included in these PIs have been checked off We now focus on PIs A C D and B C D Both of these PIs include unchecked minterm ABCD But BCD also includes unchecked minterm ABCD Since we are interested in selecting PIs that include unchecked minterms would we ever select A C D rather than BCD The answer is no First of all the literal cost of implementing these two PIs is three in both cases so their cost is the same Second BCD includes all the unchecked minterms that A C D does but contains an additional unchecked minterm So BCD always contributes more to the goal of including minterms in PIs than A C D does and as a consequence in moving forward with this solution we will never want to use A C D We denote this by saying that A CD is less than BCD and call A C D a less than PI Since we will never use A C D we delete it Then BCD becomes the only PI left that includes ABCD making it essential at this stage in the solution As a consequence we say that BCD is a secondary essential PI and add it to the PIs in the solution We say that PIi is less than PIj denoted PIi PIj if 1 PIi contains at least as many literals as PIj and 2 PIj includes at least all of the as yet unchecked minterms that PIi includes Applying this to A C D and BCD A C D contains three literals as least as many as the three literals in BCD Also BCD includes ABCD the only unchecked minterm included in A C D but includes ABCD as well Thus A C D BCD 3 C 00 01 11 1 00 ACD 10 01 1 11 1 BD 1 d B 1 1 ACD A 10 ABD 1 1 1 D FIGURE 3 Example 3 Less Than Relation between PIs Absent and