inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 23 Combinational Logic Blocks 2004 10 22 Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia Age of the Machines The UN s annual World Robotics Survey for 2004 predicts that there will be a seven fold surge in household robots by the end of 2007 Robots that mow your lawn vacuum wash windows clean swimming pools entertainment robots such as the irobot com Aibo are vying for a place in our homes Garcia Fall 2004 UCB CS 61C L23 Combinational Logic slashdot org article pl sid 04 10 21 0214230 tid 126 tid 216 Blocks 1 Review Use this table and techniques we learned to transform from 1 to another CS 61C L23 Combinational Logic Blocks 2 Garcia Fall 2004 UCB Peer Instruction Correction A a b a b b a b a b aa ab ba bb distribution 0 b a a b complimentarity commutativity distribution idempotent b 1 b identity complimentarity b b identity b idempotent CS 61C L23 Combinational Logic Blocks 3 TRUE Garcia Fall 2004 UCB Today Data Multiplexors Arithmetic and Logic Unit Adder Subtractor CS 61C L23 Combinational Logic Blocks 4 Garcia Fall 2004 UCB Data Multiplexor here 2 to 1 n bit wide mux CS 61C L23 Combinational Logic Blocks 5 Garcia Fall 2004 UCB N instances of 1 bit wide mux How many rows in TT CS 61C L23 Combinational Logic Blocks 6 Garcia Fall 2004 UCB How do we build a 1 bit wide mux CS 61C L23 Combinational Logic Blocks 7 Garcia Fall 2004 UCB 4 to 1 Multiplexor How many rows in TT CS 61C L23 Combinational Logic Blocks 8 Garcia Fall 2004 UCB Is there any other way to do it Hint NCAA tourney Ans Hierarchically CS 61C L23 Combinational Logic Blocks 9 Garcia Fall 2004 UCB Administrivia Midterm You spoke and we heard The final can be in pen OR pencil We should have given the choice of pen or pencil and if you choose pencil no regrade More scratch space will be there trees be damned Want a regrade Return your exam and a stapled paragraph explaining which question s needed regrading AND WHY and we ll take a look at the next TA mtg Your grade MAY go down no complaints CS 61C L23 Combinational Logic Blocks 10 Garcia Fall 2004 UCB Arithmetic and Logic Unit Most processors contain a special logic block called Arithmetic and Logic Unit ALU We ll show you an easy one that does ADD SUB bitwise AND bitwise OR CS 61C L23 Combinational Logic Blocks 11 Garcia Fall 2004 UCB Our simple ALU CS 61C L23 Combinational Logic Blocks 12 Garcia Fall 2004 UCB Adder Subtracter Design how Truth table then determine canonical form then minimize and implement as we ve seen before CS 61C L23 Combinational Logic Blocks 13 Look at breaking the problem down into smaller pieces that we can cascade or hierarchically layer Garcia Fall 2004 UCB Adder Subtracter One bit adder LSB CS 61C L23 Combinational Logic Blocks 14 Garcia Fall 2004 UCB Adder Subtracter One bit adder 1 2 CS 61C L23 Combinational Logic Blocks 15 Garcia Fall 2004 UCB Adder Subtracter One bit adder 2 2 CS 61C L23 Combinational Logic Blocks 16 Garcia Fall 2004 UCB N 1 bit adders 1 N bit adder b0 What about overflow Overflow cn CS 61C L23 Combinational Logic Blocks 17 Garcia Fall 2004 UCB What about overflow Consider a 2 bit signed overflow 10 11 00 01 2 2 or 1 1 2 only 0 NOTHING 1 1 only Highest adder C1 Carry in Cin C2 Carry out Cout No Cout or Cin NO overflow What Cin and Cout NO overflow op Cin but no Cout A B both 0 overflow Cout but no Cin A B both 0 overflow CS 61C L23 Combinational Logic Blocks 18 Garcia Fall 2004 UCB What about overflow Consider a 2 bit signed overflow 10 11 00 01 2 2 or 1 1 2 only 0 NOTHING 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 19 Garcia Fall 2004 UCB Extremely Clever Subtractor CS 61C L23 Combinational Logic Blocks 20 Garcia Fall 2004 UCB Peer Instruction A Truth table for mux with 4 bits of signals is 24 rows long B We could cascade N 1 bit shifters to make 1 N bit shifter for sll srl C If 1 bit adder delay is T the N bit adder delay would also be T CS 61C L23 Combinational Logic Blocks 21 1 2 3 4 5 6 7 8 ABC FFF FFT FTF FTT TFF TFT TTF TTT Garcia Fall 2004 UCB Peer Instruction Answer A Truth table for mux with 4 bits of signals controls 16 inputs for a total of 20 inputs so truth table is 220 rows FALSE B We could cascade N 1 bit shifters to make 1 N bit shifter for sll srl TRUE C What about the cascading carry FALSE ABC A Truth table for mux with 4 bits of 1 FFF 4 signals is 2 rows long 2 FFT B We could cascade N 1 bit shifters to make 1 N bit shifter for sll srl C If 1 bit adder delay is T the N bit adder delay would also be T CS 61C L23 Combinational Logic Blocks 22 3 4 5 6 7 8 FTF FTT TFF TFT TTF TTT 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 1bit adders with XOR gates on input XOR serves as conditional inverter CS 61C L23 Combinational Logic Blocks 23 Garcia Fall 2004 UCB
View Full Document
Unlocking...