Lecture #23: Arithmetic Circuits-1Arithmetic Circuits(Part I)Randy H. KatzUniversity of California, BerkeleySpring 2007Lecture #23: Arithmetic Circuits-2MotivationArithmetic circuits are excellent examples of comb. logic design• Time vs. Space Trade-offs Doing things fast requires more logic and thus more space Example: carry lookahead logic • Arithmetic Logic Units Critical component of processor datapath Inner-most "loop" of most computer instructionsLecture #23: Arithmetic Circuits-3Overview•Binary Number Representation Sign & Magnitude, Ones Complement, TwosComplement•Binary Addition Full Adder Revisted•ALU Design•BCD Circuits•Combinational Multiplier Circuit•Design Case Study: 8 Bit Multiplier•Sequential Multiplier CircuitLecture #23: Arithmetic Circuits-4Number SystemsRepresentation of Negative NumbersRepresentation of positive numbers same in most systemsMajor differences are in how negative numbers arerepresentedThree major schemes:sign and magnitudeones complementtwos complementAssumptions:we'll assume a 4 bit machine word16 different values can be representedroughly half are positive, half are negativeLecture #23: Arithmetic Circuits-5Number SystemsSign and Magnitude Representation0000011100111011111111101101110010101001100001100101010000100001+0+1+2+3+4+5+6+7-0-1-2-3-4-5-6-70 100 = + 4 1 100 = - 4+-High order bit is sign: 0 = positive (or zero), 1 = negativeThree low order bits is the magnitude: 0 (000) thru 7 (111)Number range for n bits = +/-2 -1Representations for 0n-1Lecture #23: Arithmetic Circuits-6Number SystemsSign and MagnitudeCumbersome addition/subtractionMust compare magnitudes to determine sign of resultOnes ComplementN is positive number, then N is its negative 1's complementN = (2 - 1) - NnExample: 1's complement of 72 = 10000-1 = 00001 1111-7 = 0111 1000= -7 in 1's comp.Shortcut method: simply compute bit wise complement 0111 -> 10004Lecture #23: Arithmetic Circuits-7Number SystemsOnes ComplementSubtraction implemented by addition & 1's complementStill two representations of 0! This causes some problemsSome complexities in addition0000011100111011111111101101110010101001100001100101010000100001+0+1+2+3+4+5+6+7-7-6-5-4-3-2-1-00 100 = + 4 1 011 = - 4+-Lecture #23: Arithmetic Circuits-8Number RepresentationsTwos Complement0000011100111011111111101101110010101001100001100101010000100001+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-10 100 = + 4 1 100 = - 4+-Only one representation for 0One more negative number than positive numberlike 1's compexcept shiftedone positionclockwiseLecture #23: Arithmetic Circuits-9Number SystemsTwos Complement NumbersN* = 2 - NnExample: Twos complement of 72 = 100007 = 0111 1001 = repr. of -7Example: Twos complement of -742 = 10000-7 = 1001 0111 = repr. of 74subsubShortcut method:Twos complement = bitwise complement + 10111 -> 1000 + 1 -> 1001 (representation of -7)1001 -> 0110 + 1 -> 0111 (representation of 7)Lecture #23: Arithmetic Circuits-10Number RepresentationsAddition and Subtraction of NumbersSign and Magnitude4+ 37010000110111-4+ (-3)-7110010111111result sign bit is thesame as the operands'sign4- 31010010110001-4+ 3-1110000111001when signs differ,operation is subtract,sign of result dependson sign of number withthe larger magnitudeLecture #23: Arithmetic Circuits-11Number SystemsAddition and Subtraction of NumbersOnes Complement Calculations4+ 37010000110111-4+ (-3)-71011110010111110004- 31010011001000010001-4+ 3-1101100111110End around carryEnd around carryLecture #23: Arithmetic Circuits-12Number SystemsAddition and Subtraction of Binary NumbersOnes Complement CalculationsWhy does end-around carry work? Its equivalent to subtracting 2 and adding 1nM - N = M + N = M + (2 - 1 - N) = (M - N) + 2 - 1nn(M > N)-M + (-N) = M + N = (2 - M - 1) + (2 - N - 1) = 2 + [2 - 1 - (M + N)] - 1nnn nM + N < 2n-1after end around carry:= 2 - 1 - (M + N)nthis is the correct form for representing -(M + N) in 1's comp!Lecture #23: Arithmetic Circuits-13Number SystemsAddition and Subtraction of Binary NumbersTwos Complement Calculations4+ 37010000110111-4+ (-3)-711001101110014- 310100110110001-4+ 3-1110000111111If carry-in to sign =carry-out then ignorecarryif carry-in differs fromcarry-out then overflowSimpler addition scheme makes twos complement the most commonchoice for integer number systems within digital systemsLecture #23: Arithmetic Circuits-14Number SystemsAddition and Subtraction of Binary NumbersTwos Complement CalculationsWhy can the carry-out be ignored?-M + N when N > M:M* + N = (2 - M) + N = 2 + (N - M)nnIgnoring carry-out is just like subtracting 2n-M + -N where N + M < or = 2n-1-M + (-N) = M* + N* = (2 - M) + (2 - N) = 2 - (M + N) + 2nnAfter ignoring the carry, this is just the right twos compl.representation for -(M + N)!n nLecture #23: Arithmetic Circuits-15Number SystemsOverflow ConditionsAdd two positive numbers to get a negative numberor two negative numbers to get a positive number5 + 3 = -8!-7 - 2 = +7!0000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-10000000100100011100001010110010010011010101111001101011111101111+0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-1Lecture #23: Arithmetic Circuits-16Number SystemsOverflow Conditions53-80 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0-7-271 0 0 0 1 0 0 1 1 1 0 01 0 1 1 15270 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1-3-5-81 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0OverflowOverflowNo overflowNo overflowOverflow when carry in to sign does not equal carry outLecture #23: Arithmetic Circuits-17Networks for Binary AdditionHalf AdderWith twos complement numbers, addition is sufficientAi 0 0 1 1Bi 0 1 0 1Sum 0 1 1 0Carry 0 0 0 1AiBi0 1010 11 0Sum = Ai Bi + Ai Bi= Ai + BiAiBi0 1010 010Carry = Ai BiHalf-adder SchematicCarry Sum A i B i Lecture #23: Arithmetic Circuits-18Networks for Binary AdditionFull Adder+A3 B3S3+A2 B2S2+A1 B1S1+A0 B0S0C1C2C3Cascaded Multi-bit Adderusually interested in adding more than two bits this motivates the need for the full adderLecture #23: Arithmetic Circuits-19Networks for Binary AdditionFull AdderA 0 0 0 0 1 1 1 1B 0 0 1 1 0 0 1 1CI 0 1 0 1 0 1 0 1S 0 1 1 0 1 0 0 1CO 0 0 0 1 0 1 1 1A BCI0100 01 11 1001101001A BCI0100 01 11 1000010111SCOS = CI xor A xor BCO = B CI + A CI + A B = CI (A + B) + A
View Full Document
Unlocking...