Digital Arithmetic

Digital Arithmetic

by Miloš D. Ercegovac, Tomás Lang
Released September 2003
Publisher(s): Morgan Kaufmann
ISBN: 9780080530406

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Digital arithmetic plays an important role in the design of general-purpose digital processors and of embedded systems for signal processing, graphics, and communications. In spite of a mature body of knowledge in digital arithmetic, each new generation of processors or digital systems creates new arithmetic design problems. Designers, researchers, and graduate students will find solid solutions to these problems in this comprehensive, state-of-the-art exposition of digital arithmetic.Ercegovac and Lang, two of the field's leading experts, deliver a unified treatment of digital arithmetic, tying underlying theory to design practice in a technology-independent manner. They consistently use an algorithmic approach in defining arithmetic operations, illustrate concepts with examples of designs at the logic level, and discuss cost/performance characteristics throughout. Students and practicing designers alike will find Digital Arithmetic a definitive reference and a consistent teaching tool for developing a deep understanding of the "arithmetic style" of algorithms and designs.
  • Guides readers to develop sound solutions, avoid known mistakes, and repeat successful design decisions.
  • Presents comprehensive coverage¾from fundamental theories to current research trends.
  • Written in a clear and engaging style by two masters of the field.
  • Concludes each chapter with in-depth discussions of the key literature.
  • Includes a full set of over 250 exercises

Table of contents

  1. Front Cover
  2. Digital Arithmetic
  3. Copyright Page
  4. About the Authors
  5. Contents (1/2)
  6. Contents (2/2)
  7. Preface (1/2)
  8. Preface (2/2)
  9. Symbols and Notation
  10. Chapter 1. Review of the Basic Number Representations and Arithmetic Algorithms
    1. 1.1 Digital Arithmetic and Arithmetic Units
    2. 1.2 Basic Fixed-Point Number Representation Systems (1/3)
    3. 1.2 Basic Fixed-Point Number Representation Systems (2/3)
    4. 1.2 Basic Fixed-Point Number Representation Systems (3/3)
    5. 1.3 Addition, Change of Sign, and Subtraction (1/2)
    6. 1.3 Addition, Change of Sign, and Subtraction (2/2)
    7. 1.4 Range Extension and Arithmetic Shifts
    8. 1.5 Basic Multiplication Algorithms
    9. 1.6 Basic Division Algorithms (1/2)
    10. 1.6 Basic Division Algorithms (2/2)
    11. 1.7 Exercises (1/2)
    12. 1.7 Exercises (2/2)
    13. 1.8 Further Readings
    14. 1.9 Bibliography
  11. Chapter 2. Two-Operand Addition
    1. 2.1 About Carries (1/2)
    2. 2.1 About Carries (2/2)
    3. 2.2 Basic Carry-Ripple Adder (CRA) and FA Implementation
    4. 2.3 Reducing the Adder Delay
    5. 2.4 Switched Carry-Ripple (Manchester) Adder
    6. 2.5 Carry-Skip Adder (1/2)
    7. 2.5 Carry-Skip Adder (2/2)
    8. 2.6 Carry-Lookahead Adder (CLA) (1/2)
    9. 2.6 Carry-Lookahead Adder (CLA) (2/2)
    10. 2.7 Prefix Adder (1/2)
    11. 2.7 Prefix Adder (2/2)
    12. 2.8 Carry-Select and Conditional-Sum Adders (1/2)
    13. 2.8 Carry-Select and Conditional-Sum Adders (2/2)
    14. 2.9 Pipelined Adders
    15. 2.10 Variable-Time Adder
    16. 2.11 Two's Complement and Ones' Complement Adders
    17. 2.12 Adders with Redundant Digit Set (1/3)
    18. 2.12 Adders with Redundant Digit Set (2/3)
    19. 2.12 Adders with Redundant Digit Set (3/3)
    20. 2.13 Concluding Remarks
    21. 2.14 Exercises (1/2)
    22. 2.14 Exercises (2/2)
    23. 2.15 Further Readings
    24. 2.16 Bibliography (1/2)
    25. 2.16 Bibliography (2/2)
  12. Chapter 3. Multioperand Addition
    1. 3.1 Bit-Arrays for Unsigned and Signed Operands
    2. 3.2 Reduction (1/3)
    3. 3.2 Reduction (2/3)
    4. 3.2 Reduction (3/3)
    5. 3.3 Sequential Implementation
    6. 3.4 Combinational Implementation
    7. 3.5 Partially Combinational Implementation
    8. 3.6 Exercises (1/2)
    9. 3.6 Exercises (2/2)
    10. 3.7 Further Readings
    11. 3.8 Bibliography
  13. Chapter 4. Multiplication
    1. 4.1 Sequential Multiplication with Recoding (1/3)
    2. 4.1 Sequential Multiplication with Recoding (2/3)
    3. 4.1 Sequential Multiplication with Recoding (3/3)
    4. 4.2 Combinational Multiplication with Recoding (1/4)
    5. 4.2 Combinational Multiplication with Recoding (2/4)
    6. 4.2 Combinational Multiplication with Recoding (3/4)
    7. 4.2 Combinational Multiplication with Recoding (4/4)
    8. 4.3 Partially Combinational Implementation
    9. 4.4 Arrays of Smaller Multipliers
    10. 4.5 Multiply-Add and Multiply-Accumulate (MAC)
    11. 4.6 Saturating Multiplier
    12. 4.7 Truncating Multiplier
    13. 4.8 Rectangular Multipliers
    14. 4.9 Squarers
    15. 4.10 Constant and Multiple-Constant Multipliers
    16. 4.11 Concluding Remarks
    17. 4.12 Exercises (1/2)
    18. 4.12 Exercises (2/2)
    19. 4.13 Further Readings
    20. 4.14 Bibliography (1/2)
    21. 4.14 Bibliography (2/2)
  14. Chapter 5. Division by Digit Recurrence
    1. 5.1 Definition and Notation
    2. 5.2 Algorithm and Implementation of Fractional Division (1/2)
    3. 5.2 Algorithm and Implementation of Fractional Division (2/2)
    4. 5.3 Implementations of the Division Algorithm (1/4)
    5. 5.3 Implementations of the Division Algorithm (2/4)
    6. 5.3 Implementations of the Division Algorithm (3/4)
    7. 5.3 Implementations of the Division Algorithm (4/4)
    8. 5.4 Integer Division
    9. 5.5 Quotient-Digit Selection Function (1/6)
    10. 5.5 Quotient-Digit Selection Function (2/6)
    11. 5.5 Quotient-Digit Selection Function (3/6)
    12. 5.5 Quotient-Digit Selection Function (4/6)
    13. 5.5 Quotient-Digit Selection Function (5/6)
    14. 5.5 Quotient-Digit Selection Function (6/6)
    15. 5.6 Concluding Remarks
    16. 5.7 Exercises
    17. 5.8 Further Readings (1/2)
    18. 5.8 Further Readings (2/2)
    19. 5.9 Bibliography (1/3)
    20. 5.9 Bibliography (2/3)
    21. 5.9 Bibliography (3/3)
  15. Chapter 6. Square Root by Digit Recurrence
    1. 6.1 Recurrence and Step
    2. 6.2 Generation of Adder Input F [j]
    3. 6.3 Overall Algorithm, Implementation, and Timing (1/2)
    4. 6.3 Overall Algorithm, Implementation, and Timing (2/2)
    5. 6.4 Combination of Division and Square Root
    6. 6.5 Integer Square Root
    7. 6.6 Result-Digit Selection (1/2)
    8. 6.6 Result-Digit Selection (2/2)
    9. 6.7 Exercises
    10. 6.8 Further Readings
    11. 6.9 Bibliography
  16. Chapter 7. Reciprocal, Division, Reciprocal Square Root, and Square Root by Iterative Approximation
    1. 7.1 Reciprocal (1/3)
    2. 7.1 Reciprocal (2/3)
    3. 7.1 Reciprocal (3/3)
    4. 7.2 Division
    5. 7.3 Square Root
    6. 7.4 Example of Implementation of Division and Square Root
    7. 7.5 Concluding Remarks
    8. 7.6 Exercises
    9. 7.7 Further Readings
    10. 7.8 Bibliography
  17. Chapter 8. Floating-Point Representation, Algorithms, and Implementations
    1. 8.1 Floating-Point Representation
    2. 8.2 Roundoff Modes and Error Analysis (1/2)
    3. 8.2 Roundoff Modes and Error Analysis (2/2)
    4. 8.3 IEEE Standard 754
    5. 8.4 Floating-Point Addition (1/4)
    6. 8.4 Floating-Point Addition (2/4)
    7. 8.4 Floating-Point Addition (3/4)
    8. 8.4 Floating-Point Addition (4/4)
    9. 8.5 Floating-Point Multiplication (1/4)
    10. 8.5 Floating-Point Multiplication (2/4)
    11. 8.5 Floating-Point Multiplication (3/4)
    12. 8.5 Floating-Point Multiplication (4/4)
    13. 8.6 Floating-Point Division and Square Root (1/3)
    14. 8.6 Floating-Point Division and Square Root (2/3)
    15. 8.6 Floating-Point Division and Square Root (3/3)
    16. 8.7 Concluding Remarks
    17. 8.8 Exercises (1/2)
    18. 8.8 Exercises (2/2)
    19. 8.9 Further Readings
    20. 8.10 Bibliography (1/2)
    21. 8.10 Bibliography (2/2)
  18. Chapter 9. Digit-Serial Arithmetic
    1. 9.1 Introduction
    2. 9.2 LSDF Arithmetic (1/2)
    3. 9.2 LSDF Arithmetic (2/2)
    4. 9.3 MSDF: Online Arithmetic (1/7)
    5. 9.3 MSDF: Online Arithmetic (2/7)
    6. 9.3 MSDF: Online Arithmetic (3/7)
    7. 9.3 MSDF: Online Arithmetic (4/7)
    8. 9.3 MSDF: Online Arithmetic (5/7)
    9. 9.3 MSDF: Online Arithmetic (6/7)
    10. 9.3 MSDF: Online Arithmetic (7/7)
    11. 9.4 Concluding Remarks
    12. 9.5 Exercises
    13. 9.6 Further Readings
    14. 9.7 Bibliography (1/2)
    15. 9.7 Bibliography (2/2)
  19. Chapter 10. Function Evaluation
    1. 10.1 Argument Range Reduction
    2. 10.2 Correct Rounding and Monotonicity
    3. 10.3 Polynomial Approximations and Interpolations (1/2)
    4. 10.3 Polynomial Approximations and Interpolations (2/2)
    5. 10.4 Bipartite and Multipartite Table Method
    6. 10.5 Rational Approximation (1/2)
    7. 10.5 Rational Approximation (2/2)
    8. 10.6 Linear Convergence Method (1/4)
    9. 10.6 Linear Convergence Method (2/4)
    10. 10.6 Linear Convergence Method (3/4)
    11. 10.6 Linear Convergence Method (4/4)
    12. 10.7 Concluding Remarks
    13. 10.8 Exercises
    14. 10.9 Further Readings
    15. 10.10 Bibliography (1/2)
    16. 10.10 Bibliography (2/2)
  20. Chapter 11. CORDIC Algorithm and Implementations
    1. 11.1 Rotation and Vectoring Modes
    2. 11.2 Convergence, Precision, and Range
    3. 11.3 Compensation of Scaling Factor
    4. 11.4 Implementations
    5. 11.5 Extension to Hyperbolic and Linear Coordinates
    6. 11.6 Redundant Addition and High Radix (1/2)
    7. 11.6 Redundant Addition and High Radix (2/2)
    8. 11.7 Application-Specific Variations
    9. 11.8 Concluding Remarks
    10. 11.9 Exercises
    11. 11.10 Further Readings
    12. 11.11 Bibliography (1/2)
    13. 11.11 Bibliography (2/2)
  21. Bibliography (1/11)
  22. Bibliography (2/11)
  23. Bibliography (3/11)
  24. Bibliography (4/11)
  25. Bibliography (5/11)
  26. Bibliography (6/11)
  27. Bibliography (7/11)
  28. Bibliography (8/11)
  29. Bibliography (9/11)
  30. Bibliography (10/11)
  31. Bibliography (11/11)
  32. Index (1/2)
  33. Index (2/2)

Product information

  • Title: Digital Arithmetic
  • Author(s): Miloš D. Ercegovac, Tomás Lang
  • Release date: September 2003
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080530406