Computer Arithmetic Chapter 8 – J. D. Carpinelli Chapter OutlineUnsigned NotationsSlide Number 4Addition: X  X + YOverflow (2’s complement)Subtraction: X  X - YOverflowMultiplicationMultiplicationMultiplicationMultiplicationShift-add Multiplication AlgorithmExample: UV  X  Y (X = 1101, Y = 1011)RTL CodeExample: UV  X  Y (X = 1101, Y = 1011)Hardware ImplementationOptimizing the RTL CodeOptimizing the RTL CodeExampleBooth’s AlgorithmExampleSlide Number 23RTL CodeExampleOptimized RTL CodeHardware ImplementationDivisionDivisionDivisionShift-subtract Division AlgorithmExample: UV  X (UV = 1001 0011, X = 1101)RTL CodeExampleHardware ImplementationRestoring Division AlgorithmOverflow ComparisonExampleRTL CodeExampleHardware ImplementationSigned NotationsSlide Number 43Slide Number 44Addition and SubtractionRTL CodeSlide Number 47ExamplesExamplesExamplesHardware ImplementationMultiplicationExampleBinary Coded Decimal (BCD)BCD 1-digit AdderNine’s ComplementSlide Number 57RTL Code for Addition and subtractionExamplesExamplesExamplesHardware ImplementationMultiplicationSlide Number 64Example (71*23)Arithmetic PipelinesSlide Number 67Slide Number 68ExampleSlide Number 70Slide Number 71Steady State Speedup Slide Number 73Speedup with 2-ns Latch DelaysSlide Number 75Lookup TablesExampleWallace TreesSlide Number 79Wallace TreesSlide Number 81ExampleSlide Number 834  4 Wallace Tree8  8 Wallace TreeFloating Point NumbersFloating Point NumbersRoundingExampleAddition and SubtractionAddition and SubtractionRTL CodeExample: (.1101  23) + (.1110  22)Example: (.1101  23) - (.1110  22)MultiplicationIEEE 754 Floating Point Standard IEEE 754 Floating Point StandardIEEE 754 Floating Point StandardDenormalized ValuesSummaryImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Computer ArithmeticChapter 8 – J. D. CarpinelliImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Chapter Outline• Unsigned notations• Signed notations• Binary Coded Decimal• Specialized arithmetic hardware• Floating point numbers• IEEE 754 floating point standardImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Unsigned Notations‘No additional bit to represent the sign’• Unsigned non-negative (‘0’ or positive)(0 to 2n-1)• Unsigned two’s-complement (positive and negative) (-2n-1 to 2n-1-1) (MSB=‘0’ for positive and MSB=‘1’ for negative numbers.) -7 representation is obtained by 2’s complement representation of +7.Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Unsigned Notations• Unsigned non-negative• Unsigned two’s-complementImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Addition: X ← X + YImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Overflow (2’s complement)‘Carry-into and out of the MSB are different => OV’Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Subtraction: X ← X - YImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Overflow‘Unsigned, non-negative subtraction: Carry-out =‘0’ => OV’Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Multiplication• A non-optimal method for z=x.y(by repeated addition)z = 0 FOR i = 1 TO y DO { z = z + x }=> Very slowImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Multiplication• A more typical method (shift-add)Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Multiplication• Calculating running totals (after each partial product, using two input adders)Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Multiplication• Shifting partial results to align sumsImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Shift-add Multiplication AlgorithmC = 0, U = 0;‘For binary numbers, x*0 = 0, x*1 = 1Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Example: UV ← X × Y(X = 1101, Y = 1011)C = 0, U = 0 0Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 RTL CodeC ←0, U ←0, i ←nImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Example: UV ← X × Y(X = 1101, Y = 1011)C ←0, U ←0, i ←40Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Hardware ImplementationData path-All the registersControl section-Counter, decoder, logic to generate LD, CLR, INC signalsImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Optimizing the RTL Code•UV ← X × V• Register Y is not needed• One operand is lostImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Optimizing the RTL CodeC ←0, U ←0Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 ExampleC ←0, U ←0, i ←40Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Booth’s Algorithm• Multiplying unsigned 2’s-complement numbersImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Example•UV ← X × Y, X = -3 (1101), Y = -5 (1011)Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Example•UV ← X × Y, X = -3 (1101), Y = -5 (1011)Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 RTL CodeImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 ExampleImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Optimized RTL CodeImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Hardware ImplementationImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Division• A non-optimal method for z = x ⁄ y(by repeated subtraction)=> InefficientImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Division• A more typical methodImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Division• Shifting results to align remaindersImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Shift-subtract Division AlgorithmOverflow: 11110000 / 1111 = 10000, does not fit in 4-bit regs.‘For binary numbers, 0/1 = 0, 1/1 = 1’Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Example: UV ÷ X(UV = 1001 0011, X = 1101)Images courtesy of Addison Wesley Longman, Inc. Copyright © 2001 RTL CodeImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 ExampleImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Hardware ImplementationImages courtesy of Addison Wesley Longman, Inc. Copyright © 2001 Restoring Division AlgorithmImages courtesy of Addison Wesley