University of Illinois at Urbana Champaign Dept of Electrical and Computer Engineering ECE 120 Introduction to Computing Boolean Properties and Optimization The Dual Form Swaps 0 1 and AND OR Boolean algebra has an interesting property called duality Let s define the dual form of an expression as follows Starting with the expression swap 0 with 1 just the values not variables and swap AND with OR ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 1 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 2 Every Boolean Expression Has a Dual Form The Dual of the Dual is the Expression For example what is the dual of A BC 0 D 1 First replace the 0 with 1 and the 1 with 0 Then replace OR with AND and vice versa We obtain A B C 1 D 0 So what is the dual of A B C 1 D 0 Since we re swapping things swapping them again produces the original expression A BC 0 D 1 Thus any Boolean expression has a unique dual and the dual of the dual is the expression hence the term duality two aspects of the same thing ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 3 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 4 3 4 2018 1 Pitfall Do Not Change the Order of Operations Why Do You Care One Reason the Principle of Duality Be careful not to change the order of operations when finding a dual form For example the dual form of is A BC A B C The operation on B and C must happen before the other operation Three reasons CMOS gate structures are dual forms Quick way to complement any expression the principle of duality Let s start with the last which we ll use shortly when we examine more properties Principle of duality If a Boolean theorem or identity is true false so is the dual of that theorem or identity ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 5 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 6 Generalized DeMorgan is Quick and Easy An Example of Finding a Complement with the Dual Form Let s say that we have an expression F To find F apply DeMorgan s Laws Apply repeatedly as many times as necessary Or use the generalized version based on duality Write the dual form of F Swap variables and complemented variables That s all F AB C DL G B A E H J A B What s F The dual is So A B C D L G B AE H J A B F A B C D L G BA E H J A B You can skip the middle step once you re comfortable with the process ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 7 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 8 3 4 2018 2 We Can Derive a Gate s Output from the n type Network We Can Also Derive Function from the p type Network What about CMOS gate structures Think about the network of n type MOSFETS connecting an output Q to 0V For example consider a set of four n type arranged in parallel with inputs A B C and D So Q 0 if ANY of the transistors is on In other words Q is 0 when A B C D Thus Q A B C D A NOR gate What about the p type transistors on the same gate They are arranged in series They connect Q to Vdd But p type transistors are on when their gates are set to 0 So Q 1 when ALL of the inputs are 0 Thus Q A B C D That s the same expression of course ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 9 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 10 The Expressions are Related via Generalized DeMorgan The Networks are Dual Forms of One Another But notice that we can also get the second form by applying generalized DeMorgan to the first form Starting with Q A B C D we find the dual of A B C D to be ABCD so Q A B C D The complemented variables come from the use of p type transistors The dual form is built into the gate design If we want to design a gate for something OTHER than NAND NOR NOT Write the output as Q expression Build that expression from n type MOSFETs Build the dual of the expression from p type MOSFETs ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 11 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 12 3 4 2018 3 An Example of an Unusual Gate Area and Speed for the Unusual Gate Consider the gate here From the n type network Q A B C The dual of the expression ignoring the complement is AB C which is the structure of the p type network So the function Q A B C requires six transistors and one gate delay We can of course limit ourselves to NAND NOR gates In that case Q A B C We use one two input NAND for A B and a second two input NAND for Q If we assume that A and B are available the NAND design requires eight transistors and two gate delays ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 13 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 14 Optimization versus Abstraction Simple Boolean Properties Most designers just use NAND and NOR or today even higher level abstractions In general breaking abstraction boundaries can give us an advantage but the boundaries make the design task less complex which improves human productivity and reduces the likelihood of mistakes That s another tradeoff Computer aided design CAD tools can perform some of these optimizations for us too Easy but useful to commit to memory for analyzing circuits 1 A 1 1 A A A A A A A 0 0 A 0 0 A A A A A A A 1 Each row gives two dual forms ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 15 ECE 120 Introduction to Computing 2016 Steven S Lumetta All rights reserved slide 16 3 4 2018 4 More Dual Form Boolean Properties OR Also Distributes Over AND in Boolean Algebra DeMorgan s Laws are also dual forms A B A B AB A B What about distributivity Here s the rule that you know from our usual algebra A B C AB AC multiplication distributes over addition It s also true in Boolean algebra AND distributes over OR A B C AB AC Now take the dual form A BC A …