Árbol de Wallace

Un multiplicador de Wallace es una implementación de hardware de un multiplicador binario , un circuito digital que multiplica dos enteros. Utiliza una selección de sumadores completos y medios sumadores (el árbol de Wallace o reducción de Wallace ) para sumar productos parciales en etapas hasta que queden dos números. Los multiplicadores de Wallace reducen lo máximo posible en cada capa, mientras que los multiplicadores de Dadda intentan minimizar el número de compuertas necesarias posponiendo la reducción a las capas superiores. ^{[ 1 ]}

Los multiplicadores de Wallace fueron ideados por el científico informático australiano Chris Wallace en 1964. ^{[ 2 ]}

El árbol de Wallace tiene tres pasos:

1. Multiplica cada bit de uno de los argumentos por cada bit del otro.
2. Reduzca el número de productos parciales a dos mediante capas de sumadores completos y medios .
3. Agrupa los cables en dos grupos y súmalos con un sumador convencional. ^{[ 3 ]}

En comparación con la suma ingenua de productos parciales con sumadores regulares, la ventaja del árbol de Wallace es su mayor velocidad.${\displaystyle O(\log n)}$capas de reducción, pero cada capa tiene solo${\displaystyle O(1)}$retardo de propagación. Una suma ingenua de productos parciales requeriría${\displaystyle O(\log ^{2}n)}$tiempo. Como hacer los productos parciales es${\displaystyle O(1)}$y la adición final es${\displaystyle O(\log n)}$, la multiplicación total es${\displaystyle O(\log n)}$, no mucho más lento que la suma. Desde una perspectiva de teoría de la complejidad , el algoritmo del árbol de Wallace coloca la multiplicación en la clase NC ^1. La desventaja del árbol de Wallace, en comparación con la suma ingenua de productos parciales, es su número mucho mayor de compuertas.

Estos cálculos solo tienen en cuenta los retardos de las puertas lógicas y no consideran los retardos de los cables, que también pueden ser muy importantes.

El árbol de Wallace también puede representarse mediante un árbol de sumadores 3/2 o 4/2.

A veces se combina con la codificación Booth . ^{[ 4 ] [ 5 ]}

El árbol de Wallace es una variante de la multiplicación larga . El primer paso consiste en multiplicar cada dígito (cada bit) de un factor por cada dígito del otro. Cada uno de estos productos parciales tiene un peso igual al producto de sus factores. El producto final se calcula mediante la suma ponderada de todos estos productos parciales.

El primer paso, como se mencionó anteriormente, es multiplicar cada bit de un número por cada bit del otro, lo cual se realiza como una simple puerta AND, dando como resultado:${\displaystyle n^{2}}$bits; el producto parcial de bits${\displaystyle a_{m}}$por${\displaystyle b_{n}}$tiene peso${\displaystyle 2^{(m+n)}}$

En el segundo paso, los bits resultantes se reducen a dos números; esto se logra de la siguiente manera: Siempre que haya tres o más cables con el mismo peso, agregue la siguiente capa:

• Toma tres cables cualesquiera con el mismo peso e introdúcelos en un sumador completo . El resultado será un cable de salida del mismo peso y un cable de salida con un peso mayor por cada tres cables de entrada.
• Si quedan dos cables del mismo peso, introdúzcalos en un semisumador .
• Si solo queda un cable, conéctelo a la siguiente capa.

En el tercer y último paso, los dos números resultantes se introducen en un sumador, obteniendo así el producto final.

${\displaystyle n=4}$multiplicando${\displaystyle a_{3}a_{2}a_{1}a_{0}}$por${\displaystyle b_{3}b_{2}b_{1}b_{0}}$:

1. Primero multiplicamos cada bit por cada bit:
   • peso 1 –${\displaystyle a_{0}b_{0}}$
   • peso 2 –${\displaystyle a_{0}b_{1}}$,${\displaystyle a_{1}b_{0}}$
   • peso 4 –${\displaystyle a_{0}b_{2}}$,${\displaystyle a_{1}b_{1}}$,${\displaystyle a_{2}b_{0}}$
   • peso 8 –${\displaystyle a_{0}b_{3}}$,${\displaystyle a_{1}b_{2}}$,${\displaystyle a_{2}b_{1}}$,${\displaystyle a_{3}b_{0}}$
   • peso 16 –${\displaystyle a_{1}b_{3}}$,${\displaystyle a_{2}b_{2}}$,${\displaystyle a_{3}b_{1}}$
   • peso 32 –${\displaystyle a_{2}b_{3}}$,${\displaystyle a_{3}b_{2}}$
   • peso 64 –${\displaystyle a_{3}b_{3}}$
2. Capa de reducción 1:
   • Pase el único cable de peso 1, salida: 1 cable de peso 1
   • Agregue un sumador de medio valor para peso 2, salidas: 1 cable de peso 2, 1 cable de peso 4
   • Agregue un sumador completo para peso 4, salidas: 1 cable de peso 4, 1 cable de peso 8
   • Agregue un sumador completo para el peso 8 y deje pasar el cable restante, salidas: 2 cables de peso 8, 1 cable de peso 16
   • Añade un sumador completo para peso 16, salidas: 1 cable de peso 16, 1 cable de peso 32
   • Agregue un sumador de medio valor para peso 32, salidas: 1 cable de peso 32, 1 cable de peso 64
   • Pase únicamente el cable de peso 64, salida: 1 cable de peso 64

     

3. Cables a la salida de la capa de reducción 1:
   • peso 1 – 1
   • peso 2 – 1
   • peso 4 – 2
   • peso 8 – 3
   • peso 16 – 2
   • peso 32 – 2
   • peso 64 – 2
4. Capa de reducción 2:
   • Agregue un complemento completo para el peso 8 y complementos de media longitud para los pesos 4, 16, 32 y 64.

     

5. Salidas:
   • peso 1 – 1
   • peso 2 – 1
   • peso 4 – 1
   • peso 8 – 2
   • peso 16 – 2
   • peso 32 – 2
   • peso 64 – 2
   • peso 128 – 1

     

6. Agrupa los cables en pares de números enteros y usa un sumador para sumarlos.

• Árbol Dadda

• Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .

• Implementación genérica en VHDL del multiplicador de árbol de Wallace .