Ejemplo del 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
* Decidaqué operando será 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 ejemplode 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ón aritmé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 la multiplicació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 anterioresLSB
00000 11011 0

(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 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 losproductos)
-00.010 (Mulitplicand)
11  110 (usa un fantasma prestado)
* Lugar resultado en la mitad izquierda del 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 laizquierda)
* Paso 1 está completa.

Ejemplo: Paso 2
* De productos actuales y anteriores LSB
11111 01101 1
* 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-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 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...