Algoritmos De Booth Para La Multiplicación Y División En Binario

Algoritmo de Booth
Hay algoritmos más directos para la obtención de multiplicaciones con números negativos, uno de estos es el algoritmo de Booth. El cual genera multiplicaciones de 2n bits y trata por igual tanto números positivos como negativos. Este algoritmo se basa en el hecho de que cuando tenemos un multiplicando el cual tiene una serie de unos en su representación, este valor se puededescomponer en la resta de otros dos números con una cantidad de uno menor, 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 0Pero 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 tengamos estas 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 cual introducimos un bit previo a m0, el m-1. En la página siguiente se muestra elalgoritmo.
Para entender por qué 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 en los 1’s de m’)
mneg = 1 0 0 1 0 1 0 1 (unos en los -1’s de m’)
Para realizar lamultiplicación podemos utilizar dos métodos, codificar el multiplicador como hemos visto antes (con signos negativos en los unos) o no codificarlo así y tener en cuenta la secuencia de bits de dos en dos como hemos visto.
Para comprenderlo mejor veremos el mismo ejemplo de las dos formas.
Ejemplo: de multiplicación con el algoritmo de Booth:
A=0 1 0 1 1 0 1 B=0 0 1 1 1 1 0
1º) Codificamos Bcomo 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 01 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 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 1
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 enel algoritmo vista en la hoja anterior.
Ambos métodos son equivalentes e iguales en su realización, veámoslo:
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 ados)
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 1
0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 0 0 1 1 0


Ejemplo: Vamos algunas equivalencias para calcular la forma del multiplicador. Sea B=53 y A=21, calculamos la...