Arithmetic and Logic in Computer Systems

Mi Lu9780471469452, 0-471-46945-9

Arithmetic and Logic in Computer Systems provides a useful guide to a fundamental subject of computer science and engineering. Algorithms for performing operations like addition, subtraction, multiplication, and division in digital computer systems are presented, with the goal of explaining the concepts behind the algorithms, rather than addressing any direct applications. Alternative methods are examined, and explanations are supplied of the fundamental materials and reasoning behind theories and examples.No other current books deal with this subject, and the author is a leading authority in the field of computer arithmetic. The text introduces the Conventional Radix Number System and the Signed-Digit Number System, as well as Residue Number System and Logarithmic Number System. This book serves as an essential, up-to-date guide for students of electrical engineering and computer and mathematical sciences, as well as practicing engineers and computer scientists involved in the design, application, and development of computer arithmetic units.

---

Table of contents :
Arithmetic and Logic in Computer Systems……Page 1
Contents……Page 8
Preface……Page 14
List of Figures……Page 16
List of Tables……Page 20
About the Author……Page 22
Computer Number Systems……Page 24
1.1 CONVENTIONAL RADIX NUMBER SYSTEM……Page 25
1.2 CONVERSION OF RADIX NUMBERS……Page 27
1.3 REPRESENTATIONOF SIGNED NUMBERS……Page 30
1.3.3 Radix Complement……Page 31
1.4 SIGNED-DIGIT NUMBER SYSTEM……Page 34
1.5.1 Normalization……Page 38
1.5.2 Bias……Page 39
1.6 RESIDUE NUMBER SYSTEM……Page 45
1.7 LOGARITHMIC NUMBER SYSTEM……Page 46
REFERENCES……Page 47
PROBLEMS……Page 49
2.1.1 Logical Devices……Page 52
2.1.2 Single-Bit Half-Adderand Full-Adders……Page 55
2.2 NEGATION……Page 58
2.2.1 Negation in One’s Complement System……Page 59
2.2.2 Negation in Two’s Complement System……Page 61
2.3 SUBTRACTIONTHROUGH ADDITION……Page 63
2.4 OVERFLOW……Page 66
2.5.1 Two’s Complement Addition……Page 67
2.5.2 One’s Complement Addition……Page 69
2.5.3 Sign-MagnitudeAddition……Page 71
REFERENCES……Page 73
PROBLEMS……Page 75
3.1 CONDITIONAL-SUM ADDITION……Page 76
3.2 CARRY-COMPLETION SENSING ADDITION……Page 79
3.3.1 Carry-Lookahead Adder……Page 84
3.3.2 Block Carry Lookahead Adder……Page 85
3.4 CARRY-SAVE ADDERS (CSA)……Page 89
3.5 BIT-PARTITIONED MULTIPLE ADDITION……Page 94
REFERENCES……Page 96
PROBLEMS……Page 97
Sequential Multiplication……Page 100
4.1 ADD-AND-SHIFT APPROACH……Page 101
4.2.3 One’s Complement Number Multiplication……Page 104
4.2.4 Two’s Complement Number Multiplication……Page 108
4.3 ROBERTSON’S SIGNED NUMBER MULTIPLICATION……Page 110
4.4.1 Non-overlappedMultiple Bit Scanning……Page 112
4.4.2 Overlapped MultipleBit Scanning……Page 113
4.4.3 Booth’s Algorithm……Page 116
4.4.4 Canonical Multiplier Recoding……Page 118
REFERENCES……Page 122
PROBLEMS……Page 123
5.1 WALLACE TREES……Page 126
5.2 UNSIGNEDARRAY MULTIPLIER……Page 128
5.3 TWO’S COMPLEMENT ARRAY MULTIPLIER……Page 131
5.3.1 Baugh-Wooley Two’s Complement Multiplier……Page 134
5.3.2 Pezaris Two’s Complement Multipliers……Page 140
5.4.1 Modular Structure……Page 143
5.4.2 Additive Multiply Modules……Page 146
5.4.3 Programmable Multiply Modules……Page 148
REFERENCES……Page 153
PROBLEMS……Page 155
6.1 SUBTRACT-AND-SHIFT APPROACH……Page 158
6.2 BINARY RESTORINGDIVISION……Page 161
6.3 BINARY NON-RESTORING DIVISION……Page 164
6.4.1 High-Radix Non-Restoring Division……Page 167
6.4.2 SRT Division……Page 169
6.4.4 Robertson’s High-Radix Division……Page 170
6.5 CONVERGENCE DIVISION……Page 173
6.5.1 Convergence Division Methodologies……Page 175
6.5.2 Divider Implementing Convergence Division Algorithm……Page 178
6.6 DIVISION BY DIVISOR RECIPROCATION……Page 180
REFERENCES……Page 185
PROBLEMS……Page 187
7.1 RESTORING CELLULAR ARRAY DIVIDER……Page 190
7.2 NON-RESTORING CELLULAR ARRAY DIVIDER……Page 194
7.3 CARRY-LOOKAHEAD CELLULAR ARRAY DIVIDER……Page 196
REFERENCES……Page 203
PROBLEMS……Page 204
8.1 FLOATING POINT ADDITION/SUBTRACTION……Page 206
8.2 FLOATING POINT MULTIPLICATION……Page 207
8.3 FLOATING POINT DIVISION……Page 211
8.4 ROUNDING……Page 212
REFERENCES……Page 217
PROBLEMS……Page 219
9.1 RNS ADDITION, SUBTRACTION AND MULTIPLICATION……Page 222
9.2.1 Unsigned Number Comparison……Page 223
9.2.3 Signed Numbers and Their Properties……Page 225
9.2.4 Multiplicative Inverseand the Parity Table……Page 226
9.3.1 Unsigned Number Division……Page 229
9.3.2 Signed Number Division……Page 232
REFERENCES……Page 239
PROBLEMS……Page 241
10.1 MULTIPLICATIONAND ADDITION IN LOGARITHMICSYSTEMS……Page 244
10.2 ADDITION AND SUBTRACTIONIN LOGARITHMICSYSTEMS……Page 245
10.3 REALIZING THE APPROXIMATION……Page 248
REFERENCES……Page 255
PROBLEMS……Page 256
11.1 CHARACTERISTICS……Page 258
11.2 TOTALLY PARALLELADDITION/SUBTRACTION……Page 259
11.3 REQUIRED AND ALLOWED VALUES……Page 260
11.4 MULTIPLICATIONAND DIVISION……Page 262
REFERENCES……Page 266
PROBLEMS……Page 267
Index……Page 268
End of Book……Page 269