Metraipolis › archive › dc_fc02af6bce63
Arbre de Wallace — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Arbre_de_Wallace
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-19T07:01:57.693Z
- SHA-256 of the archived text
e7e4c705386cfabd0b6b12f53d685b01f4c2a4b85933516f69e864ba2c412044- Stable URL of this page
https://metraipolis.com/documento/dc_fc02af6bce63
How to cite
Arbre de Wallace — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Arbre_de_Wallace (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_fc02af6bce63 (Metraipolis archive dc_fc02af6bce63, sha256 e7e4c705386cfabd0b6b12f53d685b01f4c2a4b85933516f69e864ba2c412044)
BibTeX
@misc{dcfc02af6bce63,
title = {Arbre de Wallace — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Arbre_de_Wallace},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_fc02af6bce63; sha256 e7e4c705386cfabd0b6b12f53d685b01f4c2a4b85933516f69e864ba2c412044},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Arbre_de_Wallace. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Les multiplieurs de Wallace ont été conçus par l’informaticien australien Chris Wallace en 1964. L’arbre de Wallace comporte trois étapes : Multiplication de chaque bit d’un argument par chaque bit de l’autre. Réduction du nombre de produits partiels à deux par des couches d'additionneurs (complets) et de demi-additionneurs. Regroupement des fils en deux nombres qui sont additionnés par un additionneur conventionnel. 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 O ( log n ) {\displaystyle O(\log n)} couches de réduction, mais chaque couche a un délai de propagation en O ( 1 ) {\displaystyle O(1)} . Une addition naïve de produits partiels nécessiterait un temps en O ( log 2 n ) {\displaystyle O(\log ^{2}n)} . Comme la fabrication des produits partiels est en O ( 1 ) {\displaystyle O(1)} et la dernière addition est en O ( log n ) {\displaystyle O(\log n)} , la multiplication totale est en O ( log n ) {\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.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Arbre de Wallace» — https://fr.wikipedia.org/wiki/Arbre_de_Wallace
Wikidata Q2542512 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2542512
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Arbre_de_Wallace?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 234377346, consultata il 2026-10-19T06:58:22.365Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 26b22d0d27f0e961b3f5711e37756b1cbd49b2843fa7f719c467e0cc8f082721