CS61C L16 Representations of Combinatorial Logic Circuits (1) Beamer, Summer 2007 © UCBScott BeamerInstructorinst.eecs.berkeley.edu/~cs61cCS61C : Machine StructuresLecture #16 – Representations of CombinatorialLogic Circuits2007-7-23Plug-in HybridUpgradesAvailablesfgate.comCS61C L16 Representations of Combinatorial Logic Circuits (2) Beamer, Summer 2007 © UCBReview• We use feedback to maintain state• Register files used to build memories• D-FlipFlops used to build Register files• Clocks tell us when D-FlipFlops change• Setup and Hold times important• TODAY• Representation of CL Circuits- Truth Tables- Logic Gates- Boolean AlgebraCS61C L16 Representations of Combinatorial Logic Circuits (3) Beamer, Summer 2007 © UCBTruth Tables0CS61C L16 Representations of Combinatorial Logic Circuits (4) Beamer, Summer 2007 © UCBTT Example #1: 1 iff one (not both) a,b=1011101110000ybaCS61C L16 Representations of Combinatorial Logic Circuits (5) Beamer, Summer 2007 © UCBTT Example #2: 2-bit adderHowManyRows?CS61C L16 Representations of Combinatorial Logic Circuits (6) Beamer, Summer 2007 © UCBTT Example #3: 32-bit unsigned adderHowManyRows?CS61C L16 Representations of Combinatorial Logic Circuits (7) Beamer, Summer 2007 © UCBTT Example #3: 3-input majority circuitCS61C L16 Representations of Combinatorial Logic Circuits (8) Beamer, Summer 2007 © UCBLogic Gates (1/2)CS61C L16 Representations of Combinatorial Logic Circuits (9) Beamer, Summer 2007 © UCBAnd vs. Or review – Dan’s mnemonicAND GateCABSymbolA B C0 0 00 1 01 0 01 1 1DefinitionANDCS61C L16 Representations of Combinatorial Logic Circuits (10) Beamer, Summer 2007 © UCBLogic Gates (2/2)CS61C L16 Representations of Combinatorial Logic Circuits (11) Beamer, Summer 2007 © UCB2-input gates extend to n-inputs• N-input XOR is theonly one which isn’tso obvious• It’s simple: XOR is a1 iff the # of 1s at itsinput is odd ⇒CS61C L16 Representations of Combinatorial Logic Circuits (12) Beamer, Summer 2007 © UCBAdministrivia• Midterm TONIGHT 7-10pm in 10 Evans• Bring- Pencils/pens- One 8.5”x11” sheet of notes- Green Sheet (or copy of it)• Don’t bring calculators (or other largeelectronics)• Assignments• HW5 due 7/26 (up today)• HW6 due 7/29CS61C L16 Representations of Combinatorial Logic Circuits (13) Beamer, Summer 2007 © UCBTruth Table ⇒ Gates (e.g., majority circ.)CS61C L16 Representations of Combinatorial Logic Circuits (14) Beamer, Summer 2007 © UCBTruth Table ⇒ Gates (e.g., FSM circ.)100110000010010101000001001100000000OutputNSInputPSor equivalently…CS61C L16 Representations of Combinatorial Logic Circuits (15) Beamer, Summer 2007 © UCBBoolean Algebra• George Boole, 19th Centurymathematician• Developed a mathematicalsystem (algebra) involvinglogic• later known as “Boolean Algebra”• Primitive functions: AND, OR and NOT• The power of BA is there’s a one-to-onecorrespondence between circuits madeup of AND, OR and NOT gates andequations in BA + means OR,• means AND, x means NOTCS61C L16 Representations of Combinatorial Logic Circuits (16) Beamer, Summer 2007 © UCBBoolean Algebra (e.g., for majority fun.)y = a • b + a • c + b • cy = ab + ac + bcCS61C L16 Representations of Combinatorial Logic Circuits (17) Beamer, Summer 2007 © UCBBoolean Algebra (e.g., for FSM)100110000010010101000001001100000000OutputNSInputPSor equivalently…y = PS1 • PS0 • INPUTCS61C L16 Representations of Combinatorial Logic Circuits (18) Beamer, Summer 2007 © UCBBA: Circuit & Algebraic SimplificationBA also great for circuit verificationCirc X = Circ Y?use BA to prove!CS61C L16 Representations of Combinatorial Logic Circuits (19) Beamer, Summer 2007 © UCBLaws of Boolean AlgebraCS61C L16 Representations of Combinatorial Logic Circuits (20) Beamer, Summer 2007 © UCBBoolean Algebraic Simplification ExampleCS61C L16 Representations of Combinatorial Logic Circuits (21) Beamer, Summer 2007 © UCBCanonical forms (1/2)Sum-of-products(ORs of ANDs)CS61C L16 Representations of Combinatorial Logic Circuits (22) Beamer, Summer 2007 © UCBCanonical forms (2/2)CS61C L16 Representations of Combinatorial Logic Circuits (23) Beamer, Summer 2007 © UCBPeer InstructionA. (a+b)• (a+b) = bB. N-input gates can be thought ofcascaded 2-input gates. I.e.,(a ∆ bc ∆ d ∆ e) = a ∆ (bc ∆ (d ∆ e))where ∆ is one of AND, OR, XOR, NANDC. You can use NOR(s) with clever wiringto simulate AND, OR, & NOT ABC1: FFF2: FFT3: FTF4: FTT5: TFF6: TFT7: TTF8: TTTCS61C L16 Representations of Combinatorial Logic Circuits (26) 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 welearned to transform from 1 to
View Full Document
Unlocking...