inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 16 Representations of Combinatorial Logic Circuits Review We use feedback to maintain state Register files used to build memories D FlipFlops used to build Register files 2007 7 23 Scott Beamer Clocks tell us when D FlipFlops change Setup and Hold times important Instructor TODAY Representation of CL Circuits Plug in Hybrid Upgrades Available Truth Tables Logic Gates Boolean Algebra sfgate com CS61C L16 Representations of Combinatorial Logic Circuits 1 Beamer Summer 2007 UCB Truth Tables CS61C L16 Representations of Combinatorial Logic Circuits 2 TT Example 1 1 iff one not both a b 1 a 0 0 1 1 0 CS61C L16 Representations of Combinatorial Logic Circuits 3 Beamer Summer 2007 UCB TT Example 2 2 bit adder b 0 1 0 1 CS61C L16 Representations of Combinatorial Logic Circuits 4 y 0 1 1 0 Beamer Summer 2007 UCB TT Example 3 32 bit unsigned adder How Many Rows CS61C L16 Representations of Combinatorial Logic Circuits 5 Beamer Summer 2007 UCB Beamer Summer 2007 UCB How Many Rows CS61C L16 Representations of Combinatorial Logic Circuits 6 Beamer Summer 2007 UCB TT Example 3 3 input majority circuit CS61C L16 Representations of Combinatorial Logic Circuits 7 Beamer Summer 2007 UCB And vs Or review Dan s mnemonic Logic Gates 1 2 CS61C L16 Representations of Combinatorial Logic Circuits 8 Beamer Summer 2007 UCB Logic Gates 2 2 AND Gate Symbol A B D AN Definition C A 0 0 1 1 B 0 1 0 1 CS61C L16 Representations of Combinatorial Logic Circuits 9 C 0 0 0 1 Beamer Summer 2007 UCB CS61C L16 Representations of Combinatorial Logic Circuits 10 Beamer Summer 2007 UCB 2 input gates extend to n inputs Administrivia N input XOR is the only one which isn t so obvious Midterm TONIGHT 7 10pm in 10 Evans Bring Pencils pens One 8 5 x11 sheet of notes Green Sheet or copy of it It s simple XOR is a 1 iff the of 1s at its input is odd Don t bring calculators or other large electronics Assignments HW5 due 7 26 up today HW6 due 7 29 CS61C L16 Representations of Combinatorial Logic Circuits 11 Beamer Summer 2007 UCB CS61C L16 Representations of Combinatorial Logic Circuits 12 Beamer Summer 2007 UCB Truth Table Gates e g majority circ 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 CS61C L16 Representations of Combinatorial Logic Circuits 13 Beamer Summer 2007 UCB Boolean Algebra or equivalently CS61C L16 Representations of Combinatorial Logic Circuits 14 Beamer Summer 2007 UCB Boolean Algebra e g for majority fun 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 CS61C L16 Representations of Combinatorial Logic Circuits 15 Beamer Summer 2007 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 y a b a c b c y ab ac bc CS61C L16 Representations of Combinatorial Logic Circuits 16 BA Circuit Algebraic Simplification or equivalently BA also great for circuit verification Circ X Circ Y use BA to prove y PS1 PS0 INPUT CS61C L16 Representations of Combinatorial Logic Circuits 17 Beamer Summer 2007 UCB Beamer Summer 2007 UCB CS61C L16 Representations of Combinatorial Logic Circuits 18 Beamer Summer 2007 UCB Laws of Boolean Algebra CS61C L16 Representations of Combinatorial Logic Circuits 19 Boolean Algebraic Simplification Example Beamer Summer 2007 UCB Canonical forms 1 2 CS61C L16 Representations of Combinatorial Logic Circuits 20 Beamer Summer 2007 UCB Canonical forms 2 2 Sum of products ORs of ANDs CS61C L16 Representations of Combinatorial Logic Circuits 21 Beamer Summer 2007 UCB Peer Instruction CS61C L16 Representations of Combinatorial Logic Circuits 22 Beamer Summer 2007 UCB And In conclusion Pipeline big delay CL for faster clock Finite State Machines extremely useful You ll see them again in 150 152 164 Use this table and techniques we learned to transform from 1 to another A a b a b b B N input gates can be thought of cascaded 2 input gates I e a bc d e a bc d e where is one of AND OR XOR NAND C You can use NOR s with clever wiring to simulate AND OR NOT CS61C L16 Representations of Combinatorial Logic Circuits 23 1 2 3 4 5 6 7 8 ABC FFF FFT FTF FTT TFF TFT TTF TTT Beamer Summer 2007 UCB CS61C L16 Representations of Combinatorial Logic Circuits 26 Beamer Summer 2007 UCB
View Full Document
Unlocking...