Algoritmo De Booth
Páginas: 2 (342 palabras)
Publicado: 6 de septiembre de 2015
1. ¿Qué es el algoritmo de Booth?
El algoritmo de Booth es una aproximación más elegante para multiplicar números
signados. Comienza haciendo la observación de que con la posibilidad de sumar yrestar
hay múltiples formas de calcular un producto. Suponer que queremos multiplicar:
Booth observo que una ALU que pudiera sumar o restar podía obtener el mismo
resultado de más de una manera. Porejemplo, como podemos sustituir una cadena de
"unos" del multiplicador por una resta inicial cuando veamos primero un uno y más
tarde sumamos el bit después del último uno. Por ejemplo:
La clavede la idea de Booth, esta en sus grupos de clasificación de bits al comienzo, en
medio o al final de una ejecución de unos. Por supuesto, una cadena de ceros evita ya
aritmética, así que podemosdejar estos sólos.
El algoritmo en sí tiene dos pasos:
1- Dependiendo de los bits actuales y anteriores hacer :
00
01
10
11
Ninguna operación aritmética.
Suma el multiplicando a la mitad izquierdadel producto.
Resta el multiplicando de la mitad izquierda del producto.
Ninguna operación aritmética.
2- Desplaza el producto a la derecha.
Si se adapta este algoritmo al circuito de sumas yrestas sucesivas, hay que introducir la
corrección A*2n cuando Bn-1=1, es decir, para multiplicandos negativos. Por tanto,
eliminando el ultimo paso del algoritmo de sumas y restas, se obtiene unalgoritmo
adecuado para trabajar en complemento a dos.
Adaptación al circuito de la figura 2:
Inicializar: A<-0 , el contador de fases I<-N, el multiplicardor B<-Multiplicador, y
el multiplicandoMQ<-Multiplicando
Comparar el bit MQ0 con el MQ-1.
Si es principio de cadena de "unos", restar A<-A-B
Si es final de cadena de "unos" (esto es, es el primer 0 después de uno o varios 1),
sumar A<-A+BDecrementar: I<-I-1
Desplazar aritméticamente a la derecha el conjunto concatenado A||MQ0||MQ-1.
Observar el contador I.
Si es menor que 0, volver al segundo paso.
Si es igual a 0, terminar.
El algoritmo de Booth es una aproximación más elegante para multiplicar números
signados. Comienza haciendo la observación de que con la posibilidad de sumar yrestar
hay múltiples formas de calcular un producto. Suponer que queremos multiplicar:
Booth observo que una ALU que pudiera sumar o restar podía obtener el mismo
resultado de más de una manera. Porejemplo, como podemos sustituir una cadena de
"unos" del multiplicador por una resta inicial cuando veamos primero un uno y más
tarde sumamos el bit después del último uno. Por ejemplo:
La clavede la idea de Booth, esta en sus grupos de clasificación de bits al comienzo, en
medio o al final de una ejecución de unos. Por supuesto, una cadena de ceros evita ya
aritmética, así que podemosdejar estos sólos.
El algoritmo en sí tiene dos pasos:
1- Dependiendo de los bits actuales y anteriores hacer :
00
01
10
11
Ninguna operación aritmética.
Suma el multiplicando a la mitad izquierdadel producto.
Resta el multiplicando de la mitad izquierda del producto.
Ninguna operación aritmética.
2- Desplaza el producto a la derecha.
Si se adapta este algoritmo al circuito de sumas yrestas sucesivas, hay que introducir la
corrección A*2n cuando Bn-1=1, es decir, para multiplicandos negativos. Por tanto,
eliminando el ultimo paso del algoritmo de sumas y restas, se obtiene unalgoritmo
adecuado para trabajar en complemento a dos.
Adaptación al circuito de la figura 2:
Inicializar: A<-0 , el contador de fases I<-N, el multiplicardor B<-Multiplicador, y
el multiplicandoMQ<-Multiplicando
Comparar el bit MQ0 con el MQ-1.
Si es principio de cadena de "unos", restar A<-A-B
Si es final de cadena de "unos" (esto es, es el primer 0 después de uno o varios 1),
sumar A<-A+BDecrementar: I<-I-1
Desplazar aritméticamente a la derecha el conjunto concatenado A||MQ0||MQ-1.
Observar el contador I.
Si es menor que 0, volver al segundo paso.
Si es igual a 0, terminar.
Leer documento completo
Regístrate para leer el documento completo.