Mate discretas

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 filasy 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, seinician 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 bitsde 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.

SumaBinario:
Primer paso |

De la misma forma que hacemos cuando sumamos números del sistema decimal, esta operación matemática la comenzamos a realizar de derecha a izquierda, comenzando por los últimosdígitos de ambos sumandos, como en el siguiente ejemplo: | | |


En la tabla de suma de números binarios podemos comprobar que 0 + 0 = 0 |



Segundo paso |

| | Se suman lossiguientes dígitos 1 + 1 = 10 (según la tabla), se escribe el “0” y se acarrea o lleva un “1”. Por tanto, el “0” correspondiente a tercera posición de izquierda a derecha del primer sumando, adquiere ahora...