Sign/Magnitude Represents –(2n-1-1) to +(2n-1-1)1’s complement Represents –(2n-1-1) to +(2n-1-1)2’s complement Represents –2n-1 to +(2n-1-1)CS150 Week 8, lecture 1 Covers:1) Number systems2) Computer datapaths3) Addition4) Hardware1) Number systemsS/M (Sign)(Magnitude) 0, 1, 2, 3 , 0, -1, -2,-3 What to do about decimal? 1’s complement X = 2n – 1 – X 0, 1, 2, 3, -3, -2, -1, 0 2 zeros Addition simple. Easy to ??2’s complement X* = 2n – X 0, 1, 2, 3, -4, -3, -2, -1 Harder to connect (a little) Addition easy2) Computer datapathsFig. 11.4, 11.13Also in book…STT:000 001 010 011 100 101 110 111 000 001 … X > 0 1’s Comp: 2n-1-X 2n2’s Comp: 2n-X 2n-1ALUACCMBRPCIRMARRAMFetchIncrementPCAdd Jump LoadStoreBranchNottaken3) AdditionOverflow/UnderflowRepresentation of negative numbersHardwareHow do you add (say you only have 4 bits.): 5 5 -5 -57 -7 7 -7 -------- ------ ------- --------12 -2 2 -12 Overflow. OK Same as Underflow Can’t represent 12 Subtract smaller 7 – 5 = 2 Can’t represent -12 with 4 bits from larger and negate with 4 bitsAddition sign rules for A + B = C:A & B same sign: Add and C’s sign is the same as A & B’s.A & B different signs: Subtract smaller number from larger number.Use sign of the bigger of |A| & |B| Sign/Magnitude Represents –(2n-1-1) to +(2n-1-1)n-Bit number.n = 4 : -7 to 7n = 8 : -127 to 127n = 32 : -2 billion to 2 billion 1st bit is sign bit. 1 negative # of bits 1 n-1 0 positiveX = Xn-1Xn-2Xn-3…X1X00100 = 4 ___- X = Xn-1Xn-2Xn-3…X1X01100 = -4ALUACCMBRRAMMARPCIRProblem: 2 zeros. 0000 & 10001’s complement Represents –(2n-1-1) to +(2n-1-1)X = Xn-1Xn-2Xn-3…X1X00100 = 4 __ __ __ __ __- X = Xn-1Xn-2Xn-3…X1 X01011 = -4Problem: Still 2 zeros. 0000 & 1111Note symmetry. 0000 1111, 0100 1011…2’s complement Represents –2n-1 to +(2n-1-1)X = Xn-1Xn-2Xn-3…X1X00100 = 4 __ __ __ __ __- X = Xn-1Xn-2Xn-3…X1 X0 + 1 1100 = -4No 2 zero problem!3 = 0011 -3 = 1100 + 1 = 11010 = 0000 -0 = 1111 + 1 = 0000-6 = 1010 --6 = 0101 + 1 = 0110-8 = 1000 --8 = 0111 + 1 = 1000 = -8!!!!! ERROR!!! Why? 000 001 010 011 100 101 110 111Sign/Mag 0 1 2 3 -0 -1 -2 -3 1’s Comp 0 1 2 3 -3 -2 -1 -0 Note symmetry 2 -2 010 1012’s Comp 0 1 2 3 -4 -3 -2 -1 Note 1xxx = -(2n-1 – xxx) MostnegativeAddition revisited:Sign/Mag: Same as decimal 001 110 (-2) 111 (-3)+ 011 + 011 (+3) + 010 (+2) 000 001 (+1) 101 (-1) Overflow1’s Complement: Positive numbers No problem-2 1101 (-2) 1110 (-1)+1 + 0001 (+1) + 0010 (+2) -1 1110 (-1) 0000 (0)????????????? Why? End around carry1’s complement is painful to implement in hardware: An-1B n-1SAME +AB --ABSAMEMUXn-1A>BABnth bitMUXAn-1B n-1If we just shifted the negative number right we’d get rid of the end-around-carry problem. But shifting the negative number right just gives us 2’s complement!!!!-2 1110 1111 -1 1 0001 0010 2-1 1111 0001 1Which are the correct results…Overflow in 2’s complement: Cin n-1 = Coutn-1Why?:0 1 2 3 -4 -3 -2 -1Overflow (Add to make number bigger than 3. Carry-in makes it negative. Can’t be carry out.) Underflow (Add to make number smaller than –4. No carry makes it positive. Carry-out is guaranteed )Either one of these gives a top bit that tells you whether there’s been overflow.Note: Positive numbers are the same in all systems. Sign/Mag and 1’s complement have 2 zeros (bad). Sign/Mag is hard to make adders (bad). 2’s complement is a little harder to negate (bad).4) Hardwarehalf-adder:Full adderAB SC Ai Bi CiSiCi+1Adder/subtracterA + B _A + ( B + 1 )Delays: Say all gates have a delay of 5ns.Then: tAS = 25 tAC = 35 tCS = This disagrees with Katz: Is carry-in (C0) zero?Note: Why would not want to make a 64 bit adder this way? (Hint: How does the delay increase per bit?) AB_B + 4 __Add/subCin 4 4OV (overflow?)NEG (Negative?)CO (Cout)SumCinFullAdderA0 B0S0CoutFullAdderA1 B1S1FullAdderA2 B2S2FullAdderA3 B3S3Overflow/Underflow Ai Bi
View Full Document
Unlocking...