Multiplicador de Dadda

Diseño de multiplicador de hardware

El multiplicador de Dadda es un diseño de multiplicador binario de hardware inventado por el científico informático Luigi Dadda en 1965. ^[1] Utiliza una selección de sumadores completos y medios para sumar los productos parciales en etapas (el árbol de Dadda o reducción de Dadda ) hasta que quedan dos números. El diseño es similar al multiplicador de Wallace , pero el árbol de reducción diferente reduce el número requerido de puertas (para todos los tamaños de operandos excepto los más pequeños) y lo hace ligeramente más rápido (para todos los tamaños de operandos). ^[2]

Los multiplicadores de Dadda y Wallace tienen los mismos tres pasos para cadenas de dos bits y de longitudes y respectivamente: ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{2}}$

1. Multiplica ( AND lógico ) cada bit de , por cada bit de , obteniendo resultados agrupados por peso en columnas ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle \ell _{1}\cdot \ell _{2}}$
2. Reducir el número de productos parciales mediante etapas de sumadores completos y medios hasta que nos queden como máximo dos bits de cada peso.
3. Sume el resultado final con un sumador convencional.

Al igual que con el multiplicador de Wallace, los productos de multiplicación del primer paso tienen pesos diferentes que reflejan la magnitud de los valores de bits originales en la multiplicación. Por ejemplo, el producto de bits tiene un peso . ${\displaystyle a_{n}b_{m}}$ ${\displaystyle n+m}$

A diferencia de los multiplicadores de Wallace, que reducen lo máximo posible en cada capa, los multiplicadores de Dadda intentan minimizar la cantidad de puertas utilizadas, así como el retardo de entrada/salida. Debido a esto, los multiplicadores de Dadda tienen una fase de reducción menos costosa, pero los números finales pueden ser unos bits más largos, por lo que se requieren sumadores ligeramente más grandes.

Descripción

Un ejemplo de un circuito sumador completo.

Para lograr un producto final más óptimo, la estructura del proceso de reducción se rige por reglas ligeramente más complejas que en los multiplicadores de Wallace.

La progresión de la reducción está controlada por una secuencia de altura máxima , definida por: ${\displaystyle d_{j}}$

${\displaystyle d_{1}=2}$, y ${\displaystyle d_{j+1}=\operatorname {floor} (1.5d_{j}).}$

Esto produce una secuencia como la siguiente:

${\displaystyle d_{1}=2,d_{2}=3,d_{3}=4,d_{4}=6,d_{5}=9,d_{6}=13,\ldots }$

El valor inicial de se elige como el valor más grande tal que , donde y son el número de bits en el multiplicando y el multiplicador de entrada. La menor de las dos longitudes de bits será la altura máxima de cada columna de pesos después de la primera etapa de la multiplicación. Para cada etapa de la reducción, el objetivo del algoritmo es reducir la altura de cada columna para que sea menor o igual al valor de . ${\displaystyle j}$ ${\displaystyle d_{j}<\min {(n_{1},n_{2})}}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$ ${\displaystyle j}$ ${\displaystyle d_{j}}$

Para cada etapa desde , reduzca cada columna comenzando en la columna de menor peso, de acuerdo con estas reglas: ${\displaystyle ,\ldots ,1}$ ${\displaystyle c_{0}}$

1. Si la columna no requiere reducción, pasar a la columna ${\displaystyle \operatorname {height} (c_{i})\leqslant d_{j}}$ ${\displaystyle c_{i+1}}$
2. Si sumamos los dos elementos superiores en un semisumador, colocamos el resultado en la parte inferior de la columna y el acarreo en la parte inferior de la columna , luego pasamos a la columna ${\displaystyle \operatorname {height} (c_{i})=d_{j}+1}$ ${\displaystyle c_{i+1}}$ ${\displaystyle c_{i+1}}$
3. De lo contrario, agregue los tres elementos superiores en un sumador completo, colocando el resultado en la parte inferior de la columna y el acarreo en la parte inferior de la columna , reinicie en el paso 1 ${\displaystyle c_{i+1}}$ ${\displaystyle c_{i}}$

Ejemplo de algoritmo

Reducción Dadda de 4 capas de una matriz de producto parcial de 8x8, utilizando 7 medios sumadores (dos puntos) y 35 sumadores completos (tres puntos). Los puntos en cada columna son bits de igual peso. Los bits con menor peso están más a la derecha.

El ejemplo de la imagen adyacente ilustra la reducción de un multiplicador de 8 × 8, explicada aquí.

El estado inicial se elige como , siendo el valor más grande menor que 8. ${\displaystyle j=4}$ ${\displaystyle d_{4}=6}$

Escenario , ${\displaystyle j=4}$ ${\displaystyle d_{4}=6}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{5})}$son todos menores o iguales a seis bits de altura, por lo que no se realizan cambios
• ${\displaystyle \operatorname {height} (c_{6})=d_{4}+1=7}$, por lo que se aplica un semisumador, reduciéndolo a seis bits y agregando su bit de acarreo a ${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{7})=9}$incluyendo el bit de acarreo de , por lo que aplicamos un sumador completo y un medio sumador para reducirlo a seis bits ${\displaystyle c_{6}}$
• ${\displaystyle \operatorname {height} (c_{8})=9}$incluyendo dos bits de acarreo de , por lo que nuevamente aplicamos un sumador completo y un medio sumador para reducirlo a seis bits ${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{9})=8}$incluyendo dos bits de acarreo de , por lo que aplicamos un único sumador completo y lo reducimos a seis bits ${\displaystyle c_{8}}$
• ${\displaystyle \operatorname {height} (c_{10}\cdots c_{14})}$son todos menores o iguales a seis bits en altura, incluidos los bits de acarreo, por lo que no se realizan cambios

Escenario , ${\displaystyle j=3}$ ${\displaystyle d_{3}=4}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{3})}$son todos menores o iguales a cuatro bits de altura, por lo que no se realizan cambios
• ${\displaystyle \operatorname {height} (c_{4})=d_{3}+1=5}$, por lo que se aplica un semisumador, reduciéndolo a cuatro bits y agregando su bit de acarreo a ${\displaystyle c_{5}}$
• ${\displaystyle \operatorname {height} (c_{5})=7}$incluyendo el bit de acarreo de , por lo que aplicamos un sumador completo y un medio sumador para reducirlo a cuatro bits ${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{6}\cdots c_{10})=8}$incluyendo los bits de acarreo anteriores, por lo que aplicamos dos sumadores completos para reducirlos a cuatro bits
• ${\displaystyle \operatorname {height} (c_{11})=6}$incluyendo los bits de acarreo anteriores, por lo que aplicamos un sumador completo para reducirlo a cuatro bits
• ${\displaystyle \operatorname {height} (c_{12}\cdots c_{14})}$son todos menores o iguales a cuatro bits en altura, incluidos los bits de acarreo, por lo que no se realizan cambios

Escenario , ${\displaystyle j=2}$ ${\displaystyle d_{2}=3}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{2})}$son todos menores o iguales a tres bits de altura, por lo que no se realizan cambios
• ${\displaystyle \operatorname {height} (c_{3})=d_{2}+1=4}$, por lo que se aplica un semisumador, reduciéndolo a tres bits y agregando su bit de acarreo a ${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{4}\cdots c_{12})=5}$incluyendo los bits de acarreo anteriores, por lo que aplicamos un sumador completo para reducirlos a tres bits
• ${\displaystyle \operatorname {height} (c_{13}\cdots c_{14})}$son todos menores o iguales a tres bits en altura, incluidos los bits de acarreo, por lo que no se realizan cambios

Escenario , ${\displaystyle j=1}$ ${\displaystyle d_{1}=2}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{1})}$son todos menores o iguales a dos bits de altura, por lo que no se realizan cambios
• ${\displaystyle \operatorname {height} (c_{2})=d_{1}+1=3}$, por lo que se aplica un semisumador, reduciéndolo a dos bits y agregando su bit de acarreo a ${\displaystyle c_{3}}$
• ${\displaystyle \operatorname {height} (c_{3}\cdots c_{13})=4}$incluyendo los bits de acarreo anteriores, por lo que aplicamos un sumador completo para reducirlos a dos bits
• ${\displaystyle \operatorname {height} (c_{14})=2}$incluido el bit de transporte de , por lo que no se realizan cambios ${\displaystyle c_{13}}$

Suma

La salida de la última etapa deja 15 columnas de altura dos o menos que pueden pasarse a un sumador estándar.

Véase también

• Algoritmo de multiplicación de Booth
• Multiplicación-suma fusionada
• Árbol de Wallace
• Algoritmo BKM para logaritmos y exponenciales complejos
• Multiplicación de Kochanski para multiplicación modular

Referencias

1. Dadda, Luigi (mayo de 1965). "Algunos esquemas para multiplicadores paralelos". Alta Frecuencia . 34 (5): 349–356.
   Dadda, L. (1976). "Algunos esquemas para multiplicadores paralelos". En Swartzlander, Earl E. (ed.). Desarrollo del diseño de computadoras: Documentos principales . Hayden Book Company. págs. 167–180. ISBN 978-0-8104-5988-5.OCLC 643640444  .
2. Townsend, Whitney J.; Swartzlander, Jr., Earl E.; Abraham, Jacob A. (diciembre de 2003). "Una comparación de los retardos de los multiplicadores de Dadda y Wallace" (PDF) . Algoritmos, arquitecturas e implementaciones de procesamiento avanzado de señales SPIE XIII . The International Society . doi :10.1117/12.507012.

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 .