He estado tratando de entender la implementación de hardware para el algoritmo de la cabina y aquí hay un diagrama que encontré tratando de explicar pero no entendí esto:
¿Cómo va? Sé que B, A, Q son registros.
He estado tratando de entender la implementación de hardware para el algoritmo de la cabina y aquí hay un diagrama que encontré tratando de explicar pero no entendí esto:
¿Cómo va? Sé que B, A, Q son registros.
La multiplicación larga (de varios dígitos) en binario es la misma que en decimal, pero más simple. Por ejemplo, en decimal:
15
x 12
----
30
15
----
180
y en binario:
1111 (15)
x 1100 (12)
------
0000
0000
1111
1111
--------
10110100 (180)
Tenga en cuenta que multiplica el multiplicando entero por cada dígito del multiplicador, luego agrega los resultados, teniendo cuidado de mantener un registro del decimal. La multiplicación binaria (al menos el método de un bit a la vez) hace lo mismo.
En la Figura 3.11, el multiplicador funciona al observar el LSB de Q y establecer A a A + B si es un 1 o dejar A solo si es un 0. Luego se desplaza Q un bit hacia la derecha y B un bit hacia la izquierda. Repita esto hasta que Q se quede sin bits válidos. Incluso podrías detenerte temprano cuando Q sea de 0 bits:
1111 (B)
x 1100 (Q)
------
0000 (Cycle 0: Q[0] == 0: A => 00000000, B => 00011110, Q => 0110)
0000 (Cycle 1: Q[0] == 0: A => 00000000, B => 00111100, Q => 0011)
1111 (Cycle 2: Q[0] == 1: A => 00111100, B => 01111000, Q => 0001)
1111 (Cycle 3: Q[0] == 1: A => 10110100, B => 11110000, Q => 0000)
--------
10110100 (A)
El inconveniente es que los registros A y B tienen que ser tan grandes como el resultado, que es el doble de bits que las entradas (un hecho que el lenguaje C ignora).
Ahora la Figura 3.13 muestra una optimización de este proceso. En lugar de desplazar el multiplicando (B) a la izquierda, desplaza el resultado a la derecha y utiliza los bits que se liberan en Q para almacenar los bits que caen del lado derecho de A:
1111 (B)
x 1100 (Q)
------
0000 (Cycle 0: Q[0] == 0: A => 0000, Q => 0110)
0000 (Cycle 1: Q[0] == 0: A => 0000, Q => 0011)
1111 (Cycle 2: Q[0] == 1: A => 0111, Q => 1001)
1111 (Cycle 3: Q[0] == 1: A => 1011, Q => 0100)
--------
10110100 (A:Q)
Tenga en cuenta que no puede detenerse antes si Q es de 0 bits; Tendría que hacer un seguimiento de cuántos bits quedaron en el multiplicador Q, que es suficiente lógica combinatoria adicional para ralentizar el ciclo.
Finalmente, tenga en cuenta que ninguno de estos son los algoritmos multiplicadores de ciclo único que se encuentran en las CPU modernas. Se basan en tener N sumadores y hacer todo el proceso de una sola vez, y el algoritmo de Booth no haría ninguna diferencia. (A tendría que ser 2N bits y B solo tendría que ser N bits.)
Lea otras preguntas en las etiquetas digital-logic