Résumé : Il est bien connu que l'addition dans un système de numération standard a une complexité linéaire, ce qui est trop lent pour faire un processeur arithmétique efficace. En 1961, Avizienis a donné un algorithme parallèle d'addition en base 10 avec les chiffres {-6, -5, ..., 5, 6} où la retenue ne se propage pas. On obtient ainsi une complexité (en parallèle) constante. Dans le langage de la dynamique symbolique, une telle addition est une fonction locale (sliding block code). Cette technique est utilisée pour accélérer les algorithmes de multiplication et de division.

Dans ce travail nous nous intéressons à des systèmes de numération où la base est un nombre algébrique beta, |beta|>1. Quand tous les conjugués algébriques de beta ont un module différent de 1, on peut trouver un alphabet symétrique de chiffres signés entiers sur lequel faire l'addition en parallèle. Cet algorithme est une généralisation de celui d'Avizienis.

L'algorithme d'addition est simple, mais l'alphabet obtenu est en général plus grand que nécessaire. Nous donnons des bornes inférieures sur la cardinalité minimale d'un alphabet permettant de faire l'addition en parallèle. Nous présentons ensuite une série de cas où la borne est atteinte.

Travail en collaboration avec Edita Pelantová et Milena Svobodová (CTU, Prague)

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr