COMP 411 Computer Organization Transistors and Logic Part Deux Don Porter Lecture 11 1 COMP 411 Computer Organization Today s Topics Basic gates Boolean algebra Synthesis using standard gates Truth tables Universal gates NAND and NOR Gates with more than 2 inputs Sum of Products DeMorgan s Law 2 COMP 411 Computer Organization Single Input Logic Gates A Y A Y NOT Y A A 0 1 Y 1 0 BUF Y A A 0 1 Y 0 1 3 COMP 411 Computer Organization Two Input Logic Gates AND Y AB B 0 1 0 1 A B A 0 0 1 1 Y Y 0 0 0 1 Y A B OR B 0 1 0 1 A B A 0 0 1 1 Y Y 0 1 1 1 4 COMP 411 Computer Organization More Two Input Logic Gates XOR XOR NAND NAND NOR NOR XNOR XNOR A A B B Y Y A A B B Y Y A A B B Y Y A A B B Y A B Y A B Y AB Y AB Y A B Y A B Y A B Y A B A A 0 0 0 0 1 1 1 1 B B 0 0 1 1 0 0 1 1 Y Y 0 0 1 1 1 1 0 0 A A 0 0 0 0 1 1 1 1 B B 0 0 1 1 0 0 1 1 Y Y 1 1 1 1 1 1 0 0 A A 0 0 0 0 1 1 1 1 B B 0 0 1 1 0 0 1 1 Y Y 1 1 0 0 0 0 0 0 A A 0 0 0 0 1 1 1 1 B B 0 0 1 1 0 0 1 1 Y Y Y Y 1 1 0 0 0 0 1 1 5 COMP 411 Computer Organization Multiple Input Logic Gates NOR3 Y A B C B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y Y 1 0 0 0 0 0 0 0 A B C A 0 0 0 0 1 1 1 1 6 COMP 411 Computer Organization Multiple Input Logic Gates NOR3 A B C A 0 0 0 0 1 1 1 1 Y Y 1 0 0 0 0 0 0 0 Y A B C B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 7 COMP 411 Computer Organization Basic gates vs single CMOS gates Not all basic gates can be implemented using a single CMOS gate Some can be inverter NAND NOR we have covered their CMOS implementation Others need multiple CMOS gates connected together AND implemented as NAND inverter OR implemented as NOR inverter buffer implemented as inverter inverter XOR XNOR will see shortly COMP 411 Computer Organization Boolean Algebra Algebra of 1s and 0s COMP 411 Computer Organization Table of Identities 10 COMP 411 Computer Organization Duals Left and right columns are duals Replace ANDs and ORs 0s and 1s 11 COMP 411 Computer Organization Single Variable Identities 12 COMP 411 Computer Organization Commutativity Operation is independent of order of variables 13 COMP 411 Computer Organization Associativity Independent of order in which we group So can also be simply written as X Y Z and XYZ 14 COMP 411 Computer Organization Distributivity 15 COMP 411 Computer Organization Substitution Can substitute arbitrarily large algebraic expressions for the variables Distribute an operation over the entire expression Example X YZ X Y X Z Substitute ABC for X ABC YZ ABC Y ABC Z 16 COMP 411 Computer Organization DeMorgan s Theorem Used a lot NOR invert then AND NAND invert then OR 17 COMP 411 Computer Organization Truth Tables for DeMorgan s 18 COMP 411 Computer Organization DeMorgan s Thm Bubble Pushing Bubble pushing imagine the bubble at the output is being pushed towards the inputs 1 2 it becomes a bubble at every input and the shape of the gate changes from AND to OR and vice versa 19 COMP 411 Computer Organization Algebraic Boolean Manipulation Apply algebraic and Boolean identities to simplify F YZ X ZYX XZ expression Example 20 COMP 411 Computer Organization F YZ X Simplification Example ZYX XZ F Z YX XZ Apply Z Apply Apply F XY 1 XZ F YX XZ 21 COMP 411 Computer Organization Fewer Gates YX XZ F 22 COMP 411 Computer Organization From Truth Table to Gate Level Circuit COMP 411 Computer Organization Start with Functional Spec We need to start somewhere usually it s the functional specification A B C If C is 1 then copy B to Y otherwise copy A to Y Y First step is to translate a verbal description into a tabular form Any combinational function can be represented as a truth table A truth table lists the output s for each combination of inputs Truth Table C B A Y 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 COMP 411 Computer Organization We Can Make Most Gates Out of Others Example 1 B A Output Y is 1 if and only if B is 1 AND A is 0 Y B AND NOT A A B y B A AB Y 00 0 01 1 10 0 11 0 COMP 411 Computer Organization Example 2 A XOR B Output Y is 1 if and only if We Can Make Most Gates Out of Others XOR AB Y 00 0 01 1 10 1 11 0 B is 1 AND A is 0 OR B is 0 AND A is 1 Y B AND NOT A OR A AND NOT B A B Y Y A B Symbol for XOR COMP 411 Computer Organization How many gates do we really need COMP 411 Computer Organization One Will Do NANDs and NORs are universal one can make any circuit out of just NANDs or out of just NORs X Y X Y X Y X Y COMP 411 Computer Organization Gates with more than two inputs Sometimes can be directly created in CMOS e g 3 input NOR 4 input NAND etc Often constructed using smaller gates e g N input AND gate using several 2 input AND gates AND A0 A1 A2 AN 1 AND AND AND A0 A1 A2 AN 1 A2 A3 AN 1 A1 A0 Delay in computing final output is linear in of gates O N can we do it faster COMP 411 Computer Organization Gate trees are faster More parallelism combine two at a time in parallel Like a tournament bracket A0 A1 A2 A3 AN 4 AN 3 AN 2 AN 1 Delay is now logarithmic O log2 N COMP 411 Computer Organization Systematic Approach Given truth table Develop Boolean equation COMP 411 Computer Organization Design Approach Sum of Products Three steps 1 Write functional spec as a truth table 2 Write down a Boolean expression for every row with 1 in the output …
View Full Document