Sistemas Computacionales
Páginas: 2 (375 palabras)
Publicado: 28 de septiembre de 2012
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 AndrewDonald 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 eldesplazamiento 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.
El algoritmo de Booth examina paresadyacentes de bits del multiplicador Y de N-bits en la representación de complemento a dos con signo, incluyendo un bit implícito debajo del bit menos significativo, y-1 = 0. Para cada bit yi, para i corriendodesde 0 hasta N-1, los bits yi y yi-1 son considerados. Cuando estos dos bits son iguales, el acumulador del producto P es dejado sin cambios. Cuando yi = 0 y yi-1 = 1, el multiplicando multiplicadopor 2i es agregado a P; y cuando yi = 1 y yi-1 = 0, el multiplicando multiplicado por 2i es restado de P. El valor final
Procedimiento
Supongamos dos números, multiplicando y multiplicador, conlongitudes en bits, x para el primero, e y para el segundo:
* Construimos una matriz de tres filas y x+y+1 columnas. Identificaremos las filas como, A la primera, S la segunda y P la tercera.
*Se inician los x primeros bits de cada fila con:
* A, el multiplicando.
* S, el complemento a dos del multiplicando.
* P, ceros.
* Los siguientes y bits se completan con:* A, ceros.
* S, ceros.
* P, el multiplicador.
* Para finalizar la matriz, se inician a 0 todos los valores de la última columna.
Una vez iniciada esta matriz, se realiza elalgoritmo.
* Se realizan y iteraciones del siguiente bucle.
1. Comparar los dos bits menos significativos de P, para realizar la siguiente acción:
* 00 o 11: no se hace nada....
El algoritmo de Booth examina paresadyacentes de bits del multiplicador Y de N-bits en la representación de complemento a dos con signo, incluyendo un bit implícito debajo del bit menos significativo, y-1 = 0. Para cada bit yi, para i corriendodesde 0 hasta N-1, los bits yi y yi-1 son considerados. Cuando estos dos bits son iguales, el acumulador del producto P es dejado sin cambios. Cuando yi = 0 y yi-1 = 1, el multiplicando multiplicadopor 2i es agregado a P; y cuando yi = 1 y yi-1 = 0, el multiplicando multiplicado por 2i es restado de P. El valor final
Procedimiento
Supongamos dos números, multiplicando y multiplicador, conlongitudes en bits, x para el primero, e y para el segundo:
* Construimos una matriz de tres filas y x+y+1 columnas. Identificaremos las filas como, A la primera, S la segunda y P la tercera.
*Se inician los x primeros bits de cada fila con:
* A, el multiplicando.
* S, el complemento a dos del multiplicando.
* P, ceros.
* Los siguientes y bits se completan con:* A, ceros.
* S, ceros.
* P, el multiplicador.
* Para finalizar la matriz, se inician a 0 todos los valores de la última columna.
Una vez iniciada esta matriz, se realiza elalgoritmo.
* Se realizan y iteraciones del siguiente bucle.
1. Comparar los dos bits menos significativos de P, para realizar la siguiente acción:
* 00 o 11: no se hace nada....
Leer documento completo
Regístrate para leer el documento completo.