Algoritmo de booth

Algoritmo de Booth
Este algoritmo es un procedimiento iterativo que se utiliza para realizar la multiplicación de dos números binarios, expresados en complementos a dos.

Para comenzar con elalgoritmo, se tienen que definir el multiplicando y el multiplicador, cada uno con “x” y “y” de longitud, medidos en bits.
Después se construye una matriz con 3 filas y (x+y+1) columnas.
A la primerafila le llamamos A, la segunda S, y la tercera P, como se muestra en la imagen.

Después, se inicializan los valores en la matriz de la siguiente manera, acomodando los bits del multiplicando, elmultiplicando en formato de complementos a dos, y el multiplicador. Los demás espacios se llenan con ceros, para una mayor comprensión se muestra la siguiente imagen:

0
0
0
0
0
0
0
0
0
0
0
00
0
0
0
0
0
0
0
0
0
0
0
MULTIPLICANDO
MULTIPLICANDO

MULTIPLICANDO C2
MULTIPLICANDO C2

0
0
0
0
0
0
0
0
MULTIPLICADOR
MULTIPLICADOR

Una vez teniendo esta matriz, secomienza con el algoritmo:

1. Se realizan “y” iteraciones del siguiente proceso:

* 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).
* Desplazamiento aritmético de P a la derecha (se conserva el bit del signo).

2. Finalmente, tras “y” iteraciones, seelimina el último bit de la derecha (el menos significativo) de la fila P, y el número que resulte, es el resultado.

Bibliografía.
Ortega, Gerardo. Ing. Informática, El algoritmo de Booth.Recuperado el 24 de febrero del 2011 en: http://gro-info.blogspot.com/2008/11/el-algoritmo-de-booth.html

Vidal, Tomás. Estructuras de Computadores Digitales, Algoritmos de Multiplicación y División.Recuperado el 24 de febrero del 2011 en: http://profesores.elo.utfsm.cl/~tarredondo/info/comp-architecture/elo311-10-Algoritmos.pdf

Patterson, David. Computer Organization & Design (2005). Segunda...