Árbol de Wallace - Wallace tree

Reducción de Wallace de 4 capas de una matriz de producto parcial de 8x8, utilizando 14 medios sumadores (dos puntos) y 38 sumadores completos (tres puntos). Los puntos en cada columna son bits de igual peso.

Un multiplicador de Wallace es una implementación de hardware de un multiplicador binario , un circuito digital que multiplica dos números enteros. Utiliza una selección de sumadores completos y medios (el árbol de Wallace o la reducción de Wallace ) para sumar productos parciales en etapas hasta que queden dos números. Los multiplicadores de Wallace reducen tanto como sea posible en cada capa, mientras que los multiplicadores de Dadda intentan minimizar el número requerido de puertas posponiendo la reducción a las capas superiores.

Los multiplicadores de Wallace fueron ideados por el informático australiano Chris Wallace en 1964.

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 por capas de sumadores completos y medios .
3. Agrupe los cables en dos números y agréguelos con un sumador convencional.

En comparación con la adición ingenua de productos parciales con sumadores regulares, el beneficio del árbol de Wallace es su velocidad más rápida. Tiene capas de reducción, pero cada capa solo tiene un retardo de propagación. Una adición ingenua de productos parciales requeriría tiempo. Como es hacer los productos parciales y la suma final , la multiplicación total es , no mucho más lenta que la suma. Desde una perspectiva teórica de la complejidad , el algoritmo del árbol de Wallace coloca la multiplicación en la clase NC ¹ . La desventaja del árbol de Wallace, en comparación con la adición ingenua de productos parciales, es su recuento de puertas mucho más alto. ${\ Displaystyle O (\ log n)}$${\ Displaystyle O (1)}$${\ Displaystyle O (\ log ^ {2} n)}$${\ Displaystyle O (1)}$${\ Displaystyle O (\ log n)}$${\ Displaystyle O (\ log n)}$

Estos cálculos solo consideran los retrasos en la puerta y no tratan los retrasos en los cables, que también pueden ser muy sustanciales.

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

A veces se combina con la codificación Booth .

Explicación detallada

El árbol de Wallace es una variante de multiplicación larga . El primer paso es 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 dijo anteriormente, es multiplicar cada bit de un número por cada bit del otro, lo que se logra como una simple puerta Y, lo que da como resultado bits; el producto parcial de bits por tiene peso${\ Displaystyle n ^ {2}}$${\ Displaystyle a_ {m}}$${\ Displaystyle b_ {n}}$${\ 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 una capa siguiente: -

• Tome tres cables con los mismos pesos e introdúzcalos 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 medio sumador .
• Si solo queda un cable, conéctelo a la siguiente capa.

En el tercer y último paso, los dos números resultantes se alimentan a un sumador, obteniendo el producto final.

Ejemplo

${\ Displaystyle n = 4}$, multiplicando por : ${\ Displaystyle a_ {3} a_ {2} a_ {1} a_ {0}}$${\ 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 medio sumador para el peso 2, salidas: 1 peso-2 hilos, 1 peso-4 hilos
   • Agregue un sumador completo para el peso 4, salidas: 1 cable de peso 4, 1 cable de peso 8
   • Agregue un sumador completo para el peso 8 y pase el cable restante a través de las salidas: 2 cables de peso 8, 1 cable de peso 16
   • Agregue un sumador completo para peso 16, salidas: 1 cable de peso 16, 1 cable de peso 32
   • Agregue un medio sumador para peso 32, salidas: 1 cable de peso 32, 1 cable de peso 64
   • Pase el único cable de 64 pesos, salida: 1 cable de 64 pesos
3. Cables en 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 sumador completo para el peso 8 y medios sumadores para los pesos 4, 16, 32, 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. Agrupe los cables en un par de números enteros y un sumador para sumarlos.

Ver también

• Árbol de papá

Referencias

Otras lecturas

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

enlaces externos

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