Arithmetic and Algebraic Circuits

Description

Prologue Contents 1 Number Systems 1.1 Introduction 1.1.1 Additional Notation 1.1.2 Positional Notation 1.2 Positional Notation Using One Base 1.2.1 Most Efficient Radix 1.2.2 Base Conversion 1.2.3 Bases Power of Two 1.2.4 Modular Arithmetic 1.2.5 Fractional Numbers: Fixed Point Representation 1.3 Multiple Radix Representations 1.3.1 Double Radix 1.3.2 Mixed Radix 1.4 Negative Integer Numbers 1.4.1 SM Representation 1.4.2 Complement Representations 1.4.3 Biased Representation 1.4.4 Advantages and Disadvantages of the Different Representations 1.5 Binary Numbers Multiplication 1.5.1 SM Representation 1.5.2 Complement Representations 1.6 Division and Square Root of Binary Integer Numbers 1.6.1 Division 1.6.2 Square Root 1.7 Decimal Numbers 1.7.1 BCD Sum 1.7.2 Negative Decimal Numbers 1.7.3 Packed BCD Codification (CHC) 1.8 Signed Digits 1.8.1 Negative Digits 1.8.2 Conversion Between Representations 1.8.3 Binary Signed Digits (BSD) 1.9 Redundant Number Systems 1.9.1 Carry Propagation 1.9.2 Binary Case 1.10 Conclusion 1.11 Exercises References 2 Basic Arithmetic Circuits 2.1 Introduction 2.1.1 Serial and Parallel Information 2.1.2 Circuit Multiplicity and Pipelining 2.2 Binary Adders 2.2.1 Parallel Adders 2.2.2 Pipelined Adders 2.2.3 Serial Adders 2.3 Binary Subtractors 2.4 Multipliers 2.4.1 Combinational Multipliers 2.4.2 Sequential Multipliers 2.4.3 Multiplying by a Constant 2.5 Exponentiation 2.5.1 Binary Methods 2.5.2 Additive Chains 2.6 Division and Square Root 2.6.1 Combinational Divisors 2.6.2 Sequential Divisors 2.6.3 Dividing by a Constant 2.6.4 Modular Reduction 2.6.5 Calculating the Quotient by Undoing the Multiplication 2.6.6 Calculating the Quotient by Multiplying by the Inverse of the Divisor 2.6.7 Modular Reduction (Again) 2.6.8 Square Root 2.7 BCD Adder/Substracter 2.8 Comparators 2.9 Shifters 2.9.1 Shifters Built with Shift Registers 2.9.2 Combinational Shifters 2.10 Conclusion 2.11 Exercises References 3 Residue Number Systems 3.1 Introduction 3.2 Residue Algebra 3.3 Integer Representation Using Residues 3.4 Arithmetic Operations Using Residues 3.5 Mixed Radix System Associated to Each RNS 3.6 Moduli Selection 3.7 Conversions 3.7.1 From Positional Notation to RNS 3.7.2 From RNS to Positional Notation 3.8 Modular Circuits 3.8.1 Addition and Subtraction 3.8.2 Multiplication and Division 3.8.3 Montgomery Multiplier 3.8.4 Exponentiation 3.8.5 Two Implementation Examples: 3 and 7 3.9 Conclusion 3.10 Exercises References 4 Floating Point 4.1 Introduction 4.2 Precision and Dynamic Range 4.3 Rounding 4.3.1 Rounding Without Halfway Point 4.3.2 Rounding with Halfway Point 4.3.3 ROM Rounding 4.4 Decimal Rounding 4.5 Basic Arithmetic Operations and Rounding Schemes 4.5.1 Comparison 4.5.2 Addition and Subtraction 4.5.3 Multiplication and Division 4.5.4 Rounding Bits 4.5.5 Leading Zeros Detection 4.6 The IEEE 754 Standard 4.6.1 Binary Interchange Formats 4.6.2 Decimal Interchange Formats 4.6.3 Zero, Infinite and NaNs 4.6.4 Arithmetic Formats 4.6.5 Formats and Roundings 4.6.6 Operations 4.7 Circuits 4.7.1 Adder/Subtractor 4.7.2 Multiplier and Divider 4.7.3 Binary Square-Root 4.7.4 Comment 4.8 The Logarithmic System 4.8.1 Conversions 4.8.2 Arithmetic Operations 4.9 Conclusion 4.10 Exercises References 5 Addition and Subtraction 5.1 Introduction 5.2 Basic Concepts 5.3 Carry Propagation: Basic Structures 5.3.1 Considerations on Carry Propagation 5.3.2 Basic Carry Look-Ahead 5.3.3 Carry Look-Ahead Adders 5.3.4 Carry Skip Adders 5.3.5 Prefix Adders 5.4 Carry-Selection Addition: Conditional Adders 5.5 Multioperand Adders 5.5.1 Carry-Save Adders 5.5.2 Adder Trees 5.5.3 Signed Operands 5.6 Conclusion 5.7 Exercises References 6 Multiplication 6.1 Introduction 6.2 Basic Concepts 6.3 Combinational Multipliers 6.4 Combinational Multiplication of Signed Numbers 6.5 Basic Sequential Multipliers 6.5.1 Shift and Add Multipliers 6.5.2 Shift and Add Multiplication of Signed Numbers 6.6 Sequential Multipliers with Recoding 6.6.1 Multiplication Using Booth Codification 6.6.2 Multiplication Using (−1, 0, 1, 2) Coding 6.7 Special Multipliers 6.7.1 Multipliers with Saturation 6.7.2 Multiply-and-Accumulate (MAC) 6.7.3 Multipliers with Truncation 6.8 Conclusion 6.9 Exercises References 7 Division 7.1 Introduction 7.2 Basic Concepts 7.3 Non-restoring Division 7.4 Signed Non-restoring Division 7.5 SRT Division 7.5.1 Radix-2 SRT 7.5.2 Radix-4 SRT 7.5.3 Radix-4 SRT with Codification [−2, 2] 7.6 Conclusion 7.7 Exercises References 8 Special Functions 8.1 Introduction 8.2 A Case Study: The CORDIC 8.2.1 Circular Case 8.2.2 Hyperbolic Case 8.2.3 Linear Case 8.2.4 Unification and Modifications 8.2.5 Implementation 8.3 Shift-and-Add Algorithms 8.3.1 Algorithm for the Function et 8.3.2 Algorithm for the Function ln( x ) 8.4 Newton-Raphson Method 8.4.1 Square Root 8.4.2 Reciprocal 8.5 Polynomial Approximation 8.5.1 Least Squares Methods 8.5.2 Least Maximum Methods 8.6 Table-Based Methods 8.6.1 Mainly Look-Up Table Based Methods 8.6.2 Small Look-Up Tables Based Methods 8.6.3 Table-Based Balanced Methods 8.7 Conclusion 8.8 Exercises References 9 Basic Algebraic Circuits 9.1 LFSR 9.1.1 Type 1 LFSR 9.1.2 M Sequences 9.1.3 Polynomials Associated to LFSR1s 9.1.4 Type 2 LFSR 9.1.5 LFSRmod2m 9.2 LFSRmodp 9.2.1 Type 1 LFSRmodp 9.2.2 Type 2 LFSRmodp 9.2.3 LFSRmodpm 9.3 Circuits for Operating with Polynomials 9.3.1 Circuits for Polynomial Addition and Subtraction 9.3.2 Circuits for Polynomial Multiplication 9.3.3 Circuits for Polynomial Division 9.3.4 Multipliers and Divisors as Filters 9.4 Cellular Automata 9.4.1 One-Dimensional Linear Cellular Automata 9.4.2 One-Dimensional Non-linear Cellular Automata 9.4.3 Bidimensional Cellular Automata 9.4.4 Mod2n and Modp Cellular Automata 9.5 Conclusion 9.6 Exercises References 10 Galois Fields GF(2m) 10.1 Addition Over GF(2m) 10.2 Multiplication Over GF(2m) with Power Representation 10.3 Multiplication Over GF(2m) Using Standard Base 10.3.1 Modular Reduction 10.3.2 Parallel Multiplication 10.3.3 Serial-Parallel Multiplication 10.3.4 Serial Multiplication 10.4 Multiplication Over GF(2m) Using the Normal Base 10.5 Multiplication Over GF(2m) Using the Dual Base 10.6 Square and Square Root Over GF(2m) 10.6.1 Square 10.6.2 Square Root 10.7 Exponentiation Over GF(2m) 10.8 Inversion and Division Over GF(2m) 10.9 Operations Over GF((2n)m) 10.10 Conclusion 10.11 Exercises References 11 Galois Fields GF(pn) 11.1 GF(p) 11.1.1 Modular Reduction 11.1.2 Inversion and Division 11.2 Addition and Subtraction Over GF(p n) 11.3 Product Over GF(pn) Using Power Representation 11.4 Product Over GF(pn) Using the Standard Base 11.4.1 Parallel Multiplication 11.4.2 Serial-Parallel Multiplication 11.4.3 Serial Multiplication 11.5 Multiplication Over GF(pm) Using the Normal Base 11.6 Multiplication Over GF(pm) Using the Dual Base 11.7 A2 and Ap Over GF(pm) 11.7.1 Square 11.7.2 Ap 11.8 Exponentiation Over GF(pm) 11.9 Inversion and Division Over GF(pm) 11.10 Operations Over GF((pn)M) 11.11 Conclusion 11.12 Exercises References 12 Two Galois Fields Cryptographic Applications 12.1 Introduction 12.2 Discrete Logarithm Based Cryptosystems 12.2.1 Fundamentals 12.2.2 A Real Example: GF(2233) 12.3 Elliptic Curve Cryptosystems 12.3.1 Fundamentals 12.3.2 A Real Example: GF(2192 - 264 - 1) 12.4 Conclusion 12.5 Exercises References Appendix A Finite or Galois Fields A.1 General Properties A.1.1 Axioms A.1.2 Theorems A.2 GF(2) A.3 GF(p) A.4 GF(pm) A.5 References Appendix B Polynomial Algebra B.1 General Properties B.1.1 Polynomial Operations B.1.2 Congruence Relationship B.2 Polynomials Over GF(2) B.3 Polynomials Over GF(p) B.4 Finite Fields GF(2m) B.4.1 Standard Basis B.4.2 Normal Basis B.4.3 Dual Basis B.4.4 Inverse B.5 Finite Fields GF(pm) B.5.1 Standard Basis B.5.2 Normal Basis B.5.3 Dual Basis B.5.4 Inverse B.6 Finite Fields GF((pm)n) B.7 Conclusion B.8 References Appendix C Elliptic Curves C.1 General Properties C.2 Points Addition C.3 Scalar Multiplication C.4 Discrete Logarithm in Elliptic Curves C.5 Koblitz Curves C.6 Projective Coordinates C.7 Conclusion C.8 References Appendix D Errors D.1 Types of Errors D.1.1 Avoidable and Unavoidable Errors D.1.2 Absolute and Relative Errors D.2 Generated and Propagated Errors in Arithmetic Operations D.2.1 Sum and Difference D.2.2 Multiplication D.2.3 Division D.2.4 Square Root D.3 Errors and Laws of Algebra D.4 Interval Arithmetic D.5 Conclusion D.6 References Appendix E Algorithms for Function Approximation E.1 Newton-Raphson Approximation E.2 Polynomial Approximation E.2.1 Least Squares Polynomial Methods E.2.1.1 Chebyshev Orthogonal Polynomials E.2.1.2 Legendre Orthogonal Polynomials E.2.2 Least Maximum Polynomial Methods E.3 Tang’s Algorithm for the Exponential Function E.4 Conclusion E.5 References Index