Arbre de Wallace

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