Practica Final 2018 PDF

Preview

Summary

PrácticaPresentaciónPor fin llegamos al final del curso. Esta práctica servirá para sintetizar todos los conocimientos del curso y ampliarlos con el diseño de circuitos más complejos. Enesta práctica se os pedirá el diseño de un circuito a partir de un grafo de estados y el diseño de una máquina de ...

Description

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Práctica Presentación Por fin llegamos al final del curso. Esta práctica servirá para sintetizar todos los conocimientos del curso y ampliarlos con el diseño de circuitos más complejos. En esta práctica se os pedirá el diseño de un circuito a partir de un grafo de estados y el diseño de una máquina de estados en concreto. Para la primera parte, tendréis que aplicar los conocimientos que habéis adquirido en este curso, como por ejemplo el de los sistemas de representación. Por lo tanto, se recomienda que le deis un vistazo.

Competencias Conocer la organización general de un computador como circuito digital y conocer las características distintivas de la arquitectura de Von Neumann.

Objetivos — Conocer varios modelos de máquinas de estados y las arquitecturas de controlador con camino de datos. — Haber adquirido una experiencia básica en la elige del modelo de máquina de estados más adecuado para la resolución de un problema concreto. — Ser capaz de diseñar circuitos secuenciales a partir de grafos de transiciones de estados.

Recursos Los recursos que se recomienda usar para esta práctica son los siguientes: Básicos: El módulo 5 de los materiales. Complementarios: VerilCIRC, VerilCHART y el Wiki de la asignatura.

Criterios de valoración — Razonad la respuesta en todos los ejercicios. Las respuestas que no estén justificadas no recibirán puntuación. — La valoración de cada apartado está indicada en los enunciados correspondientes.



1 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Formato y fecha de entrega — Para dudas y aclaraciones sobre el enunciado, dirigíos al consultor responsable de vuestra aula. — Hay que entregar la solución en un fichero PDF usando una de las plantillas entregadas conjuntamente con este enunciado. — Se tiene que entregar a través de la aplicación de Entrega y registro de EC del apartado Evaluación de vuestra aula. — La fecha límite de entrega es el 20 de Diciembre (a las 24 horas).

Ejemplo de solución PRIMERA PARTE [65%] Los vehículos autónomos que circulan sobre raíles tienen varias ventajas. Uno de estas ventajas es que los módulos de control pueden llegar a ser muy simples. La EFSM siguiente corresponde a un módulo de control de movimiento muy sencillo de uno de estos vehículos. g·d’ g’

g·d’

STOP / m+ = 0, C + = 0, w= 0

FWD / m+ = 1, C+ = C, w =0

g’

g·d g·d

g’

WAIT / m+ = 0, C+ = C+1, w =1

g·d’

g·d

Fig. 1. EFSM del módulo controlador de movimiento de un vehículo sobre raíles.

Básicamente, se ocupa de comprobar si la orden de avanzar está activa (g=1) y de si hay ningún obstáculo en la vía (d=1) para decidir si avanza (FWD), espera (WAIT) o se para completamente (STOP). La diferenciación entre el estado de espera (WAIT) y el de parada (STOP) permite contar, a través de la variable C, el tiempo que permanece parado en un trayecto por obstáculos en la vía.



2 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Se pide lo siguiente: a) [15%] A partir del grafo de la EFSM de la fig. 1 completad, en el cronograma siguiente, la evolución de las señales C, m y w, y del estado en que se encuentra la máquina en cada ciclo de reloj. Nota: Tenéis el ejercicio disponible en VerilChart, donde los valores de la señal C se representan en hexadecimal y estado por E.

clk d g C

3

m w estado

FWD

t0

t1

t2

t3

t4

t5

t6

t7

t8

A partir de las condiciones iniciales que hay en el cronograma (estado=FWD, m=0 C=3, g=1, d=0) se puede determinar cuál debe ser el estado siguiente y los valores en este estado para m y C. El valor de w depende de forma exclusiva y combinacional del estado actual. Así pues, para determinar el estado y los valores de m y de C a partir de t0 y hasta t1, hay que observar que, estando en FWD, los valores para el estado siguiente de m y C son 1 y el mismo valor de C (3), respectivamente. Además, con g=1 y d=0 se cumple que g·d’ es 1 y, por tanto, el estado siguiente es el mismo FWD. El valor para w es 0 porque el estado es FWD. Siguiendo este procedimiento, se pueden determinar los valores para el periodo t1-t2 a partir de los del periodo anterior y se puede ir repitiendo el procedimiento hasta completar el cronograma, tal como se muestra en la figura siguiente.



3 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

clk d g C

3

3

3

3

4

0

0

1

2

2

FWD

FWD

FWD

WAIT

STOP

STOP

WAIT

WAIT

FWD

STOP

m w estado

t1

t0

t2

t3

t4

t5

t6

t7

t8

b) [15%] Obtened las tablas de transiciones y de salidas de la EFSM de la fig. 1, así como las codificaciones binarias de estados y salidas correspondientes. En el grafo podemos ver que hay dos señales de entrada, g y d, las variables C y m para las que tenemos que determinar los valores que van tomando y la señal de salida w. Las tablas de transiciones y salidas que se obtienen a partir del grafo son:

Estado actual

Entrada

Estado siguiente

Estado

Salidas +

+

+

+

STOP

g'

STOP

STOP

C = 0, m = 0, w = 0

STOP

g·d’

FWD

FWD

C = C, m = 1, w = 0

STOP

g·d

WAIT

WAIT

C = C + 1, m = 0, w = 1

FWD

g'

STOP

FWD

g·d’

FWD

FWD

g·d

WAIT

WAIT

g'

STOP

WAIT

g·d’

FWD

WAIT

g·d

WAIT

+

+

Para la codificación binaria, hay que asignar a cada estado un código binario individual. En este caso, se sigue el criterio más habitual, que es el de la numeración binaria, desde el 0 para el estado inicial hasta el número de estados que haya menos 1: 00 para STOP, 01 para FWD, 10 para WAIT.



4 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Para elegir el valor siguiente que tenemos que asignar a la variable C hace falta un selector, que denominaremos s_C. En la tabla siguiente tenemos los valores entre los que se elige y una posible codificación binaria de cada uno de ellos: Operación

Selector s_C

Efecto sobre la variable

+

00

Ponerla a 0

+

01

Mantener el valor

+

10

Sumarle 1

C =0 C =C C = C+1

También se tendría que usar un selector, s_m, para elegir el valor siguiente de la variable m: Operación

Selector s_m

Efecto sobre la variable

+

0

Ponerla a 0

+

1

Ponerla a 1

m =0 m =1

El valor de la salida w se determina directamente a partir del estado. Finalmente, las tablas de transiciones y de salidas con la codificación binaria correspondiente son:

Estado actual

Entrada

Estado

+

Estado

Salidas

Símbolo

q1q0

g

d

q1+q0+

Símbolo

q1q0

s_C

s_m

w

STOP

00

0

x

00

STOP

00

00

0

0

STOP

00

1

0

01

FWD

01

01

1

0

STOP

00

1

1

10

WAIT

10

10

0

1

FWD

01

0

x

00

FWD

01

1

0

01

FWD

01

1

1

10

WAIT

10

0

x

00

WAIT

10

1

0

01

WAIT

10

1

1

10

Notad que según la codificación elegida por los estados y para los selectores, el resultado de la tabla anterior puede variar.



5 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Un método para encriptar textos se basa en codificar cada carácter en otro según una operación con un carácter de una palabra clave. Una opción sencilla para ello es que el código correspondiente sea el carácter que esté en la posición que resulte de sumar las posiciones del carácter original y la del carácter de la palabra clave. La EFSM siguiente se corresponde con el funcionamiento de un encriptador sencillo de este tipo.

(D=0)’

INIT / A + = 0, W+ = 29, r=0

PRE / A + = 0, W+ = 29, r=0

(D=0)

(D=0) (D=0)’

(D=29)’ (D=29)

OFF / A+ = 0, W += (D+K) MOD 32, r=1

(D=29)

ON / A+ = (A+1) MOD 8, W+ = (D+K) MOD 32, (D=29)’ r=0

Fig. 2. EFSM de un módulo encriptador. En el grafo anterior, las sumas para el cálculo de A+ y W+ son aritméticas y D (dato) y K (clave) son señales de entrada que representan valores naturales menores que 32. Se pide lo siguiente: c) [15%] A partir de las tablas de transiciones y de salidas del grafo de la fig. 2 que se dan a continuación, implementad la unidad de control usando ROM y los registros, los bloques combinacionales y las puertas lógicas que creáis convenientes. Especificad y justificad las dimensiones de la/las ROM que uséis e indicad el contenido. Estado actual

Entradas

Estado Estado

(D=0)

(D=29)

INIT

0

x

INIT

1

PRE

Salidas

+

Símbolo

q1q0

s_A

s_W

r

INIT

INIT

00

0

0

0

x

PRE

PRE

01

0

0

0

x

0

ON

ON

10

1

1

0

PRE

x

1

OFF

OFF

11

0

1

1

ON

x

0

ON

ON

x

1

OFF

OFF

0

x

INIT

OFF

1

x

PRE



6 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

Hay que tener presente que las señales s_A y s_W se usan como selectores para elegir qué resultados se asignan a las variables A y W, respectivamente. Nota: Tenéis el ejercicio disponible en VerilCIRC y, si queréis comprobar previamente la ROM, la tenéis disponible en VerilChart. En este entorno, las señales (D=0), (D=29) y Estado son D0, D29 y E, respectivamente. Para implementar la unidad de control con una ROM hace falta, primero, determinar el tamaño y, después, calcular el contenido a partir de la tabla de transiciones correspondiente. El bus de direcciones de la ROM debe que ser de 4 bits, ya que la dirección se forma con los bits que codifican el estado (2, en este caso) y los de las señales de entrada (2 más). Así pues, la ROM debe disponer de un total de 24 = 16 posiciones de memoria. En cada posición se almacena el código del estado siguiente y el valor, en el estado actual, de cada una de las señales de salida. Por lo tanto, harán falta 2 bits para el estado y 3 bits para las salidas, cosa que hace un total de 5 bits. Así pues, la ROM tiene que ser de 16 posiciones de 5 bits. El contenido de la ROM se determina partir de las tablas de transiciones y salidas, combinando los códigos binarios correspondientes, sin casos don’t-care (es decir, que se tienen que repetir para el valor 1 y para el valor 0). Así pues, la ROM debe tener el contenido siguiente: Posición de memoria q1q0

(D=0) (D=29)

Contenido q1+q0 +

s_A

s_W

r

Codificación hexadecimal

00

0

0

00

0

0

0

00h

00

0

1

00

0

0

0

00h

00

1

0

01

0

0

0

08h

00

1

1

01

0

0

0

08h

01

0

0

10

0

0

0

10h

01

0

1

11

0

0

0

18h

01

1

0

10

0

0

0

10h

01

1

1

11

0

0

0

18h

10

0

0

10

1

1

0

16h

10

0

1

11

1

1

0

1Eh

10

1

0

10

1

1

0

16h

10

1

1

11

1

1

0

1Eh

11

0

0

00

0

1

1

03h

11

0

1

00

0

1

1

03h

11

1

0

01

0

1

1

0Bh

11

1

1

01

0

1

1

0Bh

La figura siguiente muestra la implementación con una ROM de estas dimensiones. La entrada M@ de la ROM se configura con el valor del estado actual (los 2 bits de más peso) y el valor de las entradas (los 2 bits de menos peso). Para guardar el estado actual se usan 2 biestables.



7 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

La otra opción es usar dos ROM, una para el cálculo del estado siguiente y la otra, para las salidas. En este caso, la ROM de cálculo del estado siguiente tiene el mismo número de bits de dirección que el anterior (4) pero sólo dos bits para el contenido, puesto que sólo se almacena el código del estado siguiente: Posición de memoria q1q0

(D=0) (D=29)

Contenido +

q1 q0

+

Codificación hexadecimal

00

0

0

00

0h

00

0

1

00

0h

00

1

0

01

1h

00

1

1

01

1h

01

0

0

10

2h

01

0

1

11

3h

01

1

0

10

2h

01

1

1

11

3h

10

0

0

10

2h

10

0

1

11

3h

10

1

0

10

2h

10

1

1

11

3h

11

0

0

00

0h

11

0

1

00

0h

11

1

0

01

1h

11

1

1

01

1h



8 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

La ROM del cálculo de las salidas tiene direcciones de dos bits (el código de estado) y contenidos de 3 bits para las salidas: Posición

Contenido

q1q0

s_A

s_W

r

Codificación hexadecimal

00

0

0

0

0h

01

0

0

0

0h

10

1

1

0

6h

11

0

1

1

3h

El circuito que usa dos ROM es el siguiente:

Con esta última versión se usan menos bits de memoria ROM: de 80 (16x5) con una única ROM a 44 (16x2 + 4x3).



9 de 15

75.562 • Fundamentos de Computadores • Práctica • 2017-18· Estudios de Informática, Multimedia y Telecomunicación

d) [20%] Implementad el circuito completo de la EFSM de la fig. 2: Construid el camino de datos usando las puertas lógicas y los bloques necesarios e incorporad la unidad de control obtenida en el apartado anterior. I...