Algoritmo de booth

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

[pic]
Sabiendo que la posición de cada bit es 2^n (elevadoa 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 se muestra a continuación:
0x27+1x26+0x25+1x24+0x23+1x22+1x21+0x20= 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 deun 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):

[pic]

Realizar una suma con dosnúmeros binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación6x2=12:

[pic]

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

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

[pic]

Serealizará 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 laizquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso, quedarían los siguientes resultados:

[pic]

Finalmente se obtiene el número en binario...