Algoritmo booth
Páginas: 6 (1376 palabras)
Publicado: 13 de enero de 2012
INDICE
Introducción .................................................................................................................................. 3 El Algoritmo................................................................................................................................... 4Procedimiento............................................................................................................................... 5 Ejemplo práctico. .......................................................................................................................... 6 Codificación................................................................................................................................... 8
Booth
13/Enero/2012
Pág. 2 / 13
Introducción
Elobjetivo del presente documento es explicar la base y funcionamiento del 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 hacía investigación sobre cristalografía en la universidad de Bloomsbury, enBirkbeck, 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.
Booth
13/Enero/2012
Pág. 3 / 13
El Algoritmo.
El algoritmo de Booth examina pares adyacentes 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 menossignificativo, y-1 = 0. Para cada bit yi, para i corriendo desde 0 hasta N-1, los bits yi y yi1 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 multiplicado por 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 de P es el productocon signo. La representación del multiplicando y del producto no son especificadas; típicamente, éstos también están ambos en la representación de complemento a dos, como el multiplicador, pero cualquier sistema de numeración que soporte la adición y la substracción trabajará igual de bien. Según lo indicado aquí, el orden de los pasos no está determinado. Típicamente, procede desde el bit menossignificativo (LSB) al bit mas significativo (MSB), comenzando en i = 0; la multiplicación por 2i es entonces típicamente reemplazado por el desplazamiento (shifting) incremental del acumulador P a la derecha entre los pasos; los bits bajos pueden ser desplazados hacia fuera, y las adiciones y substracciones subsecuentes entonces pueden ser hechas justo en los N bits más altos de P.1 Hay muchasvariaciones y optimizaciones sobre estos detalles. El algoritmo es a menudo descrito como convertir secuencias de 1s en el multiplicador con un +1 de orden alto y un -1 de orden inferior en los extremos de la secuencia. Cuando una secuencia corre por el MSB, no hay +1 de orden alto, y el efecto neto es la interpretación como un negativo de valor apropiado.
Booth
13/Enero/2012
Pág. 4 / 13 Procedimiento.
Dados dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para el segundo: Se define 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: o A, el multiplicando. o S, el complemento a dos del multiplicando. o P, ceros. Lossiguientes y bits se completan con: o A, ceros. o S, ceros. o 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 el algoritmo. Se realizan y iteraciones del siguiente bucle. o Comparar los dos bits menos significativos de P, para realizar la siguiente acción: 00 o 11: no se hace nada. 01: P =...
Introducción .................................................................................................................................. 3 El Algoritmo................................................................................................................................... 4Procedimiento............................................................................................................................... 5 Ejemplo práctico. .......................................................................................................................... 6 Codificación................................................................................................................................... 8
Booth
13/Enero/2012
Pág. 2 / 13
Introducción
Elobjetivo del presente documento es explicar la base y funcionamiento del 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 hacía investigación sobre cristalografía en la universidad de Bloomsbury, enBirkbeck, 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.
Booth
13/Enero/2012
Pág. 3 / 13
El Algoritmo.
El algoritmo de Booth examina pares adyacentes 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 menossignificativo, y-1 = 0. Para cada bit yi, para i corriendo desde 0 hasta N-1, los bits yi y yi1 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 multiplicado por 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 de P es el productocon signo. La representación del multiplicando y del producto no son especificadas; típicamente, éstos también están ambos en la representación de complemento a dos, como el multiplicador, pero cualquier sistema de numeración que soporte la adición y la substracción trabajará igual de bien. Según lo indicado aquí, el orden de los pasos no está determinado. Típicamente, procede desde el bit menossignificativo (LSB) al bit mas significativo (MSB), comenzando en i = 0; la multiplicación por 2i es entonces típicamente reemplazado por el desplazamiento (shifting) incremental del acumulador P a la derecha entre los pasos; los bits bajos pueden ser desplazados hacia fuera, y las adiciones y substracciones subsecuentes entonces pueden ser hechas justo en los N bits más altos de P.1 Hay muchasvariaciones y optimizaciones sobre estos detalles. El algoritmo es a menudo descrito como convertir secuencias de 1s en el multiplicador con un +1 de orden alto y un -1 de orden inferior en los extremos de la secuencia. Cuando una secuencia corre por el MSB, no hay +1 de orden alto, y el efecto neto es la interpretación como un negativo de valor apropiado.
Booth
13/Enero/2012
Pág. 4 / 13 Procedimiento.
Dados dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para el segundo: Se define 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: o A, el multiplicando. o S, el complemento a dos del multiplicando. o P, ceros. Lossiguientes y bits se completan con: o A, ceros. o S, ceros. o 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 el algoritmo. Se realizan y iteraciones del siguiente bucle. o Comparar los dos bits menos significativos de P, para realizar la siguiente acción: 00 o 11: no se hace nada. 01: P =...
Leer documento completo
Regístrate para leer el documento completo.