Arbre de Wallace

Un arbre de Wallace, ou multiplieur de Wallace, est une implémentation matérielle d’un multiplieur binaire, un circuit numérique qui multiplie deux entiers. Il utilise une sélection d’additionneurs complets et de demi-additionneurs (l’arbre de Wallace ou la réduction de Wallace) pour additionner les produits partiels par étapes jusqu’à ce qu’il ne reste que deux nombres. Les multiplieurs de Wallace réduisent autant que possible le nombre de couches, tandis que les multiplieurs de Dadda (en) essaient de minimiser le nombre requis de portes en reportant la réduction vers les couches supérieures^[1].

Les multiplieurs de Wallace ont été conçus par l’informaticien australien Chris Wallace en 1964^[2].

L’arbre de Wallace comporte trois étapes :

1. Multiplication de chaque bit d’un argument par chaque bit de l’autre.
2. Réduction du nombre de produits partiels à deux par des couches d'additionneurs (complets) et de demi-additionneurs.
3. Regroupement des fils en deux nombres qui sont additionnés par un additionneur conventionnel^[3].

Comparé à l’ajout naïf de produits partiels avec des additionneurs classiques, l’avantage de l’arbre de Wallace est sa vitesse plus rapide. Il possède ${\displaystyle O(\log n)}$ couches de réduction, mais chaque couche a un délai de propagation en ${\displaystyle O(1)}$. Une addition naïve de produits partiels nécessiterait un temps en ${\displaystyle O(\log ^{2}n)}$. Comme la fabrication des produits partiels est en ${\displaystyle O(1)}$ et la dernière addition est en ${\displaystyle O(\log n)}$, la multiplication totale est en ${\displaystyle O(\log n)}$, pas beaucoup plus lente que l’addition. D’un point de vue théorie de la complexité, l’algorithme de l’arbre de Wallace place la multiplication dans la classe NC1. L’inconvénient de l’arbre de Wallace, comparé à l’ajout naïf de produits partiels, est son nombre de portes beaucoup plus élevé.

Ces calculs ne prennent en compte que les délais de porte (en) et ne traitent pas les délais de "fil", qui peuvent aussi être très importants.

L’arbre de Wallace peut aussi être représenté par un arbre composé d’additionneurs 3/2 ou 4/2.

Il est parfois combiné avec l'algorithme de Booth^[4],[5].

L’arbre de Wallace est une variante de la multiplication longue. La première étape consiste à multiplier chaque chiffre (chaque bit) d’un facteur par chaque chiffre de l’autre. Chacun de ces produits partiels a un poids égal au produit de ses facteurs. Le produit final est calculé par la somme pondérée de tous ces produits partiels.

La première étape, comme mentionné plus haut, consiste à multiplier chaque bit d’un nombre par chaque bit de l’autre (on suppose que chaque nombre binaire est de longueur ${\displaystyle n}$), ce qui s’accomplit avec une simple porte AND, ce qui donne ${\displaystyle n^{2}}$ bits ; le produit partiel des bits ${\displaystyle a_{m}}$ par ${\displaystyle b_{n}}$ a un poids ${\displaystyle 2^{(m+n)}}$.

À la fin de la deuxième étape, les bits résultants sont réduits à deux nombres. Cela s’accomplit comme suit : tant qu’il y a trois "fils" ou plus de même poids, ajoutez une nouvelle couche :

• Prenez chacun des trois "fils" de même poids et entrez-les dans un additionneur complet. Le résultat sera un "fil" de sortie de même poids et un "fil" de sortie de poids plus élevé pour chacun des trois "fils" d'entrée.
• S’il reste deux "fils" de même poids, entrez-les dans un demi-additionneur.
• S’il ne reste qu’un seul "fil", connectez-le à la couche suivante.

Dans la troisième et dernière étape, les deux nombres résultants sont injectés dans un additionneur, obtenant ainsi le produit final.

${\displaystyle n=4}$, multiplication de ${\displaystyle a_{3}a_{2}a_{1}a_{0}}$ par ${\displaystyle b_{3}b_{2}b_{1}b_{0}}$ :

1. Multiplier chaque bit de A par chaque bit de B :
   • poids 1 – ${\displaystyle a_{0}b_{0}}$
   • poids 2 – ${\displaystyle a_{0}b_{1}}$, ${\displaystyle a_{1}b_{0}}$
   • poids 4 – ${\displaystyle a_{0}b_{2}}$, ${\displaystyle a_{1}b_{1}}$, ${\displaystyle a_{2}b_{0}}$
   • poids 8 – ${\displaystyle a_{0}b_{3}}$, ${\displaystyle a_{1}b_{2}}$, ${\displaystyle a_{2}b_{1}}$, ${\displaystyle a_{3}b_{0}}$
   • poids 16 – ${\displaystyle a_{1}b_{3}}$, ${\displaystyle a_{2}b_{2}}$, ${\displaystyle a_{3}b_{1}}$
   • poids 32 – ${\displaystyle a_{2}b_{3}}$, ${\displaystyle a_{3}b_{2}}$
   • poids 64 – ${\displaystyle a_{3}b_{3}}$
2. Couche de réduction n°1 :
   • Passer directement le seul "fil" de poids 1, sortie : 1 "fil" de poids 1
   • Utiliser un demi-additionneur pour le poids 2, sorties : 1 "fil" de poids 2, 1 "fil" de poids 4
   • Utiliser un additionneur complet pour le poids 4, sorties : 1 "fil" de poids 4, 1 "fil" de poids 8
   • Utiliser un additionneur complet pour le poids 8 et passer directement le "fil" restant, sorties : 2 "fils" de poids 8, 1 "fil" de poids 16
   • Utiliser un additionneur complet pour le poids 16, sorties : 1 "fil" de poids 16, 1 "fil" de poids 32
   • Utiliser un demi-additionneur pour le poids 32, sorties : 1 "fil" de poids 32, 1 "fil" de poids 64
   • Passer directement le seul "fil" de poids 64, sortie : 1 "fil" de poids 64
3. "Fils" à la sortie de la couche de réduction n°1 :
   • poids 1 – 1
   • poids 2 – 1
   • poids 4 – 2
   • poids 8 – 3
   • poids 16 – 2
   • poids 32 – 2
   • poids 64 – 2
4. Couche de réduction n°2 :
   • Utiliser un additionneur complet pour le poids 8 et des demi-additionneurs pour les poids 4, 16, 32, 64
5. Sorties :
   • poids 1 – 1
   • poids 2 – 1
   • poids 4 – 1
   • poids 8 – 2
   • poids 16 – 2
   • poids 32 – 2
   • poids 64 – 2
   • poids 128 – 1
6. Grouper les "fils" (par poids) dans une paire d'entiers et les ajouter à l'aide d'un additionneur.

• Portail de l’électricité et de l’électronique
• Portail de l'informatique théorique