Chapter # 5: Arithmetic Circuits Contemporary Logic Design Randy H. Katz University of California, Berkeley Spring 2001MotivationChapter OverviewNumber SystemsSlide 5Slide 6Slide 7Number RepresentationsSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Networks for Binary AdditionSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Arithmetic Logic Unit DesignSlide 31Slide 32Slide 33Slide 34Slide 35Slide 36BCD AdditionSlide 38Combinational MultiplierSlide 40Slide 41Slide 42Case Study: 8 x 8 MultiplierSlide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Chapter ReviewContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-1Chapter # 5: Arithmetic CircuitsContemporary Logic DesignRandy H. KatzUniversity of California, BerkeleySpring 2001Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 instructionsContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-3Chapter Overview•Binary Number Representation Sign & Magnitude, Ones Complement, Twos Complement•Binary Addition Full Adder Revisted•ALU Design•BCD Circuits•Combinational Multiplier Circuit•Design Case Study: 8 Bit MultiplierContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-4Number SystemsRepresentation of Negative NumbersRepresentation of positive numbers same in most systemsMajor differences are in how negative numbers are representedThree 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 negativeContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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-1Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 -> 10004Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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+-Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 positionclockwiseContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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)Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 magnitudeContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-11Number SystemsAddition and Subtraction of NumbersOnes Complement Calculations4+ 37010000110111-4+ (-3)-71011110010111110004- 31010011001000010001-4+ 3-1101100111110End around carryEnd around carryContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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!Contemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 systemsContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-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 nContemporary Logic DesignArithmetic Circuits© R.H. Katz Transparency No. 5-15Number SystemsOverflow ConditionsAdd two positive numbers to get a negative numberor two negative numbers to get a positive number5 + 3 = -8!-7 - 2 =
View Full Document
Unlocking...