Algoritmo de multiplicación de Booth

El algoritmo de multiplicación de Booth es un algoritmo que multiplica dos números binarios con signo en notación de complemento a dos . El algoritmo fue inventado por Andrew Donald Booth en 1950 mientras realizaba investigaciones sobre cristalografía en el Birkbeck College en Bloomsbury , Londres . ^{[ 1 ]} El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras .

El algoritmo de Booth examina pares de bits adyacentes del multiplicador Y de N bits en representación de complemento a dos con signo , incluyendo un bit implícito debajo del bit menos significativo , y ₋₁ = 0. Para cada bit y _i , para i que va de 0 a N − 1, se consideran los bits y _i y y _{i −1 . Cuando estos dos bits son iguales, el acumulador de producto} P permanece sin cambios. Cuando y _i = 0 y y _{i −1} = 1, el multiplicando por 2 ⁱ se suma a P ; y cuando y _i = 1 y y _i−1 = 0, el multiplicando por 2 ⁱ se resta de P. El valor final de P es el producto con signo.

Las representaciones del multiplicando y el producto no están especificadas; normalmente, ambos están también en representación de complemento a dos, como el multiplicador, pero cualquier sistema numérico que admita suma y resta también funcionará. Como se indica aquí, el orden de los pasos no está determinado. Normalmente, procede del LSB al MSB , comenzando en i = 0; la multiplicación por 2 ⁱ se reemplaza entonces normalmente por un desplazamiento incremental del acumulador P hacia la derecha entre pasos; los bits bajos se pueden desplazar hacia fuera, y las sumas y restas subsiguientes se pueden hacer solo en los N bits más altos de ^{P. [ 2 ]} Hay ^{muchas variaciones} y optimizaciones en estos detalles.

El algoritmo se describe a menudo como la conversión de secuencias de 1 en el multiplicador a un +1 de orden superior y un -1 de orden inferior en los extremos de la secuencia. Cuando una secuencia pasa por el bit más significativo (MSB), no hay un +1 de orden superior, y el resultado es una interpretación negativa del valor correspondiente.

El algoritmo de Booth se puede implementar sumando repetidamente (con suma binaria ordinaria sin signo) uno de dos valores predeterminados A y S a un producto P , y luego realizando un desplazamiento aritmético hacia la derecha en P. Sean m y r el multiplicando y el multiplicador , respectivamente; y sean x e y el número de bits en m y r .

1. Determina los valores de A y S , y el valor inicial de P. Todos estos números deben tener una longitud igual a ( x  + y + 1).    
   1. A: Rellena los bits más significativos (los de más a la izquierda) con el valor de m . Rellena los bits restantes ( y  +  1) con ceros.
   2. S: Rellene los bits más significativos con el valor de ( − m ) en notación de complemento a dos. Rellene los bits restantes ( y  +  1) con ceros.
   3. P: Rellena los x bits más significativos con ceros. A la derecha de esto, añade el valor de r . Rellena el bit menos significativo (el de la derecha) con un cero.
2. Determina los dos bits menos significativos (los de la derecha) de P.
   1. Si son 01, encuentre el valor de P  + A. Ignore cualquier desbordamiento. 
   2. Si son 10, halla el valor de P  + S. Ignora cualquier desbordamiento. 
   3. Si son 00, no haga nada. Use P directamente en el siguiente paso.
   4. Si tienen 11 años, no haga nada. Use P directamente en el siguiente paso.
3. Desplaza aritméticamente el valor obtenido en el segundo paso una posición a la derecha. Sea P igual a este nuevo valor.
4. Repita los pasos 2 y 3 hasta que se hayan realizado y veces.
5. Elimine el bit menos significativo (el de más a la derecha) de P. Este es el producto de m y r .

Halla 3 × ( − 4 ), con m = 3 y r = − 4, y x = 4 e y = 4:

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• Realiza el bucle cuatro veces:
  1. P = 0000 110 0 0 . Los dos últimos bits son 00.
     • P = 0000 0110 0. Desplazamiento aritmético a la derecha.
  2. P = 0000 011 0 0 . Los dos últimos bits son 00.
     • P = 0000 0011 0. Desplazamiento aritmético a la derecha.
  3. P = 0000 001 1 0 . Los dos últimos bits son 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. Desplazamiento aritmético a la derecha.
  4. P = 1110 100 1 1 . Los dos últimos bits son 11.
     • P = 1111 0100 1. Desplazamiento aritmético a la derecha.
• El producto es 1111 0100, que es − 12.

La técnica mencionada anteriormente resulta inadecuada cuando el multiplicando es el número más negativo que se puede representar (por ejemplo, si el multiplicando tiene 4 bits, su valor es −8 ). Esto se debe a que se produce un desbordamiento al calcular -m, la negación del multiplicando, necesaria para establecer S. Una posible solución a este problema consiste en extender A, S y P en un bit cada uno, manteniendo la misma representación numérica. Es decir, mientras que −8 se representaba anteriormente en cuatro bits por 1000, ahora se representa en cinco bits por 1000. Esto sigue la implementación descrita anteriormente, con modificaciones en la determinación de los bits de A y S; por ejemplo, el valor de m , originalmente asignado a los primeros x bits de A, ahora se extenderá a x + 1 bits y se asignará a los primeros x + 1 bits de A. A continuación, se demuestra la técnica mejorada multiplicando −8 por 2 utilizando 4 bits para el multiplicando y el multiplicador:

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• Realiza el bucle cuatro veces:
  1. P = 0 0000 001 0 0 . Los dos últimos bits son 00.
     • P = 0 0000 0001 0. Desplazamiento a la derecha.
  2. P = 0 0000 000 1 0 . Los dos últimos bits son 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. Desplazamiento a la derecha.
  3. P = 0 0100 000 0 1 . Los dos últimos bits son 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. Desplazamiento a la derecha.
  4. P = 1 1110 000 0 0 . Los dos últimos bits son 00.
     • P = 1 1111 0000 0. Desplazamiento a la derecha.
• El producto es 11110000 (después de descartar el primer y el último bit), que es − 16.

Consideremos un multiplicador positivo que consiste en un bloque de 1s rodeado de 0s. Por ejemplo, 00111110. El producto viene dado por: $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&1&1&0\\\hline \end{array}}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$ donde M es el multiplicando. El número de operaciones se puede reducir a dos reescribiendo lo mismo como $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&0&0&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{1})=M\times 62.}$$

De hecho, se puede demostrar que cualquier secuencia de 1s en un número binario se puede descomponer en la diferencia de dos números binarios:

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

Por lo tanto, la multiplicación puede reemplazarse por la secuencia de unos del número original mediante operaciones más sencillas: sumar el multiplicador, desplazar el producto parcial resultante las posiciones adecuadas y, finalmente, restar el multiplicador. Esto se basa en el hecho de que, al trabajar con ceros en un multiplicador binario, no es necesario realizar ningún desplazamiento, y es similar a utilizar la propiedad matemática de que 99  =  100 − 1 al multiplicar por 99.  

Este esquema puede extenderse a cualquier número de bloques de 1s en un multiplicador (incluido el caso de un solo 1 en un bloque). Por lo tanto,

$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&0&1&0\\\hline \end{array}}\ =M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&-1&1&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

El algoritmo de Booth sigue este esquema antiguo: realiza una suma al encontrar el primer dígito de un bloque de unos (0 1) y una resta al llegar al final del bloque (1 0). Esto también funciona con multiplicadores negativos. Cuando los unos de un multiplicador se agrupan en bloques largos, el algoritmo de Booth realiza menos sumas y restas que el algoritmo de multiplicación convencional.

El microprocesador Pentium de Intel utiliza una variante de base 8 del algoritmo de Booth en su multiplicador de hardware de 64 bits. Debido a la forma en que implementa la multiplicación de base 8, necesita un circuito auxiliar complejo para realizar el caso especial de multiplicación por 3 de manera que se minimice la latencia, combinando el uso de anticipación de acarreo , selección de acarreo y suma de Kogge-Stone . ^{[ 3 ]}

• Multiplicador binario
• Forma no adyacente
• Representación binaria redundante
• Árbol de Wallace
• multiplicador Dadda

• Collin, Andrew (Primavera de 1993). "Los ordenadores de Andrew Booth en Birkbeck College" . Resurrección (5). Londres: Computer Conservation Society .
• Patterson, David Andrew ; Hennessy, John Leroy (1998). Organización y diseño de computadoras: la interfaz hardware/software (segunda  edición). San Francisco, California, EE. UU.: Morgan Kaufmann Publishers . ISBN 1-55860-428-6.
• Stallings, William (2000). Organización y arquitectura de computadoras: Diseño para el rendimiento (Quinta  ed.). Nueva Jersey: Prentice-Hall, Inc. ISBN 0-13-081294-3.
• Savard, John JG (2018) [2006]. "Técnicas aritméticas avanzadas" . quadibloc . Archivado del original el 3 de julio de 2018. Recuperado el 16 de julio de 2018 .

• Codificación de cabina Radix-4
• Codificación Booth de base 8 en una teoría formal de RTL y aritmética computacional
• Simulador de JavaScript del algoritmo de Booth
• Implementación en Python
• Implementación en C++
• Implementación en Java
• Ventajas de utilizar el algoritmo de Booth