1Supplement toLogic and ComputerDesign Fundamentals3rd Edition1MORE OPTIMIZATIONA PRIME IMPLICATION SELECTION ALGORITHMIn Chapter 2 of Logic and Computer Design Fundamentals by Mano and Kime, aselection rule for choosing non-essential prime implicants for a sum-of-productsexpression for a function is given. Recall this selection rule: “Minimize the overlapamong prime implicants as much as possible. In particular, in the final solutionmake sure each prime implicant selected includes at least one minterm notincluded in any other prime implicant.” While it often gives good results, the selec-tion rule does not guarantee a minimum literal or gate input cost solution. Thealternative approach given here is systematic and guarantees a minimum cost solu-tion.1© Pearson Education 2004. All rights reserved. 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. 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. S2Why Is a Prime Implicant Selection Algorithm Needed?Figure 1 illustrates the need for a prime implicant selection algorithm that goesbeyond the selection rule. In this example, the essential prime implicants havebeen selected and the minterms covered by these prime implicants have beenchecked off. The minterm without a check, ABCD, must be included in a primeimplicant in the sum-of-products expression. The two prime implicants that includethis minterm are ACD and BD. Applying the selection rule, we pick ACD sincethis overlaps other prime implicants in only one minterm. In contrast, BD overlapsother prime implicants in three minterms. But is this the best choice? The answer isclearly no, since ACD has three literals and BD has only two. Selection of BDclearly gives a smaller literal cost, demonstrating that the selection rule is inade-quate for achieving the minimum literal cost goal. The question we need to answer is: How can we construct a systematic algo-rithm for prime implicant selection? This example gives two hints at what is lackingin the selection rule. First of all, we need to take into account the number of literalsrequired to implement the product term corresponding to a prime implicant. Sec-ond, we need a more systematic way of determining the “overlap” between primeimplicants. The algorithm we will give accomplishes both of these goals. This algo-rithm solves what is generally referred to as a “minimum covering problem” –hence, we will refer to its solution which covers minterms of the function withprime implicants as a minimum prime implicant cover. Two additional conceptsrelated to the goals above and essential to the algorithm appear in the next section.Less Than PIs and Secondary Essential PIsFor simplicity, we abbreviate the term “prime implicant” using PI. For multipleprime implicants, we add an s to give PIs. In seeking a minimum PI cover, we wantto exclude those PIs that at the given stage of the algorithm execution would not beFIGURE 1Example 1 – Need for Prime Implicant Selection Algorithm00 01 11 1000011110ABDC111111111BDACD3included in the PI cover we are forming. The less than PI concept permits us to dothis. Once one or more PIs have been excluded, then some other PIs must beincluded in the PI cover and hence become essential. These are called secondaryessential PIs. We will illustrate the concept of a less than relationship between two PIs andthen proceed to definitions of less than, a less than PI, and equivalent PIs. Con-sider the function represented on the K-map in Figure 2. The essential PIs are A Band B D. The minterms included in these PIs have been checked off. We now focuson PIs A C D and B C D. Both of these PIs include unchecked minterm ABCD. ButBCD also includes unchecked minterm ABCD. Since we are interested in selectingPIs that include unchecked minterms, would we ever select A C D rather thanBCD? The answer is no. First of all, the literal cost of implementing these two PIsis three in both cases, so their cost is the same. Second, BCD includes all theunchecked minterms that A C D does, but contains an additional unchecked min-term. So BCD always contributes more to the goal of including minterms in PIsthan A C D does and, as a consequence, in moving forward with this solution, wewill never want to use A C D. We denote this by saying that A CD is less than BCDand 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 stagein the solution. As a consequence, we say that BCD is a secondary essential PI andadd it to the PIs in the solution.We say that PIi is less than PIj, denoted PIi ≤ PIj, if: 1) PIi contains at least asmany literals as PIj and 2) PIj includes at least all of the as yet unchecked mintermsthat PIi includes. Applying this to A C D and BCD, A C D contains three literals, asleast as many as the three literals in BCD. Also, BCD includes ABCD, the onlyunchecked minterm included in A C D but includes ABCD as well. Thus, A C D ≤BCD.FIGURE 2Example 2 – Less Than and Secondary Essential PIs00 01 11 1000011110ABDC1111111111A CDBCD4Assuming that BCD is now selected and ABCD and ABCD are nowchecked, are there