Nose

Algoritmo de Booth
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
El algoritmo de Booth es un procedimiento algorítmico para realizar la multiplicación de dos números consigno, expresados en base binaria en notación complemento a dos.
[editar] Procedimiento
Supongamos dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para elsegundo:
* 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, elmultiplicador.
* 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 delsiguiente 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 (menossignificativo), obteniendo el resultado.
.3. Algoritmo de Booth.
Supongamos multiplicando = 2 y multiplicador = 7 (en binario la multiplicación 0010 x 0111). Booth expresó 7 = 8 -1 y sustituyó elmultiplicador por esta descomposición:
0111 = 1000 - 0001 = +1 0 0 -1.
Con lo que siguiendo el algoritmo la multiplicación es:
0 0 1 0 Multiplicando
x +1 0 0 -1 Multiplicador según Algoritmo deBooth
1 1 1 1 1 1 0 Restamos (-1 en multiplicador)
0 0 0 0 0 0 2 desplazamientos (2 ceros en el multiplicador)
0 0 0 1 0 Sumamos (+1 en el multiplicador)
0 0 0 0 1 1 1 0
El funcionamiento del...