Christiane Frougny

Université Paris 8

cf at ai.univ-paris8.fr

Master IMA ISE - M2 : Arithmétique des ordinateurs

Il s'agit de présenter ici les principales méthodes utilisées dans la réalisation des additionneurs, des multiplieurs et des diviseurs en machine. Les possibilités algorithmiques sont conditionnées par les modes de représentation des nombres.

On étudiera dans ce cours diverses façons de représenter les nombres. En particulier, les systèmes de numération redondants permettent d'écrire des algorithmes plus rapides. Les algorithmes étudiés sont en série ou en parallèle, ou encore cellulaires. On montrera aussi comment calculer de manière performante les fonctions élémentaires en utilisant des représentations non classiques des nombres réels.

On fera également le point sur les développements récents en arithmétique embarquée.

Ce sujet a des liens nombreux avec l'algorithmique, l'architecture des machines, la conception de circuits intégrés, le calcul numérique.

Bibliographie

J.M. Muller, Arithmétique des ordinateurs, Masson, 1989. Téléchargeable ici.

A. Tisserand, cours Arithmétique des ordinateurs.

A. Guyot, site web.

Encyclopédie Wikipedia, Computer arithmetic : Fixed-point et Floating point.

Contrôle des connaissances

Devoir sur table mardi 6 janvier 2010. Seules les notes au-dessus de la moyenne seront comptabilisées.

Rapport écrit présentant l'un des articles dans la liste ci-dessous, à me renvoyer par email au plus tard le 20 janvier 2010.

RESULTATS.

Articles à lire au choix

  1. D. Menard, D. Chillet, F. Charot, O. Sentieys, Automatic Floating-point to Fixed-point Conversion for DSP Code Generation.
  2. Julius O. Smith III, Number Systems for Digital Audio.
  3. Lekatsas, Henkel and Wolf, Arithmetic coding for low power embedded system design.
  4. M. Joye and C. Tymen, Compact encoding of non-adjacent forms with applications to elliptic curves cryptography.
  5. Erle, Schulte, Hickmann, Decimal Floating-Point Multiplication Via Carry-Save Addition.
  6. A. Weimerskirch, C. Paar and S. C. Shantz, Elliptic curve cryptography on a Palm OS Device.
  7. M. Zheng and A. Albicki, Low power and high speed multiplication design through mixed number representations.
  8. A. Nannarelli and T. Lang, Low-power division: comparison among implementations of radix 4, 8 and 16.
  9. V. Paliouras and T. Stouraitis, Low-power Properties of the Logarithmic Number system.
  10. M. Arnold, The Residue Logarithmic Number System: Theory and Implementation.
  11. S. Wei, Number conversions between RNS and Mixed Radix number system.
  12. H. Neto and M. Vestias, Decimal multiplier on FGPA using embedded binary multipliers.
  13. M. Cowlishaw, Decimal Floating-Point: Algorism for Computers.
  14. Fang Fang, Tsuhan Chen, and Rob A. Rutenbar, Lightweight Floating-Point Arithmetic: Case Study of Inverse Discrete Cosine Transform.
  15. V. A. Bartlett and E. Grass, Exploiting Data-dependencies in Ultra Low-power DSP Arithmetic.