Algoritmo de prueba de stand
Un mejor método para la multiplicación de números con signo es el algoritmo de Booth. Utiliza operaciones de suma y resta para calcular el producto de datos en complemento a dos. El algoritmo de Booth juzga el multiplicador comenzando desde el bit bajo y decide si realizar una operación de suma, resta o simplemente desplazamiento en función de la situación de los dos bits de datos. Los dos bits de datos juzgados son el bit actual y el bit de la derecha (inicialmente es necesario agregar un bit auxiliar 0), y la operación de desplazamiento es moverse hacia la derecha. En el ejemplo anterior, la primera vez que juzgamos el bit más bajo 0 y el bit derecho (bit auxiliar 0) en el multiplicando 0110, obtenemos 00, por lo que solo se realiza la operación de desplazamiento la segunda vez; 0110, obtenemos 10, así que realizamos la operación de resta y desplazamos. Esta operación de resta es equivalente a restar el valor de 2a la tercera vez que juzgamos los dos dígitos del medio del multiplicando, obtenemos 11, por lo que solo realizamos la operación de desplazar. ; la cuarta vez juzgamos el 0110 en Los dos bits más altos son 01, por lo que se realizan la operación de suma y desplazamiento. Esta suma equivale a sumar el valor de 8a, porque el valor de a se ha desplazado hacia la izquierda tres veces.
En términos generales, sea y=y0, yly2...yn el multiplicando, x es el multiplicador y yi es la i-ésima posición (posición actual) en a. Según los valores de yj y yi 1, el algoritmo de Booth se muestra en la siguiente tabla y su proceso de operación se muestra en la figura siguiente. En el algoritmo de Booth, el método de operación depende del valor de la expresión (yi 1-yi). La operación representada por el valor de esta expresión es:
0 Sin operación
. 1 Sumar x
-1 Restar x
Representación de la operación del algoritmo de Booth
yi yi 1 instrucciones de operación
0 0 No hay ninguna en el 0 cadena, no se requiere operación
0 1 Sumar x al final de la cadena 1
1 0 Restar x al principio de la cadena 1
1 1 Ninguna está en la cadena 1, no se requiere operación
Durante el proceso de multiplicación, la operación de desplazamiento a la izquierda del multiplicando en relación con el producto se puede expresar como multiplicar por 2, y la operación en cada bucle se puede expresar como x (yi 1-yi)2^31 -Operación de suma de i elementos (i=3l, 30,…,1,0). De esta forma, el resultado calculado por el algoritmo de Booth se puede expresar como:
x×(0-y31)×2^0
x×(y31-y30)×2^ 1
p>x×(y30-y29)×2^2
<…
[1] x×(y1-y0)×2^31
=x×(-y0×231 y1×2^30 y2×2^29 y31×2^0)
=x×y
Ejemplo : Cálculo utilizando el algoritmo de Booth 2×(-3).
Solución: complemento [2] = 0010, complemento [-3] = 1101. Antes de que comience la multiplicación, los valores iniciales en R0 y R1 son 0000 y 1101, y el valor en R2 es 0010 .
En el primer ciclo de multiplicación, se juzga que el bit más bajo y el bit auxiliar de R1 son 10, así que ingrese al paso 1c, reste el valor de R2 del valor de R0, se envía el resultado 1110 a R0, y luego ingrese En el segundo paso, R0 y Rl se desplazan un bit hacia la derecha. El resultado de R0 y R1 es 11110110, y el bit auxiliar es l.
En el segundo ciclo, primero juzgue que el bit más bajo y el bit auxiliar de Rl son 0l, así que vaya al paso 1b y realice la suma, R0 R2=1111 0010, el resultado 0001 se envía a R0, luego R0R1 El contenido es 0001 0110, que cambia a 0000 1011 después del desplazamiento a la derecha en el segundo paso, y el bit auxiliar es 0.
En el tercer ciclo, el bit de juicio es 10, ingrese el paso lc, reste R2 de R0, el resultado 1110 se envía a R0, R1 permanece sin cambios después del cambio de paso; 2 son 1111 01011, el bit auxiliar es 1.
En el cuarto ciclo, debido a que los dos bits de juicio son 11, no se realiza ninguna suma ni resta. El resultado después de desplazarse hacia la derecha es 1111 1010, que es el resultado de la operación (-6).
La descripción de este proceso de multiplicación se muestra en la siguiente tabla. La columna de producto en la tabla indica el contenido de R0, R1 y un bit auxiliar P. Las palabras en negrita indican el juicio de los dos. bits de juicio.
El proceso de calcular 2 × (-3) usando la multiplicación de un bit en complemento de Booth
Bucle
Pasos
Producto (R0 , R1, P)
Valor inicial
0000 1101 0
Primer ciclo
1c: menos 0010
1110 1101 0
2: Desplazar a la derecha 1 bit
1111 0110 1
Segundo ciclo
1b: Agregar 0010
0001 0110 1
2: Desplazamiento a la derecha 1 bit
0000 1011 0
Tercer ciclo
1c: Restar 0010
1110 1011 0
2: Desplazamiento a la derecha 1 bit
1111 0101 1
El cuarto ciclo
1a: Sin operación
1111 0101 1
2: Desplazamiento a la derecha 1 bit
1111 1010 1
4． La regla de operación de multiplicación de dos complementos y dos complementos se basa en la regla de multiplicación de un complemento y un complemento. La operación que se debe realizar al comparar el estado de yiyi 1 y la operación que se debe realizar al comparar el estado de yi-. 1yi Combinado en un solo paso, se puede obtener el método de operación de la multiplicación de dos bits en complemento a dos.
Las reglas de operación de multiplicación de dos dígitos con complemento dos son las siguientes
Bit de juicio yi-1y iyi 1
Contenido de la operación
000
[zi 1]Suplemento=2-2[zi]Suplemento
001
[zi 1]Suplemento=2-2{[zi]Suplemento [x]Suplemento}
010
[zi 1]suplemento=2-2{[zi]suplemento[x]suplemento}
011
[ zi 1] complemento=2-2{[zi] complemento 2[x] complemento}
100
[zi 1] complemento=2-2{[ zi] complemento 2[ -x]complemento}
101
[zi 1]complemento=2-2{[zi]complemento[-x]complemento}
110
[zi 1]Suplemento=2-2{[zi]Suplemento-x}Suplemento}
111
[zi 1]Suplemento= Complemento 2-2[zi]
Como se puede ver en la tabla anterior, las operaciones incluyen sumar el complemento 2[x] y sumar el complemento 2[-x], por lo tanto, además de. la operación de desplazamiento dos lugares hacia la derecha, también hay un desplazamiento hacia la izquierda del multiplicando en uno. Las operaciones de bits y la suma del complemento a 2 [x] y la suma del complemento a 2 [-x] pueden ocupar el bit de doble signo; debido al desbordamiento, por lo que algunos multiplicandos de suma de productos usan tres bits de signo.
Ejemplo: complemento [x]=0.0101, complemento [y]=1.0101 Encuentra: complemento [x?6?1 y].
Solución: El proceso de solución se muestra en la siguiente tabla. El multiplicador toma dos bits de signo, que es 11,0101, y el complemento [-x] = 1,1011 toma tres bits de signo, que es 111,1011.
Producto parcial
Multiplicador
Descripción
000.0000
000.0101
1101010
El bit de juicio es 010, agregue [x] para complementar
000.0101
000.0001
000.0101
0111010
→2 bits
El bit de juicio es 010, suma [x] para complementar
000.0110
000.0001
111.1011
01
1001110
→2 bits
El bit de juicio es 110, agregue [-x] para complementar
111.1100
1001
Si el último paso no se desplaza, obtenemos [x?6?1 y] para complementar
Entonces [x?6?1 y] para complementar =1.11001001
Se puede ver que en comparación con la multiplicación en complemento a uno, el producto parcial de la multiplicación en complemento a dos toma un bit de signo más (***3 bits), y el multiplicador también toma un bit de signo más (***2 bits), esto se debe a que el multiplicador se desplaza 2 bits hacia la derecha cada vez y se juzga con 3 bits, por lo que el uso de bits de doble signo es más conveniente para la implementación de hardware. . Se puede ver que cuando el valor del multiplicador es un número par, el multiplicador toma 2 bits de signo, se requieren n/2 desplazamientos y se realizan como máximo n/2 sumas, y el último paso no se desplaza cuando n es; un número impar Cuando , se puede agregar 0 para convertirlo en un número par para simplificar las operaciones lógicas. También puede tomar 1 bit de signo para el multiplicador. En este caso, se realizan n/2 1 sumas y n/2 1 desplazamientos (el último paso es un desplazamiento de un dígito).
Para la multiplicación por complemento de enteros, el proceso es exactamente el mismo que el de la multiplicación decimal. Para distinguirlo de la multiplicación decimal, el "." entre el bit de signo y el bit numérico se puede cambiar a "," por escrito.
Agregue otro ejemplo para aumentar la comprensión. Jaja
Ejemplo 1.37 Supongamos el multiplicando M=0111 (7), el multiplicador Q=0011 (3), el proceso de multiplicación es el siguiente: (①②... lo sumé yo mismo)
A Q Q-1
①0000 0011 0 valor inicial
②1001 0011 0 A=A-M
③1100 1001 1 Desplazamiento a la derecha (primer ciclo)
④1110·0100·1 Desplazamiento a la derecha (2.º ciclo)
⑤0101·0100·1 A=A M
⑥0010·1010·0 Desplazamiento a la derecha (3.er ciclo) )
⑦0001 0101 0 Desplazamiento a la derecha (cuarto ciclo)
Después de completar la operación de multiplicación, el resultado es ***8 bits, el registro A es la parte de orden superior de el producto, el registro Q es la parte de orden inferior del producto, es decir, producto = 0010101 = (21) (decimal)
Ejemplo 1.38 Suponga que el multiplicando M = 0111 (7), el multiplicando Q = 1101 (-3), El proceso de multiplicación es el siguiente:
A Q Q-1
0000 1101 0 Valor inicial
1001 1101 0 A= A-M
1100 1110 1 Desplazamiento a la derecha (primer ciclo)
0011 1110 1 A = A + M
0001 1111 0 Desplazamiento a la derecha (segundo ciclo)
1010 1111 0 A = A - M
1101 0111 1 Desplazamiento a la derecha (3er ciclo)
1110 1011 1 Desplazamiento a la derecha (4º ciclo)
Producto=11101011=(-21)(decimal)