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 bitmenos significativo, y-1 = 0. Para cada bit yi, para i corriendo desde 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 sincambios. 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 elproducto con 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, perocualquier 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 bitmenos significativo (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 ala 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 losextremos 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.
[editar]Procedimiento
Supongamosdos números, multiplicando y multiplicador, con longitudes 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...
Regístrate para leer el documento completo.