Algoritmo 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.