PowerPoint PresentationReview…Representations of CL Circuits…Truth TablesTT Example #1: 1 iff one (not both) a,b=1TT Example #2: 2-bit adderTT Example #3: 32-bit unsigned adderTT Example #3: 3-input majority circuitLogic Gates (1/2)And vs. Or review – Dan’s mnemonicLogic Gates (2/2)2-input gates extend to n-inputsTruth Table Gates (e.g., majority circ.)Truth Table Gates (e.g., FSM circ.)Boolean AlgebraBoolean Algebra (e.g., for majority fun.)Boolean Algebra (e.g., for FSM)BA: Circuit & Algebraic SimplificationLaws of Boolean AlgebraBoolean Algebraic Simplification ExampleCanonical forms (1/2)Canonical forms (2/2)Peer Instruction“And In conclusion…”CS 61C L22 Representations of Combinatorial Logic Circuits (1)Garcia, Spring 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61c CS61C : Machine Structures Lecture 22 – Representations of Combinatorial Logic Circuits 2004-10-20E-voting talk todayAt 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... www.verifiedvoting.orgvotingintegrity.comCS 61C L22 Representations of Combinatorial Logic Circuits (2)Garcia, Spring 2004 © UCBReview…•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 & 164CS 61C L22 Representations of Combinatorial Logic Circuits (3)Garcia, Spring 2004 © UCBRepresentations of CL Circuits…•Truth Tables•Logic Gates•Boolean AlgebraCS 61C L22 Representations of Combinatorial Logic Circuits (4)Garcia, Spring 2004 © UCBTruth Tables0CS 61C L22 Representations of Combinatorial Logic Circuits (5)Garcia, Spring 2004 © UCBTT Example #1: 1 iff one (not both) a,b=1a b y0 0 00 1 11 0 11 1 0CS 61C L22 Representations of Combinatorial Logic Circuits (6)Garcia, Spring 2004 © UCBTT Example #2: 2-bit adderHowManyRows?CS 61C L22 Representations of Combinatorial Logic Circuits (7)Garcia, Spring 2004 © UCBTT Example #3: 32-bit unsigned adderHowManyRows?CS 61C L22 Representations of Combinatorial Logic Circuits (8)Garcia, Spring 2004 © UCBTT Example #3: 3-input majority circuitCS 61C L22 Representations of Combinatorial Logic Circuits (9)Garcia, Spring 2004 © UCBLogic Gates (1/2)CS 61C L22 Representations of Combinatorial Logic Circuits (10)Garcia, Spring 2004 © UCBAnd vs. Or review – Dan’s mnemonicAND GateCABSymbolA B C0 0 00 1 01 0 01 1 1DefinitionANDCS 61C L22 Representations of Combinatorial Logic Circuits (11)Garcia, Spring 2004 © UCBLogic Gates (2/2)CS 61C L22 Representations of Combinatorial Logic Circuits (12)Garcia, Spring 2004 © UCB2-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 (13)Garcia, Spring 2004 © UCBTruth Table Gates (e.g., majority circ.)CS 61C L22 Representations of Combinatorial Logic Circuits (14)Garcia, Spring 2004 © UCBTruth Table Gates (e.g., FSM circ.)PS Input NS Output00 0 00 000 1 01 001 0 00 001 1 10 010 0 00 010 1 00 1or equivalently…CS 61C L22 Representations of Combinatorial Logic Circuits (15)Garcia, Spring 2004 © UCBBoolean 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 NOTCS 61C L22 Representations of Combinatorial Logic Circuits (16)Garcia, Spring 2004 © UCBBoolean Algebra (e.g., for majority fun.)y = a • b + a • c + b • cy = ab + ac + bcCS 61C L22 Representations of Combinatorial Logic Circuits (17)Garcia, Spring 2004 © UCBBoolean Algebra (e.g., for FSM)PS Input NS Output00 0 00 000 1 01 001 0 00 001 1 10 010 0 00 010 1 00 1or equivalently…y = PS1 • PS0 • INPUTCS 61C L22 Representations of Combinatorial Logic Circuits (18)Garcia, Spring 2004 © UCBBA: Circuit & Algebraic SimplificationBA also great for circuit verificationCirc X = Circ Y?use BA to prove!CS 61C L22 Representations of Combinatorial Logic Circuits (19)Garcia, Spring 2004 © UCBLaws of Boolean AlgebraCS 61C L22 Representations of Combinatorial Logic Circuits (20)Garcia, Spring 2004 © UCBBoolean Algebraic Simplification ExampleCS 61C L22 Representations of Combinatorial Logic Circuits (21)Garcia, Spring 2004 © UCBCanonical forms (1/2)Sum-of-products(ORs of ANDs)CS 61C L22 Representations of Combinatorial Logic Circuits (22)Garcia, Spring 2004 © UCBCanonical forms (2/2)CS 61C L22 Representations of Combinatorial Logic Circuits (23)Garcia, Spring 2004 © UCBPeer InstructionA. (a+b)• (a+b) = bB. 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 ABC1: FFF2: FFT3: FTF4: FTT5: TFF6: TFT7: TTF8: TTTCS 61C L22 Representations of Combinatorial Logic Circuits (24)Garcia, Spring 2004 © UCB“And In conclusion…”•Use this table and techniques we learned to transform from 1 to
View Full Document
Unlocking...