Algoritmo de booth

Solo disponible en BuenasTareas
  • Páginas : 3 (717 palabras )
  • Descarga(s) : 4
  • Publicado : 4 de mayo de 2010
Leer documento completo
Vista previa del texto
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 de que cuando tenemos un multiplicando el cualtiene 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 01 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)
Elnuevo 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 algoritmode 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 ydesplazado.
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 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úmerosy 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 = 10 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...
tracking img