Ejercicios Tema 8 Con soluciones PDF

Preview

Summary

+fHOJA DE PROBLEMAS 8: ELEMENTOS DE MEMORIA1. Se desea diseñar un circuito que calcule el bit de paridad par sobre los ceros (devolver un 0 si el número de 0s es impar y un 1 en caso contrario) de una secuencia de 3 bits. Dicha secuencia se recibirá de forma serie por una única línea. Mientras la se...

Description

Universidad Rey Juan Carlos Grado en Ingeniería Informática

Fundam

HOJA DE PROBLEMAS 8: ELEMENTOS DE MEMORIA 1. Se desea diseñar un circuito que calcule el bit de paridad par sobre los ceros (devolver un 0 si el número de 0s es impar y un 1 en caso contrario) de una secuencia de 3 bits. Dicha secuencia se recibirá de forma serie por una única línea. Mientras la secuencia esté incompleta la salida del circuito tendrá valor 0. a) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Moore. b) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Mealy. 2. Sea un sistema secuencial con una entrada binaria X de un bit y una salida binaria Z de un bit capaz de detectar la secuencia baa. S is te m a s e c u e n c ia l

X

Z

Z =q

si los últimos tres datos son : baa p

caso contrario

Se pide: c) Representar el sistema (máquina de Mealy) en forma de diagrama de estados y tabla de estados. d) Elegir una codificación, representar la tabla de estados con dicha codificación, expresar las funciones de próximo estado y de salida como suma de minterms. e) Minimizar mediante diagrama de Karnaugh las funciones de próximo estado y de salida. f) Materializar el sistema secuencial utilizando puertas lógicas y biestables tipo D (Delay) con reset asíncrono. 3. Diseñar un sistema secuencial con una entrada binaria X y una única salida Z que detecte tres o más unos consecutivos en la línea de entrada X. X

Sistema Secuencial

Z

1 si los tres últimos datos son 111

a) Especificar y explicar cuáles son los estados que ha de tener el sistema si se trata de como máquina de Moore. b) Especificar y explicar cuáles son los estados que ha de tener el sistema si se trata de como máquina de Mealy. c) Elegir el tipo de FSM que proporcione la salida antes, e implementar el circuito empleando el menor número de puertas posible. Solución: a) Considerando el circuito como una Máquina de Moore, el valor de la salida del sistema depende exclusivamente del estado. Podemos distinguir cuatro estados para indicar si en los últimos datos hay 0, 1, 2 ó 3 unos. Solamente en el último estado (cuando se han detectado 3 unos seguidos) la salida del sistema vale 1. El diagrama de estados resulta: Página 1 de 34

b) Considerando el circuito como una Máquina de Mealy, el valor de la salida depende, no sólo del estado, sino también del valor actual de la entrada. Por ello, esta salida está asociada, no a cada estado (como en Moore), sino a cada una de las transiciones. En este caso, son necesarios sólo 3 estados, correspondientes a 0, 1 ó 2 unos seguidos. Efectivamente, para el estado 2, si se recibe un nuevo uno, la secuencia ‘111’ quedaría ya identificada y la salida sería 1. En caso contrario, la salida sería 0. El diagrama de transición de estados resulta:

Como puede verse, con la Máquina de Mealy se obtiene un estado menos que con la Máquina de Moore y, por tanto, la secuencia ‘111’ se detectaría antes. En ambos casos, serían necesarios dos biestables para almacenar los estados.

Página 2 de 34

Página 3 de 34

Página 4 de 34

4. Diseñar e implementar el autómata de Mealy capaz de detectar en la línea de entrada X la secuencia 1011, teniendo en cuenta posibles solapamientos en la secuencia.

X

Sistema Secuencial

Z =

1 si los cuatro últimos datos son 1011

a) b) c) d)

Obtener el diagrama de transición de estados, incluyendo sus entradas y sus salidas. Obtener la tabla de transición de estados y salidas. Obtener la tabla de transición de estados, entradas, salidas y estados codificada en binario. Obtener las tablas de excitación y salida del autómata (se utilizarán para ello únicamente biestables D). e) Obtener las expresiones mínimas para la función de transición de estados y la función de salida.

a)

Página 5 de 34

Página 6 de 34

Página 7 de 34

5. Diseñar un sistema secuencial con una entrada binaria X y una única salida Z que detecte la secuencia 0101.

X

Sistema Secuencial

Z

1 si los cuatro últimos datos son 0101

Utilizar biestables tipo D para la implementación del mismo. Para el diseño, seguir los pasos indicados a continuación: a) Escribir una secuencia de simulación cualquiera: X= Z= b) Especificar y explicar cuáles son los estados que ha de tener el sistema. Representar el sistema (máquina de Mealy) en forma de diagrama y tabla de estados. c) Realizar una asignación de estados, y escribir la tabla de transiciones y de salida del sistema. d) Dar las expresiones de las funciones de entrada a los elementos de memoria (funciones de estado siguiente) y de salida simplificadas. e) Dibujar el circuito resultante. 6. Se desea diseñar una máquina de estados finitos que detecte la secuencia 1001. La entrada será X y recibirá una secuencia de bits en serie. La salida Z valdrá 1 cuando se detecte la secuencia y 0 el resto del tiempo. Hay que tener en cuenta los posibles solapes de la secuencia. a) Diseñar el diagrama de transición de estados como una máquina de estados finitos de Mealy. b) Diseñar el diagrama de transición de estados como una máquina de estados finitos de Moore. c) Sintetizar la máquina de estados finitos del apartado a) usando al menos un biestable J-K y un biestable D, ambos síncronos por flanco de subida. Las entradas de los biestables J-K se deberán obtener mediante puertas lógicas mientras que las entradas de los biestables D se deberán obtener usando un decodificador y las puertas que se consideren necesarias. Razonar todas las decisiones que se tomen. 7. Obtener el diagrama de estados, como máquina de Mealy y de Moore de un sumador serie. Este sumador posee dos entradas binarias, A y B, de un bit y una salida binaria, S, de un bit que operan del siguiente modo: los datos entran bit a bit por las dos entradas en paralelo comenzando por el bit menos significativo, generándose la salida bit a bit también comenzando por el bit menos significativo. Por ejemplo: A>110010000100... B>111101001010... S>010000101110...

Solución: Para sintetizar este circuito como una máquina de Moore, debemos identificar los estados de tal forma que el valor de la salida sea el mismo para todas las transiciones que parten de cada estado. Para hacer la suma correctamente, debemos recordar el valor del bit de suma anterior s, así como el del acarreo de salida anterior c. Podemos considerar por tanto cuatro posibles estados, en función de las cuatro posibilidades según los valores de s y c. El diagrama de estados resulta:

Página 8 de 34

La tabla de transición de estados es: Estado

Próximo estado:

actual

C(t+1) S(t+1)

Salida

C(t) S(t)

AB: 00

01

10

11

Z

00

00

01

01

10

0

01

00

01

01

10

1

10

01

10

10

11

0

11

01

10

10

11

1

8. Para el diagrama de estados de la Según la figura, se pide responder a las siguientes cuestiones: a) ¿Qué tipo de máquina de estados es? b) Realizar una materialización con biestables JK, 4 multiplexores de 4 a 1 y el menor número posible de puertas lógicas básicas. c) Realizar una materialización con el menor número posible de puertas básicas y biestables tipo D. 0 /0

1 /0 0 /0

S 3

1 /0

S 0

1 /0

S 1

0 /0

S 2

1 /1 0 /0

9. Para el diagrama de estados de la figura, se pide responder a las siguientes cuestiones: a) ¿Qué tipo de máquina de estados es? b) Realizar una materialización con biestables JK, 2 decodificadores de 3 a 8 y el menor número posible de puertas lógicas básicas. c) Realizar una materialización con el menor número posible de puertas básicas y biestables tipo D.

Página 9 de 34

1/0 1/0

0/0 0/0

S0

Inicio

1/0 S2

S1

0/0

0/0

1/0

S3

0/0

1/1 1/0 S6

1/0

0/0 S5

S4

0/0

10. Dado el siguiente diagrama de transición de estados de un autómata de estados finitos, sintetizar el circuito correspondiente usando los biestables D (síncronos por flanco de subida), los decodificadores y el mínimo número de puertas lógicas que se consideren necesarias.

Usar la codificación que se indica en las siguientes tablas: X A B C D

X1 0 0 1 1

X0 0 1 0 1

Z ABIERTO CERRADO

Z0 0 1

11. Dado el diagrama de estados de la figura siguiente, realizar una materialización canónica con tres biestables de tipo D y: a) Dos multiplexores de 8 a 1 y puertas básicas. b) Ó una única PLA. c) Ó una única ROM.

Página 10 de 34

12. Especificar y diseñar (con puertas básicas y biestables flip-flop tipo SR disparados por flanco de subida) un sistema secuencial capaz de seguir dos secuencias de cuenta en función de una señal de control denominada X, tal que: Si X=a Cuenta=0,1,2,3,4,5,6,7. Si X=b Cuenta=7,6,5,4,3,2,1,0. Cuando la entrada cambie de X=a a X=b o viceversa el sistema (contador reversible módulo 8) continuará realizando la cuenta a partir del lugar en que se encontraba. El sistema mostrará como salida Z el valor de la cuenta. Se diseñará como una máquina de Moore síncrona por flanco de subida. a) Realizar la representación formal del sistema mediante un diagrama de estados y una tabla de estados para la máquina de Moore equivalente. b) Codificar los estados, las entradas y las salidas en binario. c) Materializar el circuito mediante las puertas lógicas y biestables SR disparados por flanco de subida. d) Materializar el circuito mediante una ROM y biestables JK disparados por flanco de subida. 13. Se desea diseñar un circuito que controle una máquina de empaquetado de naranjas. Los paquetes que se crearán deberán contener 3 naranjas. El sistema consta de un sensor que le proporciona a nuestro circuito un “1” cuando se recibe una naranja y un “0” en caso contrario. El circuito que se debe construir generará una salida que será “1” en caso de querer activar la máquina encargada de empaquetarlas y un “0” cuando todavía no se hayan recibido naranjas suficientes para hacer un paquete. Hay que tener en cuenta que antes de recibir ninguna naranja el sistema no debe activar la maquina empaquetadora. También se ha de tener en cuenta que el número de naranjas, y por tanto de paquetes, no está limitado.

a) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Moore. b) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Mealy. c) Sintetizar el circuito correspondiente al diagrama del apartado a) usando los biestables D (síncronos por flanco de subida), los decodificadores y las puertas lógicas que se consideren necesarias. Razonar todas las decisiones tomadas. 14.

Se desea diseñar un circuito que controle la apertura de una caja fuerte. Para abrir la caja fuerte es necesario introducir la secuencia de teclas correcta. Para ello se dispone de un teclado con cuatro teclas W, X, Y, Z. La secuencia que abre la caja fuerte será “W W Z”. La salida del circuito será ABIERTO, CERRADO indicando la apertura o no de la caja. La caja inicialmente se encuentra cerrada. Página 11 de 34

Una vez introducida la contraseña correcta cualquier pulsación de tecla hará que la caja se cierre se y contará como tecla para una nueva secuencia.

a) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Moore. b) Diseñar el diagrama de transición de estados usando una máquina de estados finitos de Mealy. c) Sintetizar el circuito correspondiente al diagrama del apartado b) (Mealy) usando los biestables D (síncronos por flanco de subida) y las puertas lógicas que se consideren necesarias. Razonar todas las decisiones tomadas. Nota: Se codificarán las entradas y las salidas usando la siguiente tabla: X W X Y Z

X1 0 0 1 1

X0 0 1 0 1

ABIERTO CERRADO

Z0 0 1

15. Un motor dispone de un pulsador P. Si el motor esta parado y se pulsa P, el motor no se pondría en marcha hasta que se soltara P. De igual forma si el motor esta en marcha y se pulsa P, el motor no se pararía hasta que se soltara P. Es decir, la activación o desactivación se produce por paso de 1 a 0. Por ejemplo, comenzando el motor parado, para que se active, su pulsador deberá pasar primero a activo (el motor estará en proceso de encendido) y después a inactivo (el motor pasará a estar encendido). De igual manera se realizará el paso de encendido a parado. Entrada del sistema : P (1 bit)= Salida del sistema : Z (1 bit) =

1 el pulsador está pulsado 0 el pulsador no está pulsado

1 si el motor está en marcha 0 si el motor está parado

Utilizar biestables tipo D para la implementación del mismo. a) Representar el sistema en forma de diagrama de estados y de tabla de estados suponiendo que vamos a implementarlo como una maquina de Moore. b) Representar el sistema en forma de diagrama de estados y de tabla de estados suponiendo que vamos a implementarlo como una maquina de Mealy. c) ¿Cuál es la diferencia principal entre una máquina de estados de Mealy y una de Moore? d) Realizar una asignación de estados, y escribir la tabla de transiciones y de salida del sistema para la máquina de Mealy e) Dar las expresiones de las funciones de entrada a los elementos de memoria (funciones de estado siguiente) y de salida simplificadas. f) Dibujar el circuito resultante.

Página 12 de 34

1

Página 13 de 34

Página 14 de 34

Página 15 de 34

16. Un limpiaparabrisas tiene pulsadores de marcha y paro, M y P. Si se pulsa M se activa, si se pulsa P se para, además es prioritario el pulsador de parada. Se pide: a) Representar el sistema en forma de diagrama de estados y de tabla de estados suponiendo que vamos a implementarlo como una maquina de Mealy. b) Cuál es la diferencia principal entre una máquina de estados de Mealy y una de Moore? c) Realizar una asignación de estados, y escribir la tabla de transiciones y de salida del sistema. d) De las expresiones de las funciones de entrada a los elementos de memoria (funciones de estado siguiente) y de salida simplificadas. e) Dibujar el circuito resultante. 17. Se desea diseñar un contador ascendente de 0 a 3 con entrada de habilitación de cuenta y salidas de fin de cuenta, con biestables (tipo T o tipo D), el que se crea más conveniente),y puertas lógicas. Este contador deberá implementarse como una máquina secuencial de estados finitos (FSM) tipo Mealy. La especificación binaria del sistema es la siguiente:

Página 16 de 34

Entradas: CLEAR: puesta a 0 asíncrona (activa por nivel alto). CE: habilitación de cuenta (activa por nivel alto). CLK: reloj. Salidas: Q1 y Q0 (SSD): salidas de datos. TC: se pone a 1 cuando el contador llega al final de la cuenta. RCO: se pone a 1 cuando el contador llega al final de la cuenta, y además la cuenta está habilitada

Función:

a) Obtener el diagrama de transición de estados del contador, incluyendo sus entradas y sus salidas. b) Obtener la tabla de transición de estados y salidas del contador. c) Obtener la tabla de transición de estados, entradas, salidas y estados del contador codificadas en binario. d) Obtener las tablas de excitación y salida del autómata (Se recuerda que se deben usar biestables T). e) Obtener las expresiones mínimas para la función de transición de estados y la función de salida. f) Representar gráficamente el esquema de interconexión del contador.

17

18

19

18. Se desea diseñar un registro de dos bits de desplazamiento a la izquierda como Máquina Finita de Estados tipo Moore. Las entradas y salidas del sistema son las siguientes: - E0: entrada de datos - X1 X0: contenido del registro en cada momento (Valor inicial X1 X0 = 0 0 ) a) Realizar la representación formal del sistema mediante un diagrama de estados y una tabla de transición de estados y salidas para la máquina de Moore equivalente. b) Codificar las entradas, los estados y las salidas en binario. Representar la tabla de excitación del autómata y salida. c) Materializar el circuito mediante puertas lógicas y biestables D disparados por flanco de subida.

20

19. Especificar y diseñar un sistema secuencial capaz de seguir dos secuencias de cuenta en función de una señal de control denominada A. • Si A = 1, Secuencia = 0, 2, 4, 6, 1, 3, 5, 7, 0, 2, ... • Si A = 0, Secuencia = 7, 5, 3, 1, 6, 4, 2, 0, 7, 5, ... La salida del sistema es precisamente el valor de la secuencia. Se pide: a) Realizar la representación formal del sistema mediante un diagrama de estados para la máquina de Moore equivalente. ¿Cuántos biestables serán necesarios?

21

b) Escribir la tabla de transición de estados codificada en binario, así como la tabla de excitación de los biestables, considerándolos de tipo D síncronos por flanco de subida. c) Simplificar la tabla de excitación del apartado anterior por el método de Karnaugh. Será imprescindible dibujar explícitamente los grupos e indicar claramente la expresión simplificada que le corresponde a cada uno. d) Dibujar el circuito con las puertas lógicas auxiliares que se crean necesarias. Se valorará positivamente la claridad del dibujo, con lo que se recomienda poner nombres a los cables. Solución: a) El diagrama de transición de estados es el siguiente:

Se ha dibujado en cada estado el valor de la secuencia. Las flechas corresponden al valor de la entrada A en los flancos de subida del reloj. En total identificamos 8 estados, que pueden ser codificados con 3 biestables (23 = 8). b) La tabla de transición de estados expresada en base decimal es:

22

La tabla de transición de estados codificada en binario resulta:

La tabla anterior se ha aprovechado la propiedad fundamental de los biestables D (D=Q) para incorporar también la tabla de excitación de los mismos. c) Simplificamos por Karnaugh las tres variables Q2’ Q1’ Q0’. Vamos a simplificar por minitérminos.

23

d) A continuación se incluye el circuito.

24

25

20. Diseñar un autómata de Moore que implemente un contador módulo 8 según la línea de control E0 (modo de contar). Si E0=1 cuenta ascendentemente y si E0=0 se mantiene en su número de cuenta. En el paso de reposo (E0=0) a contaje, el nuevo estado será el posterior al actual. Por ejemplo, de 4 en reposo pasará al 5.

26

27

28

29

30

31

32

33

34...