algoritmo de booth

Ejemplo de Algoritmo de Booth
CS440 



Puntos a recordar
 Cuando se utiliza el algoritmo de Booth:
Usted necesitará el doble de bits en su producto como que tiene en su original de dos operandos.
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é operandoserá el multiplicador y que será el multiplicando
Convertir ambos operandos en complemento a dos la representación utilizando bits X
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
 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:
-5 Es 11011 (multiplicador)
2 es 00010 (multiplicando)



 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.
Si es el primer paso, utilice 0 como el LSB anterior.

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



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

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



 Ejemplo
Vamos a continuar con nuestro ejemplo de lamultiplicación de (-5) x 2
Recuerde:
-5 Es 11011 (multiplicador)
2 es 00010 (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 las anteriores LSB
   00000 11011 0

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



 Ejemplo: Paso 1 continuación
 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 izquierdadel producto
      11110 11011 0



 Ejemplo: Paso 1 continuación
Paso 1, Paso 2: ASR (desplazamiento a la derecha aritmética)
Antes de ASR
           11110 11011 0
 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 y anteriores LSB
   11111 011011  
Paso 2, Paso 1: Examine los últimos 2 bits
             11111 0110 1 1 
Los dos últimos son de 11 bits, 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)
Antes de ASR
            11111 01101 1
 Después de ASR
  11111 10110 1
 (a la izquierda-lamayorí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 y anteriores LSB
             11111 10110 1  
 Paso 3, Paso 1: Examine los últimos 2 bits
            11111 1011 0 1 
Los dos últimos bits son 01, por lo que necesitamos:
Añadir el multiplicando a la mitad izquierda del producto



 Ejemplo:...