El algoritmo de multiplicación de Booth es un algoritmo de multiplicación 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 informática .
El algoritmo de Booth examina pares adyacentes de bits del multiplicador de 'N' bits Y en representación de complemento a dos con signo, incluyendo un bit implícito debajo del bit menos significativo , y −1 = 0. Para cada bit y i , para i que va de 0 a N − 1, se consideran los bits y i e y i −1 . Cuando estos dos bits son iguales, el acumulador de producto P no cambia. Cuando y i = 0 e y i −1 = 1, el multiplicando por 2 i se suma a P ; y donde y i = 1 e y i −1 = 0, el multiplicando por 2 i 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; típicamente, ambos están también en representación de complemento a dos, como el multiplicador, pero cualquier sistema numérico que admita la suma y la resta funcionará también. Como se indica aquí, el orden de los pasos no está determinado. Típicamente, se procede de LSB a MSB , comenzando en i = 0; la multiplicación por 2 i es luego típicamente reemplazada por un desplazamiento incremental del acumulador P hacia la derecha entre pasos; los bits bajos pueden desplazarse hacia afuera, y las adiciones y restas subsiguientes pueden entonces realizarse 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 cadenas de 1 en el multiplicador a un +1 de orden superior y un −1 de orden inferior en los extremos de la cadena. Cuando una cadena pasa por el MSB, no hay ningún +1 de orden superior y el efecto neto es la interpretación como un negativo del valor apropiado.
El algoritmo de Booth se puede implementar sumando repetidamente (con la 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 la cantidad de bits en m y r .
Encuentra 3 × (−4), con m = 3 y r = −4, y x = 4 e y = 4:
La técnica mencionada anteriormente es inadecuada cuando el multiplicando es el número más negativo que se puede representar (por ejemplo, si el multiplicando tiene 4 bits, entonces este valor es −8). Esto se debe a que entonces se produce un desbordamiento al calcular -m, la negación del multiplicando, que se necesita para establecer S. Una posible corrección a este problema es extender A, S y P en un bit cada uno, mientras sigan representando el mismo número. Es decir, mientras que −8 se representaba anteriormente en cuatro bits por 1000, ahora se representa en 5 bits por 1 1000. Esto sigue entonces 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:
Consideremos un multiplicador positivo que consiste en un bloque de 1 rodeado de 0. Por ejemplo, 00111110. El producto viene dado por: donde M es el multiplicando. El número de operaciones se puede reducir a dos reescribiéndolo como
De hecho, se puede demostrar que cualquier secuencia de 1 en un número binario se puede descomponer en la diferencia de dos números binarios:
Por lo tanto, la multiplicación puede reemplazarse por la cadena de unos del número original mediante operaciones más simples: sumando el multiplicador, desplazando el producto parcial así formado en los lugares apropiados y, finalmente, restando el multiplicador. Se aprovecha el hecho de que no es necesario hacer nada más que desplazar cuando se trabaja con ceros en un multiplicador binario, y es similar a usar la propiedad matemática de que 99 = 100 − 1 al multiplicar por 99.
Este esquema se puede extender a cualquier número de bloques de 1 en un multiplicador (incluido el caso de un solo 1 en un bloque). Por lo tanto,
El algoritmo de Booth sigue este viejo esquema realizando una suma cuando encuentra el primer dígito de un bloque de unos (0 1) y una resta cuando encuentra el final del bloque (1 0). Esto funciona también para un multiplicador negativo. 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 normal.