CS231 (Fall 06) Review SessionAdministrativeOutlineA Complete ALU CircuitBinary addition by handAdding two bits (half adder)Adding three bitsFull adder equationsFull adder circuitA 4-bit adderAn example of 4-bit additionHierarchical adder designSome other IssuesQuiz 8.4Slide 15A 2x2 binary multiplierSlide 17Comparing the signed number systemsConverting signed numbers to decimalA two’s complement subtraction circuitAn adder-subtractor circuitSlide 22Examples from the past ExamsSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29Midterm1 ReviewBinary-Decimal ConversionBinary-Hexa ConversionCircuit AnalysisTruth tables and expressionsBoolean AlgebraK-MapsThree-variable K-MapCircuit Design2-to-4 decoderDesign example: additionDecoder-based adderA 4-to-1 multiplexerImplementing functions with multiplexersMultiplexer-based adderSlide 45CS231 (Fall 06)Review SessionSangkyum KimSep 29, 2006CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) AdministrativeMidterm1Time: 10/4(Wed) 11:00 ~ 11:50 amPlace: 1404 SCTopics: Up to (& including) Subtraction6-7 problemsBoolean algebra rules, Decoder & Mux Truth Table providedHW1,2 GradedPick up your file at TA office.CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) OutlineAdditionMultiplicationSubtractionMidterm1 ReviewCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) A Complete ALU Circuit 4 4 4 44CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Binary addition by hand1 1 1 0 Carry in1 0 1 1 Augend+ 1 1 1 0 Addend1 1 0 0 1 SumThe initial carryin is implicitly 0most significantbit, or MSBleast significantbit, or LSBCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Adding two bits (half adder)X Y C S0 0 0 00 1 0 11 0 0 11 1 1 00 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 10C = XYS = X’ Y + X Y’= X YBe careful! Now we’re using + for both arithmetic addition and the logical OR operation.CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Adding three bits0 + 0 + 0 = 000 + 0 + 0 = 010 + 1 + 0 = 010 + 1 + 1 = 101 + 0 + 0 = 011 + 0 + 1 = 101 + 1 + 0 = 101 + 1 + 1 = 11X Y CinCoutS0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 11 1 1 01 0 1 1+ 1 1 1 01 1 0 0 1CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Full adder equationsS = m(1,2,4,7)= X’ Y’ Cin + X’ Y Cin’ + X Y’ Cin’ + X Y Cin= X’ (Y’ Cin + Y Cin’) + X (Y’ Cin’ + Y Cin)= X’ (Y Cin) + X (Y Cin)’= X Y CinCout= m(3,5,6,7) = X’ Y Cin + X Y’ Cin + X Y Cin’ + X Y Cin= (X’ Y + X Y’) Cin + XY(Cin’ + Cin)= (X Y) Cin + XYX Y CinCoutS0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Full adder circuitS = X Y CinCout= (X Y) Cin + XYCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) A 4-bit adderCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) An example of 4-bit addition1 1 1 0 1 1 0 101. Fill in all the inputs, including CI=01 15. Use C3 to compute CO and S3 (1 + 1 + 1 = 11)02. The circuit produces C1 and S0 (1 + 0 + 0 = 01)113. Use C1 to find C2 and S1 (1 + 1 + 0 = 10)014. Use C2 to compute C3 and S2 (0 + 1 + 1 = 10)0Woohoo! The final answer is 11001 (twenty-five).OverflowA=1011 (eleven), B=1110 (fourteen)CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Hierarchical adder designCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Some other IssuesGate DelaysRipple Carry AdderCarry Lookahead AdderCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Quiz 8.4Based on the 4-bit ripple adder figure. Addition would be overflow if and only if _____ For unsigned addition• CO = 1• (A3 = B3 = 1) Or (A3 B3 = 1 && C3 = 1)CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) OutlineAdditionMultiplicationSubtractionMidterm1 ReviewCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) A 2x2 binary multiplierB1B0x A1A0A0B1A0B0+ A1B1A1B0C3C2C1C0a b ab0 0 00 1 01 0 01 1 1a b ab0 0 00 1 01 0 01 1 1CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) OutlineAdditionMultiplicationSubtractionMidterm1 ReviewCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Comparing the signed number systemsDecimal S.M. 1’s comp. 2’s comp. 7 0111 0111 0111 6 0110 0110 0110 5 0101 0101 0101 4 0100 0100 0100 3 0011 0011 0011 2 0010 0010 0010 1 0001 0001 0001 0 0000 0000 0000 -0 1000 1111 — -1 1001 1110 1111 -2 1010 1101 1110 -3 1011 1100 1101 -4 1100 1011 1100 -5 1101 1010 1011 -6 1110 1001 1010 -7 1111 1000 1001 -8 — — 1000CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Converting signed numbers to decimalConvert 110101 to decimal, assuming this is a number in:(a) signed magnitude format(b) 1’s complement(c) 2’s complement010101 21 110101 -21110101001010 10 -10110101001011 11 -11CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) A two’s complement subtraction circuitA – B = A + B’ + 1C0 C3 C2 C1 1A3 A2 A1 A0+ B3’ B2’ B1’ B0’C0 S3 S2 S1 S0CS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) An adder-subtractor circuitCS231 Computer Architecture I (2006 Spring) Review Session (9/29/2006)Sangkyum Kim ([email protected]) Some other IssuesSigned OverflowSign Extension0100 (+4)+ 0101(+5)01001 (-7)1100 (-4)+ 1011 (-5)10111 (+7)• Going from 4-bit to 8-bit numbers:1100 (-4) → 1111 1100 (-4)0101 (+5) → 0000 0101 (+5)… 1 111 1 1 1 1 1 1 0 0(-4)+ … 1 11 1 1 1 1 1 1 0 1 1(-5)… 1 11 1 1 1 1 1 0 1 1 1(+7)CS231 Computer
View Full Document
Unlocking...