Ingenieria en sistemas computacionales

multiplicacion
Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:
[pic]
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.
Partiendo del número P (producto)comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:
[pic]
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 apaso nos quedarían los siguientes resultados:
[pic]
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.
ALGORITMO DE BOOTH
Genera multiplicaciones de 2n bits y trata por igual tanto números positivos como negativos. Este algoritmo se basa en el hecho deque cuando tenemos un multiplicando el cual tiene una serie de unos en su representación, este valor se puede descomponer en la resta de otros dos números con una cantidad de unos menores, por ejemplo:
0 0 1 1 1 1 0 = 0 1 0 0 0 0 0 - 0 0 0 0 0 1 0
Así la multiplicación se puede descomponer en una operación de adición para el primer número
y de una resta para el segundo:
M*0 0 1 1 1 1 0) =M(0 1 0 0 0 0 0) - M(0 0 0 0 0 1 0)
El nuevo multiplicador lo podemos representar por:
m’ = 0 1 0 0 0 -1 0
Pero este método se puede generalizar para cualquier cadena de bits en el multiplicando. Para
ello realizamos un algoritmo de forma que cuando realicemos la multiplicación, nos fijaremos en el
multiplicador viendo los bits de dos en dos: mi y mi-1, de forma que cuando tengamosestas cuatro
posibles secuencias, determinarán el valor de m’i, y realizaremos las acciones indicadas:
00 ó 11 : m’i = 0 : Solo desplazaremos el multiplicador --> poner ceros.
01 : m’i = 1 : Realizaremos el producto por 1 y desplazado.
10 : m’i = -1 : Realizaremos el complemento a dos del multiplicador con extensión de signo y desplazado.
Pero surge el problema del primer bit, para lo cualintroducimos un bit previo a m0, el m-1. En
la página siguiente se muestra el algoritmo.
Para entender por que se realiza esta asignación, hay que fijarse que todo número binario puede
ser expresado como resta de dos números y una forma de obtenerlos es aplicar la anterior codificación.
Ejemplo:
m = 1 0 1 1 0 1 0 1(0) = mpos - mneg
m’ =-1 1 0-1 1-1 1-1
mpos = 0 1 0 0 1 0 1 0 (unos enlos 1’s de m’)
mneg = 1 0 0 1 0 1 0 1 (unos en los -1’s de m’)
Para realizar la multiplicación podemos utilizar dos métodos, codificar el el multiplicador como
hemos visto antes (con signos negativos en los unos) o no codificarlo asi y tener en cuenta la secuencia de bits de dos en dos como hemos visto.
EJEMPLOS
Ejemplo: de multiplicación con el algoritmo de Booth:
A=0 1 0 1 1 0 1 B=00 1 1 1 1 0
1º) Codificamos B como ya se ha indicado:
B = 0 1 0 0 0 -1 0
Luego realizamos la operación de sumas parciales como en el caso del multiplicador por sumas
parciales haciendo el complemento a dos de los multiplicandos que sean necesarios restar
0 1 0 1 1 0 1
0+1 0 0 0-1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 1 0 0 1 1 (complemento a dos)
0 0 0 0 0 0 0 0 0 0 0
0 0 00 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 1 1 0
2º) Utilizar el segundo método basado en el algorimo vista en la hoja anterior.
Ambos métodos son equivalentes e iguales en su realizacición, veamoslo:
A=0 1 0 1 1 0 1 B=0 0 1 1 1 1 0
0 1 0 1 1 0 1
0 0 1 1 1 1 0(0)
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 1 0 0 1 1 (complemento a dos)
0 0 0 0 0 0 0...