MATEMATICAS DISCRETAS ALGORITMO DE BOOTH

[pic 1]

INSTITUTO TECNOLOGICO SUPERIOR DE ZAPOTLANEJO

MATEMATICAS DISCRETAS

ALGORITMO DE  BOOTH

Info 1          Andrés González Pulido

Docente:

Julián De Jesús García Talancón

Zapotlanejo, Jalisco, México                        28 de Agosto del 2015

¿Qué es el Algoritmo de Booth?

El Algoritmo de multiplicación de Booth es un algoritmo de multiplicación que multiplica dos números binarios con signo en la notación de complemento a dos. El algoritmo fue inventado por Andrew Donald Booth en 1950 mientras que hacía investigación sobre cristalografía en la universidad de Bloomsbury, en Birkbeck, Londres. Booth usaba calculadoras de escritorio que eran más rápidas en el desplazamiento que sumando, y creó el algoritmo para aumentar su velocidad. El algoritmo de Booth es de interés en el estudio de la arquitectura de computadoras.

Proceso:

El Algoritmo de Booth es un método rápido y sencillo para obtener los productos de los números binarios con signo en notación complemento a dos.

Debemos de saber que un número binario está formado por bits de ceros y unos y se puede traducir a decimal fácilmente de la siguiente manera:

    128 64 32 16          8  4  2  1

    1 0  1 0         0 1 1 0

Sabiendo que la posición de cada bit 2^n (elevado a la n)  y partimos n=0 de derecha a izquierda solo queda realizar la suma de multiplicar por dicho bit.

Ejemplo:

[pic 2]

Conclusión:

     El algoritmo de Booth, es igual de efectivo al de multiplicación con sumas y restas, simplemente demuestra la multiplicación con signo, representando los operandos con notación en complemento a 2.  Una posible mejora para aumentar la rapidez en la ejecución del algoritmo sería, aprovechando la propiedad conmutativa de la multiplicación, seleccionar como multiplicador entre ambos operandos aquel que tenga menos transiciones entre 0 y 1 y viceversa.  Al multiplicar N bits por Y bits obtenemos un resultado de N+Y bits.

...