Algorítmos De Booth

El algoritmo de Booth es un procedimiento algorítmico para realizar la multiplicación de dos números con signo, expresados en base binaria en notación complemento a dos.

Procedimiento

Supongamos dos 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 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 el algoritmo.

 Se realizan y iteraciones del siguiente bucle.

1. Comparar los dos últimos bits de P, para realizar la siguiente acción:

 00 o 11: no se hace nada.

 01: P = P + A. Se ignora el acarreo.

 10: P = P + S. Se ignora el acarreo.

2. Desplazamiento aritmético de P a la derecha (se conserva el bit de signo).

 Finalmente, tras y iteraciones, se elimina el último bit de la derecha (menos significativo), obteniendo el resultado.

MULTIPLICACION:

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

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

Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 de derecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso, lo que muestro a continuación:

0•27+1•26+0•25+1•24+0•23+1•22+1•21+0•20 = 86.

También debemos saber que el complemento a uno de un número binario es cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1: 101101) y que el complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario

...