stringtranslate.com

Algoritmo de multiplicación de Booth

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

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.

Una implementación típica

Un aritmómetro Walther WSR160 de 1960. Cada vuelta de la manivela suma (hacia arriba) o resta (hacia abajo) el operando establecido en el registro superior del valor del registro acumulador en la parte inferior. Al desplazar el sumador hacia la izquierda o hacia la derecha, el efecto se multiplica por diez.

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 .

  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: Rellene los bits más significativos (los que están más a la izquierda) con el valor de m . Rellene 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: Rellene los bits x más significativos con ceros. A la derecha de esto, añada el valor de r . Rellene el bit menos significativo (el más a la derecha) con un cero.
  2. Determinar los dos bits menos significativos (más a la derecha) de P.
    1. Si son 01, encuentre el valor de P  +  A. Ignore cualquier desbordamiento.
    2. Si son 10, encuentre el valor de P  +  S. Ignore cualquier desbordamiento.
    3. Si son 00, no haga nada. Utilice P directamente en el siguiente paso.
    4. Si son 11, no haga nada. Utilice P directamente en el siguiente paso.
  3. Desplazar aritméticamente el valor obtenido en el segundo paso un lugar hacia la derecha. Sea P ahora igual a este nuevo valor.
  4. Repita los pasos 2 y 3 hasta que se hayan realizado y veces.
  5. Elimina el bit menos significativo (el más a la derecha) de P. Este es el producto de m y r .

Ejemplo

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:

Cómo funciona

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.

Véase también

Referencias

  1. ^ Booth, Andrew Donald (1951) [1950-08-01]. "A Signed Binary Multiplication Technique" (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 con signos . Oxford University Press . Págs. 100–104.
  2. ^ Chen, Chi-hau (1992). Manual de procesamiento de señales. CRC Press . pág. 234. ISBN. 978-0-8247-7956-6.

Lectura adicional

Enlaces externos