Un árbol de Wallace es una implementación de hardware eficiente de un circuito digital que multiplica dos números enteros. Fue ideado por el científico informático australiano Chris Wallace en 1964. [1]
El árbol de Wallace tiene tres pasos:
- Multiplica cada bit de uno de los argumentos por cada bit del otro.
- Reduzca el número de productos parciales a dos por capas de sumadores completos y medios.
- Agrupe los cables en dos números y agréguelos con un sumador convencional . [2]
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 tiene solo retardo de propagación. Una adición ingenua de productos parciales requeriríahora. Como hacer los productos parciales es y la adición final es , la multiplicación total es , no mucho más lento 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 recuento de puertas mucho más alto.
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 . [3] [4]
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 cual se logra como una puerta simple y, lo que resulta en bits el producto parcial de bits por tiene peso
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
, multiplicando por :
- Primero multiplicamos cada bit por cada bit:
- peso 1 -
- peso 2 - ,
- peso 4 - , ,
- peso 8 - , , ,
- peso 16 - , ,
- peso 32 - ,
- peso 64 -
- 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
- 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
- Capa de reducción 2:
- Agregue un sumador completo para el peso 8 y medios sumadores para los pesos 4, 16, 32, 64
- 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
- Agrupe los cables en un par de números enteros y un sumador para sumarlos.
Ver también
Referencias
- ^ Wallace, Christopher Stewart (febrero de 1964). "Una sugerencia para un multiplicador rápido". Transacciones IEEE en computadoras electrónicas . EC-13 (1): 14–17.
- ^ Bohsali, Mounir; Doan, Michael (2010). "Multiplicadores de árbol de Wallace de estilo rectangular" (PDF) . Archivado desde el original (PDF) el 15 de febrero de 2010.
- ^ "Introducción" . Multiplicador de árbol de Wallace codificado en cabina de 8x8 . Universidad de Tufts. 2007. Archivado desde el original el 17 de junio de 2010.
- ^ 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" . quadibloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .