Árbol de Wallace

Implementación eficiente de hardware 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 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 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. ^[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. Reducir el número de productos parciales a dos mediante capas de sumadores completos y medios .
3. Agrupe los cables en dos números y súmelos con un sumador convencional. ^[3]

En comparación con la suma ingenua de productos parciales con sumadores regulares, el beneficio del árbol de Wallace es su mayor velocidad. Tiene capas de reducción, pero cada capa solo tiene un retardo de propagación. Una suma ingenua de productos parciales requeriría tiempo. Como hacer los productos parciales es y la suma final es , la multiplicación total es , no mucho más lenta 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 conteo 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 de la puerta y no abordan los retrasos del cable, que también pueden ser muy sustanciales.

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 simple puerta AND, dando 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 cualesquiera 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 sólo 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, obteniéndose 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 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 pase el cable restante; 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 el 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 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.

Véase también

• Árbol de Dadda

Referencias

1. Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). Luk, Franklin T. (ed.). "Una comparación de los retardos de los multiplicadores de Dadda y Wallace". Algoritmos, arquitecturas e implementaciones de procesamiento avanzado de señales XIII . 5205 : 552–560. Bibcode :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". IEEE Transactions on Electronic Computers . EC-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 de Wallace codificado por Booth 8x8 . Universidad de Tufts. 2007. Archivado desde el original el 17 de junio de 2010.
5. Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discussion 7: Number Representations". Amherst: Universidad de Massachusetts. Archivado desde el original el 6 de febrero de 2011.

Lectura adicional

• Savard, John JG (2018) [2006]. «Técnicas aritméticas avanzadas». quadibloc . Archivado desde el original el 2018-07-03 . Consultado el 2018-07-16 .

Enlaces externos

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