1ECE 274 - Digital LogicLecture 9 Lecture 9 – Chapter 4.5 to Chapter 4.8 Multiple-Output Circuits Multilevel Synthesis Analysis of Multilevel Circuits Cubical Representation2ECE 274 - Digital LogicMultiple-Output Circuits Some circuits require multiple outputs Seven-segment display example Can we create a less expensive circuit by sharing overlapping gates?afbdgec3ECE 274 - Digital LogicMultiple-Output Circuit Example – Seven-Segment Displaya = w’x’y’z’ + w’x’yz’ + w’x’yz + w’xy’z + w’xyz’ + w’xyz + wx’y’z’ + wx’y’zb = w’x’y’z’ + w’x’y’z + w’x’yz’ + w’x’yz + w’xy’z’ + w’xyz + wx’y’z’ + wx’y’zw’x’y’z’w’x’yz’w’x’yzw’xyzwx’y’z’wx’y’zw’xy’zw’xyz’w’x’y’zw’xy’z’ab4001100 01 11 10000001 1 11110111110 0 0f2x3x4x1x2ECE 274 - Digital LogicMultiple-Output Circuits Example 2 We can also use K-maps and share same optimized variables Find low cost implementation of each function Group like variables001100 01 11 10010001 1 11100111110 0 0f1x3x4x1x2x2x3’x4x1x3’x1’x3x2x3x4f1f2f1 = x1x3’ + x1’x3 + x2x3’x4f2 = x1x3’ + x1’x3’ + x2x3x45000000 01 11 10100001 1 11011011110 0 0f4x3x4x1x2ECE 274 - Digital LogicMultiple-Output Circuits Example 3 Let’s try another example, same procedure Find low cost implementation of each function Group like variablesf3 = x1’x4 + x2x4 + x1’x2x3000000 01 11 10110001 1 01110011110 0 0f3x3x4x1x2f4 = x1x4 + x2’x4 + x1’x2x3x4’x2’x4x1’x2f3f4x1’x2x3x1x4x1’x4x2x4x3x4’nothing to combine6ECE 274 - Digital LogicMultiple-Output Circuits Example 3 Alternative Strategy Using same K-maps, let’s try something different Try to find overlapping implicants found in both maps Then try to find minimum cover for eachf3b = x1x2x4 + x1’x2x3x4’ + x1’x4000000 01 11 10110001 1 01110011110 0 0f3x3x4x1x2f4b = x1x2x4 + x1’x2x3x4’ + x2’x4000000 01 11 10100001 1 11011011110 0 0f4x3x4x1x2x2’x4f3f4x1’x4x1x1’x2x2x4x3x4’we could also group x2x3’x4’ – but it would increase implementation cost (try it out)7ECE 274 - Digital LogicMultiple-Output Circuits Alternative Strategy Comparison Different technique yields cost improvement Other techniques exist (sum-of-products vs. product-of-sum implementation) CAD Tools typically perform many kinds of optimizations to determine best implementationcost = 8 + 21 = 29cost = 6 + 17 = 23x2’x4x1’x2f3f4x1’x2x3x1x4x1’x4x2x4x3x4’x2’x4f3f4x1’x4x1x1’x2x2x4x3x4’8ECE 274 - Digital LogicMulti-level Synthesis Introduction Many of the circuits we have built are two-levels First level comprised of AND gates followed by a second level OR gate Product-of-sums formyabcdefghy = abc + bcd + cde + def + efg + fghx2’x4x1’x2f4x1x4x3x4’f4 = x1x4 + x2’x4 + x1’x2x3f3x1’x2x3x1’x4x2x4f3 = x1’x4 + x2x4 + x1’x2x3w’x’y’z’w’x’yz’w’x’yzw’xyzwx’y’z’wx’y’zw’xy’zw’xyz’aa = w’x’y’z’ + w’x’yz’ + w’x’yz + w’xy’z + w’xyz’ + w’xyz + wx’y’z’ + wx’y’z9ECE 274 - Digital LogicFan-in Problem Depending on the underlying technology fan-in can pose a problem Fan-in is the number of inputs to a logic gateyabcdefghy = abc + bcd + cde + def + efg + fghx2’x4x1’x2f4x1x4x3x4’f4 = x1x4 + x2’x4 + x1’x2x3f3x1’x2x3x1’x4x2x4f3 = x1’x4 + x2x4 + x1’x2x3w’x’y’z’w’x’yz’w’x’yzw’xyzwx’y’z’wx’y’zw’xy’zw’xyz’aa = w’x’y’z’ + w’x’yz’ + w’x’yz + w’xy’z + w’xyz’ + w’xyz + wx’y’z’ + wx’y’zfan-in = 3fan-in = 3fan-in = 6fan-in = 810ECE 274 - Digital LogicMulti-level Functions as A Solution to the Fan-in Problem Solution : Multilevel logic expression  Logic equation in a form with more than two levels of logic How do we synthesize multilevel circuits? Factoring Functional Decompositionefgabcdf3 = (ab + cd) + efgf3f4 = x1x4 + x2’x4 + x1’x2x3x2’x4x2’x4x1x4x1x4f411ECE 274 - Digital LogicFactoring We can take advantage of distributive property How much factoring should we perform? Assume we can have a maximum fan-in of 212a. x · (y + z) = xy + xz12b. x + y · z = (x+y) · (x+z)out = af’c + af’de + bgc + bgdeoutaf’af’cedbgbgcedf = af’c + af’de + bgc + bgdef = af’(c + de) + bg(c + de)f = (af’ + bg)(c + de)f = (af’ + bg)(c + de)cdebgaf’f412ECE 274 - Digital LogicFactoring Example 2 Implement F = x1x2’x3x4’x5x6 + x1x2x3’x4’x5’x6 Assume we can only have a fan-in of 4F = x1x2’x3x4’x5x6 + x1x2x3’x4’x5’x6Fx4’x5x1x2’x3x6x4’x5’x1x2x3’x6f = x1x2’x3x4’x5x6 + x1x2x3’x4’x5’x6f = x1x4’x6(x2’x3x5 + x2x3’x5’)f = x1x4’x6(x2’x3x5 + x2x3’x5’)fx2’x3x5x2x3’x5’x1x4’x613ECE 274 - Digital LogicFactoring Example 3 Design a circuit with the following specifications Four inputs x1, x2, x3, x4 Output f1 must be 1 when  At least one of the inputs x1 and x2 is equal to 1 and both x3 and x4 are equal to 1 x1 and x2 are equal to 0 and either x3 or x4 is equal to 1 All other cases f1 is 0 Output f2 is 1 in all cases, except x1 and x2 are equal to 0, or when both x3 and x4 are equal to 0f2’= x1’x2’ + x3’x4’f1= (x1+x2)x3x4+ x1’x2’(x3+x4)f1= x3x4 + x1’x2’(x3+ x4)f2’’= (x1’x2’ + x3’x4’)’Simplificationf2= (x1 +x2)(x3 + x4)DeMorgan’s Law14ECE 274 - Digital LogicFactoring Example 3f2= (x1 +x2)(x3 + x4)f1= x3x4 + x1’x2’(x3+ x4)f1= x3x4 + (x1+x2)’(x3+ x4)DeMorgan’s Lawx1’x2’ = (x1 + x2)’x3x4x1x2f1f2We can share (x3 + x4)We can share (x1 + x2)15ECE 274 - Digital LogicFunctional Decomposition Solution : Multilevel logic expression  Logic equation in a form with more than two levels of logic How do we synthesize multilevel circuits? Factoring Functional Decompositionefgabcdf3 = (ab + cd) + efgf3f4 = x1x4 + x2’x4 + x1’x2x3x2’x4x2’x4x1x4x1x4f4replace two-level logic equation with two or more new expressions which are then combined to define multilevel circuit16ECE 274 - Digital LogicFunctional Decomposition By Example Let’s look at an example F = x1’x2x3 + x1x2’x3 + x1x2x4 + x1’x2’x41. We’ve learned how to factor out common variablesF = x1’x2x3 + x1x2’x3 + x1x2x4 + x1’x2’x4F = (x1’x2 + x1x2’)x3 + (x1x2 + x1’x2’)x44. We can re-write the equation using gF = gx3 + g’x4g =