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 una investigación sobre cristalografía en Birkbeck College en Bloomsbury , Londres . [1] El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras .
El algoritmo
El algoritmo de Booth examina pares adyacentes de bits del multiplicador de 'N' bits Y en la representación del complemento a dos con signo , incluido 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 y y i −1 . Cuando estos dos bits son iguales, el acumulador de producto P no se modifica. Donde y i = 0 y y i −1 = 1, el multiplicando por 2 i se suma a P ; y donde Y i = 1 y y i-1 = 0, los tiempos de multiplicando 2 i se resta de P . El valor final de P es el producto firmado.
No se especifican las representaciones del multiplicando y el producto; Por lo general, 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 también funcionará. Como se indica aquí, el orden de los pasos no está determinado. Normalmente, procede de LSB a MSB , comenzando en i = 0; la multiplicación por 2 i se reemplaza entonces típicamente por un desplazamiento incremental del acumulador P hacia la derecha entre pasos; bits bajos pueden ser desplazados hacia fuera, y las adiciones y sustracciones posteriores a continuación, se pueden realizar sólo en los más altos de N bits 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 en 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 +1 de orden superior y el efecto neto es la interpretación como un valor negativo del valor apropiado.
Una implementación típica
Algoritmo de Booth puede implementarse añadiendo repetidamente (con la adición ordinaria binario sin signo) uno de dos valores predeterminados A y S a un producto P , a continuación, realizar una hacia la derecha de desplazamiento aritmético en P . Deje que m y r sea el multiplicando y el multiplicador , respectivamente; y dejar que x y y representan el número de bits en m y r .
- Determinar 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).
- R: Complete los bits más significativos (más a la izquierda) con el valor de m . Llene los bits restantes ( y + 1) con ceros.
- S: Complete los bits más significativos con el valor de (- m ) en notación en complemento a dos. Llene los bits restantes ( y + 1) con ceros.
- P: Llene los bits x más significativos con ceros. A la derecha de esto, agregue el valor de r . Llene el bit menos significativo (más a la derecha) con un cero.
- Determinar los dos bits menos significativos (más a la derecha) de P .
- Si son 01, encontrar el valor de P + A . Ignore cualquier desbordamiento.
- Si son 10, encontrar el valor de P + S . Ignore cualquier desbordamiento.
- Si son 00, no hagas nada. Utilice P directamente en el siguiente paso.
- Si tienen 11 años, no hagas nada. Utilice P directamente en el siguiente paso.
- Desplace aritméticamente el valor obtenido en el segundo paso un solo lugar a la derecha. Sea P ahora igual a este nuevo valor.
- Repita los pasos 2 y 3 hasta que los haya realizado y veces.
- La caída de la bit menos significativo (más a la derecha) a partir de P . Este es el producto de m y r .
Ejemplo
Encuentre 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
- Realice el bucle cuatro veces:
- P = 0000 110 0 0 . Los dos últimos bits son 00.
- P = 0000 0110 0. Desplazamiento aritmético a la derecha.
- P = 0000 011 0 0 . Los dos últimos bits son 00.
- P = 0000 0011 0. Desplazamiento aritmético a la derecha.
- 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.
- P = 1110 100 1 1 . Los dos últimos bits son 11.
- P = 1111 0100 1. Desplazamiento aritmético a la derecha.
- P = 0000 110 0 0 . Los dos últimos bits son 00.
- El producto es 1111 0100, que es −12.
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). Una posible corrección a este problema es agregar un bit más a la izquierda de A, S y P. Esto luego 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, se asignará a los primeros x +1 bits de A. A continuación, la técnica mejorada se demuestra multiplicando −8 por 2 usando 4 bits para el multiplicando y el multiplicador:
- A = 1 1000 0000 0
- S = 0 1000 0000 0
- P = 0 0000 0010 0
- Realice el bucle cuatro veces:
- P = 0 0000001 0 0 . Los dos últimos bits son 00.
- P = 0 0000 0001 0. Desplazamiento a la derecha.
- 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.
- 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.
- P = 1 1110 000 0 0 . Los dos últimos bits son 00.
- P = 1 1111 0000 0. Desplazamiento a la derecha.
- P = 0 0000001 0 0 . Los dos últimos bits son 00.
- El producto es 11110000 (después de descartar el primer bit y el último) que es −16.
Cómo funciona
Considere un multiplicador positivo que consiste en un bloque de unos rodeados de ceros. Por ejemplo, 00111110. El producto viene dado por:
donde M es el multiplicando. El número de operaciones se puede reducir a dos reescribiendo lo mismo que
De hecho, se puede demostrar que cualquier secuencia de unos en un número binario se puede dividir en la diferencia de dos números binarios:
Por lo tanto, la multiplicación en realidad puede ser reemplazada por la cadena de unos en el número original mediante operaciones más simples, sumando el multiplicador, desplazando el producto parcial así formado por lugares apropiados y finalmente restando el multiplicador. Aprovecha el hecho de que no es necesario hacer nada más que cambiar mientras se trabaja con ceros en un multiplicador binario, y es similar a usar la propiedad matemática de que 99 = 100 - 1 mientras se multiplica 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 antiguo esquema al realizar 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 también funciona para un multiplicador negativo. Cuando los de un multiplicador se agrupan en bloques largos, el algoritmo de Booth realiza menos sumas y restas que el algoritmo de multiplicación normal.
Ver también
Referencias
- ↑ Booth, Andrew Donald (1951) [1 de agosto de 1950]. "Una técnica de multiplicación binaria firmada" (PDF) . The Quarterly Journal of Mechanics and Applied Mathematics . IV (2): 236–240. Archivado (PDF) desde el original el 16 de julio de 2018 . Consultado el 16 de julio de 2018 . Reimpreso en Booth, Andrew Donald . Una técnica de multiplicación binaria firmada . Prensa de la Universidad de Oxford . págs. 100-104.
- ^ Chen, Chi-hau (1992). Manual de procesamiento de señales . Prensa CRC . pag. 234. ISBN 978-0-8247-7956-6.
Otras lecturas
- Collin, Andrew (primavera de 1993). "Computadoras de Andrew Booth en Birkbeck College" . Resurrección . Londres: Computer Conservation Society (5).
- Patterson, David Andrew ; Hennessy, John Leroy (1998). Organización y diseño de computadoras: la interfaz hardware / software (segunda ed.). 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 desempeño (Quinta ed.). Nueva Jersey: Prentice-Hall, Inc. ISBN 0-13-081294-3.
- 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 .
enlaces externos
- Codificación de cabina Radix-4
- Codificación de cabina Radix-8 en una teoría formal de RTL y aritmética informática
- Simulador de JavaScript de algoritmo de Booth
- Implementación en Python