Universidad del País Vasco Facultad de Informática

eman ta zabal zazu

Departamento de Arquitectura y Tecnología de Computadores

Laboratorio de Diseño Digital

Ejercicios de diseño 1

1 Un sistema lógico debe contar el número de unos de una palabra de 20 bits. El esquema de entradas y salidas es el siguiente: dato resultado final

dato (20 bits) calcular

dato calcular resultado final

dato a procesar, que también debe darse como salida señal de 1 bit que da inicio a la operación palabra que indica el número de unos que tiene el dato indica final de operación y debe durar activado 1 ms.

La frecuencia del reloj es de 1 MHz. ¿cuál será el tiempo de respuesta?

2 Un algoritmo para el cálculo del Máximo Común Divisor de dos números es el que se presenta a continuación. Las variables que toman parte en el algoritmo son: MCD X0 e Y0 Resultado FIN

señal de un bit que inicia el proceso de cálculo los dos números a procesar máximo común divisor de X0 e Y0 indica que el proceso ha terminado.

Algoritmo: repetir mientras MCD=0 hacer X := X0 ; Y := Y0 finmientras; Fin := false; mientras X ≠ Y hacer si X < Y entonces Y := Y - X sino X := X - Y finmientras; Resultado := X ; Fin := true hasta que false

Diseña un sistema para realizar esa operación, desarrollando la unidad de proceso y la de control. A continuación: a) Suponiendo que X0 = 12 e Y0 = 15 y que la frecuencia del reloj que controla la máquina es de 100 KHz, calcula el tiempo que necesitará tu diseño para ejecutar la operación. b) Tomando como referencia un retraso de 10 ns para todos los circuitos combinacionales y de 20 ns para todos los secuenciales, calcular la frecuencia máxima de funcionamiento si las señales deben ser estables en las entradas de los circuitos síncronos al menos 100 ns antes del flanco de reloj. Especificar para ello el camino de máximo retardo de la máquina. c)

Suponer que la frecuencia del reloj es de 1 Mhz. y que MCD es una señal proveniente de un pulsador. ¿Qué tipo de problemas podrían presentarse? ¿Cómo se resolverían?

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 2

3 Diseñar un sistema que sume/reste números naturales de N bits y ofrezca su resultado acumulado. Los datos se introducirán mediante N interruptores y la máquina poseerá además tres pulsadores: LD (load), para cargar en el registro un dato de N bits; SUM (sumar) para sumar al contenido el número de entrada; RES (restar), para restar al contenido el número a la entrada. El resultado será de 2N bits y además del resultado se generarán dos indicadores a la salida para reflejar si ha existido overflow o underflow en la operación. Caso de ocurrir alguna de estas dos excepciones la única operación que se aceptará a continuación será la de carga

4 Diseñar un sistema contra el que se pueda jugar al siguiente juego (NIM). La máquina inicializa un marcador en 15 "objetos". El jugador empieza quitando 1, 2 o 3 "objetos" del total. A continuación, la máquina realiza su jugada, siguiendo así hasta dejar el marcador en 0. Pierde el que quita el último "objeto". La máquina tiene tres pulsadores: 1, 2 y 3 y un par de LEDs para indicar "ganar" y "perder". Un pulsador de RESET sirve para inicializar un nuevo juego. (Hay que diseñar la jugada óptima de la máquina).

G P Reset 1

2

3

5 Un teclado puede verse como una matriz de pulsadores. En este ejemplo se quiere controlar una matriz 5 x 5 formada por 25 pulsadores. Deseamos diseñar un sistema que detecte que se ha pulsado algún pulsador y deje en un registro el código correspondiente. La matriz de pulsadores tiene 5 entradas -filas- y 5 salidas -columnas-. Los pulsadores se encuentran conectados entre una fila y una columna. Para detectar si se ha pulsado un pulsador activaremos la primera fila (conectando 5 volt) y leeremos las 5 columnas. Si no se ha pulsado ninguno de los pulsadores conectados a esa fila entonces a la salida (columnas) tendremos 00000, ya que no hay conexión; sin embargo, si alguno está pulsado, obtendremos 5 voltios en la columna correspondiente a la fila en la que está conectado. Este proceso hay que repetirlo de cíclicamente para todas las filas. Por lo tanto el algoritmo de lectura de un teclado es: activar la fila; leer las columnas; si todas las columnas están desactivadas entonces activar la siguiente fila, en caso contrario (una tecla activada) buscar cuál, buscar su posición en la matriz y devolver el código. En este caso, el código correspondiente a cada pulsador es de 8 bits y está almacenado en una memoria. Los pulsadores no tienen rebote.

P

0

1

2

3

4

5

6

7

8

9

10

11

12

15

16 17

20

21

13 14 18

19

22 23

24

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 3

6 Se dispone de una memoria EPROM en la que se han almacenado de manera comprimida, de cara a ahorrar espacio en memoria, un conjunto de datos que representan el comportamiento de una determinada variable física. El algoritmo de compresión utilizado es muy sencillo: • Se ha almacenado un dato si la diferencia de éste con el último almacenado supera una determinada cota de error. • Aún no superando la cota de error, un dato se almacena al superarse un número máximo de datos sin almacenar. • Los datos que se encuentran dentro de la cota de error se consideran "iguales". Por ello, junto con el dato, se almacena también el número de veces que ese dato se ha repetido, considerando el margen de error. Ejemplo: cota de error = 1 datos de entrada: información almacenada:

7 8 8 7 7 12 13 11 14 8 4 3 3 2 2 2 1 3 3 3 2 7 6 6 13 ..... 7 12 14 8 4 2 7 … datos 5 3 11383… número de repeticiones

De este modo podría recuperarse la información original, aunque con un cierto nivel de error. Del ejemplo anterior obtendríamos: información reconstruida

7 7 7 7 7 12 12 12 14 8 4 4 4 2 2 2 2 2 2 2 2 7 7 7 …

15

10

5

0 0

5

10

15

20

25

Se trata de diseñar un sistema digital que imprima la serie de datos reconstruida de acuerdo al criterio anterior, enviando los datos a la entrada paralelo de una impresora. Las características del sistema en concreto son las siguientes: • Una señal de entrada, I, que indica el inicio de un proceso de impresión. • EPROM de 256 x 8 bits, divididos en dos campos de 4 bits: los cuatro bits de menos peso representan el dato almacenado (D) y los cuatro bits de más peso indican el número de veces que se repite (REP). • Los datos almacenados varían entre 0 y 9. • La serie comienza en la dirección 0 de la memoria y el fin de la misma viene dado por una posición de memoria en la que el campo REP vale 0. Esta posición no indica un dato válido; únicamente marca el fin de la serie.

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 4

La comunicación con la impresora se efectúa mediante el protocolo mostrado en la figura. La señal STRB.L indica a la impresora la existencia de un dato a imprimir. Como respuesta, ésta activa BUSY, indicando que está ocupada y devuelve la señal ACK.L, indicando que se ha aceptado el dato a imprimir. Al terminar la impresión, la impresora vuelve a poner BUSY a 0.

BUSY

5µs (min)

ACK.L

1 ms (max)

DATA STRB.L

0.5 µs (min)

0.5 µs (min)

0.5 µs (min)

DATA: los datos que se envían a la impresora, que deben ir en ASCII de 8 bits. Recuerda que el número x se codifica en ASCII como 3xH STRB.L: señal de validación que indica a la impresora que los datos están disponibles. BUSY: indica que la impresora no está disponible. Al acabar la impresión se pone a 0. ACK.L: confirmación de la recepción de un dato. La relación temporal entre señales es importante, debiendo cumplirse las condiciones que se indican en la figura. Si no se activa ACK.L en el tiempo máximo establecido se supondrá que hay un error, se suspenderá la transmisión y se indicará convenientemente. Los caracteres que se envían a una impresora sólo se imprimen si se completa una línea o si se reciben los caracteres especiales de cambio de línea (0AH 0DH). Por ello, en la EPROM, hay intercalados entre los datos caracteres de control. Estos caracteres de control son fáciles de detectar, ya que, a diferencia de los datos, el valor de los 4 bits de menos peso es mayor que 9. El campo REP de estos caracteres es 1, pues no se repiten. Aunque no es necesario, se sugiere dividir el diseño en dos módulos: uno encargado de leer la memoria y otro de la comunicación con la impresora, tal como se indica en la figura. El primer módulo obtiene cada dato de la memoria y le pide al segundo que inicie el protocolo de impresión. Al completarlo, el segundo módulo se lo indica al primero. Datos a imprimir

Módulo 1

ENV

8

BUSY

Módulo 2

ACK.L

I

impresora

LISTO

STRB.L

error

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 5

7 Se recibe una serie de datos de 8 bits de la que se desea calcular su MODA (valor más frecuente). Los 8 bits de cada dato llegan en paralelo. Una señal DP ("dato presente") indica que existe un dato para ser procesado. La serie de datos termina al recibirse un 00, que no se toma como dato. Como resultado debe dejarse la MODA de la serie y su frecuencia absoluta de aparición en la misma en dos registros de 8 bits. Entradas:

datos de 8 bits señal DP RESET (asíncrono)

Salidas: MODA (8 bits) Frecuencia absoluta (8 bits)

Diseñar un sistema que resuelva este problema usando un controlador microprogramado.

8 Diseñar un sistema que localice la dirección de un determinado dato en una lista de 100 elementos. En el caso de que el dato no se encuentre en la lista, el sistema debe obtener la dirección del dato inferior más próximo al buscado. De hallarse repetido el dato obtendremos su primera dirección. Las entradas y salidas del sistema serán las siguientes: ENTRADAS:

• B: • DAT:

da comienzo a la búsqueda dato de 8 bits del que se desea buscar la dirección en la lista

SALIDAS:

• • • •

DIR: DIF: FIN: LOC:

dirección del dato buscado o, en su defecto, del inferior más cercano si el dato no está en la lista, diferencia con el inferior más cercano señal de fin de búsqueda señal de "dato localizado" 8

B DAT

8

DIF DIR FIN LOC

Realizar una Unidad de Control cableada en base a un algoritmo ASM. Especificar claramente las señales de control que se utilicen. Suponer para ello, que se dispone de una señal de reloj de 20 MHz y que el tiempo de ciclo de la memoria es de 200ns. De acuerdo a tu algoritmo de control, cuál sería el tiempo mínimo y máximo de búsqueda?

9 Por un bus de 5 bits se envía información a un sistema que debe almacenarla en forma condensada. El algoritmo de condensación es el siguiente: • Se almacena un dato si la diferencia con el último almacenado supera una cota de error. • Si los últimos 15 datos no se han guardado, el 16 se almacena obligatoriamente. • Por cada dato guardado, se almacena también el nº de datos llegados desde el anterior guardado. Ejemplo: cota de error = 2 datos de entrada: 7 8 8 7 7 12 13 11 14 8 4 3 3 2 2 2 1 3 3 3 2 7 ..... información almacenada: 7 12 8 4 1 7 datos 1 5 4165 nª de datos recibidos. De los 5 bits que llegan al sistema, 4 son de datos y el quinto es una señal READY, que indica, cuando se halla en cero voltios, que existe un dato válido en la entrada al sistema. (Tomar como ejemplo una memoria de 256 x 4)

Universidad del País Vasco Facultad de Informática

eman ta zabal zazu

Laboratorio de Diseño Digital

Departamento de Arquitectura y Tecnología de Computadores Ejercicios de diseño 6

10 Queremos diseñar un sistema para incluirlo dentro de un cajero automático y que se encargue de la verificación de la clave tecleada al insertar una tarjeta y de la actualización de información asociada a la misma. El esquema del sistema es el siguiente: INCORR

Sistema a diseñar

RETEN CORR

IN

20 NUM

TEC

Cajero

4

DIG

Entradas: IN: indica el comienzo de la operación (inserción de la tarjeta). NUM: 20 bits que indican el nº de la tarjeta. TEC: indica que se ha pulsado un dígito. DIG: 4 bits que indican el dígito tecleado. Salidas: CORR: indica que la clave es correcta. INCORR: indica que la clave es incorrecta. RETEN: indica que la tarjeta ha sido retenida.

Al introducir la tarjeta, el cajero activa la señal IN y proporciona el nº de la tarjeta en NUM, manteniendo la información durante 3 ciclos de reloj. A continuación, nuestro sistema debe recoger los 4 dígitos de la clave, que llegan a medida que se teclean, por la entrada DIG. Cada vez que se teclea un dígito se activa TEC. El tiempo que transcurre entre la pulsación de dos dígitos es variable, pero lo vamos a limitar a un máximo de 5 segundos. Si se supera ese tiempo, hay que finalizar el proceso activando durante un ciclo la señal RETEN, que indica que la tarjeta es retenida por el sistema, y actualizar la información de memoria como se indica más adelante. Si se recoge la clave completa, hay que verificar si coincide con la clave asociada a la tarjeta y que está almacenada en una memoria. Tenemos dos casos posibles: • si ambas claves coinciden, hay que finalizar activando durante un ciclo CORR. • si no coinciden, hay que activar durante un ciclo INCORR, volver a leer una nueva clave completa (los 4 dígitos) tal y como se ha hecho antes y volver a hacer la verificación. El máximo número de fallos consecutivos para una misma tarjeta es de 3, de modo que si se recogen tres claves incorrectas, hay que finalizar el proceso activando durante un ciclo la señal RETEN. Aparte de la clave, en memoria se almacena más información para cada tarjeta. Cada palabra de memoria, de 48 bits, contiene: los 16 bits correspondientes a la clave asociada a la tarjeta, otros 16 bits que guardan el número total de accesos hechos con esa tarjeta, y otros 16 bits que indican el número total de fallos cometidos al teclear la clave. Cada vez que se introduce una tarjeta hay que actualizar dicha información, ya que como mínimo habrá que modificar el número de accesos (se incrementa en 1), y puede ser que también el número de fallos (puede incrementarse en 1, 2 o 3). a).

Diseña el sistema de acuerdo a la metodología vista en el curso Vamos a suponer que la frecuencia del reloj del sistema es de 1 Mhz.

b). De acuerdo con las características del sistema, responde brevemente a las siguientes cuestiones: o ¿qué tipo de memoria utilizarías en este sistema y por qué? o Dada tu solución y la frecuencia de reloj, ¿podrías tener problemas con la memoria? o ¿Sería posible utilizar una memoria RAM dinámica? ¿en qué variaría el algoritmo que propones?

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 7

11 Queremos diseñar un módulo capaz de enviar el contenido de una memoria EPROM a una impresora a través de su entrada paralelo Centronics. La siguiente figura muestra las señales que intercambian la impresora y nuestro módulo. I es una señal externa, un pulsador, que da comienzo al envío de datos a la impresora. BUSY ACK.L

I

impresora DATA STRB.L

error

La entrada paralelo de la impresora se controla mediante el protocolo de la figura. BUSY

5µs (min)

BUSY:

señal que indica que la impresora está ocupada

ACK.L:

aceptación de un dato (con cada byte)

DATA:

datos que se envían impresora (8 bits.

ACK.L 1 ms (max)

DATA STRB.L

0.5 µs (min)

la

STRB.L: señal que indica a la impresora que los datos están disponibles.

0.5 µs (min)

0.5 µs (min)

a

La secuencia de señales debe cumplir con las condiciones temporales que se indican en la figura. Si tras el tiempo acordado no se recibe la señal ACK.L se supondrá que hay un error en la impresora, se suspenderá la transmisión y se indicará convenientemente. La cadena de caracteres que se quiere imprimir termina con el código de fin_de_texto, 0000xxxxB. Este carácter deberá ser detectado pero no enviado a la impresora.

11b Una impresora recibe datos por su entrada paralelo de acuerdo a un determinado protocolo (idéntico al del ejercicio anterior). Los datos, de 8 bits, son almacenados temporalmente en una memoria RAM local de 80 caracteres. Los caracteres recibidos sólo se imprimen cuando se recibe el carácter Fin-de-Línea (FL), o bien cuando se han recibido ya 80 caracteres. Para ello, los caracteres ASCII almacenados en la memoria RAM son traducidos al código correspondiente (código dat de m bits, ver figura), y se envían junto con una señal P.L al dispositivo mecánico que los imprime. La señal P.L y el código final enviado a la parte mecánica han de durar al menos 0.1ms (ver figuras). Diseñar el módulo de la impresora indicado en la figura, desarrollando una unidad de control microprogramada y la correspondiente unidad de proceso. Especificar claramente las señales de control utilizadas. Indicar así mismo qué condiciones son necesarias para cumplir las especificaciones de tiempo fijadas. STRB.L DATA

BUSY

8

m

?

dat

parte mecánica

Dat PL

0,1 ms (min)

P.l

ACK.L

Impresora. Hay que diseñar el módulo ?

Protocolo para el envío de datos al dispositivo mecánico

Universidad del País Vasco Facultad de Informática

eman ta zabal zazu

Departamento de Arquitectura y Tecnología de Computadores

Laboratorio de Diseño Digital

Ejercicios de diseño 8

12 Un determinado sistema digital recibe datos a través de una entrada de 3 bits de acuerdo al siguiente protocolo:

DATOS

3 3

RES

REC YA

C_M

La señal REC indica presencia de datos en las líneas de entrada de datos. La señal C_M indica "cambio de modo" en la recepción de datos. Los datos se reciben en dos modos diferentes: MODO 0

Modo 0 : los tres bits de entrada representan un número N0 de tres bits. Modo 1: los tres bits de entrada representan cada uno un bit de un número de tres bits diferente: N1, N2 y N3, que se van a ir recibiendo de manera continuada bit a bit, uno por ciclo de reloj; en serie por tanto.

N0 D0 D1 D2

MODO 1 D0 D1 D2

N1.i N2.i N3.i

El modo de recepción de datos sólo se cambia al recibir nuevos datos. Como resultado, el sistema debe ofrecer: En modo 0 RES = N0 En modo 1 RES = Mayor (N1, N2, N3) Una señal, YA, indica la presencia del resultado. a Construir un circuito digital que ofrezca el mayor de tres números de tres bits. b Construye la unidad de control y la unidad de proceso para solucionar el problema propuesto. Utiliza un contador de 3 bits para implementar la unidad de control y en la unidad de proceso el circuito construido en el apartado a. Especifica cómo se controlan todos los circuitos. c Indicar cómo se añadiría al sistema una señal luminosa que indicara de manera permanente el modo de recepción en que se halla el sistema: encendida, modo 0; apagada, modo 1. d Calcular el tiempo de respuesta en ambos modos si la señal de reloj es de 500 KHz.

Universidad del País Vasco Facultad de Informática

Departamento de Arquitectura y Tecnología de Computadores

eman ta zabal zazu

Laboratorio de Diseño Digital

Ejercicios de diseño 9

13 Tenemos almacenados en memoria los elementos de un vector pero no en posiciones consecutivas, de modo que junto con cada elemento del vector se ha almacenado también la dirección del siguiente elemento, formando así una lista encadenada. dirección comienzo

D1

DS

D2

DS

D3

DS

DS = dirección siguiente

Queremos diseñar un circuito digital para realizar la siguiente operación sobre dicho vector, consistente en comparar el campo de datos de dos elementos de manera que: Si D(i) < D(i+1) entonces

D(i) := - D(i) (cambio de signo)

Los datos están representados en SIGNO-MAGNITUD. La información de entrada es la siguiente: • OP: señal de un bit que indica el comienzo de la operación. • DCV: dirección de comienzo del vector • I: elementos del vector a comparar: el (i) y el (i+1). (i = 0 .. 254) EJEMPLO: si DCV = 100 e I = 7, hay que comparar los elementos 7 y 8 del vector que comienza en la dirección 100, para realizar la operación indicada anteriormente Como salida del circuito, además de realizar la operación ya indicada, hay que generar los dos bits siguientes: • FIN: indica final de la operación • CS: indica que se ha realizado el cambio de signo. OP DCV I

FIN n p

CS

a Diseña un comparador de números en signo-magnitud para obtener la función a