Computer Arithmetic:Principles,Architectures,and VLSI Design

1 IntroducTIon and ConvenTIons  4

1.1 Outline4

1.2 MoTIvaTIon  4

1.3 Conventions 5

1.4 Recursive Function Evaluation 6

2 Arithmetic Operations 8

2.1 Overview  8

2.2 Implementation Techniques  9

3 Number Representations10

3.1 Binary Number Systems (BNS) 10

3.2 Gray Numbers13

3.3 Redundant Number Systems  14

3.4 Residue Number Systems (RNS)16

3.5 Floating-Point Numbers18

3.6 Logarithmic Number System 19

3.7 Antitetrational Number System 19

3.8 Composite Arithmetic20

3.9 Round-Off Schemes21

4 Addition22

4.1 Overview  22

4.2 1-Bit Adders, (m, k)-Counters 23

4.3 Carry-Propagate Adders (CPA) 26

4.4 Carry-Save Adder (CSA)45

4.5 Multi-Operand Adders46

4.6 Sequential Adders 52

5 Simple / Addition-Based Operations53

5.1 Complement and Subtraction 53

5.2 Increment / Decrement54

5.3 Counting  58

5.4 Comparison, Coding, Detection 60

5.5 Shift, Extension, Saturation  64

5.6 Addition Flags66

5.7 Arithmetic Logic Unit (ALU) 68

6 Multiplication 69

6.1 Multiplication Basics69

6.2 Unsigned Array Multiplier  71

6.3 Signed Array Multipliers72

6.4 Booth Recoding73

6.5 Wallace Tree Addition75

6.6 Multiplier Implementations  75

6.7 Composition from Smaller Multipliers 76

6.8 Squaring  76

7 Division / Square Root Extraction77

7.1 Division Basics77

7.2 Restoring Division 78

7.3 Non-Restoring Division78

7.4 Signed Division79

7.5 SRT Division80

7.6 High-Radix Division81

7.7 Division by Multiplication  81

7.8 Remainder / Modulus82

7.9 Divider Implementations83

7.10 Square Root Extraction84

8 Elementary Functions85

8.1 Algorithms 85

8.2 Integer Exponentiation86

8.3 Integer Logarithm 87

9 VLSI Design Aspects 88

9.1 Design Levels88

9.2 Synthesis  90

9.3 VHDL91

9.4 Performance 93

9.5 Testability 95

Bibliography 96