Árbol de Wallace

Implementación hardware eficiente de un multiplicador digital

Reducción de Wallace de 4 capas de una matriz de producto parcial de 8x8, utilizando 15 medios sumadores (dos puntos) y 38 sumadores completos (tres puntos). Los puntos de 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 reducción de Wallace ) para sumar productos parciales en etapas hasta que quedan 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. ^[1]

Los multiplicadores de Wallace fueron ideados por el 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. Reducir el número de productos parciales a dos mediante capas de sumadores completos y medios .
3. Agrupa los cables en dos números y súmalos con un sumador convencional. ^[3]

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 retardo de propagación. Una simple adición de productos parciales requeriría tiempo. Como hacer los productos parciales y la suma final es , la multiplicación total no es 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 1 . La desventaja del árbol de Wallace, en comparación con la adición ingenua de productos parciales, es su número de puertas mucho mayor. ${\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 sólo consideran los retrasos en las puertas y no se ocupan de los retrasos en 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]}

Explicación detallada

El árbol de Wallace es una variante de la 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 puerta AND simple, 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 la siguiente capa:

• 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 introducen en 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 medio sumador para el peso 2, salidas: 1 peso de 2 cables, 1 peso de 4 cables
   • Agregue un sumador completo para el peso 4, salidas: 1 peso de 4 cables, 1 peso de 8 cables
   • Agregue un sumador completo para el peso 8 y pase el cable restante. Salidas: 2 cables de peso 8, 1 cable de peso 16
   • Agregue un sumador completo para el peso 16, salidas: 1 cable de peso 16, 1 cable de peso 32
   • Agregue medio sumador para peso 32, salidas: 1 cable de peso 32, 1 cable de peso 64
   • Pase el único cable de peso 64, salida: 1 cable de peso 64
3. Cables a la salida de la capa reductora 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. Agrupa los cables en un par de números enteros y un sumador para sumarlos.

Ver también

• árbol de papá

Referencias

1. Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). Luk, Franklin T. (ed.). "Una comparación de los retrasos del multiplicador de Dadda y Wallace". Algoritmos, arquitecturas e implementaciones avanzadas de procesamiento de señales XIII . 5205 : 552–560. Código Bib : 2003SPIE.5205..552T. doi :10.1117/12.507012. ISSN  0277-786X. S2CID  121437680.
2. Wallace, Christopher Stewart (febrero de 1964). "Una sugerencia para un multiplicador rápido". Transacciones IEEE en computadoras electrónicas . CE-13 (1): 14-17. doi :10.1109/PGEC.1964.263830. S2CID  34688264.
3. Bohsali, Mounir; Doan, Michael (2010). "Multiplicadores de árboles de Wallace de estilo rectangular" (PDF) . Archivado desde el original (PDF) el 15 de febrero de 2010.
4. "Introducción". Multiplicador de árbol Wallace codificado en cabina 8x8 . Universidad de Tufts. 2007. Archivado desde el original el 17 de junio de 2010.
5. Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discusión 7: Representaciones numéricas". Amherst: Universidad de Massachusetts. Archivado desde el original el 6 de febrero de 2011.

Otras lecturas

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

enlaces externos

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