Chapter 1: Introduction

1.1  Number representation

1.2  Algorithms

1.3  Hardware platforms

1.4  Hardware - software partitioning

1.5  Software generation

1.6  Synthesis

1.7 A first example

  1.7.1  Specification

  1.7.2  Number representation

  1.7.3  Algorithms

  1.7.4  Hardware platform

  1.7.5  Hardware - software partitioning     

  1.7.6  Program generation

  1.7.7  Synthesis

  1.7.8  Prototype       

1.8  Bibliography

Chapter 2: Mathematical Background

2.1  Number theory

  2.1.1  Basic definitions

  2.1.2  Euclidean algorithms 

  2.1.3  Congruences

2.2  Algebra   

  2.2.1  Groups           

  2.2.2  Rings  

  2.2.3  Fields 

  2.2.4  Polynomial rings       

  2.2.5  Congruences of polynomial   

2.3  Function approximation  

2.4  Bibliography       

Chapter 3: Number representation

3.1  Natural numbers

  3.1.1  Weighted systems

  3.1.2  Residue Number System

3.2  Integers

  3.2.1  Sign-magnitude representation

  3.2.2  Excess-E representation

  3.2.3  B's complement representation

  3.2.4  Booth's encoding

3.3  Real numbers

3.4  Bibliography

Chapter 4: Arithmetic operations: addition and subtraction

4.1  Addition of natural numbers

  4.1.1  Basic algorithm

  4.1.2  Faster algorithms

  4.1.3  Long-operand addition

  4.1.4  Multioperand addition

  4.1.5  Long - multioperand addition

4.2  Subtraction of natural numbers

4.3  Integers

  4.3.1  B's complement addition

  4.3.2  B's complement sign change

  4.3.3  B's complement subtraction

  4.3.4  B's complement overflow detection

  4.3.5 Excess-E addition and subtraction     

  4.3.6  Sign-magnitude addition and subtraction

4.4  Bibliography

Chapter 5: Arithmetic operations: multiplication

5.1  Natural numbers multiplication

  5.1.1  Introduction

  5.1.2  Shift and Add algorithms

    5.1.2.1  Shift and Add 1

    5.1.2.2  Shift and Add 2

    5.1.2.3  Extended Shift and Add algorithm:  XY+C+D

    5.1.2.4  Cellular Shift and Add

      5.1.2.4.1  Cellular ripple-carry algorithm

      5.1.2.4.2  Cellular carry-save algorithm

  5.1.3  Long-operand algorithm

5.2  Integers

  5.2.1  B's complement multiplication

    5.2.1.1  Mod Bn+m B’s complement multiplication

    5.2.1.2 Signed Shift and Add

    5.2.1.3 Post-correction B’s complement multiplication

  5.2.2  Post-correction 2’s complement multiplication

  5.2.3  Booth multiplication for binary numbers

    5.2.3.1 Booth-r algorithms

    5.2.3.2  Per Gelosia signed-digit algorithm

  5.2.4  Booth multiplication for base-B numbers (Booth-r algorithm in base B)

  5.3  Squaring

    5.3.1  Base-B squaring

      5.3.1.1  Cellular carry-save squaring algorithm 

    5.3.2  Base-2 Squaring

5.4 Bibliography

Chapter 6: Arithmetic operations: division

6.1  Natural numbers

6.2  Integers

  6.2.1  General algorithm

  6.2.2  Restoring division algorithm

  6.2.3  Base-2 non-restoring division algorithm

  6.2.4  SRT radix-2 division

  6.2.5  SRT radix-2 division with stored-carry encoding

  6.2.6  P-D diagram

  6.2.7  SRT-4 division

  6.2.8  Base-B non-restoring division algorithm

6.3  Convergence (functional iteration) algorithms

  6.3.1  Introduction

  6.3.2  Newton-Raphson’s iteration technique

  6.3.3  MacLaurin expansion – Goldschmidt’s Algorithm.

6.4 Bibliography

Chapter 7: Other arithmetic operations

7.1  Base conversion

7.2  Residue-Number-System conversion

  7.2.1  Introduction

  7.2.2  Base-B to RNS conversion

  7.2.3  RNS to Base-B conversion

7.3  Logarithmic, exponential and trigonometric functions

  7.3.1  Taylor-MacLaurin series

  7.3.2  Polynomial approximation

  7.3.3 Logarithm and exponential functions approximation by convergence methods

    7.3.3.1  Logarithm function approximation by multiplicative normalization

    7.3.3.2  Exponential function approximation by additive normalization

  7.3.4  Trigonometric functions – CORDIC algorithms

7.4  Square rooting

  7.4.1  Digit recurrence algorithm – base-B integers

  7.4.2  Restoring binary shift-and-subtract square rooting algorithm

  7.4.3  Non-restoring binary add-and-subtract square rooting algorithm

  7.4.4  Convergence method – Newton-Raphson

7.5  Bibliography

Chapter 8: Finite field operations

8.1  Operations in Zm

  8.1.1  Addition

  8.1.2  Subtraction

  8.1.3  Multiplication

    8.1.3.1  Multiply and reduce

    8.1.3.2  Modified shift-and-add algorithm

    8.1.3.3  Montgomery multiplication

    8.1.3.4  Specific ring

  8.1.4  Exponentiation

8.2   Operations in GF(p)

8.3  Operations in Zp [x] / f(x)

  8.3.1  Addition and subtraction

  8.3.2  Multiplication

8.4  Operations in GF(p**n)

8.5  Bibliography

Appendix 8.1 Computation of f(ki)

Chapter 9: Hardware Platforms

9.1  Design methods for electronic systems

  9.1.1  Basic blocks of integrated systems

  9.1.2  Recurring topics in electronic design

    9.1.2.1  Cost in integrated circuits

    9.1.2.2  Moore’s law

    9.1.2.3  Time-to-market

    9.1.2.4  Performance metric

    9.1.2.5  The power dimension

9.2  Processors instruction set

  9.2.1  Microprocessors

  9.2.2  Microcontrollers

  9.2.3  Embedded processors everywhere

  9.2.4  Digital signal processors

  9.2.5  Application-Specific Instruction-Set Processors

  9.2.6  Programming instruction set processors

9.3  ASIC designs

  9.3.1  Full-custom ASIC

  9.3.2  Semi-custom ASIC

    9.3.2.1  Gate Array - ASIC

    9.3.2.2  Standard-cell based ASIC

  9.3.3  Design flow in ASIC

9.4  Programmable Logic

  9.4.1  Programmable logic devices (PLD)

  9.4.2  Field Programmable Gate Array (FPGA)

    9.4.2.1  Why FPGA? A short historical survey

    9.4.2.2  Basic FPGA concepts

      9.4.2.2.1  Programming methods

      9.4.2.2.2  Look-up tables

      9.4.2.2.3  FPGA logic block

  9.4.3  Xilinx™ specifics

    9.4.3.1  Configurable Logic Blocks (CLB)

    9.4.3.2  Input/Output Blocks (IOB)

    9.4.3.3  RAM Blocks

    9.4.3.4  Programmable Routing

    9.4.3.5  Arithmetic resources in Xilinx™ FPGAs

  9.4.4  FPGA Generic Design Flow

9.5  Hardware Description Languages (HDL)

  9.5.1  Today’s and Tomorrow’s HDLs

9.6  Further readings

9.7  Bibliography

Chapter 10: Circuit synthesis: general principles

10.1  Resources

10.2  Precedence relation and scheduling

10.3  Pipeline

10.4  Self-timed circuits

10.5  Bibliography

Chapter 11: Adders and subtractors

11.1  Natural numbers

  11.1.1  Basic adder (ripple-carry adder)

  11.1.2  Carry-chain adder

  11.1.3  Carry-skip adder

  11.1.4  Optimization of carry-skip adders

  11.1.5  Base-Bs adder

  11.1.6  Carry-select adder

  11.1.7  Optimization of carry-select adders

  11.1.8  Carry-lookahead adders (CLA)

  11.1.9  Prefix adders

  11.1.10  FPGA implementation of adders

   11.1.10.1  Carry-chain adders

   11.1.10.2  Carry-skip adders

   11.1.10.3  Experimental results [BIO2003]

  11.1.11 Long-operand adders

  11.1.12  Multioperand adders

    11.1.12.1 Sequential multioperand adders

    11.1.12.2 Combinational multioperand adders     

    11.1.12.3 Carry-save adders

    11.1.12.4  Parallel counters

  11.1.13  Subtractors and adder-subtractors

  11.1.14  Termination detection

  11.1.15  FPGA implementation of the termination detection

11.2  Integers

  11.2.1  B's complement adders and subtractors

  11.2.2  Excess-E adders and subtractors

  11.2.3  Sign-magnitude adders and subtractors

11.3  Bibliography

Chapter 12: Multipliers

12.1  Natural numbers

  12.1.1  Basic multiplier

  12.1.2  Sequential multipliers

  12.1.3  Cellular multiplier arrays

    12.1.3.1  Ripple-carry multiplier

    12.1.3.2  Carry-save multiplier

    12.1.3.3  Figures of merit

  12.1.4  Multipliers based on dissymmetric Br x Bs cells

  12.1.5  Multipliers based on multioperand adders

  12.1.6  Per Gelosia multiplication arrays

    12.1.6.1 Introduction

    12.1.6.2 Adding tree for base B partial products

  12.1.7  FPGA Implementation of multipliers

12.2  Integers

  12.2.1  B's complement multipliers

  12.2.2  Booth multipliers

    12.2.2.1  Booth-1 multiplier

    12.2.2.2  Booth-2 multiplier

    12.2.2.3  Signed-digit multiplier

  12.2.3  FPGA Implementation of the Booth-1 multiplier

12.3 Bibliography

Chapter 13: Dividers

13.1  Natural numbers

13.2  Integers

  13.2.1  Base-2 non-restoring divider

  13.2.2  Base-B non-restoring divider

  13.2.3  SRT dividers

    13.2.3.1  SRT-2 divider

    13.2.3.2  SRT-2 divider with carry-save computation of the remainder

    13.2.3.3  FPGA Implementation of the carry-save SRT-2 divider

  13.2.4  SRT-4 divider

  13.2.5  Convergence dividers

    13.2.5.1  Newton-Raphson divider

    13.2.5.2  Goldschmidt divider

    13.2.5.3  Comparative data between Newton-Raphson (NR) and Goldschmidt (G) implementations

13.3  Bibliography

Chapter 14: Other arithmetic operators

14.1  Base conversion

  14.1.1  General base conversion

  14.1.2  BCD to binary converter

    14.1.2.1  Non-restoring 2p ’s subtracting implementation

    14.1.2.2  Shift-and-Add BCD to binary converter

  14.1.3  Binary to BCD converter

  14.1.4  Base-B to RNS converter

  14.1.5  CRT RNS to base-B converter

  14.1.6  RNS to Mixed-radix system converter

14.2  Polynomial computation circuits

14.3  Logarithm operator

14.4  Exponential operator

14.5  Sine and Cosine operators

14.6  Square rooters

  14.6.1  Restoring shift-and-subtract square rooter (naturals)

  14.6.2  Non-restoring shift-and-subtract square rooter (naturals)

  14.6.3  Newton-Raphson square rooter (naturals)

14.7  Bibliography

Chapter 15: Circuits for finite field operations

15.1  Operations in Zm

  15.1.1  Adders and subtractors

  15.1.2  Multiplication

    15.1.2.1  Multiply and reduce

    15.1.2.2  Shift and add

    15.1.2.3  Montgomery multiplication

    15.1.2.4  Modulo (Bk-c) reduction

    15.1.2.5  Exponentiation

15.2  Inversion in GF(p)

15.3  Operations in Zp [x] / f(x)

15.4  Inversion in GF(pn)

15.5  Bibliography

Chapter 16: Floating Point Units

16.1  Floating-point system definition

16.2  Arithmetic operations

  16.2.1  Addition of positive numbers

  16.2.2  Difference of positive numbers

  16.2.3  Addition and subtraction

  16.2.4  Multiplication

  16.2.5  Division

  16.2.6  Square root

16.3  Rounding schemes

16.4  Guard digits

16.5  Adder - subtractor

  16.5.1  Alignment

  16.5.2  Additions

  16.5.3  Normalization

  16.5.4  Rounding

16.6  Multiplier

16.7  Divider

16.8  Square root

16.9  Comments

16.10  Bibliography