1ECE 274 - Digital LogicLecture 8 Lecture 8 – Chapter 4.2 to Chapter 4.4 Minimization Strategies Minimization of Product-of-Sums Forms Incompletely Specified Function2 Learned how to use K-map for logic optimization General strategy Pick biggest circles Pick as few circles as possible to cover all 1s Problems Is hard for functions with 5 or more variables May not yield minimum cover depending on order we choose Is error prone ECE 274 - Digital LogicK-map Methodology4 termsOnly 3 terms111000 01 11 10100111Iyzxy’z’ x’y’ yz xyxy111000 01 11 10100111Iyzxy’z’ x’z3xy111000 01 11 10100111Iyzxy’z’ x’z Minimization thus typically done by automated tools Exact algorithm: finds optimal solution Heuristic: finds good solution, but not necessarily optimal Let’s come up with our own heuristic to determine minimum-cost implementationECE 274 - Digital LogicK-map Methodology4010000 01 11 10000111Fbcaababc’abca’b’c4 implicants010000 01 11 10000111Fbcaaba’b’c2 prime ImplicantsECE 274 - Digital LogicTerminology Literal Appearance of a variable (true or complemented form)  Implicant Any product term (minterm or other) that when 1 causes F=1 On K-map, any legal (but not necessarily largest) circle Prime implicant Maximally expanded implicant – any further expansion would cover 1sF = a’b’c + abc + abc’6 Literals(a, a’, b, b’, c, c’)51 100000 01 11 1010111Gbcaa’b’ab4 prime implicants2 essential prime implicantsECE 274 - Digital LogicTerminology Essential prime implicant The only prime implicant that covers a particular minterm in a function’s on-setImportance: We must include all essential PIs in a function’s cover In contrast, some, but not all, non-essential PIs will be included6ECE 274 - Digital LogicTerminology Cover Collection of implicants that account for every instance F = 1 Particular implementation of the function Cost Number of gates + number of inputs Ignore complement (NOT)1100000 01 11 1010111Gbcaa’b’Cover 1: G = a’b’ + ac + ababac1100000 01 11 1010111Gbcaa’b’c’Cover 2: G = a’b’c’ + b’c + ababb’cG = a’b’c’ + b’c + abcost = 4 + 10 = 141 3-input OR gates1 3-input AND gates2 2-input AND gates7ECE 274 - Digital LogicK-Map Optimization MethodologyMethodology1. Generate all prime implicants 2. Find the set of essential prime implicants3. Does set of e.p.i covers all 1’s?o Yes - were done!o No – determine non-essential prime implicants that need to be added to form a complete coverHow? Randomly choose a n.e.p.i I, include I in the cover. Determine rest of cover. Assume I is not in cover, determine rest of cover. Compare cost of two covers, choose lowest.8ECE 274 - Digital LogicK-Map Optimization Methodology – Example 1Example 11. Generate all prime implicants 2. Find the set of essential prime implicants3. Does set of e.p.i covers all 1’s?o Yes - were done!o No – determine non-essential prime implicants that need to be added to form a complete coverI11000 01 11 10100101yzx11 11000 01 11 101 00101Iyzxx’zxz’Cover:e.p.i : x’z, xz’1 11000 01 11 10100101Iyzxy’z’x’ zxz’Cover 1:e.p.i : x’z, xz’, y’z’1 11000 01 11 10100101Iyzxy’z’x’ zxz’Cover 2:e.p.i : x’z, xz’, x’y’cost = 13 cost = 139ECE 274 - Digital LogicK-Map Optimization Methodology – Example 2Example 21. Generate all prime implicants 2. Find the set of essential prime implicants3. Does set of e.p.i covers all 1’s?o Yes - were done!o No – determine non-essential prime implicants that need to be added to form a complete coverCover:e.p.i : a’b’00 01 11 10cdab11110010001100010001111000 01 11 10cdab11110010001100010001111010ECE 274 - Digital LogicK-Map Optimization Methodology – Example 2Example 2Which non-essential prime implicants? Randomly choose a n.e.p.iI, include I in the cover. Determine rest of cover.Cover:e.p.i : a’b’00 01 11 10cdab111100100011000100011110Cover 1:e.p.i : a’b’, a’cd00 01 11 10cdab111100100011000100011110Cover 1:e.p.i : a’b’, a’cd, abc, b’cd’00 01 11 10cdab111100100011000100011110Cover 1:e.p.i : a’b’, a’cd, abc00 01 11 10cdab11110010001100010001111011ECE 274 - Digital LogicK-Map Optimization Methodology – Example 2Example 2Which non-essential prime implicants? Randomly choose a n.e.p.iI, include I in the cover. Determine rest of cover. Assume I is not in cover, determine rest of cover.Cover:e.p.i : a’b’00 01 11 10cdab111100100011000100011110Cover 2:e.p.i : a’b’, bcd00 01 11 10cdab111100100011000100011110Cover 2:e.p.i : a’b’, bcd, acd’00 01 11 10cdab11110010001100010001111012ECE 274 - Digital LogicK-Map Optimization Methodology – Example 2Example 2Which non-essential prime implicants? Randomly choose a n.e.p.iI, include I in the cover. Determine rest of cover. Assume I is not in cover, determine rest of cover. Compare cost of two covers, choose lowest.Cover:e.p.i : a’b’00 01 11 10cdab111100100011000100011110Cover 2 (cost = 15)F = a’b’ + bcd + acd’00 01 11 10cdab111100100011000100011110Cover 1 (cost = 20)F = a’b’ + a’cd + abc + b’cd’00 01 11 10cdab11110010001100010001111013ECE 274 - Digital LogicK-Map Methodology for Sum-of-Product vs. Product-of-SumsSum-of-productsF = a’b’ + abc00 01 11 10cdab111100000011000000011110Product-of-sumsF = (a+b’)(b’+c)(a’+b)00 01 11 10cdab111100000011000000011110 K-maps result in sum-of-products form We can also implement product-of-sums form Circle 0s instead of 1’s Use maxterms instead of mintermsWe’ll stick with sum-of-products form14abc Z000 x001 0010 0011 0100 1101 1110 1111 xabc = 000 and abc = 111 are unused inputsx00000 01 11 101101x1Gbcaaincluding this term doesn’t help usincluding this term enables better minimization Don’t Care Input Input combination that the designer doesn’t care what the output is i.e. input condition can never occur Represented as Xs in K-map Potential to enable further optimizationECE 274 - Digital LogicDon’t Care Input Combinations15ECE 274 - Digital LogicUsing Don’t Care Input CombinationsGood use of don’t caresUnnecessary use of don’t cares; results in extra term Assign don’t care outputs in a way that best minimizes the equation Include X in circle ONLY if minimizes equation Don’t include other XsX00000 01 11 101X0100Fyz y’z’ unneededxy’xX00000