Ejemplo de algoritmo de booth

1. Ejemplo de Algoritmo de Booth
CS440



Puntos a recordar
Cuando se utiliza el algoritmo de Booth:
o Usted necesitará el doble de bits en su producto como que tiene en su
original de dos operandos.
o El bit más a la izquierda de sus operandos (tanto multiplicando y
multiplicador) es un bit de signo, y no puede ser utilizado como parte del
valor.



Para empezar
Decida qué operando será el multiplicador y que será el multiplicando
Convertir ambos operandos en complemento a dos la representación
utilizando bits X
o X debe ser al menos un poco más de lo necesario para la representación
binaria del operando numéricamente más grande
Comience con un producto que consiste en el multiplicador con una X adicional
cero bits



Ejemplo

Un ejemplo de multiplicación de 2 x (-5)
Para nuestro ejemplo, vamos a revertir la operación, y se multiplican (-5) x 2
o El operando numéricamente mayor (5) se requieren 3 bits para
representar en binario (101). Así que debemos utilizar al menos 4 bits
para representar los operandos, para permitir el bit de signo.
Vamos a usar 5-bit complemento a 2:
o -5 Es11011(multiplicador)
o 2 es00010(multiplicando)

2. A partir de productos
El multiplicador es:
11011
Añadir 5 ceros a la izquierda para el multiplicador
para obtener el producto de principio:
00000 11011



Paso 1 para cada paso
Utilice el LSB (bit menos significativo) y el LSB anterior para determinar la
acción de la aritmética.
o Si es el primer paso, utilice0como el LSB anterior.

Aritmética de las acciones posibles:
o 00 ninguna operación aritmética
o 01 añadir multiplicando a la mitad izquierda del producto
o 10 restar multiplicando de la mitad izquierda del producto
o 11 ninguna operación aritmética



Paso 2 para cada paso
Realizar un cambio aritmético a la derecha (ASR)
en todo el producto.

3. NOTA: Para operandos X-bit, algoritmo de Booth requiere X pasa.



Ejemplo
Vamos a continuar con nuestro ejemplo de la multiplicación de (-5) x 2
Recuerde:
o -5 Es11011(multiplicador)
o 2 es00010(multiplicando)

Y hemos añadido 5 ceros a la izquierda para el multiplicador para obtener el
producto de principio:
00000 11011



Ejemplo continuación
Producto inicial y de lasanteriores LSB
00000 110110

(Nota: Ya que este es el primer paso, se utiliza 0 para el LSB anterior)
Paso 1, Paso 1:Examine los últimos 2 bits
00000 110110
Los dos últimos son de10bits, por lo que necesitamos:
restar el multiplicando de la mitad izquierda del producto



Ejemplo: Paso 1 continuación

4. Paso 1, Paso 1: Aritmética de acción
(1)00.000(a la izquierda de la mitad de los productos)
-00.010(Mulitplicand)
11 110(usa un fantasma prestado)
Lugar resultado en la mitad izquierda del producto
1111011011 0



Ejemplo: Paso 1 continuación
Paso 1, Paso 2: ASR(desplazamiento a la derecha aritmética)
o Antes de ASR
11110 11011 0
o Después de ASR
11111 01101 1
(a la izquierda-la mayoría fue de 1 bit, de modo que un 1
se desplazó en a la izquierda)
Paso 1 está completa.



Ejemplo: Paso 2
De productos actuales yanteriores LSB
11111 011011

5. Paso 2, Paso 1: Examine los últimos 2 bits
11111 011011
Los dos últimos son de11bits, por lo que NO es necesario realizar una acción aritmética
--
simplemente vaya al paso 2.



Ejemplo: Paso 2 continuación
Paso 2, Paso 2: ASR(desplazamiento a la derecha aritmética)
o Antes de ASR
11111 01101 1
o Después de ASR
11111 10110 1
(a la izquierda-la mayoría fue de 1 bit, de modo que un 1
se desplazó en a la izquierda)
Paso 2 está completo.



Ejemplo: Paso 3
De productos actuales yanteriores LSB
11111 101101
Paso 3, Paso 1: Examine los últimos 2 bits
11111 101101

6. Los dos últimos bits son01, por lo que necesitamos:
Añadir el multiplicando a la mitad izquierda del producto



Ejemplo: Paso 3 continuación
Paso 3, Paso 1: Aritmética de acción
(1)11.111(a la izquierda de la mitad de los productos)
00 010(mulitplicand)
00 001(caída de llevar a la a la izquierda)
Lugar resultado en la mitad izquierda del producto
0000110110 1



Ejemplo: Paso 3 continuación
Paso 3, Paso 2: ASR(desplazamiento a la derecha aritmética)
o Antes de ASR
00001 10110 1
o Después de ASR
00000 11011 0
(a la izquierda-la mayoría poco fue de 0, por lo que se
desplazó a 0 en el de la izquierda)
Paso 3 está completa.

7. Ejemplo: Paso 4
De productos actuales yanteriores LSB
00000 110110
Paso 4, Paso 1: Examine los últimos 2 bits
00000 110110
Los dos últimos son de10bits, por lo que necesitamos:
restar el multiplicando de la mitad izquierda del producto



Ejemplo: Paso 4 continuación
Paso 4, Paso 1: Aritmética de acción
(1)00.000(a la izquierda de la mitad de los productos)
-00.010(Mulitplicand)
11 110(usa un fantasma prestado)
Lugar resultado en la mitad izquierda del producto
1111011011 0



Ejemplo: Paso 4 continuación
Paso 4, Paso 2: ASR(desplazamiento a la derecha aritmética)

8. o Antes de ASR
11110 11011 0
o Después de ASR
11111 01101 1
(a la izquierda-la mayoría fue de 1 bit, de modo que un 1
se desplazó en a la izquierda)
Paso 4 es completo.



Ejemplo: Pase 5
De productos actuales yanteriores LSB
11111 011011
Pase 5, Paso 1: Examine los últimos 2 bits
11111 011011
Los dos últimos son de11bits, por lo que NO es necesario realizar una acción aritmética
--
simplemente vaya al paso 2.



Ejemplo: Pase 5 continuó
Pase 5, Paso 2: ASR(desplazamiento a la derecha aritmética)
o Antes de ASR
11111 01101 1

9. o Después de ASR
11111 10110 1
(a la izquierda-la mayoría fue de 1 bit, de modo que un 1
se desplazó en a la izquierda)
Paso 5 es completa.



Producto Final
Hemos completado 5 pases de la 5-operandos poco,
así que hemos terminado.

La eliminación de laLSB anterior,el producto final
resultante es:
11111 10110



Verificación
Para confirmar que tenemos la respuesta correcta,
convertir el complemento a 2 producto final de
nuevo a decimal.
Producto final:11111 10110
Decimal Valor:-10
que es el producto correcto de:
(-5) X 2

10. http://translate.google.com.ec/translate?hl=es&langpair=en|es&u=http://academic.r
egis.edu/psmallwo/SitePages/CS440/Presentations/Wk1online-BoothsAlg.ppt