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^[1].

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 ${\displaystyle b}$ nécessite au moins ${\displaystyle b}$ chiffres pour pouvoir représenter tous les entiers. Typiquement, la valeur de ces chiffres va de ${\displaystyle 0}$ à ${\displaystyle 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 ${\displaystyle b}$ un nombre de chiffres strictement supérieur à ${\displaystyle 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.

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

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

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

représente le nombre ${\displaystyle 43}$, puisque

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

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

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

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

L'algorithme d'addition d'Avizienis sans propagation de retenue^{[3],[1],[5],[6]} suppose une base ${\displaystyle b>2}$ et ${\displaystyle 2a+1}$ chiffres ${\displaystyle {\bar {a}},\ldots ,a}$, avec ${\displaystyle b/2<a<b}$^[7]. La condition ${\displaystyle b/2<a}$ est plus forte que la relation ${\displaystyle 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 ${\displaystyle a<b}$, assure que les chiffres sont plus petits en valeur absolue que la base.

Étant donnés deux entiers

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

écrits sur ${\displaystyle n}$ chiffres dans cette base, on cherche à calculer dans cette base

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

où

${\displaystyle z=x+y}$

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

${\displaystyle 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 :

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

On pose également :

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

Les calculs de retenues ${\displaystyle 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 ${\displaystyle i=0,\ldots ,n}$,

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

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

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

Les calculs sont regroupés dans le tableau que voici

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

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

On a

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

À chaque position ${\displaystyle i}$, le chiffre calculé est la somme des chiffres ${\displaystyle x_{i}}$ et ${\displaystyle y_{i}}$, plus la retenue ${\displaystyle t_{i}}$ de la position précédente; si la somme de ${\displaystyle x_{i}}$ et ${\displaystyle 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 ${\displaystyle t_{i+1}}$ ne dépend pas de la retenue précédente ${\displaystyle 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 ${\displaystyle x_{i}}$ et ${\displaystyle y_{i}}$ et de la retenue ${\displaystyle 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 ${\displaystyle t_{i}}$, puisque ${\displaystyle -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 ${\displaystyle z_{i}}$ sont bien compris dans l'intervalle de ${\displaystyle -a}$ à ${\displaystyle a}$. Pour cela^[9], on part de

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

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

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

${\displaystyle {\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}}}$.

Les systèmes de numération redondants ont plusieurs applications^[1] : 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]

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

• si ${\displaystyle q+1<b}$, il n'y a pas assez de chiffres pour représenter tous les nombres ;
• si ${\displaystyle 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 ${\displaystyle {\bar {1}},0,1}$ en base 3, appelée « notation ternaire équilibrée »^[10];
• si ${\displaystyle q+1>b}$, la représentation est redondante.

La méthode d'Avizienis nécessite une base plus grande que 2. Pour la base ${\displaystyle 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^[1]. Les chiffres sont composés par des couples ${\displaystyle (c,s)}$, dont la valeur est ${\displaystyle c+s}$. Ainsi, en base 2, l'entier ${\displaystyle x=2}$ a les deux représentations ${\displaystyle (1,1)}$ et ${\displaystyle (0,1)(0,0)}$. La valeur de la représentation

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

est

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

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

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

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

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)

• Portail des mathématiques
• Portail de l'informatique théorique