1.4 Algoritmos de Booth para la multiplicación y división en binario.

1.4 Algoritmos de Booth para la multiplicación y división en binario.

ALGORITMO DE BOOTH 

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.

Complemento a1

Para obtener el complemento a uno del numero en binario solo consta en cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1:101101)

Complemento a2

El complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo):  mi numero en decimal es 86

Realizar una multiplicación con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:

1º Obtengo mis números (multiplicando y multiplicador) en binario con longitud de 8 bits

2º  asigno A= multiplicando, S= Complemento a2 de A, P= 8 bits en 0. Agrego 7 bits extras a la derecha de A y S, en P agrego el valor de multiplicador con longitud de 8 bits y un bit extra con valor 0. Como se indica a continuación:

Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P.

3o Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:

0  0  No hacer nada

0  1 P = P + A

1  0  P = P + S

1  1  No hacer nada

Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo el último bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados:

Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha.