# Algorithms and Number Systems for Hardware Computer Arithmetic

Arnaud TISSERAND
tutorial at ISSAC 2005

Affiliation in July 2005 : INRIA / LIP / Arénaire
Current affiliation : CNRS / LIRMM / ARITH

## 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
• Bibliography
• Part 2: hardware computer arithmetic basics
• Basic number systems: signed and unsigned integer, carry-save
• Basic cells and adders: HA, FA, counters, ripple, propagate/generate
• Bibliography
• Multiplication
• 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

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
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)
Arnaud Tisserand