Système de numération d'Avizienis

En mathématiques, et notamment en arithmétique, un système de numération d'Avizienis est un système de numération positionnel des entiers, relativement à une base entière qui est complet, au sens que tout entier est représentable, et redondant (un entier peut avoir plusieurs représentations). La redondance est assurée par l'introduction de chiffres (ou digits) en sus de ceux de la base. L'intérêt du système réside dans sa capacité à effectuer l'addition (et la soustraction) d'entiers sans propagation de retenue. Le système a été proposé par Algirdas Antanas Avižienis en 1961.

Les systèmes positionnels classiques utilisent des chiffres, dont la place dans l'écriture du nombre indique le poids qui leur est affecté, c'est-à-dire la puissance de la base par laquelle ils sont multipliés et qui correspond à leur position dans la représentation. Dans un tel système, une base $b$ nécessite au moins $b$ chiffres pour pouvoir représenter tous les entiers. Typiquement, la valeur de ces chiffres va de $0$ à $b-1$, et alors la représentation des entiers naturels dans un système positionnel est unique. Les systèmes redondants utilisent pour une base $b$ un nombre de chiffres strictement supérieur à $b$. Le système d'Avizienis est un système redondant à chiffres signés, ce qui signifie que les chiffres peuvent être positifs ou négatifs. Par exemple, pour la base 3, les chiffres vont de −2 à +2.

Notations

On se fixe une base entière $b\geq 2$ (en fait il faut $b\geq 3$ pour que l'addition fonctionne), et un entier $a>0$. Le système de numération d'Avizienis possède $2a+1$ chiffres qui vont de $-a$ à $a$. On note les chiffres négatifs en les surlignant, ainsi ${\bar {1}},{\bar {2}},{\bar {3}},\ldots$ signifient $-1,-2,-3,\ldots$.

Par exemple, en base 3, avec les chiffres ${\bar {2}},{\bar {1}},0,1,2$, la notation

$2{\bar {1}}0{\bar {2}}$

représente le nombre $43$, puisque

$2\cdot 3^{3}-1\cdot 3^{2}+0\cdot 3^{1}-2\cdot 3^{0}=2\cdot 27-9-2=43$.

Le plus grand entier de $n$ chiffres que l'on peut représenter dans cette base s'écrit en utilisant des chiffres tous égaux à $a$, c'est donc

$a(b^{n-1}+\cdots +b+1)=a(b^{n}-1)/(b-1)$.

On peut montrer que l'on doit avoir $2a>b-2$ pour pouvoir représenter tous les entiers (c'est nécessaire puisque par exemple pour $a=1$ et $b=4$, on ne peut représenter $2$).

Algorithme d'addition

Prérequis

L'algorithme d'addition d'Avizienis sans propagation de retenue suppose une base $b>2$ et $2a+1$ chiffres ${\bar {a}},\ldots ,a$, avec $b/2<a<b$. La condition $b/2<a$ est plus forte que la relation $b/2-1<a$, qui assure que tout entier est représentable, et garantit l'absence de propagation de retenue. La deuxième condition, à savoir $a<b$, assure que les chiffres sont plus petits en valeur absolue que la base.

Présentation

Étant donnés deux entiers

$x=x_{n-1}\cdots x_{0}$ et $y=y_{n-1}\cdots y_{0}$

écrits sur $n$ chiffres dans cette base, on cherche à calculer dans cette base

$z=z_{n}\cdots z_{0}$

où

$z=x+y$

Pour cela, pour $i=0,\ldots ,n-1$, on calcule la retenue qui est prise comme un chiffre prenant deux valeurs : $1$ et ${\bar {1}}$.

$t_{i+1}={\begin{cases}{\bar {1}}&{\text{si }}\ x_{i}+y_{i}\leq -a,\\0&{\text{si }}\ {-a}<x_{i}+y_{i}<a,\\1&{\text{si }}\ x_{i}+y_{i}\geq a.\end{cases}}$

et on pose :

$w_{i}=x_{i}+y_{i}-bt_{i+1}$.

On pose également :

$w_{n}=t_{0}=0$.

Les calculs de retenues $t_{i}$ peuvent se faire en parallèle; en d'autres termes, il n'y a pas d'ordre à respecter dans leur évaluation. On a enfin, pour $i=0,\ldots ,n$,

$z_{i}=w_{i}+t_{i}$.

Exemple

On prend la base $b=4$. La condition $b/2<a<b$ s'écrit ici $2<a<4$, et on prend donc $a=3$. Les chiffres autorisés sont ${\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3$. Les nombres à additionner sont à $n=5$ chiffres

$x=(-697)_{10}={\bar {3}}102{\bar {1}}$ et $y=(498)_{10}=20{\bar {1}}1{\bar {2}}$

Les calculs sont regroupés dans le tableau que voici

$i$	5	4	3	2	1	0
$x_{i}$		${\bar {3}}$	$1$	$0$	$2$	${\bar {1}}$
$y_{i}$		$2$	$0$	${\bar {1}}$	$1$	${\bar {2}}$
$x_{i}+y_{i}$		${\bar {1}}$	$1$	${\bar {1}}$	$3$	${\bar {3}}$
$t_{i}$	$0$	$0$	$0$	$1$	${\bar {1}}$	$0$
$w_{i}$	$0$	${\bar {1}}$	$1$	${\bar {1}}$	${\bar {1}}$	$1$
$z_{i}$	$0$	${\bar {1}}$	$1$	$0$	${\bar {2}}$	$1$

On obtient bien: ${\bar {1}}10{\bar {2}}1=(-199)_{10}=(-697)_{10}+(498)_{10}$.

Principe de fonctionnement

On a

$z_{i}=w_{i}+t_{i}=x_{i}+y_{i}+t_{i}-bt_{i+1}$.

À chaque position $i$, le chiffre calculé est la somme des chiffres $x_{i}$ et $y_{i}$, plus la retenue $t_{i}$ de la position précédente; si la somme de $x_{i}$ et $y_{i}$ dépasse les bornes autorisées, on en soustrait ou ajoute la base, pour rentrer dans les bornes permises. Ce qui est particulier dans cet algorithme, c'est que la retenue $t_{i+1}$ ne dépend pas de la retenue précédente $t_{i}$. Dans l'addition classique avec retenue, on fait la même opération, mais dans le cas où la somme des deux chiffres $x_{i}$ et $y_{i}$ et de la retenue $t_{i}$ dépasse la base, il faut la reporter, conduisant dans le cas classique, à calculer la valeur de la retenue précédente avant celle de la retenue courante, d'où une séquentialisation des calculs. Ici, le test laisse assez de marge pour pouvoir absorber la retenue $t_{i}$, puisque $-a<w_{i}<a$. Les calculs de retenues peuvent donc se faire en parallèle. Le seul ordonnancement est la nécessité d'avoir calculé la retenue courante et la retenue précédente avant de calculer chaque chiffre de la somme.

Pour être précis, il faut d'abord vérifier que les chiffres $z_{i}$ sont bien compris dans l'intervalle de $-a$ à $a$. Pour cela, on part de

$z_{i}=w_{i}+t_{i}=x_{i}+y_{i}+t_{i}-bt_{i+1}$.

Si $-a<x_{i}+y_{i}<a$, alors $t_{i+1}=0$, et comme $t_{i}\in \{0,{\bar {1}},1\}$, on a $-a\leq x_{i}+y_{i}\leq a$. Si au contraire $x_{i}+y_{i}\geq a$ (par exemple), alors $t_{i+1}=1$ et donc $z_{i}=x_{i}+y_{i}+t_{i}-b\leq 2a-b+1\leq a$, et aussi$z_{i}\geq a-b>-a$.

Il faut ensuite vérifier que le nombre $z$ est bien égal à $x+y$. Pour cela, en se souvenant que $t_{0}=0$, on calcule

${\begin{aligned}\sum _{i=0}^{n}z_{i}b^{i}&=\sum _{i=0}^{n}(w_{i}+t_{i})b^{i}=\sum _{i=0}^{n-1}(x_{i}+y_{i}-bt_{i+1}+t_{i})b^{i}+t_{n}b^{n}\\&=\sum _{i=0}^{n-1}x_{i}b^{i}+\sum _{i=0}^{n-1}y_{i}b^{i}-\sum _{i=0}^{n-1}t_{i+1}b^{i+1}+\sum _{i=1}^{n-1}t_{i}b^{i}+t_{n}b^{n}\\&=x+y\end{aligned}}$.

Applications

Les systèmes de numération redondants ont plusieurs applications : le codage de multiplieurs, les quotients dans les opérations de division ou d'opérations qui s'y rattachent, l'arithmétique en ligne. Les additions redondantes sont couramment employés dans les opérateurs de multiplication et de division (même si les données sont présentées, en entrée et en sortie, dans un système non redondant, les calculs internes sont réalisés dans un système redondant). Par exemple, la plupart des multiplieurs utilisent, au moins implicitement, un système de numération redondant. Un processeur particulier utilisait même deux systèmes redondants différents : les itérations dans les divisions sont réalisées dans une notation à retenues conservées, et le quotient est d'abord calculé en base 4 avec des chiffres entre −2 et 2 avant d'être converti dans la notation binaire usuelle.^[pas clair]

Extensions

Choix des chiffres

Guillaume Revy présente une extension de la notation qu'il appelle encore la notation d'Avizienis. Au lieu de prendre, pour une base $b$, les chiffres de $-a$ à $a$, il prend les chiffres d'un autre intervalle, formé de $q+1$ chiffres, allant de $\omega$ à $\omega +q$. Le cas classique s'obtient pour $\omega =-a$ et $q=2a$. On peut distinguer trois cas :

• si $q+1<b$, il n'y a pas assez de chiffres pour représenter tous les nombres ;
• si $q+1=b$, il y a exactement le nombre de chiffres nécessaire pour représenter les nombres et ils ont une représentation unique ; c'est le cas par exemple des chiffres ${\bar {1}},0,1$ en base 3, appelée « notation ternaire équilibrée »;
• si $q+1>b$, la représentation est redondante.

Base 2

La méthode d'Avizienis nécessite une base plus grande que 2. Pour la base $b=2$, deux méthodes d'addition en parallèle ont été développées, appelée en anglais « carry save » et « borrow save »; la première est traduite par addition à retenues conservées, la deuxième par addition à retenues conservées signées. On appelle la première aussi méthode de Chow et Robertson d'après leurs inventeurs qui l'ont décrite en 1978. Les chiffres sont composés par des couples $(c,s)$, dont la valeur est $c+s$. Ainsi, en base 2, l'entier $x=2$ a les deux représentations $(1,1)$ et $(0,1)(0,0)$. La valeur de la représentation

$(c_{n-1},s_{n-1})\cdots (c_{0},s_{0})$

est

$\sum _{i=0}^{n-1}(c_{i}+s_{i})2^{i}$.

Les méthodes à retenues conservées s'étendent à d'autres bases.

Historique

Quand Avižienis a créé son système de numération redondante il ne savait pas qu'un système très similaire avait déjà été proposé par Augustin Cauchy pour la base 10 dès 1840.

Annexes

Articles connexes

• Système de numération
• Algirdas Antanas Avižienis
• Notation positionnelle

Bibliographie

L'article original d'Avizienis, difficile à trouver :

• Algirdas Avizienis, « Signed-Digit number representations for fast parallel arithmetic », IRE Transactions on Electronic Computers, vol. EC-10, n^o 3,‎ septembre 1961, p. 389 - 400 (ISSN 0367-9950, DOI 10.1109/TEC.1961.5219227).

Exposés :

• Bruno Pettazoni, Seize problèmes d'informatique, Springer, coll. « Scopos » (n^o 8), 2001, 226 p. (ISBN 3-540-67387-3, présentation en ligne), « Problème 14, deuxième partie : Numération d'Avizienis Numération d'Avizienis. Énoncé p. 166, corrigé p. 173-174 », p. 166 (énonce) et 173-174 (corrigé).
• (en) Jean-Michel Muller, Elementary Functions : Algorithms and Implementation, Boston, Birkhäuser, 2005, 2^e éd., 265 p. (ISBN 0-8176-4372-9, présentation en ligne), « 2.2. Redundant number systems », p. 19-22.

Exposé didactique :

• Guillaume Revy, « Systèmes de représentation des nombres : Les nombres entiers », Licence 2 Sciences, Technologies, Santé, 2010/2011 (consulté le 2 août 2014), p. 24 - 34 ter.

Autre mention :

• (en) Christiane Frougny, Edita Pelantová et Milena Svobodová, « Parallel addition in non-standard numeration systems », sur Université Perpignan, 4^e Rencontres Arithmétique de l'Informatique Mathématique, 7 au 10 février 2011 (consulté le 2 août 2014).

Knuth a un long paragraphe sur les notations positionnelles :

• (en) Donald E. Knuth, The Art of Computer Programming, vol. 2 : Seminumerical algorithms, Reading (Mass.), Addison-Wesley, 1997, 3^e éd., 762 p. (ISBN 0-201-89684-2, présentation en ligne)