Multiplicador de papá - Dadda multiplier

El multiplicador de Dadda es un diseño de multiplicador binario de hardware inventado por el informático Luigi Dadda en 1965. Utiliza una selección de sumadores completos y medios para sumar los productos parciales en etapas (el árbol de Dadda o la reducción de Dadda ) hasta que queden 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 un poco más rápido (para todos los tamaños de operandos).

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

1. Multiplica ( Y lógico ) cada bit de , por cada bit de , dando 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 por etapas de sumadores completos y medios hasta que nos quedemos como máximo con dos bits de cada peso.
3. Agrega 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 peso . ${\ Displaystyle a_ {n} b_ {m}}$${\ Displaystyle n + m}$

A diferencia de los multiplicadores de Wallace que reducen tanto como sea 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 algunos bits más largos, por lo que se requieren sumadores un poco más grandes.

Descripción

Un ejemplo de circuito sumador completo.

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

La progresión de la reducción se controla mediante una secuencia de altura máxima , definida por: ${\ Displaystyle d_ {j}}$

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

Esto produce una secuencia como esta:

${\ 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 de modo 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 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 de , 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, muévase a la columna${\ Displaystyle \ operatorname {altura} (c_ {i}) \ leqslant d_ {j}}$${\ Displaystyle c_ {i + 1}}$
2. Si agrega los dos elementos superiores en un medio sumador, colocando el resultado en la parte inferior de la columna y el acarreo en la parte superior de la columna , luego muévase a la columna${\ Displaystyle \ operatorname {altura} (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 superior 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 se encuentran en el extremo derecho.

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

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

etapa ,${\ Displaystyle j = 4}$${\ Displaystyle d_ {4} = 6}$

• ${\ Displaystyle \ operatorname {altura} (c_ {0} \ cdots c_ {5})}$ son todos menores o iguales a seis bits de altura, por lo que no se realizan cambios
• ${\ Displaystyle \ operatorname {altura} (c_ {6}) = d_ {4} + 1 = 7}$, por lo que se aplica un medio sumador, reduciéndolo a seis bits y agregando su bit de acarreo a ${\ Displaystyle c_ {7}}$
• ${\ Displaystyle \ operatorname {altura} (c_ {7}) = 9}$incluido 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 {altura} (c_ {8}) = 9}$incluidos dos bits de acarreo de , por lo que de nuevo aplicamos un sumador completo y un medio sumador para reducirlo a seis bits${\ Displaystyle c_ {7}}$
• ${\ Displaystyle \ operatorname {altura} (c_ {9}) = 8}$incluidos dos bits de acarreo de , por lo que aplicamos un solo sumador completo y lo reducimos a seis bits${\ Displaystyle c_ {8}}$
• ${\ Displaystyle \ operatorname {altura} (c_ {10} \ cdots c_ {14})}$ son todos menores o iguales a seis bits de altura, incluidos los bits de acarreo, por lo que no se realizan cambios

etapa ,${\ Displaystyle j = 3}$${\ Displaystyle d_ {3} = 4}$

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

etapa ,${\ Displaystyle j = 2}$${\ Displaystyle d_ {2} = 3}$

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

etapa ,${\ Displaystyle j = 1}$${\ Displaystyle d_ {1} = 2}$

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

Adición

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

Ver también

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

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 .