Contenido Introducción Operaciones lógicas: desplazamientos lógicos Operaciones aritméticas: multiplicación y división Multiplicación Sin signo: suma desplazamiento Sin signo: sumas y restas Con signo: Algoritmo de Booth División Con restauración Sin restauración Coma flotante
La ALU dentro del computador
Operaciones lógicas: desplazamientos
Operaciones aritméticas: multiplicación y división La operación básica es la suma, que se supone conocida en este curso
También se suponen conocidos los multiplicadores paralelo de tipo combinacional
En este tema se estudian los algoritmos para realizar las operaciones desde el punto de vista de la arquitectura, centrados en la multiplicación y la división
MULTIPLICACIÓN BINARIA SIN SIGNO: SUMA DESPLAZAMIENTO
Fundamentos Se multiplica cada bit del multiplicador, empezando por el menos significativo, por todos los bits del multiplicando Si es 0, el resultado es 0 Si es 1, el resultado es el multiplicando Cada vez que se considera un nuevo bit del multiplicador, se desplaza hacia la izquierda una posición el nuevo producto y se añade a la suma parcial acumulada La última suma parcial será el resultado
Ejemplo 0 1 1 0 1 0 0 1 0 1 1 0 inicial 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 x Primera suma parcial acumulada Segunda suma parcial acumulada Ultima suma parcial acumulada (RESULTADO) 0 0 1 1 0 1 1 0 6×9=54 0 1 1 0
IDEA BÁSICA Hay que sumar las sumas acumuladas con el multiplicando DESPLAZADO A LA IZQUIERDA cuando el LSB del multiplicador sea 1. EN LUGAR DE DESPLAZAR A LA IZQUIERDA EL MULTIPLICANDO, SE DESPLAZAN A LA DERECHA LAS SUMAS PARCIALES
Necesidades El producto de un número binario de n bits con otro de m bits necesita m+n bits Sea A el multiplicador y B el multiplicando En el caso de que m=n, se necesitan dos registros iguales para almacenar el resultado Sean R3 y R4 los registros donde se va almacenando el resultado
Arquitectura (Gp:) C (Gp:) R2 (Gp:) R4 (Gp:) R3 (Gp:) R1 (Gp:) CON (Gp:) Contador
Algoritmo Suma Desplazamiento Se inicializan a 0 el contador de bits del multiplicador y el registro R3 Se carga R1 con el multiplicando A y R2 con el multiplicador B Se analiza el LSB de R2 Si es 1, se suma R1+ R3 y el resultado se deja en R3 Si es 0, se suma R1 + 0 (es decir, no se hace nada) y el resultado se deja en R3 Se incrementa el contador Se produce un desplazamiento aritmético (con extensión de signo) de una posición hacia la derecha del conjunto C-R3-R4 Se realiza una rotación circular a derecha de R2 Se mira si el contador ha llegado hasta el final En caso negativo se repite el proceso, volviendo a preguntar por el LSB de R2 En caso afirmativo se finaliza el proceso y el resultado está en C-R3-R4
Inicio, R3?0, Cont?0 R1?A R2?B R20? R3? R3+R1 Incrementa contador C-R3-R4 desplaza derecha R2 rota circul Cont? Fin 1 0 NO SI SUMA DESPLAZAMIENTO
Ejemplo Multiplicar A=0110 por B=1001 El resultado debe ser 6×9=54 (en binario 0011 0110) (Gp:) C (Gp:) R2 (Gp:) R4 (Gp:) R3 (Gp:) R1 (Gp:) (Gp:) Contador
Inicialización Se carga A en R1 y B en R2. Se pone a 0 el registro R3 y el contador (Gp:) 0 (Gp:) 1001 (Gp:) XXXX (Gp:) 0000 (Gp:) 0110 (Gp:) 0 (Gp:) Contador
Comprobación de R20 y acción Como el LSB de R2 es 1 se suman R3 + R1 y se deja el resultado en R3 (Gp:) 0 (Gp:) 1001 (Gp:) XXXX (Gp:) 0110 (Gp:) 0110 (Gp:) 0 (Gp:) Contador
Incremento contador Se incrementa el contador en una unidad (Gp:) 0 (Gp:) 1001 (Gp:) XXXX (Gp:) 0110 (Gp:) 0110 (Gp:) 1 (Gp:) Contador
Desplazamiento a derecha Se desplaza el conjunto C-R3-R4 una posición a la derecha (Gp:) 0 (Gp:) 1001 (Gp:) 0XXX (Gp:) 0011 (Gp:) 0110 (Gp:) 1 (Gp:) Contador
Rotación circular de R2 El registro R2 rota a la derecha de forma circular (Gp:) 0 (Gp:) 1100 (Gp:) 0XXX (Gp:) 0011 (Gp:) 0110 (Gp:) 1 (Gp:) Contador
¿Ha llegado al final? Comprueba que el contador no es 4 y repite el bucle (Gp:) 0 (Gp:) 1100 (Gp:) 0XXX (Gp:) 0011 (Gp:) 0110 (Gp:) 1 (Gp:) Contador
Como el LSB de R2 es 0 se suman R3 + 0, es decir, NO hace nada, y se deja el resultado que había en R3
(Gp:) 0 (Gp:) 1100 (Gp:) 0XXX (Gp:) 0011 (Gp:) 0110 (Gp:) 1 (Gp:) Contador
Comprobación de R20 y acción
Incremento contador Se incrementa el contador en una unidad (Gp:) 0 (Gp:) 1100 (Gp:) 0XXX (Gp:) 0011 (Gp:) 0110 (Gp:) 2 (Gp:) Contador
Desplazamiento a derecha Se desplaza el conjunto C-R3-R4 una posición a la derecha
(Gp:) 0 (Gp:) 1100 (Gp:) 10XX (Gp:) 0001 (Gp:) 0110 (Gp:) 2 (Gp:) Contador
Rotación circular de R2 El registro R2 rota a la derecha de forma circular (Gp:) 0 (Gp:) 0110 (Gp:) 10XX (Gp:) 0001 (Gp:) 0110 (Gp:) 2 (Gp:) Contador
¿Ha llegado al final? Comprueba que el contador no es 4 y repite el bucle (Gp:) 0 (Gp:) 0110 (Gp:) 10XX (Gp:) 0001 (Gp:) 0110 (Gp:) 2 (Gp:) Contador
Como el LSB de R2 es 0 se suman R3 + 0, es decir, NO hace nada, y se deja el resultado que había en R3
(Gp:) 0 (Gp:) 0110 (Gp:) 10XX (Gp:) 0001 (Gp:) 0110 (Gp:) 2 (Gp:) Contador
Comprobación de R20 y acción
Incremento contador Se incrementa el contador en una unidad
(Gp:) 0 (Gp:) 0110 (Gp:) 10XX (Gp:) 0001 (Gp:) 0110 (Gp:) 3 (Gp:) Contador
Desplazamiento a derecha Se desplaza el conjunto C-R3-R4 una posición a la derecha (Gp:) 0 (Gp:) 0110 (Gp:) 110X (Gp:) 0000 (Gp:) 0110 (Gp:) 3 (Gp:) Contador
Rotación circular de R2 El registro R2 rota a la derecha de forma circular
(Gp:) 0 (Gp:) 0011 (Gp:) 110X (Gp:) 0000 (Gp:) 0110 (Gp:) 3 (Gp:) Contador
¿Ha llegado al final? Comprueba que el contador no es 4 y repite el bucle (Gp:) 0 (Gp:) 0011 (Gp:) 110X (Gp:) 0000 (Gp:) 0110 (Gp:) 3 (Gp:) Contador
Como el LSB de R2 es 1 se suman R3 + R1 y se deja el resultado en R3 (Gp:) 0 (Gp:) 0011 (Gp:) 110X (Gp:) 0110 (Gp:) 0110 (Gp:) 3 (Gp:) Contador
Comprobación de R20 y acción
Incremento contador Se incrementa el contador en una unidad
(Gp:) 0 (Gp:) 0011 (Gp:) 110X (Gp:) 0110 (Gp:) 0110 (Gp:) 4 (Gp:) Contador
Desplazamiento a derecha Se desplaza el conjunto C-R3-R4 una posición a la derecha (Gp:) 0 (Gp:) 0011 (Gp:) 0110 (Gp:) 0011 (Gp:) 0110 (Gp:) 4 (Gp:) Contador
Rotación circular de R2 El registro R2 rota a la derecha de forma circular
(Gp:) 0 (Gp:) 1001 (Gp:) 0110 (Gp:) 0011 (Gp:) 0110 (Gp:) 4 (Gp:) Contador
¿Ha llegado al final? Comprueba que el contador es 4 y acaba. El resultado está en el registro R3 seguido de R4 (Gp:) 0 (Gp:) 0011 (Gp:) 0110 (Gp:) 0011 (Gp:) 0110 (Gp:) 4 (Gp:) Contador
Otro ejemplo Multiplicar A=1001 por B=0110 El resultado debe ser 9×6=54 (en binario 0011 0110) (Gp:) C (Gp:) R2 (Gp:) R4 (Gp:) R3 (Gp:) R1 (Gp:) Contador
Inicialización Se carga A en R1 y B en R2. Se pone a 0 el registro R3 y el contador (Gp:) 0 (Gp:) 0110 (Gp:) XXXX (Gp:) 0000 (Gp:) 1001 (Gp:) 0 (Gp:) Contador
Como el LSB de R2 es 0 se suman R3 + 0, es decir, NO hace nada, y se deja el resultado que había en R3
(Gp:) 0 (Gp:) 0110 (Gp:) XXXX (Gp:) 0000 (Gp:) 1001 (Gp:) 0 (Gp:) Contador
1001 0110 00000 Comprobación de R20 y acción
Incremento contador Se incrementa el contador en una unidad (Gp:) 0 (Gp:) 0110 (Gp:) XXXX (Gp:) 0000 (Gp:) 1001 (Gp:) 1 (Gp:) Contador
Desplazamiento a derecha Se desplaza el conjunto C-R3-R4 una posición a la derecha (Gp:) 0 (Gp:) 0110 (Gp:) 0XXX (Gp:) 0000 (Gp:) 1001 (Gp:) 1 (Gp:) Contador
1001 0110 00000 00000 0
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN LA VERSIÓN DE DESCARGA