Contenido elegido para ti
Esta es una vista previa del archivo. Inicie sesión para ver el archivo original
FCproblemas1.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 1 / pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES
TEMA 1
Problemas básicos:
1. Usando aritmética binaria, realice las siguientes operaciones (todos los operandos están
expresados en decimal):
695 + 272 695 – 272 272 × 23 159 10
Compruebe que el resultado binario concuerda con el que se obtendría operando en
decimal.
2. Realice los siguientes cambios de base:
(10110110)2 a hexadecimal, a decimal y a octal
(73)8 a hexadecimal, a decimal y a binario
(137)10 a hexadecimal, a octal y a binario
(AF3)16 a decimal, a octal y a binario
3. Exprese en octal y hexadecimal las siguientes secuencias de 16 bits:
A = 0000 0110 0000 0111 B = 0000 0000 1101 0110
C = 1100 0001 1111 0011 D = 1001 0000 0000 1010
Calcule también el número que representan suponiendo que lo codifican en binario puro,
en MyS, en C2 y en C1.
4. Dados los números A = (+36)10 y B = (+54)10 determine el número de bits mínimo para
representar ambos en el convenio C2. Realice las operaciones A+B y A-B usando
aritmética en C2. En cada caso indique razonadamente si se produce desbordamiento.
Exprese el resultado de la operación A-B en hexadecimal de 8 bits.
5. Extienda a 16 bits las siguientes secuencias de 8 bits:
A = 01110010 B = 11010110 C = 00001101 D = 11110101
suponiendo que representan números codificados en binario puro, MyS, C2 o C1.
Exprese en hexadecimal el resultado de cada una de las extensiones.
6. Considere las siguientes secuencias de 8 bits:
A = 01001001 B = 00010001 C = 10111101 D = 11110011
a) Suponiendo que codifican números en C2, represéntelos en MyS de 8 bits.
b) Suponiendo que codifican números en MyS, represéntelos en C2 de 8 bits.
7. Exprese los siguientes números decimales en códigos BCD y EX-3 de 16 bits.
A = 1486 B = 0 C = 349 D = 37
Problemas adicionales:
8. Halle el valor decimal de los siguientes secuencias de 8 bits:
A = 11100111 B = 10111111 C = 00010110 D = 11111111
suponiendo que representan números codificados en binario puro, MyS, C2 o C1.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 1 / pág. 2
9. Considere las siguientes secuencias de 8 bits:
A = 00101101 B = 00011011 C = 11101101 D = 11010000
a) Suponiendo que representan números codificados en C2, realice las operaciones: A–
B, -C–D, -A–B+C indicando si se produce desbordamiento. Calcule también el valor
decimal de los resultados
b) Ídem, suponiendo que representan números codificados en MyS.
10. Calcule el número mínimo de bits necesarios para representar en binario puro, MyS, C2
y C1 cada uno de los números siguientes, así como su representación binaria en dichas
codificaciones:
A = -100 B = +240 C = +15 D = +16 E = -16
11. Usando aritmética en C2, primero, y en MyS, después, realice las siguientes operaciones:
10110111 – 10000111
00001000 + 11100001
Indique para cada caso si se produce desbordamiento.
12. Halle el valor decimal de las siguientes secuencias de 16 bits suponiendo que codifican
números en BCD:
A = 0000 0100 1000 0010 B = 1001 0101 0111 0000
Problemas de examen:
13. (Febrero 2011) Dados los siguientes números A = +35 (en decimal), B = -27 (en
decimal), C = +22 (en octal) y D = +28 (en hexadecimal):
a) Expréselos en representación en complemento a dos con 8 bits.
b) Efectué las operaciones (A-B) y (-C-D) indicando si hay desbordamiento o acarreo y
el por qué.
c) Represente (-B) en complemento a uno y en magnitud y signo ambos con 8 bits.
14. (Septiembre 2012) Dados los números A = (11101010)C2, B = (00111101)C2, C = -(523)8
y D = +(543)8
a) Determinar el valor de los números en decimal.
b) Representar C y D en notación en complemento a 2 de 10 bits.
c) Utilizando únicamente notación en complemento a 2 de 10 bits efectuar las
operaciones (A-B) y (-C+D), indicando si hay desbordamiento o acarreo y el por
qué.
FCproblemas2.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES
TEMA 2
Problemas básicos:
1. Usando los mapas de Karnaugh, obtenga expresiones como mínima SDP de las
funciones:
a) f(a,b,c,d) = m(0,4,6,10,11,13)
b) f(a,b,c,d) = m(3,4,7,11,12,14,15)
c) f(a,b,c,d,e) = m(0,2,3,4,5,12,13,18,19,20,21,25,27, 28,29,31)
2. Empleando los mapas de Karnaugh, encuentre expresiones como suma de minterms de
las funciones:
f1(a,b,c,d) = f(a,b,c,d) · f(a,b,c,d)
f2(a,b,c,d) = f(a,b,c,d) + f(a,b,c,d)
f3(a,b,c,d) = f1(a,b,c,d) · f2(a,b,c,d)
siendo:
3. Se desea diseñar el control de un detector de situaciones de alarma en el hogar. El
sistema tiene como entradas:
FU (se activa cuando el detector de humos reconoce un fuego)
IN (se activa cuando el detector de agua reconoce una inundación)
AT (se activa cuando el detector de intrusos identifica movimiento en la terraza)
AP (se activa cuando el detector de intrusos identifica movimiento en la puerta)
Las salidas que debe proporcionar el sistema son:
PO (llama a la policía)
BO (llama a los bomberos)
El comportamiento de la alarma es:
El sistema debe llamar a la policía cuando se detecta movimiento en la terraza o en
la puerta pero no hay inundación ni fuego (ya que en estos casos los detectores de
movimiento no son fiables)
El sistema debe llamar a los bomberos cuando se detecte inundación o fuego
Describa el sistema mediante expresiones de conmutación simplificadas.
4. Obtenga una SDP simplificada equivalente a cada una de las siguientes expresiones de
conmutación:
a) f a, b a ∙ b a ∙ b a ∙ b
b) f a, b, c a ∙ b b ∙ c a ∙ b b ∙ c
c) f a, b, c a b c ∙ a ∙ b ∙ c
cb a+bd+ab = f
db+ba = f
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 2
d) f a, b, c a b ∙ a c ∙ a ∙ b ∙ c
e) f a, b, c a ∙ c a ∙ b ∙ c b ∙ c
f) f a, b, c, d a ∙ b ∙ c b ∙ c ∙ d b ∙ c c ∙ d
Problemas adicionales:
5. Dadas las funciones de conmutación:
g1(a,b,c,d) = m(0,1,2,4,6,8,10,13,15)
g2(b,c,d) = m(2,4,5,6,7)
g3(a,b,c,d) = m(0,2,3,4,6,10,11,12,14)
g4(a,b,c,d) = m(1,2,4,6,12)
g5(a,b,c,d) = m(2,3,5,6,13)
complete las siguientes cadenas de igualdades:
a) f1(a,b,c,d) = g1· g2 = m(.....)
b) f2(a,b,c,d) = g1 g3 = m(.....)
c) f3(a,b,c,d) = g4 NAND g5 = m(.....)
6. Obtenga la suma de productos canónica equivalente a la expresión de conmutación:
Z(x3, x2, x1, x0) = )xx(x)xx( 10123
7. Obtenga una especificación mediante una EC simplificada de un sistema combinacional
que acepta como entrada dos números binarios de dos bits, X e Y, y da salida uno si y
solo si XY.
8. Obtenga la especificación mediante ECs simplificadas de un conversor de código BCD a
Exceso-3.
9. Especifique mediante ECs simplificadas un sistema combinacional capaz de detectar
números primos. El sistema admite como entrada números enteros en el rango 0 a 31.
10. Un sistema combinacional tiene una entrada, X, que representa un dígito decimal. La
salida, Z, es la entrada dividida entre 2 si X>4. En caso contrario, la salida es el doble de
la entrada. Obtenga una especificación mediante ECs simplificadas del sistema
suponiendo:
a) Que la entrada y la salida se codifican en BCD
b) Ídem en Exceso-3.
11. Una escalera tiene cuatro pisos y un conmutador por piso para controlar la luz. Si todos
los conmutadores están apagados la luz está apagada, pero cualquier cambio en un con-
mutador modifica el estado de la luz. Describa mediante una EC simplificada el sistema
combinacional necesario para controlar la luz.
12. Un estudiante será seleccionado para participar en un programa experimental si
pertenece, al menos, a uno de los grupos siguientes:
Varón, no de 2º ciclo, español
De 2º ciclo, español,
no sabe programar
Varón, de 2º ciclo, español
Mujer, de 2º ciclo, sabe programar
No de 2º ciclo, español, no sabe programar
Mujer, no de 2º ciclo, española
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 3
Se pide:
a) Especifique mediante una función de conmutación un sistema digital tal que
conocidas las características de un estudiante permita determinar
automáticamente si será seleccionado para el programa.
b) Halle un conjunto de requerimientos equivalente, pero más simple, para ser
seleccionado.
13. El ayuntamiento de Madrid quiere eliminar el peligro que suponen las fuentes
ornamentales los días de fuerte viento para el tráfico que circula por los alrededores, para
lo cual ha encargado un sistema digital con dos entradas T y V y una salida F, que
cumpla las siguientes especificaciones:
Sensor de tráfico (T1, T0): codificado según la tabla adjunta
Sensor de viento (V1, V0): codificado según tabla adjunta.
Siempre que la fuerza del viento sea alta se apaga la fuente (F = 0). Siempre que no haya
viento o la fuerza de éste sea pequeña se mantendrá la fuente encendida (F = 1). Sólo en
el caso de viento moderado y densidad de tráfico media o alta se apagará la fuente.
Escribir la tabla de verdad que refleja el funcionamiento del sistema.
T1 T0 Tráfico V1 V0 Fuerza del Viento
0 0 Bajo 0 0 Sin viento
0 1 Medio 0 1 Pequeña
1 0 Alto 1 0 Moderado
1 1 Alta
14. Un sistema para el control de un paso a nivel de la vía férrea Madrid-Segovia tiene tres
salidas: B indica si la barrera del paso a nivel está bajada o subida, y las otras dos indican
si está verde o rojo el semáforo que permite pasar trenes en cada uno de los dos sentidos
(si Pm es 1 pasan trenes desde Madrid y si Ps es 1 pasan trenes desde Segovia). El
sistema debe garantizar que sólo pasa un tren a la vez y nunca está subida la barrera
cuando pasa un tren.
El sistema tiene como entrada dos conjuntos de tres variables: las variables Mt, Mm y Mr
valen 1 cuando viene un talgo procedente de Madrid, viene un mercancías procedente de
Madrid y cuando el tren que viene de Madrid está retrasado respectivamente (sólo vale 1
si viene algún tren y además está retrasado). Las variables St, Sm y Sr tienen el mismo
significado pero para los trenes procedentes de Segovia.
El funcionamiento del sistema cuando más de un tren quiere pasar es el siguiente: si sólo
uno de los trenes lleva retraso pasa ese en primer lugar y espera el otro. En caso
contrario, si sólo uno de los trenes es talgo, el talgo pasa primero; si ninguno es talgo,
pasa primero el que va a Madrid y si ambos son talgo, primero pasa el que viene de
Madrid.
Obtenga una especificación binaria del sistema.
15. Se desea diseñar un sistema que descodifique el rumbo de un barco. El sistema recibe el
rumbo actual por cuatro entradas, N, S, E y W, que se activan cuando el barco lleva el
rumbo correspondiente, de manera que, por ejemplo, la entrada NSEW=1010 se
corresponde con el rumbo noreste (NE). La salida del sistema debe mostrar el rumbo de
la siguiente forma codificado en binario puro:
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 4
0
7 1
6 2
5 3
4
Especifique el sistema mediante una tabla de verdad y obtenga las expresiones de
conmutación simplificadas como suma de productos.
16. Un sistema combinacional para controlar el aparcamiento de una empresa de transportes
tiene 4 entradas y 3 salidas. Las entradas indican las características del vehículo: C
(1=Camión; 0=Furgoneta), F (1=Aislamiento con cámara frigorífica; 0=Aislamiento
convencional), R (1 = Remolque mayor de 5 metros de longitud; 0=Remolque reducido o
no remolque), P (1=mercancías peligrosas; 0=mercancías convencionales). Las salidas
indican la seguridad, lugar de aparcamiento y turno en función de estas características
descritas: Z (1=Zona amplia; 0=Zona convencional), S (1=Seguridad reforzada;
0=Seguridad convencional). T (1=Turno de salida prioritario, 0=Turno de acuerdo al
programa). Las condiciones que debe de cumplir el sistema son las siguientes:
Los vehículos pesados (camiones con o sin remolque y furgonetas con remolque
mayor de 5 metros) se aparcan en zona amplia siempre que no transporten
mercancías peligrosas. El resto en zona convencional.
Para los vehículos que transporten mercancías peligrosas la seguridad se verá
reforzada. También si el vehículo considerado es un camión y lleva un remolque
mayor de 5 metros, además de cámara frigorífica. El resto llevará seguridad
convencional.
Todos los vehículos cuya seguridad esté reforzada, estén aparcados en zona
convencional y tengan cámara frigorífica saldrán de forma prioritaria. El resto de
vehículos saldrá de acuerdo al programa.
Se pide:
a) Obtenga una especificación del sistema en forma de tabla de verdad.
b) Obtenga la implementación como suma de productos mínima.
17. Un sistema combinacional que controla una carrera de regatas tiene 4 entradas y 2
salidas. Las entradas indican las características del barco:
B (1=extranjero; 0=nacional)
E (1=eslora mayor de 8 metros; 0=eslora menor o igual a 8 metros)
M (1=manga mayor de 5 metros; 0=manga menor o igual a 5 metros)
S (1=equipamiento superior; 0=equipamiento convencional)
Las dos salidas indican la categoría en la que participa el barco en función de sus
características:
C (1=clase I; 0=clase II)
I (1=instrucciones de tipo A; 0=instrucciones de tipo B)
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 5
Para organizar a los barcos se usan las siguientes condiciones:
Los barcos de bandera extranjera y eslora mayor de 8 metros navegan en Clase II
junto a los de bandera española. Los demás, en Clase I.
Para los barcos pertenecientes a Clase II el conjunto de instrucciones depende del
tipo de equipamiento: los barcos con equipamiento superior usan el conjunto de
instrucciones A, mientras que los de equipamiento convencional usan el conjunto de
instrucciones B.
Todos los barcos de Clase I usan el conjunto de instrucciones B, salvo que tengan
una manga mayor de 5 metros o equipamiento superior, en cuyo caso usan el
conjunto de instrucciones A.
Se pide:
a) Obtenga una especificación del sistema en forma de tabla de verdad.
b) Obtenga la implementación como suma de productos mínima.
18. Obtener las expresiones de conmutación que especifican un sistema para controlar la
temperatura de una sala de computadores.
El sistema tiene las siguientes entradas:
Temperatura ºC T1 T0 V D Modo M
de 5 a 14º 0 0 Verano 1 Día 1 Ahorro 1
de 15 a 24º 0 1 Invierno 0 Noche 0 Normal 0
de 25 a 34º 1 1
de 35 a 44º 1 0
El sistema tiene dos salidas: Una enciende el aire acondicionado y otra enciende la
calefacción. La salida Enfriar (E) sólo puede valer 1 en verano y la salida Calentar (C)
sólo en invierno.
El funcionamiento del sistema es el siguiente:
Si está en modo ahorro de energía sólo enfría si T * 35º y sólo calienta si es de día y
T < 15º.
Si no está en modo ahorro de energía, el sistema debe garantizar que la temperatura
se mantiene entre 5 y 34º por la noche y entre 15 y 24º por el día.
Problemas de examen:
19. (Febrero 2011) Considere las siguientes expresiones de conmutación:
f x, y, z, w ∑m 0,1,8,10,11
g x, y, z, w yz yz
Obtenga la forma simplificada de f x, y, z, w AND g x, y, z, w .
20. (Junio 2012) Un sistema combinacional recibe como entrada (X) un número del 1 al 6
codificado usando el código Gray de 3 bits. El sistema tiene otra entrada de control
(Inc/Dec) que indica si la salida Z es la entrada + 1 o la entrada – 1, es decir:
11
01
Dec/IncsiX
Dec/IncsiX
Z
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 2 / pág. 6
La salida también está codificada en Gray de 3 bits. Se pide:
a) Obtener la tabla de verdad.
b) Obtener expresiones simplificadas de las salidas.
Nota: La siguiente tabla muestra la codificación Gray de 3 bits:
0 = (000) 1 = (001) 2 = (011) 3 = (010) 4 = (110) 5 = (111) 6 = (101) 7 = (100)
FCproblemas3.pdf
Proble
Prob
1. Im
c
in
d
d
(p
m
e
u
2. A
Prob
3. D
s
4. U
c
e
p
N
5. E
h
n
m
in
d
d
v
D
p
fi
s
Facu
Unive
emas de Fund
P
blemas bá
mplemente
controle el m
ndicando el
de monedas
dos salidas, u
p.ej. cambia
monedas deb
el retardo de
utilizando lo
Analice el s
blemas ad
Demuestre
iguiente exp
Un sistema c
complement
en complem
para codific
NAND de 2
El sistema n
hecho de cé
neurona tien
muestra en
nhibición. U
de sinapsis d
de sinapsis
valor de umb
Determine l
pulsos a trav
figura, para
alida ‘1’ s
ultad de In
ersidad Complu
damentos de C
PROBLEMA
ásicos:
con el me
mecanismo d
l tipo de mo
que se dese
una de error
ar una mon
be entregar
e propagaci
os datos de la
iguiente circ
dicionales
que el blo
presión de c
combinacion
to a 2, en el
mento a 2 de
ar la salida
entradas.
nervioso hu
élulas espec
ne sinapsis
la figura ad
Una neurona
de excitació
de inhibició
bral de la ne
a función b
vés del cana
un valor de
i el númer
a
c
nformática
utense de Mad
Computadores
AS DE FU
enor número
de una máqu
oneda introd
ea obtener: 0
r que se acti
eda de 0.50
la máquina
ión (máxim
a biblioteca
cuito y dé u
s:
oque combi
conmutación
nal tiene po
rango -3 ≤
e forma que
a. Implemen
umano, incl
cializadas ll
(puntos de
djunta) de
a produce un
ón con puls
ón con pul
eurona.
booleana f(a
l de salida (
e umbral 1.
o de sinap
a
b
c
a
c
b
a
drid
(versión 7-10
NDAMENT
TEMA
o de puerta
uina de cam
ducida: 0.20
0.05€, 0.10€
ivará cuand
0€ en mone
a a cambio d
mo) y el reta
a de celdas p
una descripc
inacional cu
n es conjunt
or entrada un
x ≤ 3. La sa
e z( x ) = -2
nte el siste
luyendo el
lamadas ne
interconex
excitación
na salida ‘1
os ‘1’ exce
sos ’1’ por
a,b,c,d,e) d
(axón) en el
Es decir, se
psis de exci
c
b
a
0-14)
TOS DE C
A 3
as NAND u
mbio de mon
0€, 0.50€, 1€
€, 0.20€, 0.5
o la operaci
das de 0.20
de la moned
ardo contam
presentada e
ión de alto n
uyo compo
to universal:
n número bi
alida del sis
2x. Determin
ema usando
cerebro, es
euronas. Ca
xión, como
y sinapsis
’ si el núme
ede el núme
r al menos
de emisión
l modelo de
e produce u
itación a ‘
OMPUTAD
un sistema
nedas. Posee
€, 2€ y otra
50€. A su ve
ión solicitad
0€), y otra q
da introducid
minación (m
n teoría.
nivel de la f
ortamiento
: xxyP
inario de 3 b
stema es tam
ne el númer
el menor
stá
da
se
de
ero
ero
el
de
la
na
1’,
f
Tema
DORES
combinacio
erá dos entra
a para indica
ez, el sistem
da no se pue
que indicará
da. Calcule
mínimo) del
función que
viene dado
x .
bits represe
mbién un nú
ero de bits n
número de
a 3 / pág. 1
onal que
adas, una
ar el tipo
ma tendrá
eda hacer
á cuántas
el coste,
l circuito
realiza:
o por la
ntado en
úmero (z)
necesario
e puertas
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 3 / pág. 2
excede por al menos en uno el número de sinapsis de inhibición a ‘1’. Minimice
f(a,b,c,d,e) y obtenga una implementación usando el menor número de puertas lógicas de
no más de 3 entradas. Calcule el coste, el retardo de propagación (máximo) y el retardo
contaminación (mínimo) del circuito utilizando los datos de la biblioteca de celdas
presentada en teoría.
6. Sea un sistema de seguridad para 2 puertas, tal que para que una de ellas se abra, el
usuario debe haber insertado una tarjeta válida que identifique a la puerta y tecleado un
cierto código de acceso.
El sistema lee la información generada por un lector de tarjetas y por un lector de
teclado. El sistema generará como salida las señales de apertura de cada una de las
puertas y de activación de una alarma. Las salidas del lector de tarjetas son: no se ha
insertado tarjeta, tarjeta válida para puerta 1, tarjeta válida para la puerta 2, tarjeta no
válida. La salida del lector de teclado es el código introducido codificado con 2 bits. Los
códigos autorizados para la puerta 1 son “01” y “10” y los códigos autorizados para la
puerta 2 son “01” y “11”. El código “00” indica que no se ha tecleado nada.
La alarma deberá sonar si la tarjeta insertada no es válida o si la tarjeta insertada es
válida, pero el código tecleado no está autorizado para la correspondiente puerta. Una
puerta se abrirá cuando la tarjeta y el código tecleado asociados a ella sean válidos. En el
resto de casos, las puertas permanecerán cerradas y la alarma sin activar.
Implemente el sistema usando el menor número de puertas AND y NAND de no más de
3 entradas. Calcule el coste, el retardo de propagación (máximo) y el retardo
contaminación (mínimo) del circuito utilizando los datos de la biblioteca de celdas
presentada en teoría.
7. Utilizando el menor número de puertas NAND implemente un sistema combinacional
que tiene dos entradas de 2 bits cada una, X{0,1,2,3} e Y{1,2}, y una salida, Z, que
realiza la función: Z = 2×(X + Y - 1) Y.
8. Se quiere un diseñar un radar. El sistema recibirá como entrada el ángulo que forma el
objeto con la horizontal. Los ángulos se miden en sentido antihorario a partir de las 3
horas con una resolución de 30º. Si un objeto se encuentra en la frontera entre dos
cuadrantes se considera que pertenece al mayor de los dos.
La salida del radar estará compuesta por 3 bits (A,B,C):
A se activa cuando la entrada está en el 1er o en el 3er cuadrante, no se activa en
caso contrario.
B se activa cuando la entrada está entre 0 y 29º o entre 60º y 119º o entre 210º y
299º, no se activa en caso contrario.
C se activa cuando sólo se activa una de las salidas anteriores y sólo una.
Se pide:
a) Obtener la tabla de verdad de A, B, C.
b) Sintetizar la expresión de conmutación de cada una de las salidas del sistema
requerido, mediante una red NAND de 2 niveles con el menor número de puertas.
c) Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en
teoría.
9. Utilizando el mínimo número posible de puertas NAND de 2 entradas, implemente las
siguientes funciones de conmutación:
f(a,b,c,d)=Σm(0,1,6,7,9,13)
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 3 / pág. 3
g(a,b,c,d)=Σm(0,3,5,6,8,11,13,14)
h(a,b,c,d)=Σm(4,5,6,7,9,11,12,14)
10. Se desea implementar el mecanismo de control y aviso de una presa. El sistema tiene una
entrada, L, que indica la cantidad de lluvia que está cayendo (ver tabla) y dos entradas
provenientes de sensores: uno ubicado a mitad de la presa, M, que devolverá ‘1’ cuando
la presa esté completa al 50% o más y ‘0’ en caso contrario; y otro R, que devolverá ‘1’
cuando el 90% de la presa o más esté completa. Se desea implementar un sistema de
alarma con una salida A codificada (según tabla) que se comporte de la siguiente manera:
Siempre que el nivel de la presa esté por debajo de la mitad y la lluvia no sea fuerte
estaremos en alerta amarilla, y en caso de lluvia fuerte estaremos en el alerta naranja.
Siempre que el nivel este por encima del 50% pero por debajo del 90% esteremos en
alerta naranja si y sólo si la lluvia es moderada o fuerte, en cualquier otro caso
estaremos en alerta amarilla.
Siempre que el nivel esté por encima del 90% y haya lluvia estaremos en el alerta
roja, si no, estaremos en alerta naranja.
Además el sistema tiene un tiene una salida C que será igual a ‘1’ cuando las compuertas
de la presa estén abiertas, estas compuertas se abrirán siempre que estemos en las
condiciones de la entrada que generan alerta roja, se abrirán también siempre que
estemos por encima del 50%, con condiciones de alerta naranja y haya lluvia. Además en
caso de que los sensores de nivel de la presa den señales
inconsistentes se abrirán las
compuertas y se fijará el nivel de alerta a amarillo.
Se pide:
a) Escribir la tabla de verdad que describe el sistema.
b) Implementar la salida C utilizando el menor número de puertas lógicas de 2
entradas.
c) Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en
teoría.
Entrada L1L0 Salida A1A0
No llueve 00 Amarilla 01
Débil 01 Naranja 10
Moderado 10 Roja 11
Fuerte 11
11. En un restaurante de la compañía FAST-FOOD se elaboran distintos platos de comida a
partir de los componentes: ensalada de lechuga (E), patatas fritas (F), pescado (P) y carne
(C). Estos componentes pesan 100, 150, 250 y 200 gramos, respectivamente. Las
comidas se transportan por medio de una banda hasta una báscula. Si el peso indicado en
la báscula es más de 350 gramos, entonces el cliente deberá pagar 3 euros de suplemento.
No es posible que lleguen a la báscula ni platos vacíos, ni platos que sólo contengan
ensalada y patatas, ni platos que contengan pescado y carne. Todas las demás
combinaciones sí pueden llegar hasta la báscula.
El sistema tiene 2 salidas: Suplemento (S), que vale 1 cuando debe pagar suplemento, y
Báscula (B), que indica el peso del plato medido por la báscula medido en múltiplos de
50 gramos. Por ejemplo, si un plato pesa 300gr la salida Báscula vale 6. Se pide:
a) Obtenga la tabla de verdad de la salida S, que calcula el suplemento y de la salida
B, que indica el peso.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 3 / pág. 4
b) Realice el circuito usando el menor número de inversores y puertas NAND.
c) Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en
teoría.
12. Se desea diseñar un sistema combinacional para controlar el motor de un reproductor de
cintas de audio. El circuito dispone de 5 entradas y 3 salidas.
Las señales de entrada son las siguientes:
PL, vale ‘1’ cuando se pulsa el botón de reproducción.
RE, vale ‘1’ cuando se pulsa el botón de rebobinado.
FF, vale ‘1’ cuando se pulsa el botón de avance rápido.
ST, vale ‘1’ cuando se pulsa el botón de parada.
M es una señal que proviene de un sensor especial de música que detecta música en
la actual posición de la cinta.
Las salidas son:
P, si vale ‘1’ la cinta avanza
R, si vale ‘1’ se rebobina
F, si vale ‘1’ se avanza rápido.
Sólo puede haber una salida activa y cuando las 3 valen ‘0’, el motor está parado.
Especificaciones de diseño:
Si se pulsa el botón de reproducción, el reproductor reproduce la cinta.
Si estando pulsado el botón de reproducción se pulsa el de rebobinado, el
reproductor de cintas rebobinará si estamos en medio de una canción. Si no,
reproducirá la cinta
Si estando pulsado el botón de reproducción se pulsa el de avance rápido, el
reproductor de cintas avanzará rápido si estamos en medio de una canción. Si no,
reproducirá la cinta
Si se presiona el botón de avance rápido o el de rebobinado estando el botón de
reproducción sin apretar, el reproductor rebobinara o avanzara rápido.
Si se pulsa el botón de parada, se detiene el reproductor de cintas
Se pide:
a) Obtener una implementación simplificada con puertas NOT, AND, OR de 2
entradas.
b) Ídem con puertas NAND y AND de 2 entradas.
c) Calcule en ambos casos el coste, el retardo de propagación (máximo) y el retardo
contaminación (mínimo) del circuito utilizando los datos de la biblioteca de
celdas presentada en teoría.
13. Un operador de avionetas para rutas turísticas desea instalar un climatizador inteligente,
para lo cual añade a los aeroplanos un sistema de calefacción (C) y un sistema de
refrigeración (R) y los siguientes sensores: un sensor de temperatura (T) con la
codificación que muestra la tabla, un altímetro que indica si la altura es superior a 350
metros (A = ‘1’) y un interruptor que enciende la calefacción (I = ’1’). El operador
encarga al fabricante las siguientes especificaciones:
La calefacción se encenderá automáticamente cuando haya temperaturas inferiores a
15º y el altímetro sea superior a 350 metros.
La refrigeración se encenderá automáticamente cuando haya temperaturas superiores
a 25º si el avión vuela con una altura inferior a 350 metros.
El interruptor de calefacción deshabilita la refrigeración (en su caso) y enciende la
calefacción si la temperatura es inferior a 25º.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 3 / pág. 5
Temperatura Menos de 5º De 5º a 15º De 16º a 25º Más de 25º
T “00” “01” “10” “11”
a) Halle la tabla de verdad que describe el funcionamiento del circuito.
b) Implemente el sistema utilizando el menor número posible de puertas lógicas.
c) Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en
teoría.
14. Sea un sistema que controla el riego automático de un parque. El sistema tiene como
entradas las señales E y D que provienen de un reloj-calendario y la señal L que viene de
un sensor de lluvia, tales que:
E D L
verano 1 mañana 0 llueve 1
no verano 0 mediodía 1 no llueve 0
tarde 2
noche 3
El sistema tiene una única salida, Z, que vale ‘1’ cuando el riego debe activarse y ‘0’
cuando debe desactivarse. Dicha salida viene determinada de la siguiente manera:
Si es invierno y mediodía, el riego se activa
Si es verano, el riego se activa por la mañana, mediodía y noche
Si llueve, el riego se desactiva
Implemente el sistema utilizando el menor número de puertas lógicas de no más de 3
entradas. Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en teoría.
15. Un sistema combinacional que controla una carrera de regatas tiene 4 entradas y 2
salidas. Las entradas indican las características del barco:
B (‘1’=extranjero; ‘0’=nacional)
E (‘1’=eslora mayor de 8 metros; ‘0’=eslora menor o igual a 8 metros)
M (‘1’=manga mayor de 5 metros; ‘0’=manga menor o igual a 5 metros)
S (‘1’=equipamiento superior; ‘0’=equipamiento convencional)
Las dos salidas indican la categoría en la que participa el barco en función de sus
características:
C (‘1’=clase I; ‘0’=clase II)
I (‘1’=instrucciones de tipo A; ‘0’=instrucciones de tipo B)
Para organizar a los barcos se usan las siguientes condiciones:
Los barcos de bandera extranjera y eslora mayor de 8 metros navegan en Clase II
junto a los de bandera española. Los demás, en Clase I.
Para los barcos pertenecientes a Clase II el conjunto de instrucciones depende del
tipo de equipamiento: los barcos con equipamiento superior usan el conjunto de
instrucciones A, mientras que los de equipamiento convencional usan el conjunto de
instrucciones B.
Todos los barcos de Clase I usan el conjunto de instrucciones B, salvo que tengan
una manga mayor de 5 metros o equipamiento superior, en cuyo caso usan el
conjunto de instrucciones A.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 3 / pág. 6
Se pide:
a) Obtenga una especificación del sistema en forma de tabla de verdad.
b) Obtenga la implementación con puertas de su suma de productos mínima.
c) Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) del circuito utilizando los datos de la biblioteca de celdas presentada en
teoría.
16. Obtenga un circuito con el menor número de puertas lógicas equivalente al circuito
mostrado en la figura, siendo M un bloque combinacional cuya salida vale 1 cuando en
sus entradas hay más unos que ceros (función mayoría).
Problemas de examen:
17. (Febrero 2013) Se desea realizar un circuito combinacional que permita clasificar, según
su forma, las piezas que se sitúan en un receptáculo.
Para ello, las entradas del sistema están conectadas a una matriz de 4 células
fotoeléctricas dispuestas como se muestra en la figura.
Cuando no hay pieza en el receptáculo, todas las células generan valor ‘0’.
Cuando la hay, unas células generan valor ‘0’ y otras ‘1’ según la forma de la pieza
(véanse algunos ejemplos en la figura).
El sistema generará un vector de 2 bits indicando si la pieza es cuadrada (00), triangular
(01), en forma de L (10) o defectuosa (11), es decir, no es una de las anteriores.
Considérese que todas las piezas encajan en el receptáculo pero que podrán estar rotadas
90º, 180 ó 270º.
Se pide:
a) Indicar la tabla de verdad del sistema.
b) Diseñarlo utilizando el menor número de puertas NAND e inversores.
18. (Febrero 2014) Se desea implementar un sistema combinacional que regule el tiempo que
debe estar en funcionamiento una secadora industrial. La secadora funcionará durante
más o menos tiempo de acuerdo con la cantidad de ropa introducida y el nivel de
humedad que tenga.
A = 0
D = 0
C = 0
B = 0
A B
C D
A = 1
D = 0
C = 1
B = 1
A B
C D
A = 0
D = 1
C = 1
B = 0
A B
C D
A = 1
D = 1
C = 1
B = 1
A B
C D
clasificador F
A
D
C
B 2
A B
C D
M M
M M
A
B
1
A
D
C
D
C
F
Proble
E
d
b
S
E
s
S
emas de Fund
El sistema re
de volumen:
baja (0), med
Si, por ejemp
El sistema, d
ecado codif
Menor o
Mayor d
Mayor o
Se pide:
a) Indic
b) Diseñ
damentos de C
ecibe estos
poca ropa
dia (1), alta
tiempo( vo
plo, hay poc
tiem
de acuerdo
ficado en bin
o igual que 3
de 30’ y men
o igual a 60’
car la tabla d
ñarlo utiliza
Computadores
datos codifi
(0), cantida
(2). El tiem
olumen, hum
ca ropa y su
mpo( 0, 2 ) =
con el tiem
nario que de
30’, program
nor que 60’
’, programa
de verdad de
ando el men
(versión 7-10
ficados en b
ad media (1)
mpo de secad
medad ) = 30
u humedad e
30’ + (0+2)
mpo calculad
ebe realizar
ma corto (0)
, programa
a largo (2).
el sistema.
nor número d
0-14)
binario por 2
), mucha rop
do se calcula
0’ + (volume
es alta, el tie
)×10’ = 30’
do, indicará
la secadora
);
normal (1)
de puertas N
2 entradas q
pa (2); y el
a con la sigu
en+humedad
mpo de seca
+ 20’ = 50’
por una sa
. Si el tiemp
NAND e inv
Tema
que indican
tramo de h
uiente funció
d)×10’
ado será:
’
alida el prog
po es:
versores.
a 3 / pág. 7
el tramo
humedad:
ón:
grama de
FCproblemas4.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 4 / pág. 1
FUNDAMENTOS DE COMPUTADORES
TEMA 4
Problemas básicos:
1. Los computadores disponen de un circuito
combinacional capaz de realizar las ope-
raciones más elementales AND, OR, Suma
Aritmética, etc. sobre dos configuraciones
binarias de n bits. Dicho circuito se denomi-
na Unidad Aritmético Lógica (UAL).
Diseñe una UAL como la mostrada en la
figura, capaz de realizar las siguientes
funciones: A AND B, A OR B, C1 B, A+B
(suma aritmética), desplazamiento de B un
bit a la derecha, desplazamiento de B un bit
a la izquierda.
El diseño se realizará para n=4 bits. La función que en cada caso realiza la UAL se selec-
ciona mediante las entradas de control s2, s1, s0.
2. Diseñe un multiplexor de 8 a 1 usando:
a) 4 multiplexores de 2 a 1 y el mínimo número de puertas.
b) 1 decodificador 3 a 8 y el menor número de puertas.
3. Considere la implementación en una ROM de un sumador de números naturales
codificados en binario puro con 3 bits que codifica el resultado en BCD. Discuta
razonadamente el tamaño mínimo de la ROM e indique el contenido de la ROM en las
direcciones (3E)16 y (1D)16.
4. Usando un sumador y puertas lógicas diseñe un conversor de MyS a C2 de 8 bits. Ídem
para un conversor de C2 a MyS que tenga una salida adicional de overflow. Generalice el
diseño para que el tipo de conversión sea seleccionable por una entrada de control.
Problemas adicionales:
5. Para la construcción de un teclado de 24 teclas (T0, T1, ... T23) se dispone de
codificadores de prioridad de 8 entradas. Diseñe el circuito de codificación del teclado
usando dichos codificadores más las puertas lógicas que se consideren necesarias,
teniendo en cuenta que el circuito funcionará de la siguiente forma:
Si sólo se pulsa la tecla Ti, entonces la salida tomará el valor i.
Si se pulsan simultáneamente varias teclas, entonces la salida tomará el valor
correspondiente al mayor subíndice de las teclas pulsadas.
6. Implemente un sistema que tiene 6 entradas de datos (x5…x0), 2 entradas de control
(s1,s0), 4 salidas de datos (z3...z0) y cuyo comportamiento viene descrito de la forma
siguiente:
(z3…z0) = (x5…x2) si (s1,s0) = (01)
= (x3…x0) si (s1,s0) = (10)
= (x4…x1) si (s1,s0) = (11)
= (0000) si (s1,s0) = (00)
n bits n bits
n bits
carry
UAL
s2
s1
s0
A B
F(A,B)
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 4 / pág. 2
7. Diseñe un conversor de código BCD a código Exceso-3 usando:
a) Un codificador y un descodificador.
b) Un descodificador y puertas OR.
c) Multiplexores de 16 a 1.
d) Multiplexores de 4 a 1 y puertas lógicas.
e) Una ROM de tamaño mínimo.
8. Un sistema combinacional tiene una entrada X de 4 bits y una salida Z de 4 bits. Los
datos, tanto a la entrada como a la salida, son números enteros codificados en C2. El
sistema tiene otra entrada de control C que determina la función del sistema de acuerdo
con la siguiente tabla:
C Z
0 X+1
1 X+2
2 X-1
3 X-2
Diseñe el circuito que tenga la estructura mostrada en la figura y use únicamente un
sumador binario de 4 bits, multiplexores e inversores. Se valorará que el número y
tamaño de los multiplexores sea el menor posible.
9. Se desea implementar un conversor de números de 8 bits en binario puro a números en
BCD mediante una memoria ROM:
a) Determine el tamaño mínimo necesario de la memoria, y el esquema de
implementación. Indicando claramente el significado de las líneas de
direcciones y salida de la ROM.
b) Obtenga el contenido de la ROM en las direcciones (41)10 y (2F)16
10. Dado el circuito de la figura, obtenga la especificación de Z en función de X. Justifique
la respuesta.
11. Calcule el número de puertas AND, OR y NOT necesarias para diseñar
implementaciones directas de un:
a) Decodificador 3 a 8.
b) Multiplexor 8 a 1.
c) Codificador de prioridad 16 a 4.
12. Calcule el número de:
a) Multiplexores 4 a 1 necesarios para implementar en árbol uno de 256 a 1.
b) Multiplexores 2 a 1 necesarios para implementar en árbol uno de 16 a 1.
0
1
2
E
0
1x0
x
1
x
2
2
3
4
5
7
6
1
0
1
2
E
z
0
z
1
z
2
0
1
2
3
4
5
7
6
1
0
1
2
E
0
1x0
x
0
x
1
x
1
x
2
x
2
2
3
4
5
7
6
1
0
1
2
E
z
0
z
0
z
1
z
1
z
2
z
2
0
1
2
3
4
5
7
6
0
1
2
3
4
5
7
6
1
Z
+
X
C
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 4 / pág. 3
c) Multiplexores 2 a 1 necesarios para implementar uno vectorial de 4 a 1 de 8b.
d) Decodificadores 1 a 2 necesarios para implementar en árbol uno de 4 a 16.
e) Decodificadores 2 a 4 necesarios para implementar en árbol uno de 8 a 256.
13. Diseñe una ROM de 210×16 bits (2 KiB) usando un decodificador 2 a 4 y el número de
módulos ROM de 28×8 bits (256 B) que estime necesarios.
14. Diseñe 3 módulos combinacionales que calculen el máximo de 2 números de 8 bits
considerando, en cada caso, que ambos números están codificados:
a) En binario puro.
b) En MyS.
c) En C2.
En todos ellos se utilizará un multiplexor vectorial 2 a 1, un restador binario y el menor
número posible de puertas lógicas.
15. Diseñe un multiplicador combinacional de números binarios sin signo de 4 bits. El
multiplicador tiene 2 entradas de 4 bits para los operandos y una salida de 8 bits para el
resultado. Use únicamente puertas AND de
2 entradas para calcular los productos
parciales y sumadores completos de 4 bits para sumar en cascada dichos productos.
16. Diseñe un conversor de códigos BCD y EX3 usando un sumador/restador de 4 bits, un
multiplexor 2 a 1 y las puertas que estime necesarias. El conversor tendrá una entrada de
datos de 4 bits, una señal de control para seleccionar si el dato a la entrada debe
convertirse de BCD a EX3 o de EX3 a BCD, una salida de datos de 4 bits y una salida de
error para indicar si el código que hay a la entrada no puede convertirse por ser inválido.
Es decir, esta salida de error deberá activarse cuando habiendo seleccionado una
conversión BCD a EX3, en la entrada de datos haya, por ejemplo, 1011 (dado que no es
un código BCD válido), sin embargo no deberá hacerlo si la conversión EX3 a BCD ha
sido seleccionada (dado que representa a un 8 en EX3).
17. Diseñe un módulo combinacional que ordene 3 números enteros codificados en binario
puro con 8 bits. El modulo tendrá 3 entradas de 8 bits para los operandos y 3 salidas de 8
bits para los resultados (por una de ellas siempre saldrá el mayor de los tres operandos,
por otra siempre el intermedio y por la última siempre el menor). Utilice el menor
número posible de comparadores de magnitud, multiplexores vectoriales 2 a 1 de 8 bits y
puertas lógicas.
18. Calcule el coste, el retardo de propagación (máximo) y el retardo contaminación
(mínimo) de un sumador binario de 4 bits utilizando los datos de la biblioteca de celdas
presentada en teoría. Ídem para un sumador de 8 bits. Obtenga expresiones genéricas de
coste y retardo para un sumador de n bits.
FCproblemas5.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES
TEMA 5
Problemas básicos:
1. Especifique como máquina de Moore un sistema secuencial cuya salida z se comporta,
en función del valor su entrada x, de la forma siguiente:
Si x = ‘1’, entonces z sigue cíclicamente la siguiente secuencia de 4 valores: 0, 3, 7,
7. La salida pasa de un valor de la secuencia al siguiente cada vez que el sistema
recibe un pulso de reloj.
Si x = ‘0’, entonces la llegada de un pulso de reloj no altera el valor de la salida. Por
tanto, z(t+1) = z(t).
Obtenga una descripción binaria del sistema codificando las salidas en binario puro y
exprese las funciones de transición de estados y salida en forma de sumas de productos
mínimas.
2. Sea un sistema secuencial con una entrada binaria x, una salida binaria z y el siguiente
comportamiento temporal:
1 3… "0111"
0
Especifique el sistema como máquina de Mealy, y exprese las funciones de transición de
estados y salida en forma de sumas de productos mínimas.
3. Considere el diagrama de estados del sistema secuencial especificado como máquina de
Mealy mostrado en la figura. Se pide:
a) Obtener el diagrama de estados equivalente como máquina de Moore.
b) Completar el cronograma.
4. Sea un sistema secuencial con una entrada x{a,b}, una salida z{s,n} y el siguiente
comportamiento temporal:
3… 1 " " " "
S0
S1
S2
b/n
a/n
a/n
b/n
a/mb/ninicial
entrada
clk
estado
a
S0
salida
s
n
b
estado S0
salida
s
n
m
á
q
u
in
a
d
e
M
o
o
re
m
á
q
u
in
a
d
e
M
ea
ly
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 2
Se pide:
a) Completar el cronograma
b) Expresar las funciones de transición de estados y salida en forma de sumas de
productos mínimas.
Problemas adicionales:
5. Un contador reversible módulo p, es un sistema secuencial capaz de contar en sentido
ascendente o descendente, en función del valor de una entrada de control que
denominamos "Sentido". Especifique un contador reversible módulo 6 tal que:
Si Sentido = ‘0’, entonces cuente en sentido ascendente.
Si Sentido = ‘1’, entonces cuente en sentido descendente.
Exprese las funciones de transición de estados y salida en forma de sumas de productos
mínimas.
6. Obtenga el diagrama de estados como máquina de Mealy de un sistema secuencial con
una entrada x{a,b} y una salida z{m,n}, tal que z(t)=m, si y solo si la secuencia
formada por x(t-2), x(t-1), x(t) comienza o termina con "aa".
7. Un sistema secuencial posee una entrada x{0,1,2} y una salida z{0,1}. La salida toma
el valor ‘1’ si y sólo si la secuencia de entradas contiene un número impar de ceros y un
número par de unos. Se pide:
a) Especificar el sistema como una máquina de Mealy usando un diagrama de
estados.
b) Realizar una implementación del sistema con un registro de estado y una ROM.
8. Especifique como máquina de Mealy un sistema secuencial con una entrada x{a,b,c} y
una salida z{0,1}, de forma que la salida toma el valor ‘1’ si por la entrada se reciben
secuencialmente un número impar de ‘a’, una ‘c’ y un número par de ‘b’. La salida toma
valor ‘0’ en cualquier otro caso. Por ejemplo, para la secuencia de entrada
“aaacbbbbaccbb...”, la salida toma los valores “0000010100000...”.
9. Especifique como máquina de Mealy un sistema secuencial con una entrada binaria x y
una salida binaria z. Inicialmente la salida vale ‘0’ y pasa a valer ‘1’ cuando el sistema
detecta el tercer ‘0’ consecutivo en la entrada. Desde ese momento, la salida sigue
valiendo ‘1’ hasta que se reciben por la entrada dos ‘1’ consecutivos. Una vez recibido el
par de ‘1’ el sistema vuelve a su estado inicial.
x
clk
estado
a
S0
z
s
n
b
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 3
10. Especifique como máquina de Mealy un sistema secuencial con una entrada binaria y
una salida binaria, tal que la salida vale ‘1’ siempre que, tomando las entradas en bloques
de 3 bits consecutivos, el sistema detecta el patrón “111” en uno de dichos bloques. Por
ejemplo:
x(t) = 011 111 101 110 111 111 011
z(t) = 000 001 000 000 001 001 000
11. El funcionamiento de un semáforo está regulado por un sistema secuencial cuyas
entradas y salidas se muestran en la figura y tiene el comportamiento siguiente:
Inicialmente el sistema se encuentra en el estado S0 y continúa en él mientras que no
se detecte la presencia de un peatón dispuesto a cruzar la calle, es decir, mientras
peatón valga ‘0’. La salida del sistema en el estado S0 es “100” (en correspondencia
a las señales Verde, Ámbar y Rojo). Cuando la señal peatón vale ‘1’ el sistema pasa
al estado S1.
En el estado S1 la salida es “010”. Del estado S1 el sistema pasa al estado S3 si la
señal de parpadeo vale ‘1’, en caso contrario el sistema pasa al estado S2.
En el estado S3 la salida es “000”, e independientemente de los valores de las
señales de entrada el sistema vuelve al estado S1.
En S2 la salida del sistema es “001”. El sistema permanece en el estado S2 mientras
que la señal peatón valga ‘1’. En caso contrario vuelve al estado inicial S0.
Considerando la especificación anterior:
a) Especifique el sistema anterior mediante su diagrama de estados.
b) Obtenga expresiones de conmutación mínimas para las funciones de transición
de estados y de salida.
12. Mi perro puede estar contento (C), tranquilo (T), nervioso (N) o asustado (A). Si está
contento y le doy un hueso lo agradece moviendo el rabo (r). Cuando está tranquilo si le
doy un hueso (h) se pone contento y lo indica moviendo el rabo; sin embargo si está
nervioso o asustado se tranquiliza y ladra (l). Si le tocan (t) estando tranquilo o contento
se pone nervioso y ladra, estando nervioso se asusta y ladra, pero si está asustado muerde
(m). Modele el comportamiento del animal como una máquina de Mealy.
13. Realice el diagrama de estados como máquina de Moore del sistema de apertura de una
puerta de garaje controlada por un mando a distancia.
El sistema tiene 3 entradas binarias, M, S1 y S2. M vale ‘1’ cuando recibe la orden del
mando, y ‘0’ en caso contrario. Las entradas
S1 y S2 valen ‘1’ cuando la puerta está,
respectivamente, completamente cerrada o completamente abierta y valen ‘0’ durante las
operaciones de apertura o cierre.
Controlador
de un semáforo
Peatón
Parpadeo
Verde
Ámbar
Rojo
r
h
l
h/t
PERRO
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 4
El sistema tiene 2 salidas, F1 y F2. Si F1 vale ‘1’ el motor se pone en marcha, mientras
que si vale ‘0’ se detiene. Si el motor está en marcha, lo hace en sentido apertura cuando
F2 vale ‘1’ y en sentido contrario cuando F2 vale ‘0’.
El sistema de apertura tiene el siguiente comportamiento:
Cuando la puerta está cerrada y recibe una orden del mando, el motor se pone en
marcha abriendo la puerta hasta que la entrada S2 indique que está totalmente
abierta.
Cuando la puerta está abierta y recibe una orden del mando, el motor se pone en
marcha cerrando la puerta hasta que la entrada S1 indique que está totalmente
abierta.
Si durante la apertura o cierre de la puerta, y antes de que se haya completado la
operación, se recibe una nueva orden del mando, ésta será ignorada.
14. En una estación de tren se va a instalar una máquina automática de venta de billetes con
el siguiente modo de funcionamiento:
Sólo existen dos tipos de billetes: sencillo e ida-y-vuelta, cuyos precios son
respectivamente 1 y 2 euros. El usuario pulsa el botón correspondiente al tipo de
billete que desea y, a continuación, aparece en un display la cantidad de monedas de
1 euro necesarias para su adquisición.
Esta cantidad va disminuyendo a medida que el usuario introduce monedas de 1
euro. Cuando se completa el importe, la máquina emite el billete correspondiente.
Una vez elegido el tipo de billete no se puede cambiar a otro. Si se introduce una
moneda antes de seleccionar el tipo de billete, la máquina devuelve la moneda.
El sistema que implementa este dispositivo tiene 1 entrada y 4 salidas.
La entrada, X, vale
“00” cuando no hay ningún botón pulsado ni se introduce moneda
“01” cuando se introduce una moneda de 1 euro
“10” cuando se pulsa el botón de billete sencillo
“11” cuando se pulsa el botón de billete de ida-y-vuelta.
Las salidas son las siguientes:
IS – Imprime billete sencillo
IV – Imprime billete ida-y-vuelta
DM – Devuelve moneda de 1 euro
P – Cantidad pendiente (codificada en binario)
Se pide:
a) Especificar el sistema como una máquina de Mealy.
b) Especificar el sistema como una máquina de Moore.
15. Especifique un sistema secuencial que controle los intermitentes de un coche. El vehículo
dispone de dos bombillas, una izquierda (BI) y otra derecha (BD), que lucen de forma
intermitente cuando se activan. El sistema se controla a partir de una palanca con tres
posiciones, izquierda (I), derecha (D) y centro (C) y la llave de encendido (LL). El
intermitente de cada lado debe activarse cuando el usuario indique dicha dirección con la
palanca, siempre y cuando se haya accionado la llave de encendido del vehículo.
Además, el sistema incorporará un botón de emergencia (E), que hará que las luces de los
lados izquierdo y derecho parpadeen de forma simultánea mientras esté pulsado. El
sistema de emergencia funcionará incluso si se retira la llave de encendido.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 5
16. Obtener el diagrama de estados como máquina de Moore de un sistema secuencial que
controla el funcionamiento de un coche teledirigido.
El sistema tiene 2 entradas de 1 bit: izquierdo (I) y derecho (D) que valen ‘1’ cuando se
presionan los correspondientes pulsadores del mando a distancia. El sistema tiene una
salida, Z, de 2 bits para indicar al coche el tipo de movimiento que debe hacer:
“00” parar
“01” girar a la derecha
“10” girar a la izquierda
“11” avanzar recto.
Si el coche está parado y se pulsa cualquier botón empieza a moverse: si se presiona I, va
hacia la izquierda; si se presiona D, va a la derecha y si se presionan ambos pulsadores a
la vez, avanza recto.
Si el coche va en una dirección no cambia su movimiento cuando se presiona el pulsador
correspondiente a esa dirección o no se presiona ningún pulsador. En cambio, cambia el
movimiento en los siguientes casos:
Si el coche va hacia la derecha y se pulsa I, el coche avanzará recto.
Si el coche va hacia la izquierda y se pulsa D, el coche avanzará recto.
Si el coche avanza recto y se pulsan I o D el coche girará hacia la izquierda o
derecha respectivamente.
El coche se parará independientemente de la dirección que llevara si apretamos I y D
simultáneamente.
Problemas de examen:
17. (Febrero 2012) El diagrama de estados de la figura representa un reconocedor de patrón.
a) ¿Qué tipo de sistema secuencial es: Mealy o Moore?
b) ¿Qué patrón reconoce?
c) Complete el cronograma.
18. (Junio 2012) Sea el siguiente sistema secuencial:
contrariocasoen
abbóbba=t1,t2,tx
)t(z
0
1
a) Dibuje su diagrama de estados.
S0 S1
S2S3
a/0
b/0
b/0
a/0
b/0
a/1
a/0
b/0
inicial
entrada
clk
estado
b
a
S0
salida
1
0
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 5 / pág. 6
b) Complete el siguiente cronograma:
19. (Septiembre 2012) Sea el siguiente sistema secuencial:
contrariocasoen
bbbóaaa=ttx
tz
0
t1,2,1
)(
a) Dibuje su diagrama de estados como máquina Mealy.
b) Complete el siguiente cronograma:
x
clk
estado
a
S0
z
1
0
b
x
clk
estado
a
S0
z
1
0
b
FCproblemas6.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES
TEMA 6
Problemas básicos:
1. Los dispositivos USB transmiten los datos en serie utilizando un formato denominado
non-return-to-zero inverted (NRZI). Se desea diseñar un circuito secuencial con una
entrada, x, y una salida, z, ambas de 1 bit, que convierta una secuencia binaria en una
secuencia equivalente en formato NRZI. Lo hará de la siguiente manera:
Si x vale ‘1’, la salida conservará su valor anterior.
Si x vale ‘0’, la salida cambiará de polaridad, es decir, si valía ‘1’ pasará a ‘0’ y si
valía ‘0’ pasará a ‘1’.
Por ejemplo, asumiendo que el valor inicial de la salida es ‘1’, la secuencia de entrada
“10001110011010...” deberá transformarse en la secuencia “10100001000110...”
Se pide:
a) Especificar el sistema como máquina de Mealy.
b) Implementar el conversor usando biestables D y puertas lógicas.
c) Encontrar una implementación equivalente como máquina de Moore.
2. Un sistema secuencial síncrono tiene una entrada, x, y una salida, z, ambas de 1 bit.
Inicialmente la salida vale ‘0’ y no pasa a valer ‘1’ hasta que no recibe tres ‘0’
consecutivos. Desde ese momento, la salida vale 1 durante dos ciclos de reloj con
independencia del valor que tome la entrada. Después vuelve al estado inicial.
Implemente el sistema como máquina de Moore usando el menor número de puertas y
biestables D. Calcule el coste y la frecuencia de reloj máxima a la que podría funcionar el
circuito utilizando los datos de la biblioteca de celdas presentada en teoría.
3. Implemente un sistema secuencial que realice el complemento a 2 de números de
longitud variable recibidos en serie y en orden creciente de pesos (primero el bit menos
significativo). El sistema tiene una entrada de datos, x, una salida de datos, z, y una
entrada de control, inicio, que se pone a 1 para indicar el comienzo y el final del número
a complementar. El comportamiento esperado es el siguiente:
t 0 1 2 3 4 5 6 7 8 9 10 11 12
inicio(t) 1 1 0 0 0 0 0 1 0 0 0 0 1
x(t) - - 0 0 1 0 1 - 0 1 1 1 -
z(t) 0 0 0 0 1 1 0 0 0 1 0 0 0
4. Usando el menor número de puertas lógicas y series de biestables D encadenados, diseñe
como máquina de Mealy un reconocedor de secuencias que responda a las
siguientes
especificaciones:
Tiene una entrada, x de 3 bits, por la que en cada ciclo de reloj llega un dígito
decimal del conjunto {0,1,...,7} codificado en binario.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 2
La salida binaria, z de 1 bit, toma el valor ‘1’ si y solo si los últimos 4 dígitos
recibidos forman la secuencia (0,3,4,7).
Problemas adicionales:
5. Un circuito secuencial con dos biestables D, dos entradas, x e y, y una salida, z, está
definido por las siguientes ecuaciones lógicas:
⋅ ⋅
̅ ⋅ ⋅
̅ ⋅
Se pide:
a. Dibuje el circuito.
b. Obtenga la tabla de transición de estados.
c. Dibuje el diagrama de estados que lo define.
d. Convierta el diagrama Mealy a un diagrama Moore equivalente. Obtenga la tabla
de transición de estados y el circuito resultante.
6. Diseñe un circuito secuencial síncrono que genere la secuencia “00000001” cada vez que
su entrada, x, valga ‘1’. Una vez que la secuencia comienza, debe completarse con
independencia del valor que tome la entrada. Si la entrada vale 0, la salida debe
mantenerse constantemente a ‘1’.
Se pide:
a. Especificar el sistema como máquina de Moore.
b. Diseñe el circuito utilizando biestables D y puertas lógicas. No olvide distribuir
adecuadamente la señal de reset para que el circuito se inicialice al estado inicial
(en donde lee el valor de la entrada para determinar si debe comenzar a generar la
secuencia o debe mantener a ‘1’ la salida).
7. Usando el menor número de puertas lógicas y series de biestables D encadenados, diseñe
un circuito con una entrada de 4 bits, x, por la que en cada ciclo de reloj recibe un dígito
BCD y una salida, z, que puede tomar, codificados en binario, los siguientes valores:
0 si {x(t-2), x(t-1), x(t)} forman un número múltiplo de 5.
1 si {x(t-2), x(t-1), x(t)} forman un número mayor o igual que 400.
2 si se cumplen las dos anteriores condiciones a la vez.
3 en cualquier otro caso.
Para el diseño se utilizarán biestables y puertas lógicas. Calcule el coste y la frecuencia
de reloj máxima a la que podría funcionar el circuito utilizando los datos de la biblioteca
de celdas presentada en teoría.
8. Se desea diseñar un sistema secuencial síncrono con una entrada x{Norte, Sur, Este,
Oeste} y una salida z{0,1}. La salida z(t) tomará el valor ‘1’ si:
{ x(t-2), x(t-1), x(t) } = { Norte, Este, Este } o { Sur, Este, Este }
En todos los demás casos el valor de z(t) será ‘0’. Se pide:
a) Construir el diagrama de estados del sistema en la forma de una máquina
Mealy. Explique el significado de cada estado.
b) Implemente el sistema con el menor número posible de biestables D y puertas
lógicas.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 3
9. Implemente un sistema secuencial que realice la suma de 2 de números de longitud
variable recibidos en serie y en orden creciente de pesos (primero el bit menos
significativo). El sistema tiene dos entradas de datos, x e y, una salida de datos, z, y una
entrada de control, inicio, que se pone a ‘1’ para indicar el comienzo y el final de los
números sumar. El comportamiento esperado es el siguiente:
t 0 1 2 3 4 5 6 7 8 9 10 11 12
inicio(t) 1 1 0 0 0 0 0 1 0 0 0 0 1
x(t) - - 0 0 1 0 1 - 0 1 1 1 -
y(t) - - 0 1 1 0 1 - 0 1 1 1 -
z(t) 0 0 0 1 0 1 0 1 0 0 1 1 1
10. Diseñe un comparador para números de números binarios de n bits sin signo, A y B,
según el esquema mostrado en la figura. Los números llegan en serie por las entradas x e
y, comenzando por el bit menos significativo. El circuito es capaz de analizar diversas
relaciones de comparación entre A y B, mediante las entradas de control (a, b, c) de
acuerdo con la tabla. La salida, z, toma el valor ‘1’ si la relación es cierta y ‘0’ en otro
caso. Use puertas y biestables D. Calcule el coste y la frecuencia de reloj máxima a la
que podría funcionar el circuito utilizando los datos de la biblioteca de celdas presentada
en teoría.
11. Un sistema secuencial tiene una entrada, x, de 2 bits y dos salidas, z y m. La salida z vale
‘1’ cuando el valor actual de la entrada es igual al valor anterior de la misma. Cuando el
valor actual y anterior de x no coinciden, la salida m vale ‘1’ si el valor actual de la
entrada es mayor que el anterior. En el resto de casos z y m valen ‘0’. Implemente el
sistema como máquina de Mealy usando el menor número de biestables D y puertas
lógicas. Ídem como máquina de Moore. Calcule en cada caso el coste y la frecuencia de
reloj máxima a la que podría funcionar el circuito utilizando los datos de la biblioteca de
celdas presentada en teoría.
12. Se desea diseñar el sistema de control de una escalera mecánica bidireccional que puede
estar parada, subiendo o bajando.
El sistema tiene 2 entradas conectadas a dos
sensores de presión, P1 y P2, situados en las
posiciones mostradas en la figura. Cuando se
activa un sensor, la escalera empieza a moverse en
sentido al otro sensor y no para hasta que dicho
sensor se active. No se considera la situación de
que se activen simultáneamente ambos sensores ya
que cuando se activa uno, se desactiva
automáticamente y no vuelve a activarse hasta que
se ha activado el contrario y viceversa.
x
y
Ck
a b cClear
z
abc
relación
analizada
000
001
010
011
100
101
A=B
A#B
A>B
A>=B
A<B
A<=B
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 4
El sistema tiene 2 salidas: encendido, E, (si E vale ‘1’ la escalera se mueve) y sentido, S,
(si S vale ‘1’ la escalera sube y si vale ‘0’ la escalera baja).
Diseñe el sistema como máquina de Moore usando el menor número de biestables D y
puertas lógicas.
13. Diseñe como máquina de Moore un sistema capaz de detectar los flancos de una señal
digital que transmite a baja velocidad datos en serie (es decir, el tiempo transcurrido entre
dos cambios sucesivos de polaridad es bastante superior al periodo del reloj del sistema).
El sistema tendrá una entrada, x, y dos salidas, up y down. La salida up valdrá 1 durante
un ciclo de reloj cada vez que detecte una transición de 0 a 1 en la entrada. La salida
down valdrá 1 durante un ciclo de reloj cada vez que detecte una transición de 1 a 0 en la
entrada.
14. Despreciando los retardos, complete el cronograma mostrado en la figura para un latch D
(biestable D síncrono por nivel en alta) y un flip-flop D (biestable D síncrono por flanco
de subida). Suponga que el valor inicial de la salida de ambos biestables es ‘0’.
15. Usando un biestable D disparado por flanco y las puertas necesarias, implemente un
biestable T cuyo comportamiento coincida con el de la tabla siguiente:
T(t) Q(t+1)
0 Q(t)
1 Q(t)
16. Usando un biestable D disparado por flanco y las puertas necesarias, implemente un
biestable JK cuyo comportamiento coincida con el de la tabla siguiente:
J(t) K(t) Q(t+1)
0 0 Q(t)
0 1 0
1 0 1
1 1 Q(t)
Problemas de examen:
17. (Junio 2012) Se desea diseñar un sistema que permita fotografiar las matrículas de
aquellos coches que circulen con exceso de velocidad por una carretera.
El sistema tendrá 2 entradas (A y B) conectadas a sensores de presión ubicados debajo
del pavimento y una salida (F) conectada al disparador de una cámara. En ausencia de
D
Q
QG
D
Q
Q
D
clk / G
QA
QB
B
A
Proble
c
c
n
a
U
tr
c
S
a
b
18. (F
fu
e
S
c
e
S
emas de Fund
coches las en
correspondie
nunca ambas
alternando (e
Un coche ir
ranscurren d
caso deberá
Se pide:
a) Especific
b) Impleme
Febrero 201
fuentes (llam
encienden de
Si el va
encendi
encendi
Si el val
Siempre que
correspondie
están apagad
Se pide:
a) Espe
b) Indic
estad
c) Impl
mínim
damentos de C
ntradas vald
ente entrada
s entradas v
es decir, tras
rá a más v
desde la act
ser fotograf
car el sistem
entarlo utiliz
13) Se quier
madas a, b,
epende de u
alor de S e
das; c y d
das; a y b: a
lor de S es ‘
e cambia el
ente. El sist
das y desde
ecificar el sis
car las tablas
dos del sistem
ementar el
mo.
Computadores
drán ‘0’ y ca
a se activará
valdrán simu
s un pulso e
velocidad de
tivación de
fiado (véase
ma como má
zando 2 bies
re diseñar el
c y d) que h
una señal de
es ‘1’, la se
d: apagadas
apagadas)...
0’, la secuen
l valor de
tema tiene a
el que salta
stema media
s de verdad
ma.
sistema me
(versión 7-10
ada vez que
á (valdrá ‘1’
ultáneament
en A vendrá
e la permit
A hasta la
la figura).
áquina de M
stables D y e
l sistema qu
hay en un p
control S.
ecuencia es
s), (b y c:
ncia es: ad,
S, se empie
además un
a la corresp
ante un diag
que especif
ediante biest
0-14)
e un coche p
’ durante un
te ‘1’ y que
siempre un
tida si el n
activación
Mealy.
el menor nú
ue controla e
parque. La s
: ab, bc, cd
encendidas
bc, ad, bc…
eza por el
estado inic
pondiente se
grama de est
fican las fun
tables D y u
pase por enc
n ciclo de re
e los pulsos
pulso en B
número de
de B es me
úmero de pu
el encendido
ecuencia en
d, ab, bc…
s; a y d:
…
primer esta
ial en el qu
ecuencia seg
tados como
nciones de sa
una memor
Tema
cima de un s
eloj). Supón
en A y en B
y viceversa
ciclos de r
enor que 3,
uertas lógica
o y apagado
n la que se a
… Es decir
apagadas),
ado de la s
ue todas las
gún el valor
máquina de
alida y trans
ria ROM de
a 6 / pág. 5
sensor la
gase que
B se irán
a).
reloj que
en cuyo
as.
o de las 4
apagan y
r (a y b:
(c y d:
ecuencia
s fuentes
de S.
e Moore.
sición de
e tamaño
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 6
19. (Junio 2013) Se quiere diseñar un circuito digital que controle el funcionamiento de una
máquina expendedora de caramelos. Dicho controlador recibe una señal de entrada S
procedente de un sensor que toma el valor (00)2 mientras no se introduzca ninguna
moneda en la máquina, o la moneda introducida no sea de 5 o 10 céntimos. Cuando se
introduce una moneda de 5 o 10 céntimos la señal S toma los valores (01)2 y (10)2
respectivamente. Para expender un caramelo el controlador deberá activar la señal de
salida z. La máquina se comporta de la siguiente manera:
Cada caramelo cuesta 15 céntimos.
El cliente puede ir introduciendo monedas en el orden que quiera.
Cuando el saldo introducido alcanza o supera los 15 céntimos la máquina expende
un caramelo, quedando almacenado el saldo restante por si el cliente quiere comprar
otro caramelo. Por ejemplo, si un cliente introduce dos monedas de 10 céntimos
seguidas, al introducir la segunda moneda la máquina expende un caramelo y deja
almacenados los 5 céntimos sobrantes por si el cliente quiere seguir comprando.
El cliente puede pulsar en cualquier momento un botón de reinicio, la máquina le
devolverá entonces el saldo actual y quedará a la espera de que algún nuevo cliente
comience a usar la máquina.
Se pide:
a) Especificar el sistema mediante un diagrama de estados como máquina de Moore.
b) Indicar las tablas de verdad que especifican las funciones de salida y transición de
estados del sistema.
c) Implementar el sistema mediante biestables D y una memoria ROM de tamaño
mínimo.
20. (Septiembre 2013) Se quiere diseñar un circuito digital para arbitrar el acceso de tres
dispositivos a un bus, con el interfaz indicado en la figura. El árbitro recibirá una señal de
petición por cada canal, X = (x2, x1, x0): si xi vale ‘1’ hay petición por el canal i, si vale ‘0’
no la hay. El canal 0 es más prioritario que el 1, que a su vez es más prioritario que el 2.
El árbitro concederá el bus activando la correspondiente señal de grant: G = (g2, g1, g0):
si gi vale ’1’ se concede el uso del bus al dispositivo conectado al canal i, si vale ‘0’ el
dispositivo no puede hacer uso del bus. El comportamiento del árbitro debe ser el
siguiente:
Mientras no haya petición por ninguno de los canales el árbitro permanece Inactivo,
dejando las tres señales de grant a ‘0’.
Si estando Inactivo se recibe petición por alguno de los canales (puede haber varias
peticiones simultáneas), el árbitro debe conceder el uso del bus al canal más
prioritario, activando su señal de grant.
Una vez concedido el bus a un dispositivo, la señal de grant correspondiente debe
permanecer activa hasta que el dispositivo que está siendo atendido desactive la
petición (incluso si otro dispositivo más prioritario solicita el uso del bus). Por
ejemplo, si se ha concedido el bus al dispositivo del canal 1, la señal g1 debe
permanecer activa hasta que x1 se ponga a ‘0’. Cuando el dispositivo desactiva la
petición el árbitro pasará a estado Inactivo para iniciar un nuevo ciclo de bus.
Se pide:
a) Especificar el sistema mediante un diagrama de estados como máquina de Moore.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 6 / pág. 7
b) Indicar las tablas de verdad que especifican las funciones de salida y transición de
estados del sistema.
c) Implementar el sistema usando biestables D y puertas.
21. (Febrero 2014) Se desea diseñar un sistema secuencial para controlar la velocidad de
circulación en un túnel por el que únicamente pueden circular coches y camiones (ambos
vehículos de dos ejes). Para ello se instala un sensor de presión que ofrece tres lecturas:
eje de coche detectado, eje de camión detectado y eje no detectado.
Para comprobar si un vehículo circula a la velocidad permitida el sistema mide los ciclos
de reloj que transcurren entre la detección del eje delantero y el trasero aplicando las
siguientes reglas:
En caso de que se haya detectado el eje delantero de un coche, deberá transcurrir al
menos 1 ciclo de reloj hasta la detección del trasero.
En caso de detección de eje delantero de un camión, deberán transcurrir al menos 2
ciclos de reloj hasta la detección del eje trasero.
En caso de que no se cumplan los márgenes de tiempo el sistema activará una señal de
salida multa (M) y volverá al estado inicial. En caso de que la detección del eje trasero no
corresponda al mismo tipo de vehículo que el delantero activará una señal de error (E) y
volverá al estado inicial. La figura muestra un ejemplo del comportamiento esperado.
Se pide:
a) Especifique el sistema mediante un diagrama de estados como máquina de
Mealy, definiendo las entradas, salidas y estados.
b) Implemente el sistema utilizando biestables D y una memoria ROM.
clk
sensor
M
1
0
no
eje
eje
coche
no
eje
no
eje
no
eje
no
eje
eje
coche
eje
coche
eje
coche
detectado
eje delantero
coche 1
detectado
eje trasero
coche 1
detectado
eje delantero
coche 2
detectado
eje trasero
coche 2
ha transcurrido
1 ciclo: no hay multa
no ha transcurrido
1 ciclo: hay multa
FCproblemas7.pdf
Facultad de Informática
Universidad Complutense de Madrid
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 7 / pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES
TEMA 7
Problemas básicos:
1. Utilizando un contador con carga paralela módulo 8 y el menor número de puertas
lógicas, diseñe un dado electrónico cuyo diagrama de bloques se muestra en la figura
siguiente:
El sistema tiene una entrada, J, conectada a un pulsador. Cuando esta entrada vale ‘1’, el
contador sigue cíclicamente una secuencia de 6 valores distintos cada uno codificando
una cara diferente del dado; cuando vale ‘0’, el contador se detiene. La salida del
contador está conectada a un conversor que, para cada valor de la secuencia, enciende los
leds que correspondan según la cara del dado representada. Para evitar que el usuario
pueda averiguar cuál es el valor que está marcando el dado mientras mantiene presionado
el pulsador, la frecuencia de la señal de reloj debe ser lo suficientemente alta (por
ejemplo, 1 KHz). Así, como el valor final del dado está determinado por el tiempo que la
entrada permanece a ‘1’ y este no puede ser controlado con exactitud por un humano, se
consigue la deseada sensación de
aleatoriedad.
2. Complete un cronograma, como el mostrado en la figura, para cada uno de los diseños
basados en contadores mostrados en la misma.
3. Utilizando un contador con carga en paralelo y el mínimo número de puertas lógicas,
implemente un sistema secuencial cuya salida repita la secuencia: 0, 1, 4, 4, 7, 7.
4. Utilizando un contador con carga en paralelo y el menor número de puertas lógicas,
implemente un sistema secuencial con una entrada binaria que se comporte de acuerdo
con el diagrama de la figura siguiente:
S
clk
ld
cl
1
0
1
0
5 6
4
CONT MOD 16
ld
cl
0
4
3
0
4
CONT MOD 16
ld
cl
0
4
3
1
conversor
de código
contadorJ
3 7
0 1 4 5 6
0
7
2 3
1
0
1
Proble
5. U
p
v
1
6. D
e
re
7. D
ti
s
S
emas de Fund
Usando pue
paralela cone
vale 1 duran
1 KHz.
Diseñar un r
en paralelo, E
ealizar segú
Diseñe un si
iene las 2 e
iguientes es
En el est
inicial si
‘1’, mom
Durante
dependie
del valor
siempre
Durante
En el seg
mueven
Durante
del aclar
Durante
Se pide:
a) Esp
Mo
b) Dis
damentos de C
rtas lógicas
ectados a un
nte un ciclo d
registro de d
E1 y E2. El
ún la siguien
stema secue
entradas y
specificacion
tado inicial,
iempre que
mento en com
su funcion
endo del va
r de la tecl
al estado ini
el lavado en
gundo ciclo
las aspas.
el aclarado
ado.
el secado se
pecifique el
oore.
señe el sistem
Computadores
s y contado
n reloj de 60
de cada 60).
desplazamie
l registro ten
nte tabla:
S
000
00
010
01
100
10
110
11
encial que c
5 salidas m
nes:
todas las sa
la tecla on/
mienza desd
namiento, e
lor de la te
a ciclo rápi
icial.
ntra agua du
o se abre el
entra agua
e activa la sa
sistema m
ma usando u
(versión 7-10
ores módulo
0 Hz, diseñ
. Ídem para
ento bidirec
ndrá una en
Q(t+
0 Q(t
1 Q(t)
0 Q(t)
1 C1( Q
0 E1(
1 E2(
0 Q(t) and
1 not Q
ontrole el fu
mostradas en
alidas valen
/off vale ‘0’
de el princip
el aparato p
cla ciclo rá
ido) y seca
urante el pr
cajetín del
el primer c
alida secar.
mediante un
un contador
0-14)
o 16 con c
ñe un tempor
el caso de q
ccional de 3
ntrada de con
+1)
t)
× 2
2
Q(t) )
(t)
(t)
d E2(t)
Q(t)
uncionamien
n la figura
‘0’. Desde
, y allí se p
pio el ciclo d
pasa por 3
ápido), aclar
ado (1 ciclo
imer ciclo,
detergente.
ciclo. Se mu
n diagrama
r y el mínim
apacitación
rizador de 1
que la frecue
bits con do
ntrol, S, que
nto de un la
y debe com
cualquier es
ermanece h
de lavado.
etapas: lav
rado (1 ó 2
). Después
y durante el
Todos los
ueven las as
de estados
mo número d
Tema
n de cuenta
1 segundo (
encia de rel
os entradas
e indica la f
avaplatos. El
mportarse s
stado se va a
hasta que on
vado (2 ó
ciclos depe
del secado
l mismo se
ciclos del la
spas todos lo
como máq
de puertas po
a 7 / pág. 2
y carga
su salida
oj sea de
de datos
función a
l sistema
egún las
al estado
n/off vale
4 ciclos
endiendo
o se pasa
calienta.
avado se
os ciclos
quina de
osible.
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 7 / pág. 3
Problemas adicionales:
8. Utilizando como bloque básico un contador con carga paralela módulo 16, implemente
un contador ascendente programable módulo m (siendo 1 < m < 16). El sistema tendrá
una entrada de capacitación de cuenta, una entrada de 4 bits por la que se indicará el
valor máximo alcanzable en la cuenta y una salida de saturación que tomará el valor ‘1’
cuando el contador alcance dicho valor máximo y adicionalmente su entrada de
capacitación valga ‘1’.
9. Diseñe un cronómetro digital que visualiza sobre 5 displays 7-segmentos los minutos,
segundos y décimas de segundo transcurridos. El cronómetro tiene una entrada
asíncrona, reset, para puesta a cero y una entrada, stop, que cuando toma el valor ‘0’
detiene la cuenta y cuando vale ‘1’ la reanuda. En su diseño use contadores como los
desarrollados en el ejercicio anterior y conversores de BCD a 7-segmentos. Suponga que
la frecuencia del reloj del sistema es de 100 Hz.
10. Se desea implementar un sistema secuencial que controle un rótulo luminoso formado
por 8 leds. El sistema tendrá una señal de control C. Si C vale ‘0’, los 8 leds
permanecerán apagados. Si C vale ‘1’, el sistema hará que los leds se iluminen siguiendo
cíclicamente la secuencia mostrada en la figura, al ritmo fijado por la frecuencia del reloj
del sistema.
Se pide:
a) Implemente el sistema usando un contador y una ROM 16×8.
b) Amplíe el sistema para que los leds puedan iluminarse siguiendo 4 secuencias
distintas, seleccionables a través de una entrada de 2 bits.
c) Amplíe el sistema para que el usuario, a través de un entrada de 2 bits, pueda
seleccionar la velocidad a la que se sigue la secuencia (normal, ×2, ×4 y ×8).
11. La luminosidad de un led puede regularse digitalmente mediante la técnica conocida
como led dimming. Dado que la intensidad suministrada por la salida de un sistema
digital es fija para encender un led y nula para apagarlo, esta técnica consiste modificar al
porcentaje de tiempo durante el que sistema digital suministra intensidad al led cuando
éste debe estar encendido. Así, el sistema digital en lugar de enviar una señal constante
para encender el led (que daría lugar a un encendido de máxima luminosidad) envía una
señal periódica de anchura de pulso variable cuyo factor de trabajo (el tiempo que está a
‘1’) determina la luminosidad del led. Diseñe un circuito con una señal de carga paralela,
una entrada para el valor de luminosidad (0-100) codificado en binario y una salida por la
que generar la señal que regula la luminosidad de un led. Para diseñar el circuito
t
t+1
t+2
t+8
t+9
t+10
...
t+13
t+14
t+15
...
control de
luces
C leds
8
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 7 / pág. 4
utilícese un contador, un registro y un comparador. La frecuencia de reloj es de 100 Hz
(frecuencias inferiores hacen que el ojo humano detecte el parpadeo).
12. Diseñe un circuito secuencial que elimine los rebotes de un pulsador. El circuito
funcionará a 1 MHz, tendrá una entrada, x, por la que entra la señal con rebotes y una
salida, z, por la que sale la señal filtrada. Su comportamiento, que se muestra en la figura,
será el siguiente:
En reposo, mientras la entrada valga ‘1’ (es decir, mientras el pulsador no se
presione), la salida debe valer ‘1’.
Tras la detección del primer flanco de bajada (provocado por la presión del
pulsador), la salida debe permanecer estable a ‘0’ durante 100 ms con independencia
de los valores que tome la entrada durante ese intervalo.
Transcurridos los 100 ms y mientras que la entrada valga ‘0’ (es decir, mientras se
mantenga el pulsador presionado), la salida debe valer ‘0’.
Tras la detección del primer flanco de subida (provocado por la depresión del
pulsador), la salida debe permanecer estable a ‘1’ durante 100 ms con independencia
de los valores que tome la entrada durante ese intervalo.
Transcurridos los 100 ms, el sistema volverá al estado de reposo.
Para medir un intervalo de 100 ms utilícese un temporizador formado por un contador y
un comparador. El sistema constará de una máquina de estados que convenientemente
lea la entrada, escriba la salida, arranque el temporizador y espere su finalización.
13. Se desea ampliar la funcionalidad de un banco de 4 registros de 8 bits añadiéndole una
función de copia. Para ello, dispondrá de una entrada de control adicional, copy. Cuando
vale ‘0’ el banco de registros debe comportarse normalmente y cuando vale ‘1’ (y we
también vale ‘1’) debe copiar el contenido del registro indicado por ra en el registro
indicado por ra ignorando el valor presente en di.
14. Un watchdog es un temporizador que se utiliza para la detección y recuperación de
posibles errores de funcionamiento en un computador. Durante un funcionamiento
normal, el computador reinicia regularmente el watchdog para
evitar que este consuma
su tiempo. Si el watchdog alcanza el time-out, activa una señal que dispara una acción
correctiva (típicamente el reinicio del computador). Diseñe un watchdog con time-out
REG FILE
di
do
8
8
we
clk
ra
2
wa
2
copy
< 100 ms
x
< 100 ms
z
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 7 / pág. 5
seleccionable (1s, 500ms, 250ms, 125ms) a través de una entrada de 2 bits. Además el
sistema tendrá una entrada para reiniciar la cuenta y una salida que se activará al alcanzar
el time-out. El sistema funcionará a 50 KHz y se diseñará usando un contador, un
comparador y un multiplexor 4 a 1.
15. Diseñe el sistema para controlar la apertura y cierre de una caja fuerte mostrado en la
figura. Las entradas, code y newCode, están conectadas a un teclado, la salida trials a un
display y la salida lock al motor del cerrojo. El sistema debe comportarse según las
siguientes especificaciones:
El cerrojo permanece abierto mientras lock vale ‘0’ y cerrado en caso contrario.
Inicialmente la caja fuerte debe estar abierta.
Cada vez que el usuario teclee una clave de 4 dígitos, el teclado pondrá en code un
código de 16 bits (codificando en BCD las 4 teclas pulsadas) y pondrá la señal
newCode a ‘1’ durante un único ciclo de reloj para que el sistema lea en paralelo la
clave introducida.
El primer código enviado hará que el sistema almacene la clave y cierre el cerrojo.
Los sucesivos códigos permitirán abrir el cerrojo siempre y cuando la clave leída
coincida con la clave almacenada.
Se tendrán un máximo de 3 intentos para acertar la clave almacenada.
Tras fallar los 3 intentos el cerrojo quedará indefinidamente cerrado.
El sistema indicará a través de trials el número de intentos restantes hasta el bloqueo
del cerrojo.
Para diseñar el sistema utilícese un registro de 16 bits, un comparador de igualdad de
16 bits y una máquina de estados.
16. Una UART (Universal Asynchronous Receiver-Transmitter) es uno de los dispositivos
de E/S serie más comunes. Consta de un transmisor que serializa los datos paralelos que
se quieren enviar, un receptor que paraleliza los datos serie que se reciben y un
controlador que comunica ambos elementos con el computador. Se desea diseñar el
circuito que efectúa la transmisión serie asíncrona de datos de 8 bits. El circuito tiene las
entradas y salidas mostradas en la figura y debe comportarse según las siguientes
especificaciones:
En inactividad, la señal Tx debe valer ‘1’.
Los datos se transmitirán en una trama de 11 bits que comenzará con un bit de start a
‘0’, los 8 bits de datos comenzando por el bit menos significativo, un bit de paridad
impar (el patrón formado por este bit y los 8 bits de datos debe tener siempre un
número impar de ‘1’) y un bit de stop a ‘1’.
El sistema, cada vez que detecte que la señal start vale ‘1’, cargará de data el dato a
transmitir y comenzará a transmitirlo en serie.
La señal ready debe valer ‘0’ mientras que se esté transmitiendo el dato y ‘1’ en caso
contrario
La frecuencia de reloj es de 5 MHz y los datos deberán transmitirse a 9600 baudios
(bits/segundo). Para diseñar el circuito utilícese un registro de desplazamiento de 11
bits (para la conversión paralelo-serie de los datos), un contador 0-11 (para la cuenta
controlador de
caja fuerte
newCode lock
trials
2
code
16
Problemas de Fundamentos de Computadores (versión 7-10-14) Tema 7 / pág. 6
del número de bits desplazados), un contador del tamaño que considere oportuno (para
la cuenta del número de ciclos que deben transcurrir entre un desplazamiento y otro
calculados como el cociente entre la frecuencia de reloj y la velocidad de transmisión)
y las puertas lógicas que estime necesarias.
17. Un buffer LIFO (last in, first out) es un almacén de datos no accesibles por dirección sino
legibles en orden inverso al orden en que se escribieron (es decir, el primer dato que se
puede leer es siempre el último que se ha escrito). Usando un contador
ascendente/descendente, 2 RAM 256×8 bits y otros componentes que estime necesarios,
diseñe una LIFO capaz de almacenar un máximo de 256 datos de 16 bits. El sistema
tendrá una entrada/salida de datos, d, de 16 bits, 3 señales de control, ce, we y oe, para
capacitar el módulo, la escritura y la lectura respectivamente y 2 señales de estado, full y
empty, para indicar cuándo la LIFO está llena y cuándo está vacía.
18. Usando un sumador/restador y un registro, diseñe un acumulador genérico que opere con
números enteros con signo codificados en C2 con n bits. El sistema acepta un operando,
y lo suma/resta al resultado calculado en con anterioridad. El sistema tiene un puerto de
datos de entrada, x, un puerto de datos de salida, z, dos entradas de control, ld y op, y una
salida de estado, ov. Si ld vale ‘1’, el dato en la entrada x debe acumularse; si vale ‘0’,
no. Si la entrada op vale ‘0’, el dato debe sumarse; si vale ‘1’, restarse. La salida ov debe
activarse cuando el resultado no sea representable en C2 con n bits.
19. Usando multiplicadores, sumadores, multiplexores y registros, diseñe 3 rutas de datos sin
controlador tal que cada una pueda realizar una de las siguientes expresiones, donde x, a
y b son puertos de entrada de n bits y z es un puerto de salida de n bits:
a) z ∑ a ∙ x ≡ 1 a ∙ x
b) z ∑ a ∙ x b ≡ 1 a ∙ x b
c) z ∑ x x b ≡ 1 x x b
Rediseñe las rutas de datos b) y c) de modo que utilicen un único sumador. Discuta por
qué estos diseños con solo un sumador requieren tener controlador y no pueden aceptar
datos nuevos y generar resultados en todos los ciclos.
20. Diseñar un circuito secuencial capaz de calcular iterativamente el elemento i-ésimo de la
serie de Fibonacci. El circuito tendrá una entrada, i de 5 bits, para indicar el elemento de
la serie; una entrada, inicio, para indicar el comienzo del cálculo; una salida, fin, para
indicar el fin del cálculo y una salida z de 20 bits, para indicar el valor del elemento de la
serie indicado. La serie de Fibonacci se define recursivamente de la siguiente manera:
fib(0)=0, fib(1)=1, fib(i)=fib(i-1) + fib(i-2). El sistema deberá diseñarse usando circuito
realizará el cálculo iterativamente. Tendrá 1 sumador de 20 bits, 2 registros para
almacenar los 2 últimos elementos de la serie y un contador que llevará la cuenta del
índice.
transmisor
serie
start
ready
data
8
Tx
LIFO
d
16
empty
we
full
oe
ce
Proble
21. D
c
E
p
s
fi
Prob
22. (F
q
d
p
tr
E
d
tr
fu
S
in
emas de Fund
Diseñar un s
codificados e
begin
Div
Div
Co
wh
end
C :
R :
end;
El sistema te
para indicar
alidas, c y
figura y utili
blemas de
Febrero 201
que dispone
diseñar un si
permita que
ramo superi
El sistema ti
durante un c
rayectos cir
función del v
Cuando
Cuando
Cuando
Cuando
Suponiendo
ndicados en
a) Espe
damentos de C
sistema secu
en binario u
videndo := D
visor := Dvs
ociente := 0;
hile Dividen
Dividendo
Cociente
d while;
:= Cociente
:= Dividend
endrá dos en
el comienzo
r de 8 bits,
izará 2 regis
e examen:
12) Sea un t
de un senso
istema que,
el tren rea
ior, dos vuel
ene como e
ciclo de rel
culares supe
valor en las
C1=’0’ y C
C1=’1’ y C
C1=’0’ y C
C1=’1’ y C
que el tre
n la figura, s
ecificar el sis
Computadores
uencial que
utilizando el
Dvnd;
sr;
ndo >= Divis
o := Dividen
:= Cociente
;
do;
ntradas, dvn
o del cálcul
para result
stros, 1 cont
:
tren eléctric
or de presen
leyendo el
alice indefin
ltas por el tr
ntrada P y c
oj) cuando
erior e infer
salidas C1 y
C2=’0’, el tre
C2=’1’, el tre
C2=’1’, el tre
C2=’0’, el tre
en se encue
e pide:
stema como
(versión 7-10
implemente
algoritmo d
sor do begin
ndo - Diviso
e + 1;
d y dvsr de
lo; una salid
tados. El si
ntador y 1 re
co de juguet
ncia (P) y do
valor del se
nidamente l
ramo inferio
como salida
el tren pas
rior. Por su
y C2:
en realiza re
en realiza re
en pasa del
en
pasa del
entra en la
o máquina d
0-14)
e la división
de restas suc
n
or;
8 bits, para
da, fin, para
stema tendr
estador.
e con un tra
os cambios
ensor y cont
la siguiente
or, una vuelt
as C1 y C2.
sa por el tra
parte el tren
ecorridos cir
ecorridos cir
tramo super
tramo infer
posición i
de Moore
D
n entera de 2
cesivas sigu
operandos;
indicar el f
rá los puert
azado de vía
de agujas (
trolando los
secuencia:
ta en ocho.
La entrada P
amo de vía
n seguirá un
rculares por
rculares por
rior al inferi
ior al superi
nicial y cir
Divisor
Dvnd
C
8
8
Tema
2 números n
uiente:
; una entrad
fin del cálcu
tos mostrad
as en forma
C1 y C2).
s cambios de
dos vuelta
P se activa
a que compa
na trayectori
r el tramo su
r el tramo in
ior.
ior.
rcula en el
r
Dvsr
8
R
8
a 7 / pág. 7
naturales
da, inicio,
ulo y dos
dos en la
a de ocho
Se desea
e agujas,
as por el
(vale ‘1’
arten los
ia que es
uperior.
nferior.
l sentido
inicio
fin
Proble
23. (
s
h
p
ig
U
e
c
“
te
“
m
“
S
emas de Fund
b) Impl
lógic
Septiembre
istema tiene
haya ruido y
parte, la salid
gual a ‘1’) o
Una vez enc
estímulos, n
chupete (hay
“dormida”.
ener el chu
“asustada”.
mantenga. C
“tranquila” e
Se pide:
a) Esp
b) Imp
lógi
damentos de C
ementarlo u
cas.
2012) Se d
e 2 entradas
y la entrada C
da G habilit
o bien algun
cendida, la
i habla, ni l
ya o no ruid
En el estad
upete puesto
En el est
Cuando el r
en función d
pecificar el s
plementarlo
icas.
Computadores
utilizando u
desea diseña
s y 2 salidas
C lo hará cu
ta un genera
nas palabras
muñeca se
llora. Si se h
do), dejará d
do “dormida
o, se escuch
tado “asust
ruido desapa
de si tiene o
sistema com
utilizando
(versión 7-10
un contador
ar el sistema
s, todas ella
uando haya u
ador de soni
(si L es igu
e encontrará
hace ruido,
de hablar (s
a” no hace
he un ruido
tada” perm
arezca deja
o no el chup
mo máquina
un contado
0-14)
módulo-8
a de control
as binarias. L
un chupete
idos que rep
ual a ‘0’).
á en estado
sigue “tran
i lo estuvier
nada y per
o. En ese c
manecerá llo
ará de llorar
pete puesto.
de Mealy.
or mod-4 y
y el menor
l de una mu
La entrada R
en la boca d
produce o bi
o “tranquila
nquila” y hab
ra haciendo
rmanecerá e
caso llorará
orando mie
r y pasará a
y el menor
Tema
r número de
uñeca intera
R valdrá ‘1
de la muñec
ien un llanto
a” donde, si
abla. Si se le
o) y pasará a
en él hasta
y pasará a
entras el r
a estar “dor
número de
a 7 / pág. 8
e puertas
activa. El
’ cuando
a. Por su
o (si L es
i no hay
e pone el
al estado
que, sin
al estado
ruido se
rmida” o
e puertas
FC_2_2_Problemas_V2.pdf
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES (HOJA 2.2)
PROGRAMACIÓN EN ENSAMBLADOR
1. Indica cuál es el resultado de ejecutar las siguientes instrucciones, dando el contenido final de los registros y
posiciones de memoria para cada instrucción. Se supone que para cada instrucción a ejecutar el contenido de los
registros y posiciones de memoria es el siguiente:
Registros
r0 0000 0016h
r1 0000 0054h
r2 FFFF FFFFh
r3 0000 0000h
r4 0000 0004h
Memoria
00h 0339 3826h
04h EA00 63AFh
08h 17FA 8912h
0Ch BC98 3304h
10h 7845 F34Ah
14h 534B 4AAAh
Las instrucciones a ejecutar son:
1. add r3, r0, r1
2. add r2, r2, #1
3. sub r4, r1, r0
4. sub r4, r0, r1
5. mul r4, r0, r1
6. or r3, r1, r0
7. mov r4, #0
8. lsr r2, r0, r4
9. ldr r0, [r4]
10. ldr r0, [r4,#-4]
11. str r2, [r4,r3]
12. str r2, [r0]
2. Codifica en ensamblador la siguiente condición IF-THEN:
if (x >= y) {
x = x+2;
y = y-2;
}
3. Codifica en ensamblador la siguiente condición IF-THEN-ELSE:
if (x >= y) {
x = x+2;
y = y+2;
}
else {
x = x-2;
y = y-2;
}
4. Codifica en ensamblador el siguiente bucle REPEAT-UNTIL:
a = 81;
b = 18;
do {
a = a-b;
} while (a > 0);
5. Codifica en ensamblador el siguiente bucle WHILE-DO:
n = 5;
fant = 1;
f = 1;
i = 2;
while (i <= n) {
faux = f;
f = f + fant;
fant = faux;
i = i+1;
}
6. Codifica en ensamblador el siguiente bucle FOR:
for (i=2; i<=n; i++) {
f=f+f;
}
7. El siguiente programa calcula el máximo común divisor de dos números a y b según el algoritmo de restas de
Euclides. Traducirlo a ensamblador del ARM:
int a=5, b=15, mcd;
While (a≠b){
if (a>b)
a=a-b;
else
b=b-a;
}
mcd=a;
8. Traduce la siguiente sentencia en C a ensamblador, donde f, g y h son enteros contenidos en memoria y B es un
vector de 10 componentes: f=g+h+B[4].
9. Tenemos un vector de 10 componentes almacenado en la posición de memoria etiquetada como V. Diseña un
programa en ensamblador que sume uno a cada una de sus componentes.
10. Tenemos un vector de 6 componentes almacenado en la posición de memoria etiquetada como V. Diseña un
programa en ensamblador que cuente el número de valores mayores que 0 que contiene.
11. Implementar un programa en ensamblador que calcule la sucesión de Fibonacci y la almacene en un vector V de
longitud arbitraria N. Esta sucesión infinita de números naturales queda definida como V(0)=0, V(1)=1,
V(n)=V(n-1)+V(n-2). Se proporciona como ayuda el siguiente código de alto nivel:
Nota: definir una constante N que almacene el número de elementos del vector V.
for i from 0 to N-2 do:
V[i+2] = V[i] + V[i+1]
end for
12. Dado un vector A de 12 componentes se desea generar otro vector B, tal que B sólo contiene las componentes de A
que son números pares mayores que cero. Ejemplo:
A = (0,1,2,7,-8,4,5,12,11,-2,6,3) à B = (2,4,12,6).
Escriba un programa en lenguaje de alto nivel que implemente el procesamiento descrito y calcule el número de
componentes del vector B. Traduzca el programa al lenguaje ensamblador del ARM.
13. Dados dos vectores A y B de 10 componentes cada uno se desea construir otro vector C tal que:
C(i) = |A(i) + B(9-i)|, i = 0,...,9.
Escriba un programa en lenguaje de alto nivel que construya el vector C. Traduzca el programa al lenguaje
ensamblador del ARM.
14. Traduce el siguiente programa escrito en un lenguaje de alto nivel a lenguaje ensamblador. La órden swap(a,
b) intercambia los valores de las variables a y b.
int a=13, b=16;
While (a>10){
a=a-1;
b=b+2;
}
if (a<b)
swap (a, b);
else
b= a-1;
15. Escribe un programa para el ensamblador del ARM que llame a una subrutina, swap(int *a, int *b),
encargada de intercambiar el contenido de dos posiciones de memoria. La subrutina recibirá como parámetros de
entrada las posiciones de memoria correspondiente a a y b y deberá preservar el contenido de todos los registros
que se empleen para realizar la operación.
Cuestión: ¿Qué registros debemos utilizar dentro de la función para evitar tener que salvar y restaurar registros
durante el proceso?
16. Escribe un programa para el ensamblador del ARM que cuente el número de 0’s de un vector de longitud
arbitraria. Emplea para ello una subrutina llamada cuenta0s que reciba como parámetros de entrada toda la
información necesaria para llevar a cabo la tarea.
17. Implementar el algoritmo de ordenación de la burbuja o bubble sort en ensamblador. Este sencillo algoritmo
ordena los elementos de un vector de menor a mayor por medio de un procedimiento muy sencillo: recorre
repetidas veces el vector, intercambiado posiciones sucesivas si V(i)>V(i+1), hasta que no se realiza ningún
cambio. Se proporciona como ayuda el siguiente código de alto nivel:
Nota: definir una constante N que almacene el número de elementos del vector V.
do
swapped=0
for i from 0 to N-2 do:
if V[i] > V[i+1] then
swap( V[i], V[i+1] )
swapped = true
end if
end for
while swapped
18. Escriba un programa en lenguaje de alto nivel que llame a una función fact que calcule el factorial de un
número n usando un bucle. Traduzca el programa al lenguaje ensamblador del ARM.
19. Escriba un programa en lenguaje de alto nivel que calcule el factorial de un número n usando recursividad,
sabiendo que fact(n)=n*fact(n-1). Traduzca el programa al lenguaje ensamblador del ARM.
20. Ejercicio 1 (3 puntos). Supongamos que definimos que un número natural es “bonito” si es menor que cien mil y
además su valor puede obtenerse como una suma de números naturales de la forma 1+2+3+4+5+…
Se pide:
a) (1,5 puntos) Escribir un programa en lenguaje ensamblador del ARM tal que dado un número natural N
decida si es o no bonito. El programa escribirá en la variable B un 1 si el número es bonito y un 0 en caso
contrario.
b) (1,5 puntos) Convertir el código anterior en una subrutina que reciba como entrada un número natural N y
devuelva como salida un 1 si el número N es bonito y un 0 si no lo es. Escribir un programa en lenguaje
ensamblador del ARM que llame a la subrutina, y tal que dado un vector A de M números naturales sea
capaz de hallar cuántos números bonitos hay en el vector. El programa debe almacenar la cantidad de
números bonitos hallada en la variable “cuenta_bonitos”.
Nota: Se debe respetar el convenio del ARM visto en clase para llamadas a subrutinas. Además, en ambos
apartados se deben incluir las directivas para reservar memoria y declarar las secciones (.data, .bss y .text)
correspondientes.
21. Responde a las cuestiones suponiendo que el vector V está almacenado a partir de la dirección de memoria
0x0C000000, que el código se encuentra a continuación de los datos y que las pseudo-instrucciones ocupan el
mismo espacio que las instrucciones.
# Codigo 1
.global start
.data
V: .word 12,21,13,14,5,9
N: .word 6
.bss
CuentaTotal: .space 4
.text
start: ldr R0,=V
ldr R2,=N
ldr R1,[R2]
mov R2,#0
mov R3,#0
bucle: cmp R2,R1
beq fin_bucle
ldr R4,[R0]
and R4,R4,#1
add R3,R3,R4
add R2,R2,#1
add R0,R0,#4
b bucle
fin_bucle: ldr R1,=CuentaTotal
str R3, [R1]
b .
.end
#Código 2
.global start
.data
V: .word 12,21,13,14,5,9
N: .word 6
.bss
CuentaTotal: .space 4
.text
start: mov sp,#0x0C200000
ldr R0,=V
ldr R2,=N
ldr R1,[R2]
bl Cuenta
ldr R2,=CuentaTotal
str R0,[R2]
b .
Cuenta: PRÓLOGO_1
mov R4,#0
mov R5,#0
mov R6,R0
mov R7,R1
bucle: cmp R4,R7
beq fin_bucle
ldr R0, [R6]
bl Comprobar
add R5,R5,R0
add R4,R4,#1
add R6,R6,#4
b bucle
fin_bucle: mov R0,R5
EPÍLOGO_1
mov pc,lr
Comprobar: PRÓLOGO_2
mov R4,#1
and R0,R0,R4
EPÍLOGO_2
mov pc,lr
.end
a) ¿En qué dirección de memoria del código 1 está almacenada la variable N? ¿Y la primera instrucción del
bucle para el código 1? Razona las respuestas.
b) ¿Cuál es el contenido final de la variable de memoria CuentaTotal en el código 1? ¿Y de los registros R0,
R1 y R2? Razona la respuesta.
c) Supongamos que queremos estructurar el código con subrutinas, y lo rescribimos en código 2. Completa
el prólogo y epílogo de cada una de las dos subrutinas, explicando por qué incluyes cada instrucción.
22. Dado un vector V de N componentes se dice que es Melchoriforme si posee al menos un elemento Rubio. Un
elemento V[i] es Rubio si satisface la siguiente expresión:
Se pide:
a) Una subrutina SumaVector( V, N ) que sume los N elementos del vector V, respetando el convenio de
llamadas a subrutinas visto en clase.
b) Un programa que dado un vector V y su dimensión N decida si es Melchoriforme, utilizando la subrutina
SumaVector.
23. Un vector V de N números naturales es noeliano si es una secuencia monótona creciente y sus elementos suman
en total 45. Por ejemplo: 0-1-2-3-4-5-6-7-8-9 es noeliano porque 0≤1≤2≤3≤4≤5≤6≤7≤8≤9 y
1+2+3+4+5+6+7+8+9=45. También: 3-5-5-7-10-15 es noeliano, ya que 3≤5≤5≤7≤10≤15 y 3+5+5+7+10+15=45.
Se pide:
a) Escribir una subrutina en ensamblador de ARM Sum45(A, N) que reciba la dirección de comienzo de un
vector A como primer parámetro, el número N de elementos del vector como segundo parámetro y
devuelva 1 si su suma es 45 y 0 en otro caso. La subrutina debe programarse de acuerdo con el estándar
de llamadas a subrutinas que hemos estudiado en clase.
b) Escribir un programa ARM que, utilizando la subrutina anterior, determine si un vector de entrada es
noeliano o no.
FC_2_1_Solucion_V2.pdf
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 1
PROBLEMAS DE FUNDAMENTOS DE COMPUTADORES (HOJA 2.1)
ISA Y DISEÑO DE CPU
1.- ¿Qué modificaciones hay que realizar en la ruta de datos y en la máquina de estados para
añadir la instrucción bne (bifurcar si no igual) que se comporta de manera similar a beq?
Solución:
En la ruta de datos multiciclo no habrá que añadir nada, sólo habrá cambios en la unidad de
control. Habrá que añadir nuevos estados:
2.- Añadir los elementos y puntos de control necesarios a la ruta de datos y a la máquina de
estados finitos para implementar la instrucción addiu.
addiu ri, rj, inmediato // ri = rj + SignExt(inmediato)
Solución
No es necesario realizar ningún cambio en la ruta de datos. En cuanto a la FSM habría que
añadir dos estados:
3.- Deseamos añadir la instrucción j a la ruta de datos. Añadir los elementos y puntos de
control necesarios para realizar esta instrucción. Mostrar los añadidos a la máquina de
ALUout¬ A funct B
BR( rd ) ¬ ALUout
A - B
IR ¬Memoria( PC )
PC ¬ PC + 4
A ¬ BR( rs )
B ¬ BR( rt )
ALUout ¬ A + SignExt( inmed )
MDR ¬Memoria( ALUout )
Memoria( ALUout ) ¬ BBR( rt ) ¬MDR
op = ‘lw’
0
1
2
3
4
57
8
9
PC ¬ PC + 4·SignExt( inmed )
10
Zero = 1
Zero = 0
ALUout ¬ A + SignExt( inmed )
6
A - B
Zero = 1
Zero = 0
11
ALUout¬ A + SignExt(inmediato)
11
op = ‘addiu’
BR(rt) ¬ ALUout
12
0
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 2
estados finitos que se implementó en clase para realizar esta operación.
j dirección // PC=4*dirección, los 4 bits más significativos son los del PC+4
El código de operación de la instrucción j es 000001.
Solución:
M
em
or
ia
ADDR
DR
DW
MemRead
MemWrite
0
1
M
U
X
IorD
Ba
nc
o
de
re
gi
st
ro
s
busA
busB
RA
RB
RW
busW
RegWrite
AL
U
Zero
Ex
te
ns
ió
n
de
si
gn
o
<<
2
PC
A
B
1
0
3
2
0
1
M
U
X
M
U
X
AL
U
ou
t
IR
M
DR
RegDst
0
1
M
U
X
0
1
M
U
X
Instrucción [25-21]
Instrucción [20-16]
Instrucción [15-11]
Instruc. [15-0]
4
PCWrite IRWrite ALUSrcA
ALUSrcB
MemtoReg
AWrite
BWrite
OutWrite
MDRWrite
Control
de ALU
ALUop
Instrucción [25-0] 28
<<
2
(PC+4) [31-28] 4
32
JUMP
1
0
ALUout¬ A funct B
BR( rd ) ¬ ALUout
A - B
IR ¬Memoria( PC )
PC ¬ PC + 4
A ¬ BR( rs )
B ¬ BR( rt )
ALUout ¬ A + SignExt( inmed )
MDR ¬Memoria( ALUout )
Memoria( ALUout ) ¬ BBR( rt ) ¬MDR
op = ‘lw’
0
1
2
3
4
57
8
9
PC ¬ PC + 4·SignExt( inmed )
10
Zero = 1
Zero = 0
ALUout ¬ A + SignExt( inmed )
6
PC ¬ 4 * Inst[25-0]
11
op = ‘j’
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 3
4.- Deseamos añadir la instrucción jal a la ruta de datos multiciclo. Añadir los elementos y
puntos de control necesarios para realizar esta instrucción. Mostrar los añadidos a la
máquina de estados finitos.
jal dirección // ($31= PC+4; PC=4*dir., los 4 bits más significativos son los del PC+4)
El código de operación de la instrucción jal es 0000011.
Solución:
M
em
or
ia
ADDR
DR
DW
MemRead
MemWrite
0
1
M
U
X
IorD
Ba
nc
o
de
re
gi
st
ro
s
busA
busB
RA
RB
RW
busW
RegWrite
AL
U
Zero
Ex
te
ns
ió
n
de
si
gn
o
<<
2
PC
A
B
1
0
3
2
0
1
M
U
X
M
U
X
AL
U
ou
t
IR
M
DR
Instrucción [25-21]
Instrucción [20-16]
Instrucción [15-11]
Instruc. [15-0]
4
PCWrite IRWrite ALUSrcA
ALUSrcB
AWrite
BWrite
OutWrite
MDRWrite
Control
de ALU
ALUop
Instrucción [25-0] 28
<<
2
(PC+4) [31-28] 4
32
JUMP
1
0
MemtoReg
RegDst
2
11111
2
0
1
2
0
2
1
Problemas de Fundamentos de Computadores (Hoja 2.1)
pág. 4
5.- Se está considerando la ampliación del repertorio MIPS con la instrucción addm Rt, Rs,
despl. que suma el contenido del registro Rt con el contenido de la posición de memoria
BR[Rs] + SignExt(despl) y deposita el resultado en Rt. Modifica la ruta de datos y la FSM de
control para incluir esta nueva instrucción.
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 5
Solución
6.- Se desea añadir al procesador multiciclo la instrucción MOVZ, de tipo R:
movz rd, rs, rt # si (BR[rt]==0) entonces BR[rd]ßBR[rs]
Se pide:
a) (1 punto) Completar la ruta de datos de la figura con los elementos que faltan para que
se puedan ejecutar las instrucciones del procesador MIPS estudiadas en clase,
incluyendo además los cambios que tendrían que realizarse para poder ejecutar esta
instrucción.
Solución
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 6
Las operaciones a realizar son:
1. IR ß Mem[PC]; PC ß PC+4
2. A ß BR[rs]; B ß BR[rt]
3. 0-B (zero?) # AluSrcA 3 entradas
4. si zero=1, BR[rd] ß A # MemtoReg 3 entradas
Se amplían entonces los multiplexores ALUSrcA y MemtoReg con una tercera entrada.
b) (1 punto) Añadir los estados necesarios a la máquina de estados (ver figura siguiente)
para poder implementar el control de esta instrucción.
Solución
c) Indicar los valores que van tomando todos los registros implicados en la ejecución de la
instrucción MOVZ R1, R2, R3. El código de operación de la función MOVZ es 000000 y
el valor de los campos SHAMT y FUNCT son 00000 y 100110, respectivamente. El
estado actual de la máquina es:
• R1=0x00000017
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 7
• R2=0x00110011
• R3=0x00000000
• PC=0x00003400
Tras el estado 0:
• PC=0x00003404
• IR=0x00430826 (000000|00010|00011|00001|00000|100110)
Tras el estado 1:
• A=0x00110011
• B=0x00000000
Tras el estado 11:
• ALUOut=0x00000000
Tras el estado 12:
• R1=0x00110011
7.- Se desea añadir al procesador multiciclo la instrucción JALR Rd, Rs, con el formato tipo R
pero código de operación 001001:
JALR Rd, Rs # Temp <- BR[Rs], BR[Rd] <- PC+8 , PC <- Temp
Nótese que Temp no es un registro físico, sino que se introduce en la descripción para
aclarar qué ocurre en el caso de que Rs=Rd: en PC se escribe el valor antiguo de Rs, antes de
que este mismo registro se actualice con el valor PC+8.
a) Indica todos los cambios que tendrían que realizarse a la ruta de datos para poder ejecutar
esta instrucción.
Solución:
Hay dos posibles soluciones, A y B.
A. Añadiendo un nuevo mux para seleccionar lo que se va a escribir en PC, con su señal de
control
5. IR ß Mem[PC]; PC ß PC+4
6. A ß BR[rs]; B ß BR[rt]
7. AluOut <- PC + 4, PC <- A # Es necesario un nuevo mux para PC
8. BR[Rd] <- AluOut
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 8
B. Modificando la selección del operando B para poder seleccionar 0
1. IR ß Mem[PC]; PC ß PC+4
2. A ß BR[rs]; B ß BR[rt]
3. AluOut <- PC + 4
4. BR[Rd] <- AluOut, PC<-A+0
b) Describir los cambios necesarios en la máquina de estados del controlador para poder
ejecutar correctamente esta instrucción.
Las modificaciones en el controlador son similares en los dos casos también:
A
M
em
or
ia
(
ADDR$
DR$
DW$
MemRead'
MemWrite'
0$
1$
M
U
X(
IorD'
Ba
nc
o(
de
(
re
gi
st
ro
s(
busA$
busB$
RA$
RB$
RW$
busW$
RegWrite'
AL
U
(
Zero'
Ex
te
ns
ió
n(
(
de
(si
gn
o(
<<
2(
PC
(
A(
B(
1$
0$
3$
2$
0$
1$
M
U
X(
M
U
X(
AL
U
ou
t(
IR
(
M
DR
(
RegDst'
0$
1$
M
U
X(
0$
1$
M
U
X(
Instrucción$[25721]$
Instrucción$[20716]$
Instrucción$[15711]$
Instruc.$[1570]$
4"
PCWrite' IRWrite' ALUSrcA'
ALUSrcB'
MemtoReg'
AWrite'
BWrite'
OutWrite'
MDRWrite'
Control((
de(ALU(
ALUop'
M
U
X(
0$
1$
PCSrc'
M
em
or
ia
(
ADDR$
DR$
DW$
MemRead'
MemWrite'
0$
1$
M
U
X(
IorD'
Ba
nc
o(
de
(
re
gi
st
ro
s(
busA$
busB$
RA$
RB$
RW$
busW$
RegWrite'
AL
U
(
Zero'
Ex
te
ns
ió
n(
(
de
(si
gn
o(
<<
2(
PC
(
A(
B(
1$
0$
3$
2$
0$
1$
M
U
X(
M
U
X(
AL
U
ou
t(
IR
(
M
DR
(
RegDst'
0$
1$
M
U
X(
0$
1$
M
U
X(
Instrucción$[25721]$
Instrucción$[20716]$
Instrucción$[15711]$
Instruc.$[1570]$
4"
PCWrite' IRWrite' ALUSrcA'
ALUSrcB'
MemtoReg'
AWrite'
BWrite'
OutWrite'
MDRWrite'
Control((
de(ALU(
ALUop'
0$
1$
M
U
X(
0"
ALUSrcB2l'
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 9
B
c) (1 punto) Indica los valores que van tomando todos los registros implicados en la ejecución
de la instrucción JALR R1,R3, sabiendo que los campos Rt, SHAMT y FUNCT se dejan a 0.
El estado actual de la máquina es:
• R0=0x000000FA
• R1=0x00000030
• R2=0x0C001600
• R3=0x0C00E040
• PC=0x0C000020
Apartado C:
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 10
Caso A:
1. En Fetch:
• PC toma el valor 0x0C000024
• IR toma el valor 0x24600800
2. En Deco:
• A toma el valor 0x0C00E040
• B toma el valor 0x000000FA
3. En Exe;
• AluOut toma el valor 0x0C000028
• PC toma el valor 0x0C00E040
4. En WB:
• R1 toma el valor 0x0C000028
Caso B:
5. En Fetch:
• PC toma el valor 0x0C000024
• IR toma el valor 0x24600800
6. En Deco:
• A toma el valor 0x0C00E040
• B toma el valor 0x000000FA
7. En Exe;
• AluOut toma el valor 0x0C000028
8. En WB:
• R1 toma el valor 0x0C000028
• PC toma el valor 0x0C00E040
8.- Sobre la ruta de datos vista en clase, indicar los valores de todas las líneas de datos y los
registros, en los siguientes casos:
a) Ejecución de la instrucción OR r1, r2, r3, al final de cada una de sus cuatro etapas
Estado actual de la máquina:
r1=0x00000017
r2=0x001100FF
r3=0xFF000345
PC=0x00003400
b) Ejecución de la instrucción JAL 1024 (1024 en decimal) al final de las tres etapas
Estado actual de la máquina:
r0=0x00000017
PC=0x00003400
Solución
OR:
a) Tras el estado 0:
a. PC=0x00003404
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 11
b. IR=0x00430825 (Codificación de la or:
000000|00010|00011|00001|00000|100101)
b) Tras el estado 1:
a. A=0x001100FF
b. B=0xFF000345
c) Tras el estado 7:
a. ALUOut=0xFF1103FF
d) Tras el estado 8:
a. R1=0xFF1103FF
JAL:
a) Tras el estado 0:
a. PC=0x00003404
b. IR=0x0C000400 (Codificación de jal: 000011|00000000000000010000000000)
b) Tras el estado 1:
a. A=0x00000017
b. B=0x00000017
c) Tras el estado último del jal:
a. R31=0x00003404
b. PC=0x00001000
9.- Para el computador MIPS estudiado en clase, responder a las siguientes preguntas:
a) Qué instrucción/es, del repertorio de instrucciones del procesador MIPS estudiado en
clase, se ven afectada/s y no se podrían ejecutar si se elimina de la ruta de datos el
registro MDR, la entrada 1 del Mux que selecciona el dato que se escribe en el banco de
registros, y por lo tanto dicho Multiplexor.
La instrucción load, porque con ese cambio la ruta de datos no permite escribir el dato
leído de memoria en el banco de registros
b) Partiendo de la ruta de datos completa del MIPS, se desea añadir una nueva instrucción
Store con Direccionamiento Absoluto (SMDA). Se añade para ello un nuevo formato de
instrucción con los siguientes campos (Op, Rs, dirección):
El comportamiento de la instrucción SMDA sería el siguiente:
SMDA Rs, dirección Mem[ExtCeros(dirección)] ß BR[rs]
donde ExtCeros(dirección) extiende la dirección de 21 bits a 32 bits añadiendo ceros
por la izquierda. Añade a la ruta de datos los cambios que tendrían que realizarse para
poder ejecutar esta instrucción.
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 12
c) Añade los cambios necesarios en el diagrama de transición de estados del controlador
para poder ejecutar correctamente esta nueva instrucción.
d) Indicar los cambios necesarios en la tabla de verdad del controlador (añadir las filas y
columnas
necesarias).
10.- Suponer que los tiempos de operación para las principales unidades funcionales de una
implementación MIPS son:
• Lectura unidad de memoria: 10 ns
• Escritura unidad de memoria: 5 ns
• ALU: 10 ns
• Banco de registros (lectura o escritura): 5 ns
• Multiplexores: 2 ns
• Extensor de signo: 1 ns
• Desplazador:0.5 ns
a) Suponiendo que el resto de elementos no tengan retardo (no hay retardo de la unidad
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 13
de control, de la lectura o escritura de los registros temporales, del cableado, etc.),
calcula la frecuencia de reloj máxima a la que podría trabajar este procesador.
b) Calcula el tiempo de ejecución en el procesador multiciclo de un programa con la
siguiente frecuencia de uso de las diferentes instrucciones y que conste de 1000
instrucciones:
• Carga: 22%
• Almacenamiento: 11%
• Formato R: 49%
• Salto condicional: 18%, donde la mitad de los saltos se toman.
Solución
Estado 0:
a. Escritura del PC: 2+10
b. Escritura de IR: 2+10
Estado 1: 5
Estado 2: 1+2+10 (la extensión de signo se puede asumir que ya esté calculada de antes)
Estado 3: 2+10
Estado 4: 2+5
Estado 5: 1+2+10 (la extensión de signo se puede asumir que ya esté calculada de antes)
Estado 6: 2+5
Estado 7: 2+10
Estado 8: 2+5
Estado 9: 2+10
Estado 10: 1+0.5+2+10 (la extensión y el x4 se puede asumir ya calculado de antes)
La etapa más lenta limita el tiempo de ciclo
Tciclo = 13.5 ns => f = 1/13.5 GHz = 74 MHz
El número de ciclos promedio por instrucción viene dado por
(lw: 5, sw/r: 4, beq:3)
CPI = 0.22*5+0.11*4+0.49*4+0.18*3.5 = 4.13
De donde
Tcpu = NI*CPI*Tciclo = 1000*4.13*13.5 = 55755 ns
11.- Un programa tiene 140 instrucciones de las cuales 70 tardan en ejecutarse en un
determinado procesador cuatro ciclos, 35 tardan cinco ciclos, 20 tardan tres ciclos y las 15
restantes tardan siete ciclos. Calcule el CPI promedio para dicho programa. Si el procesador
funciona a una frecuencia de 2.0 GHz, determine el tiempo de ejecución del programa.
SOLUCIÓN:
Tipo instr nºinst nºciclos/inst
A 70 4
B 35 5
C 20 3
D 15 7
Nº total inst=140
CPI=(70*4+35*5+20*3+15*7)/140=4.4285 ciclos
Tiempo_ejecucion=CPI*nºint/frecuencia=140*4.4285/2*109=310ns
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 14
12.- Se dispone de los siguientes datos de dos procesadores y de su rendimiento en la
ejecución de una determinada tarea:
• PowerPC que funciona a una frecuencia de 1.8 GHz y obtiene 700 MIPS.
• Pentium 4 que funciona a 1.6 GHz y 850 MIPS.
Calcule el CPI de cada procesador.
SOLUCIÓN:
Procesador Frecuencia MPIS
PowerPc 1.8GHz 700
Pentium4 1.6GHz 850
CPIPowerPC=1.8*109 [ciclos/s] / 700*106 [instr/s] = 2.57 [ciclos/instr]
CPIPentium4=1.6*109 [ciclos/s] / 850*106 [instr/s] = 1.88 [ciclos/instr]
13.- Considere los dos procesadores del ejercicio anterior. En la ejecución de un determinado
programa los procesadores obtienen un CPI de 5.5 (PowerPC) y 7 (Pentium 4). El
compilador genera un código máquina para dicho programa que tiene 9 millones de
instrucciones (PowerPC) y 7.2 millones de instrucciones (Pentium) ¿Qué computador
ejecutará más rápidamente la tarea?
SOLUCIÓN:
TiempoPowerPC= 9*106 [instr] *5.5 [ciclos/instr] / 1.8*109 [ciclos/s] = 0.0275s = 27.5ms
TiempoPentium4=7.2*106 [instr] * 7 [ciclos/instr] / 1.6*109 [ciclos/s] = 0.0315s = 31.5ms
14.- Se desea añadir al procesador multiciclo la instrucción BEQAL Rs, Rt, Offset con código de
operación 000001, cuyo comportamiento es:
Si Rs = Rt
R31 <- PC + 4;
PC <- PC + 4 + 4*Offset;
Si no
PC <- PC + 4
Se pide:
a) Indica todos los cambios que tendrían que realizarse a la ruta de datos para poder
ejecutar esta instrucción.
b) Describir los cambios necesarios en el diagrama de transición de estados del controlador
para poder ejecutar correctamente esta instrucción.
c) Indicar los cambios necesarios en las tablas de verdad del controlador.
Solución :
a) La instrucción tendrá formato I, ya que el offset se da como operando inmediato. Los
movimientos registro a registro que hay que hacer son:
1. IR ß Mem[PC]; PC ß PC+4
2. A ß BR[rs]; B ß BR[rt]
3. A - B
4. PC<- PC + 4*SignExt( Inmediato ) y BR(31) <- PC (PCorig + 4 )
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 15
b) Las modificaciones en el controlador son:
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 16
c)
15.- Ejercicio 4 Un mismo programa se ejecuta en dos computadores A y B que tienen
frecuencias de reloj de 1 GHz y 1.5 GHz, respectivamente. Para ejecutar el programa en A es
necesario ejecutar un cierto número de instrucciones repartidas de la siguiente manera:
Aritmética Load Store Salto tomado Salto no
tomado
Frecuencia 50% 25% 10% 10% 5%
Ciclos 4 5 4 4 3
a) Calcula el CPI del programa en el computador A.
b) En el computador B el número de instrucciones ejecutadas es el 60% de las ejecutadas en
A y el tiempo de ejecución es la mitad que en A. ¿Cuál es el CPI obtenido en la ejecución
del programa en el computador B?
SOLUCIÓN
Solución:
CPI(A) = 4x0,5 + 5x0,25 + 4x0,10 + 4x0,10 + 3x0,05 = 4,2
Datos: T(B) = 0,5xT(A); NI(B) = 0,6xNI(A)
Tiempo en A: T(A) = NI(A) x CPI(A) / f(A)
Tiempo en B: 0,5xT(A) = 0,6xNI(A) x CPI(B) / f(B)
E
st
ad
o
ac
tu
al
op
Ze
ro
E
st
ad
o
si
gu
ie
nt
e
IR
W
rit
e
P
C
W
rit
e
A
W
rit
e
B
W
rit
e
A
LU
S
rc
A
A
LU
S
cr
B
A
LU
O
p
O
ut
W
rit
e
M
em
W
rit
e
M
em
R
ea
d
Io
rD
M
D
R
W
rit
e
M
em
to
R
eg
R
eg
D
es
t
R
eg
W
rit
e
0000 XXXXXX X 0001 1 1 0 01 00 (add) 0 1 0 0
0001 100011 (lw) X 0010
0 0 1 1 0 0 0
0001 101011 (sw) X 0101
0001 000000 (tipo-R) X 0111
0001 000100 (beq) X 1001
0001 000001 (beqal) X 1011
0010 XXXXXX X 0011 0 0 1 10 00 (add) 1 0 0 0
0011 XXXXXX X 0100 0 0 0 1 1 1 0
0100 XXXXXX X 0000 0 0 0 0 01 00 1
0101 XXXXXX X 0110 0 0 0 1 10 00 (add) 1 0 0 0
0110 XXXXXX X 0000 0 0 1 0 1 0
0111 XXXXXX X 1000 0 0 1 00 10 (funct) 1 0 0 0
1000 XXXXXX X 0000 0 0 0 0 00 01 1
1001 XXXXXX 0 0000
0 0 1 00 01 (sub) 0 0 0
1001 XXXXXX 1 1010
1010 XXXXXX X 0000 0 1 0 11 00 (add) 0 0 0
1011 XXXXXX 0 0000 0 0 1 00 01 (add) 0 0 0
1011 XXXXXX 1 1100 0 0 1 00 01 (add) 0 0 0
1100 XXXXXX X 0000 0 1 0 11 00 (add) 0 0 10 10 1
Problemas de Fundamentos de Computadores (Hoja 2.1) pág. 17
0,5 = [0,6xCPI(B) / f(B)] / [ CPI(A) / f(A)] = 0,6 x CPI(B) x f(A) / CPI(A) x f(B)
CPI(B) = 0,5 x CPI(A) x f(B) / 0,6 x f(A) = 0,5x4,2x1,5x109 / 0,6x1x109 = 3,15 / 0,6 = 5,25