CS 61C L23 Combinational Logic Blocks (1)Garcia, Fall 2004 © UCBslashdot.org/article.pl?sid=04/10/21/0214230&tid=126&tid=216Lecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture 23 – Combinational Logic Blocks 2004-10-22Age of the Machines?⇒ “The UN's annual World RoboticsSurvey for 2004 predicts that there will be aseven-fold surge in household robots by theend of 2007. Robots that mow your lawn,vacuum, wash windows, clean swimmingpools, & entertainment robots such as theAibo are vying for a place in our homes.”irobot.comCS 61C L23 Combinational Logic Blocks (2)Garcia, Fall 2004 © UCBReview• Use this table and techniques welearned to transform from 1 to anotherCS 61C L23 Combinational Logic Blocks (3)Garcia, Fall 2004 © UCBA. (a+b) • (a+b) =?= b(a+b)•(a+b)aa+ab+ba+bbdistribution0+b(a+a)+bcomplimentarity,commutativity,distribution,idempotentb(1)+bidentity, complimentarityb+bidentitybidempotentPeer Instruction CorrectionTRUECS 61C L23 Combinational Logic Blocks (4)Garcia, Fall 2004 © UCBToday• Data Multiplexors• Arithmetic and Logic Unit• Adder/SubtractorCS 61C L23 Combinational Logic Blocks (5)Garcia, Fall 2004 © UCBData Multiplexor (here 2-to-1, n-bit-wide)“mux”CS 61C L23 Combinational Logic Blocks (6)Garcia, Fall 2004 © UCBN instances of 1-bit-wide muxHow many rows in TT?CS 61C L23 Combinational Logic Blocks (7)Garcia, Fall 2004 © UCBHow do we build a 1-bit-wide mux?CS 61C L23 Combinational Logic Blocks (8)Garcia, Fall 2004 © UCB4-to-1 Multiplexor?How many rows in TT?CS 61C L23 Combinational Logic Blocks (9)Garcia, Fall 2004 © UCBIs there any other way to do it?Hint: NCAA tourney!Ans: Hierarchically!CS 61C L23 Combinational Logic Blocks (10)Garcia, Fall 2004 © UCBAdministrivia : Midterm…• You spoke and we heard• The final can be in pen OR pencil- We should have given the choice of pen orpencil, and if you choose pencil, no regrade• More scratch space…will be there(trees be damned)• Want a regrade?• Return your exam and a stapledparagraph explaining which question(s)needed regrading AND WHY and we’lltake a look at the next TA mtg• Your grade MAY go down, no complaintsCS 61C L23 Combinational Logic Blocks (11)Garcia, Fall 2004 © UCBArithmetic and Logic Unit• Most processors contain a speciallogic block called “Arithmetic andLogic Unit” (ALU)• We’ll show you an easy one that doesADD, SUB, bitwise AND, bitwise ORCS 61C L23 Combinational Logic Blocks (12)Garcia, Fall 2004 © UCBOur simple ALUCS 61C L23 Combinational Logic Blocks (13)Garcia, Fall 2004 © UCBAdder/Subtracter Design -- how?• Truth-table, thendeterminecanonical form,then minimize andimplement as we’veseen before• Look at breakingthe problem downinto smaller piecesthat we cancascade orhierarchically layerCS 61C L23 Combinational Logic Blocks (14)Garcia, Fall 2004 © UCBAdder/Subtracter – One-bit adder LSB…CS 61C L23 Combinational Logic Blocks (15)Garcia, Fall 2004 © UCBAdder/Subtracter – One-bit adder (1/2)…CS 61C L23 Combinational Logic Blocks (16)Garcia, Fall 2004 © UCBAdder/Subtracter – One-bit adder (2/2)…CS 61C L23 Combinational Logic Blocks (17)Garcia, Fall 2004 © UCBN 1-bit adders ⇒ 1 N-bit adderWhat about overflow?Overflow = cn?+ + +b0CS 61C L23 Combinational Logic Blocks (18)Garcia, Fall 2004 © UCBWhat about overflow?• Consider a 2-bit signed # & overflow:•10 = -2 + -2 or -1•11 = -1 + -2 only•00 = 0 NOTHING!•01 = 1 + 1 only• Highest adder• C1 = Carry-in = Cin, C2 = Carry-out = Cout• No Cout or Cin ⇒ NO overflow!• Cin, and Cout ⇒ NO overflow!• Cin, but no Cout ⇒ A,B both > 0, overflow!• Cout, but no Cin ⇒ A,B both < 0, overflow!±#Whatop?CS 61C L23 Combinational Logic Blocks (19)Garcia, Fall 2004 © UCBWhat about overflow?• Consider a 2-bit signed # & overflow:10 = -2 + -2 or -111 = -1 + -2 only00 = 0 NOTHING!01 = 1 + 1 only• Overflows when…• Cin, but no Cout ⇒ A,B both > 0, overflow!• Cout, but no Cin ⇒ A,B both < 0, overflow!±#CS 61C L23 Combinational Logic Blocks (20)Garcia, Fall 2004 © UCBExtremely Clever SubtractorCS 61C L23 Combinational Logic Blocks (21)Garcia, Fall 2004 © UCBPeer InstructionA. Truth table for mux with 4-bits ofsignals is 24 rows longB. We could cascade N 1-bit shiftersto make 1 N-bit shifter for sll, srlC. If 1-bit adder delay is T, the N-bitadder delay would also be T ABC1: FFF2: FFT3: FTF4: FTT5: TFF6: TFT7: TTF8: TTTCS 61C L23 Combinational Logic Blocks (22)Garcia, Fall 2004 © UCBPeer Instruction AnswerA. Truth table for mux with 4-bits ofsignals is 24 rows longB. We could cascade N 1-bit shiftersto make 1 N-bit shifter for sll, srlC. If 1-bit adder delay is T, the N-bitadder delay would also be T ABC1: FFF2: FFT3: FTF4: FTT5: TFF6: TFT7: TTF8: TTTA. Truth table for mux with 4-bits of signalscontrols 16 inputs, for a total of 20inputs, so truth table is 220 rows…FALSEB. We could cascade N 1-bit shifters tomake 1 N-bit shifter for sll, srl … TRUEC. What about the cascading carry? FALSECS 61C L23 Combinational Logic Blocks (23)Garcia, Fall 2004 © UCB“And In conclusion…”• Use muxes to select among input• S input bits selects 2S inputs• Each input can be n-bits wide, indep of S• Implement muxes hierarchically• ALU can be implemented using a mux• Coupled with basic block elements• N-bit adder-subtractor done using N 1-bit adders with XOR gates on input• XOR serves as conditional
View Full Document
Unlocking...