Abstract
Computer arithmetic includes the study and the implementation of
algorithms for arithmetic operations (addition,
multiplication...), algebraic functions (division, square root...) and
elementary functions (sine, cosine, exponential, logarithm...). It
also includes the study of number systems for the
representation of numbers in practice and the various problems related
to accuracy. Depending on the implementation target,
hardware or software, several
solutions may be used. As usual in computer science, the correct
choice of the representation of data and of the algorithms widely
impacts the performances.
The goal of this tutorial is to present the main notions about
hardware computer arithmetic. After an
introduction on digital integrated circuit design, we will study the
main number systems and algorithms used in hardware implementations
for arithmetic operators. As an illustration, we will present some
examples in the field of hardware arithmetic operators for
cryptography.
Outline:
- Part 1: A Short Introduction to Digital Integrated Circuits
- Logic values: representation, standard levels
- Basic elements: wires, capacitors, transistors, logic gates, memory elements
- High-speed design: limits, fanout, transistor sizing
- Hardware complexity: definitions, examples
- Power consumption: definitions, low-power design
- Examples: gate libraries
- New technologies: roadmap
- Bibliography
- Part 2: hardware computer arithmetic basics
- Basic number systems: signed and unsigned integer, carry-save
- Addition
- Basic cells and adders: HA, FA, counters, ripple, propagate/generate
- Fast adders: select, skip, lookahead, parallel-prefix
- Redundant adders and multi-operand adders: carry-save, borrow-save
- Bibliography
- Multiplication
- Basic algorithms: shift-and-add, high-radix, Braun, Baugh-Wooley
- Recoding: Booth, modified Booth
- Fast multipliers: partial product generation, reduction, fast assimilation
- Modified multipliers: MAC, FMA, squarer
- Bibliography
- Part 3: examples in cryptography
- Modular operations
- Implementation examples
- Side-channel attacks
- Residue Number System
- Bibliography
Tutorial handout
PDF file
Prerequisites
- Computer arithmetic: binary representation of integers, modular arithmetic
- Digital integrated circuits: NOTHING
References
Books:
- CMOS VLSI Design: A Circuits and Systems Perspective
- Neil H.E. Weste and David Harris
- 3rd Edition, Addison Wesley, 2004
- Digital Arithmetic
- Milos Ercegovac and Tomas Lang
- Morgan Kaufmann, 2003
Conferences:
- ARITH17
- Symposium on Computer Arithmetic
- June 27-29, 2005, Cape Cod, Massachusetts, USA
- Asilomar 2005
- Asilomar Conference on Signals, Systems, and Computers
- Oct. 30 - Nov. 2, 2005, Pacific Grove, California, USA
- CHES 2005
- Workshop on Cryptographic Hardware and Embedded Systems
- Aug. 29 - Sep 1, 2005, Edinburgh, Scotland
Acknowledgments
- Dr Claude-Pierre Jeannerod and Dr Ziming Li for technical and organization support
- Ministère des Affaires Etrangères Français for
financial support (travel)