TEMA 3 : LA UNIDAD ARITMÉTICA Y LÓGICA (A.L.U.) • Introducción. Este tema va a tratar sobre la Unidad Aritmético y Lógica más conocida como A.L.U.. Para realizar su diseño debemos de tener en cuenta ciertos requerimientos: • Debemos considerar las operaciones a realizar. • Quién es el registro temporal y cuántos de éstos necesito. • Quién es el registro acumulador y cuántos de éstos necesito. • Indicadores de resultado: señalizadores. Nosotros tendremos los siguientes componentes tal y como se ven a continuación: • Cuatro operaciones lógicas mediante el operador aritmético y lógico (uno o varios). • Un registro temporal: Temp • Un registro acumulador: A. • Cuatro registros: B, C, D y E. • Indicadores de resultado: • Acarreo (C). • Negativo (N). • Desbordamiento (O o V). • Cero (Z). A.L.U. • Operaciones lógicas. Son fáciles de implementar por que mantienen una correspondencia directa con el hardware y los componentes más utilizados son las puertas lógicas AND, OR, OR−EXCLUSIVA, INVERSORES, ... Por ejemplo: Operación Resultado B A • La suma y la resta. La suma y la resta son operaciones de dos palabras de 1 bit de las que obtengo una suma y un carry. Existen distintas formas de implementar la suma y la resta. En este apartado veremos distintos circuitos combinacionales basados en distintas funciones lógicas. Cada componente vendrá descrito por los siguientes aspectos: • Tabla de verdad. • Función lógica de cada salida de la tabla de verdad. 1

• Bloque combinacional y, en algunos, los componentes que integran el bloque. 3.1. Semisumador binario (H.A.). El semisumador posee la siguiente tabla de verdad: Entradas A 0 0 1 1

B 0 1 0 1

Salidas S 0 1 1 0

C 0 0 0 1

Las funciones de las salidas del semisumador son las siguientes: __ • S = A · B + A · B = A " B ! Suma. • C = A · B ! Acarreo. El bloque combinacional y el bloque con sus componentes integrados serían los siguientes: AC BS H.A. A C S B 3.2. Sumador completo (F.A.). En este circuito combinacional se realiza una suma con los dos operandos A y B como en el semisumador pero con el acarreo, Cin, proveniente de otra suma y así obtener la suma completa, que tarda 3 unidades de tiempo, y el acarreo, que tarda 2. El bloque sería el siguiente: Cin A S B Cout 2

El sumador completo posee la siguiente tabla de verdad: Entradas A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

Cin 0 1 0 1 0 1 0 1

Salidas S 0 1 1 0 1 0 0 1

Cout 0 0 0 1 0 1 1 1

Las funciones de las salidas del sumador son las siguientes: _ _ _ __ _ __ • S = A · B · Cin + A · B · Cin + A · B · Cin + A · B · Cin ! Suma. • Cout = A · B + A · Cin + B · Cin ! Acarreo. Otra forma de implementarlo sería por medio de semisumadores donde al final la suma tarda 9 unidades de tiempo para el resultado final. Tendríamos las siguientes funciones para la suma total y el acarreo de salida producido por la suma total: • S = (A " B) " Cin ! Suma. • Cout = A · B + Cin · (A " B) ! Acarreo. El bloque combinacional con sus componentes integrados serían el siguiente: F.A. AS B Cin Cout 3.3. Sumador con propagación de acarreo. Este sumador se encuentra como circuito integrado denominado 74ls83 y son varios sumadores que se emplean en sumas de palabras de un bit. En nuestro caso sumaremos palabras de 4 bits: dos entradas para los operandos A y B en el circuito así como para el carry de entrada, tendrá entonces dos salidas para el resultado, de ancho de palabra de cuatro bits, y para el bit del carry de salida cuyo ancho de palabra es de un bit. Para sumar dos números de n bits se necesita colocar en cascada n sumadores completos. El acarreo se propaga de una etapa a la siguiente con lo que el circuito combinacional será un Sumador con Propagación de Acarreo (Carry Propagated Adder). Los sumadores han sido construidos con puertas lógicas a partir de la 3

expresión: _ _ _ __ _ __ • S = A · B · Cin + A · B · Cin + A · B · Cin + A · B · Cin ! Suma. • Cout = A · B + A · Cin + B · Cin ! Acarreo. El bloque combinacional del sumador formado por estos sumadores completos que han sido integrados con puertas lógicas sería el siguiente: B3 A3 B2 A2 B1 A1 B0 A0 C3 C2 C1 C0 8T 6T 4T 2T 9T 7T 5T 3T C4 S3 S2 S1 S0 Los sumadores completos también pueden estar construidos con semisumadores con lo que la suma NO varía en su resultado aunque sí el bloque combinacional. El bloque combinacional con sus componentes integrados serían los siguientes: F.A. AS B Cin Cout B3 A3 B2 A2 B1 A1 B0 A0 C3 C2 C1 C0 9T 7T 5T 3T 8T 6T 4T 2T C4 S3 S2 S1 S0 El tiempo total del sumador con propagación de acarreo se calcula con la siguiente expresión: Tiempo Total = ( 2 · n + 1 ) · T 3.4. Circuito restador. Para restar lo que hacemos es suponer que se trabaja con números expresados en complemento a 2 y, por lo tanto, para realizar una resta lo que se hace es sumar al minuendo el complemento a 2 del sustraendo. La 4

expresión de la resta será: A − B = A + C2 ( B ) Este circuito tarda un período más que la suma puesto que al tratar con complemento a dos tenemos que poner en el operando B un inversor que junto con el acarreo, que al principio del circuito vale 1, obtendrá el resultado de la resta y así la expresión de tiempo será la siguiente: Tiempo Total = ( 2 · n + 2 ) · T El bloque combinacional del circuito restador será el que se muestra en la figura siguiente: B3 A3 B2 A2 B1 A1 B0 A0 C3 C2 C1 C0 = 1 C4 S3 S2 S1 S0 IMPORTANTE Nota 1, sobre Complemento a 2: El complemento a dos de un número −B, C2(B), se calcula: • Se expresa el número B en binario, por ej., 510 ! 01012. • Se cambian los ceros por unos y los unos por ceros, en el ej., 0101 ! 1010 (así obtenemos el complemento a uno, C1(B), del número). • Para acabar y obtener el C2 se le suma 1, en el ej., 1010 ! 1011. 3.5. Circuito sumador − restador. Este circuito combina las dos operaciones aritméticas más importantes como son la suma y la resta. El circuito está implementado por: • Una señal R/S, para discernir entre calcular una suma o una resta según la operación a realizar, que valdrá 0 si quiero realizar una suma y 1 si lo que quiero calcular es una resta. • Sumadores completos con propagación de acarreo; en el primer bloque el Cin vale lo mismo que la señal R/S. • Una puerta xor cuyas entradas son el operando B y la señal R/S y con una salida que se conecta a la patilla del sumador completo que no está conectada al operando A. La salida de la xor valdrá, teniendo en cuenta el valor de B y de R/S, B si quiero realizar una suma y el complementario de B, complemento a dos, si lo que quiero hacer es una resta. La expresión del tiempo de la resta será: Tiempo Total = 2 ( n + 1 + tiempo de la or − exclusiva ) · T. El sumador − restador posee puertas xor, para el operando B y la señal de control R/S, cuya tabla de verdad es la siguiente: Entradas XOR R/S 0

Bi 0

Salida XOR Entrada al F.A. 0 5

0 1 1

1 0 1

1 1 0

El bloque combinacional con el que se implementa el circuito sumador − restador es el mostrado en la figura siguiente: B3 A3 B2 A2 B1 A1 B0 A0 R/S C3 C2 C1 C0 = 1 C4 S3 S2 S1 S0 Un integrado del tipo sumador − restador es el 74ls181 que sirve para implementar una A.L.U. de cuatro bits de entrada para seleccionar operaciones como +, −, ", or, and,... hasta 16 operaciones distintas. Tiene 20 patillas y las más importantes son:

• Entrada H para modo aritmético y L para lógico. • Salida de carry y operación realizada. • Entrada de carry. • Entradas Ai y Bi para los bits de los dos operandos. • A = B puedo utilizarlo como flag de Z. • P corresponde propagación del acarreo anticipado. • G corresponde generación del acarreo anticipado. 3.6. Detección de desbordamiento. Cuando trabajo con números en C2 se puede producir desbordamiento debido a que el bit de más peso corresponde al bit de signo; por ejemplo, con números de 4 bits donde el 7 en binario es el máximo número a representar ya que el bit de mayor peso ya se ha dicho que corresponde al bit de signo puede ocurrir que, al realizar operaciones suma y resta, se pueden dar casos de overflow (si se sobrepasa el rango de representación de los números para n bits, n = 4 en nuestro caso): • Si NO hay acarreo el resultado es negativo y se calcula postcomplementando el resultado, es decir, cambiando los 0 por 1 y los 1 por 0 y sumándole una unidad obtendremos el número resultado real − ( número en binario resultado postcomplementado). • Si hay acarreo el resultado es positivo y es : + ( número en binario resultado sin el bit de carry). • Ejemplo 1: 0111 + 0111! Suma de dos números positivos ( 7 + 7 ) que da 1110. Al NO haber carry, el resultado obtenido será negativo y NO puede dar resultado real negativo; si lo postcomplementamos daría 1000 y como el bit de mayor peso es 1 implica que ha habido overflow porque sólo tengo 3 bits para representar el número y el cuarto bit es para el signo. • Ejemplo 2: 1001C2 + 1011C2 ! Suma de dos números negativos ( −7 + −5 ) que NO puede dar resultado positivo; como da 10100 el bit de mayor peso implica que ha habido overflow ya que la solución viene dada por 5 bits y carry también por que el quinto bit aparece porque el cuarto bit de ambos números se suman y, por valer 1, se produce 10 lo cual es acarreo y al haber acarreo el resultado es positivo y sería +0100, lo cual es imposible.

6

Para la detección del desbordamiento emplearemos como bloque combinacional un sumador − restador en complemento a 2 con detección de desbordamiento como es el mostrado en la figura siguiente: B3 A3 B2 A2 B1 A1 B0 A0 R/S C3 C2 C1 C0 = 1 C4 S3 S2 S1 S0 V Según la tabla de verdad del circuito combinacional sólo habrá overflow en dos casos: Entradas Sumador − Restador Ai Bi ... ... 0 0 ... ... 1 1

(A, B y Carry) Ci ... 1 ... 0

Salida Entrada al F.A. ... 1 ... 1

Para evitar el overflow y detectarlo emplearemos una or exclusiva con entradas C4 y C3 y la salida de un bit será el bit V de detección overflow. 3.7. Sumador con anticipación de acarreo (C.L.A.). Este bloque combinacional llamado Carry Lookahead Adder, C.L.A., tiene las siguientes características: • Suponer A y B números de cuatro bits. • Señal generadora de acarreo: Gi = ai · bi. • Señal propagadora de acarreo: Pi = ai + bi " ai " bi. • Acarreo de la etapa i: Ci = Func. Generadora + Func. Propagadora · Ci − 1 = Gi + Pi · Ci − 1. • Como hemos supuesto que trabajamos con números de cuatro bits particularizaremos las distintas etapas del acarreo: • C0 = G0 + P0 · C−1 • C1 = G1 + P1 · C0 • C2 = G2 + P2 · C1 • C3 = G3 + P3 · C2 • Desarrollando las expresiones y poniéndolas en función de C−1: • C0 = G0 + P0 · C−1 • C1 = G1 + P1 · (G0 + P0 · C−1) • C2 = G2 + P2 · (G1 + P1 · (G0 + P0 · C−1)) • C3 = G3 + P3 · (G2 + P2 · (G1 + P1 · (G0 + P0 · C−1))) • Todos los acarreos dependen de ai y bi. • Estas expresiones se resuelven como suma de productos.

7

• Tres niveles de puertas lógicas para obtener cada uno de los acarreos. Por lo que el acarreo tarda 3 unidades de tiempo en ejecutarse ya que halla los acarreos que halla. El circuito tarda menos en realizar la suma y su la tabla de verdad será la siguiente: B1 0 0 0 0 1 1 1 1

A1 0 0 1 1 0 0 1 1

C0 0 1 0 1 0 1 0 1

C1 0 0 0 1 0 1 1 1

El bloque combinacional y el bloque con sus componentes integrados serían los siguientes: B3 A3 B2 A2 B1 A1 B0 A0 C2 C1 C0 C−1 G3 P3 G2 P2 G1 P1 G0 P0 S3 S2 S1 S0 C3 IMPORTANTE Nota 2, sobre Sumador: Los bloques empleados en este bloque combinacional NO son los que hemos empleado hasta el momento ya que generan la señal generadora y la señal propagadora de acarreo. Si los sumadores completos están construidos con semisumadores el bloque combinacional varía. El bloque combinacional con sus componentes integrados serían los siguientes: F.A. Ai 4T Si Bi 1T Ci −1 3T Ci B3 A3 B2 A2 B1 A1 B0 A0 C2 C1 C0 C−1 8

3T 3T 3T G3 P3 G2 P2 G1 P1 G0 P0 1T 1T 4T 1T 1T 4T 1T 1T 4T 1T 1T 2T S3 S2 S1 S0 C3 El total del tiempo total invertido por todo el circuito sumador con anticipación de acarreo es de 17 unidades de tiempo. 3.8. Ejemplo (Sumador C.L.A. de 8 bits). Dado que se hacen de 2 operandos de 4 bits de entrada, para 8 habrá que montarlos. El bloque combinacional del sumador con anticipación de acarreo de 8 bits se implementará como se muestra en la figura: B7 A7 B6 A6 B5 A5 B4 A4 C6 C5 C4 C3 G7 P7 G6 P6 G5 P5 G4 P4 S7 S6 S5 S4 C7 B3 A3 B2 A2 B1 A1 B0 A0 C2 C1 C0 C−1 G3 P3 G2 P2 G1 P1 G0 P0 S3 S2 S1 S0 C3 • La multiplicación. La multiplicación se puede calcular fácilmente mediante un algoritmo de sumas y desplazamientos. Si el multiplicando es de n bits y el multiplicador de m, entonces el producto es de n + m bits. La multiplicación en binario es muy sencilla ya que se trata de multiplicar por 1 ó por 0. Veamos un ejemplo en sistema decimal y otro en sistema binario: • Ejemplo en sistema decimal: Multiplicando 5 3 2 Multiplicador 4 3 1 2532 9

1596 2128 Producto 2 2 9 2 9 2 • Ejemplo en sistema binario: Multiplicando 1 0 1 1 Multiplicador 1 1 0 1 11011 10000 11011 1011 Producto 1 0 0 0 1 1 1 1 Existen dos tipos de multiplicación en binario: multiplicación binaria sin signo y con signo cuyos algoritmos veremos más adelante. 4.1. Multiplicación binaria sin signo. El algoritmo para calcular la multiplicación binario sin signo es el siguiente: Versión Preliminar La máquina calcula con el algoritmo la multiplicación usando los siguientes bloques y circuitos: Desplaz. dcha. n bits Suma n bits A.L.U. Desplaz. dcha. Escribir 2·n bits Ahora bien, el algoritmo se puede mejorar llegando a la versión siguiente: Versión 10

Final La máquina calcula con el algoritmo la multiplicación usando los siguientes bloques y circuitos: n bits Suma A.L.U. Desplaz. dcha. Escribir 2·n bits El algoritmo funciona de forma muy sencilla como veremos en el siguiente ejemplo: • Ejemplo multiplicación sin signo: Multiplicando = 1010 Multiplicador = 0101 Producto 0000 0101 1010 0101 0101 0010 0010 1001 1100 1001 0110 0100 0011 0010

Multiplicando 1010 1010 1010 1010 1010 1010 1010

Acción Valores iniciales Sumar producto y multiplicando Desplazar producto 1 bit a la derecha Desplazar producto 1 bit a la derecha Sumar producto y multiplicando Desplazar producto 1 bit a la derecha Desplazar producto 1 bit a la derecha

Iteración 0 1 1 2 3 3 4

Paso a paso en la máquina se calcula: 1º.) A.L.U. 2º.) Como tengo un 0 desplazo otra vez. 3º.) Se encuentra un 1, hace la suma y el resultado. Luego el producto de dos números de 3 bits, por ejemplo, es: A3 A2 A1

11

B3 B2 B1 A3B1 A2B1 A1B1 ...............+ P5 P4 P3 P2 P1 Si implementásemos el circuito nos daríamos cuenta que en todos los productos bit a bit necesitamos unas puertas lógicas AND y para el resto del bloque combinacional necesitamos sumadores de acarreo anticipado, por ser los más rápidos, para sumar todos los resultados de las puertas AND. 4.2. Multiplicación binaria con signo. En la multiplicación con signo debemos de tener en cuenta que trabajamos con números expresados en complemento a dos, después sólo hay que aplicar el algoritmo de sumas y desplazamientos. Debemos de tener en cuenta que hay que entender el signo en cada iteración y, después de multiplicar cada bit del multiplicador con todos los bits del multiplicando, debemos repetirlo tantas veces delante de este subproducto hasta igualar la posición del bit de mayor peso del resultado que será de longitud n + m bits, donde el bit de mayor peso nos dará el signo del número y el resto del resultado el número si lo postcomplementamos si es negativo. Si no tenemos en cuenta el signo nos puede dar un resultado erróneo. Ejemplo: A= 1010 y B = 0011 Multiplicando = 1010 ! −5 Multiplicador = 0011 ! 3 10101010 x0011x0011 101011111010 10101111010 0000000000 000000000 0 0 1 1 1 1 0 ! No es −15 1 1 1 0 1 1 1 0 ! Sí es −15 Versión errónea Versión correcta 4.3. Algoritmo de Booth. Supongamos multiplicando = 2 y multiplicador = 7 (en binario la multiplicación 0010 x 0111). Booth expresó 7 = 8 −1 y sustituyó el multiplicador por esta descomposición: 0111 = 1000 − 0001 = +1 0 0 −1.

12

Con lo que siguiendo el algoritmo la multiplicación es: 0 0 1 0 Multiplicando x +1 0 0 −1 Multiplicador según Algoritmo de Booth 1 1 1 1 1 1 0 Restamos (−1 en multiplicador) 0 0 0 0 0 0 2 desplazamientos (2 ceros en el multiplicador) 0 0 0 1 0 Sumamos (+1 en el multiplicador) 00001110 El funcionamiento del Algoritmo de Booth realiza las sustituciones mostradas en las tablas: • Tabla 1: Bit actual 0 0 1 1

Bit a la derecha 0 1 0 1

Sustitución 0 (no hay transición) +1 (transición hacia positivo) −1 (transición hacia negativo) 0 (no hay transición)

Bit a la izquierda 0 1 0 1

Sustitución 0 (no hay transición) −1 (transición hacia negativo) +1 (transición hacia positivo) 0 (no hay transición)

• Tabla 2: Bit actual 0 0 1 1 • Ejemplo 1: Multiplicando = 11101110 Multiplicador = 01111010 ! recodificación según Booth = +1000−1+1−10 ( otro 0 para desplazamiento puesto que inicialmente eso va q−1 ). El producto sería el siguiente: 1 1 1 0 1 1 10 x +1 0 0 0 −1 +1−10 00000000 0 0 0 0 0 0 0 0 00000000 0 0 1 0 0 1 0 11111111 1 0 1 1 1 0 13

00000000 1 0 0 1 0 11110111 0 0 0 0 111110111 0 1 1 0 1 1 0 0 Ahora bien, el pseudocódigo del Algoritmo de Booth es el siguiente: La máquina calcula con el algoritmo la multiplicación usando los siguientes bloques y circuitos: n bits Suma / Resta A.L.U. Desplaz. dcha. 2·n bits Veamos una traza del Algoritmo de Booth para un ejemplo: • Ejemplo 2: Multiplicando = 1010 Multiplicador = 1110 Multiplicando 1010 1010 1010 1010 1010 1010 1010 1010 1010

Producto 0000 1110 0000 1110 0000 0111 0110 0111 0011 0011 0011 0011 0001 1001 0001 1001 0000 1100

q−1 0 0 0 0 1 1 1 1 1

Acción Valores iniciales 00 ! Ninguna operación Desplazamiento derecha 10 ! Resta Desplazamiento derecha 11 ! Ninguna operación Desplazamiento derecha 11 ! Ninguna operación Desplazamiento derecha

Iteración 0 1 1 2 2 3 3 4 4

• La división. Podemos expresar la división como: Dividendo = Cociente x Divisor + Resto. El resto es más pequeño que el divisor y hay que reservar el doble de espacio de éste para el dividendo. Supondremos números positivos. Veamos un ejemplo: • Ejemplo 1: Dividendo ! 1 0 0 1 0 0 1 1 1 0 1 1 ! Divisor 1 0 0 1 0 0 1 1 0 1 ! Cociente 14

1011 001110 1011 00111 1011 0 1 0 0 ! Resto La división, al igual que la multiplicación, se puede calcular fácilmente mediante la ejecución de un algoritmo de pseudocódigo llamado Algoritmo de restauración tal y como veremos más adelante. 5.1. Algoritmo con restauración. La división se calcula sencillamente gracias al Algoritmo de restauración que veremos a continuación implementado en pseudocódigo: La máquina calcula con el algoritmo la división usando los siguientes bloques y circuitos: n bits Suma / Resta A.L.U. Desplaz. Izq. Cociente Resto 2·n bits (long. bloque) Veamos una traza del Algoritmo de Restauración para un ejemplo: • Ejemplo 2: Dividendo = 0101 0011 Divisor = 0110 Dividendo 0101 0011 1010 011_ 0100 011_ 0100 0111 1000 111_ 0010 111_ 0010 1111

Divisor 0110 0110 0110 0110 0110 0110 0110

Acción Valores iniciales Desplazar un bit a la izquierda Restar: Dividendoh − Divisor Dividendoh > 0 ! q0 = 1 Desplazar un bit a la izquierda Restar: Dividendoh − Divisor Dividendoh > 0 ! q0 = 1

Iteración 0 1 1 1 2 2 2

15

0101 111_ 1111 111_ 1111 1110 0101 1110 1011 110_ 0101 110_ 0101 1101

0110 0110 0110 0110 0110 0110 0110

Desplazar un bit a la izquierda Restar: Dividendoh − Divisor Dividendoh < = 0 ! q0 = 0 Restaurar: Dividendoh + Divisor Desplazar un bit a la izquierda Restar: Dividendoh − Divisor Dividendoh > 0 ! q0 = 1

3 3 3 3 4 4 4

Resto/Cociente • Conclusiones. Hemos visto a lo largo del tema todos los pormenores al respecto de la A.L.U. y con todo ello podemos sacar conclusiones de distinta índole: • Sumadores: • Problemática temporal de los Sumadores con Propagación de Acarreo (CPA), especialmente sin n elevado. • Los Sumadores con Propagación de Acarreo (CPA) mejoran el tiempo de respuesta. • Multiplicación: • Problemática de la multiplicación de números con signo. • El algoritmo de Booth permite multiplicar números en C2 y en algunos casos reduce el número de operaciones si aparecen cadenas de 1's o 0's en el multiplicador. • División: • En la división con signo consultar el bit de mayor peso para saber el signo. • Algoritmo para la división con restauración para números positivos. Si hay números negativos, entonces tratamiento previo del signo, y en función de éste se obtiene el signo del resultado. Tema 3: A.L.U. − 56 − Estructura de Computadores 1 Guardado por José David Balibrea Sánchez Tema 3: A.L.U. − 66 − H.A. F.A. ZCO Banco de registros: B, C,

16

DyE TEMP A 00 01 10 H.A. Repetir n veces Si el bit 0 del multiplicador = 1 entonces Sumar el multiplicando a la mitad izquierda del producto y colocar el resultado en la mitad izquierda del producto Fin entonces Desplazar 1 bit a la derecha el registro producto Desplazar 1 bit a la derecha el registro multiplicador Fin repetir H.A. F.A. F.A. F.A. F.A. H.A. H.A. F.A. F.A. F.A. F.A. F.A. 17

F.A. F.A. F.A. F.A. F.A. F.A. F.A. XOR XOR XOR XOR F.A. F.A. F.A. F.A. XOR XOR XOR XOR

XOR

Generador de acarreo anticipado H.A.

18

H.A. Generador de acarreo anticipado 2T

Generador de acarreo anticipado

Generador de acarreo anticipado Multiplicando Multiplicador Producto FC Control Repetir n veces Si el bit 0 del registro producto = 1 entonces Sumar el multiplicando a la mitad izquierda del producto y colocar el resultado en la mitad izquierda del producto Fin entonces 19

Desplazar 1 bit a la derecha el registro producto Fin repetir Multiplicando 1010 FC Producto Multiplicador Control 0000 010 1 0 Control Inicialmente q−1 = 0 Repetir n veces Si q0 = 1 y q−1 = 0 entonces Productoh = Productoh − Multiplicando Si q0 = 0 y q−1 = 1 entonces Productoh = Productoh + Multiplicando Desplazamiento aritmético a la derecha de Producto y q−1 (que es coger el bit de mayor peso y repetirlo ahí para que se desplacen el resto de bits) Fin repetir 0101 001 0 Producto Multiplicador q0 0010 100 1 q−1 1100 100 1 Multiplicando Control Repetir n veces 20

Desplazar el Dividendo a la izquierda Dividendoh = Dividendoh − Divisor Si Dividendoh < 0 entonces (no cabe) q0 = 0 Dividendoh = Dividendoh + Divisor (restaurar) Sino q0 = 1 Fin Si Fin repetir Divisor Control Dividendo q0

21