inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 22 Representations of Combinatorial Logic Circuits 2004 10 20 Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia E voting talk today At 4pm in 306 Soda SU Prof David Dill will give a talk about important issues in electronic voting This affects us all Get there early CS 61C L22 Representations of Combinatorial Logic Circuits 1 www verifiedvoting org votingintegrity com Garcia Spring 2004 UCB Review We use feedback to maintain state Register files used to build memories D FlipFlops used for Register files Clocks usually tied to D FlipFlop load Setup and Hold times important Pipeline big delay CL for faster clock Finite State Machines extremely useful You ll see them again in 150 152 164 CS 61C L22 Representations of Combinatorial Logic Circuits 2 Garcia Spring 2004 UCB Representations of CL Circuits Truth Tables Logic Gates Boolean Algebra CS 61C L22 Representations of Combinatorial Logic Circuits 3 Garcia Spring 2004 UCB Truth Tables 0 CS 61C L22 Representations of Combinatorial Logic Circuits 4 Garcia Spring 2004 UCB TT Example 1 1 iff one not both a b 1 a 0 0 1 1 b 0 1 0 1 CS 61C L22 Representations of Combinatorial Logic Circuits 5 y 0 1 1 0 Garcia Spring 2004 UCB TT Example 2 2 bit adder How Many Rows CS 61C L22 Representations of Combinatorial Logic Circuits 6 Garcia Spring 2004 UCB TT Example 3 32 bit unsigned adder How Many Rows CS 61C L22 Representations of Combinatorial Logic Circuits 7 Garcia Spring 2004 UCB TT Example 3 3 input majority circuit CS 61C L22 Representations of Combinatorial Logic Circuits 8 Garcia Spring 2004 UCB Logic Gates 1 2 CS 61C L22 Representations of Combinatorial Logic Circuits 9 Garcia Spring 2004 UCB And vs Or review Dan s mnemonic AND Gate Symbol A B AN D Definition C CS 61C L22 Representations of Combinatorial Logic Circuits 10 A 0 0 1 1 B 0 1 0 1 C 0 0 0 1 Garcia Spring 2004 UCB Logic Gates 2 2 CS 61C L22 Representations of Combinatorial Logic Circuits 11 Garcia Spring 2004 UCB 2 input gates extend to n inputs N input XOR is the only one which isn t so obvious It s simple XOR is a 1 iff the of 1s at its input is odd CS 61C L22 Representations of Combinatorial Logic Circuits 12 Garcia Spring 2004 UCB Truth Table Gates e g majority circ CS 61C L22 Representations of Combinatorial Logic Circuits 13 Garcia Spring 2004 UCB Truth Table Gates e g FSM circ PS Input NS Output 00 0 00 0 00 1 01 0 01 0 00 0 01 1 10 0 10 0 00 0 10 1 00 1 CS 61C L22 Representations of Combinatorial Logic Circuits 14 or equivalently Garcia Spring 2004 UCB Boolean Algebra George Boole 19th Century mathematician Developed a mathematical system algebra involving logic later known as Boolean Algebra Primitive functions AND OR and NOT The power of BA is there s a one to one correspondence between circuits made up of AND OR and NOT gates and equations in BA means OR means AND x means NOT CS 61C L22 Representations of Combinatorial Logic Circuits 15 Garcia Spring 2004 UCB Boolean Algebra e g for majority fun y a b a c b c y ab ac bc CS 61C L22 Representations of Combinatorial Logic Circuits 16 Garcia Spring 2004 UCB Boolean Algebra e g for FSM PS Input NS Output 00 0 00 0 00 1 01 0 01 0 00 0 01 1 10 0 10 0 00 0 10 1 00 1 or equivalently y PS1 PS0 INPUT CS 61C L22 Representations of Combinatorial Logic Circuits 17 Garcia Spring 2004 UCB BA Circuit Algebraic Simplification BA also great for circuit verification Circ X Circ Y use BA to prove CS 61C L22 Representations of Combinatorial Logic Circuits 18 Garcia Spring 2004 UCB Laws of Boolean Algebra CS 61C L22 Representations of Combinatorial Logic Circuits 19 Garcia Spring 2004 UCB Boolean Algebraic Simplification Example CS 61C L22 Representations of Combinatorial Logic Circuits 20 Garcia Spring 2004 UCB Canonical forms 1 2 Sum of products ORs of ANDs CS 61C L22 Representations of Combinatorial Logic Circuits 21 Garcia Spring 2004 UCB Canonical forms 2 2 CS 61C L22 Representations of Combinatorial Logic Circuits 22 Garcia Spring 2004 UCB Peer Instruction A a b a b b 1 B N input gates can be thought of 2 3 cascaded 2 input gates I e 4 a bc d e a bc d e where is one of AND OR XOR NAND 5 6 C You can use NOR s with clever wiring 7 8 to simulate AND OR NOT CS 61C L22 Representations of Combinatorial Logic Circuits 23 ABC FFF FFT FTF FTT TFF TFT TTF TTT Garcia Spring 2004 UCB And In conclusion Use this table and techniques we learned to transform from 1 to another CS 61C L22 Representations of Combinatorial Logic Circuits 24 Garcia Spring 2004 UCB
View Full Document
Unlocking...