[Wiley] Synthesis of Arithmetic Circuits - FPGA, ASIC and Embedded Systems - crop.pdf

SYNTHESIS OF
ARITHMETIC CIRCUITS
FPGA, ASIC, and Embedded Systems
JEAN-PIERRE DESCHAMPS
University Rovira i Virgili
GE´ RY JEAN ANTOINE BIOUL
National University of the Center of the Province of Buenos Aires
GUSTAVO D. SUTTER
University Autonoma of Madrid
A JOHN WILEY & SONS, INC., PUBLICATION
CONTENTS
Preface xvii
About the Authors xix
1 Introduction 1
Number Representation, 1
Algorithms, 2
Hardware Platforms, 2
Hardware–Software Partitioning, 3
Software Generation, 3
Synthesis, 3
A First Example, 3
Specification, 3
Number Representation, 6
Algorithms, 6
Hardware Platform, 8
Hardware–Software Partitioning, 8
Program Generation, 9
Synthesis, 10
Prototype, 12
Bibliography, 14
vii
viii CONTENTS
2 Mathematical Background 15
Number Theory, 15
Basic Definitions, 15
Euclidean Algorithms, 17
Congruences, 19
Algebra, 25
Groups, 25
Rings, 27
Fields, 27
Polynomial Rings, 27
Congruences of Polynomial, 32
Function Approximation, 35
Bibliography, 36
3 Number Representation 39
Natural Numbers, 39
Weighted Systems, 39
Residue Number System, 42
Integers, 42
Sign-Magnitude Representation, 42
Excess-E Representation, 43
B’plement Representation, 44
Booth’s Encoding, 47
Real Numbers, 51
Bibliography, 54
4 Arithmetic Operations: Addition and Subtraction 55
Addition of Natural Numbers, 55
Basic Algorithm, 55
Faster Algorithms, 57
Long-Operand Addition, 66
Multioperand Addition, 67
Long-Multioperand Addition, 70
Subtraction of Natural Numbers, 71
Integers, 71
B’plement Addition, 71
B’plement Sign Change, 72
B’plement Subtraction, 74
CONTENTS ix
B’plement Overflow Detection, 74
Excess-E Addition and Subtr