Algoritmo de booth

INSTITUTO TECNOLOGICO DE CELAYA MATEMATICAS DISCRETAS

TORRES ESTRADA JESUS MIGUEL

ALGORITMO DE BOOTH
El algoritmo de Booth es un algoritmo que sirve para multiplicar (y dividir) númerosbinarios con signo de manera rápida y sencilla en complemento a dos. Aquí se explica de manera detallada el funcionamiento de ese algoritmo.
El complemento a dos de un número N que, expresado en el sistemabinario está compuesto por n dígitos, se define como: Su utilidad principal se encuentra en las operaciones matemáticas con números binarios. En particular, la resta de números binarios se facilitaenormemente utilizando el complemento a dos: la resta de dos números binarios puede obtenerse sumando al minuendo el complemento a dos del sustraendo. Se utiliza porque la unidad aritmético-lógica noresta números binarios, suma binarios negativos, por eso esta conversión al negativo.

La manera en que se representan los números binarios negativos es mediante su complemento a dos. El complementoa uno consiste en invertir el valor de cada bit, esto es que si se tiene el número 5 binario b’00000101′ su complemento a uno sería b’11111010′. Una vez teniendo el complemento a 1 para obtener elcomplemento a dos simplemente se le debe sumar un 1, así que se tiene b’11111010 + 1′ de modo que el complemento a dos del número 5 binario es b’11111011′. PROCEDIMIENTO Supongamos dos números,multiplicando y multiplicador, con longitudes en bits. Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo mas complicada. Con el algoritmo de Booth, resulta muchomas sencillo de implementar. Partimos del ejemplo de la multiplicación 6*2=12:

INSTITUTO TECNOLOGICO DE CELAYA MATEMATICAS DISCRETAS

TORRES ESTRADA JESUS MIGUEL

Como se puede ver, partiendo delos números binarios de a multiplicación 6*2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P. Pariendo del número P (producto)...