1. No category

Facultad de Informática
Universidad Complutense de Madrid
EJERCICIOS
DISEÑO AUTOMÁTICO DE SISTEMAS
Sistemas combinacionales:
1. En un codificador de prioridad convencional, la prioridad relativa de cada una de las
entradas (la que determina el valor que codifica la salida cuando uno o varias entradas se
activan) es fija. Algunas aplicaciones requieren que la prioridad pueda cambiar
dinámicamente para dar un acceso a los recursos más equilibrado. Diseñar un codificador
de prioridad 8 a 3 programable que, aparte de las 8 entradas de solicitud convencionales,
ri, tenga una entrada de control, c, que indique la petición de mayor prioridad. Por
ejemplo, si c = “011”, la prioridad relativa de las entradas será r3, r2, r1, r0, r7,..., r4.
(Pista: El diseño utiliza la señal c para generar 2 máscaras de 8 bits que se usan para
eliminar respectivamente la parte baja y alta de la palabra de solicitud. Aplicando
ambas máscaras a la palabra de solicitud original y pasando ambos resultados por
sendos codificadores de prioridad obtendremos 2 códigos, uno de los cuales deberá ser
seleccionado en función de si existe o no una petición en la parte baja de la solicitud.
Por ejemplo, si c es “011” y r es “11010101”, la máscara a usar para eliminar los bits
menos significativos de la solicitud será “00001111” y la máscara a usar para eliminar
los bits más significativos de la solicitud será su inversa, es decir, “11110000”.
Aplicando ambas máscaras a r, tenemos “00000101” y “11010000” que generan
respectivamente los códigos “010” y “111”. Finalmente “010” es seleccionado ya que
la parte baja de la solicitud contiene algún ‘1’).
2. Diseñar un codificador de prioridad 8 a 3 dual. El sistema funcionará como un
codificador de prioridad convencional con la diferencia de que en lugar de tener 2 salidas
de 3 bits para códigos y 2 salidas de activación por las que indicará, cuando corresponda,
los códigos de las 2 entradas de mayor peso que se activen.
3. Se define la distancia Hamming entre 2 palabras binarias del mismo tamaño como el
número de posiciones en las que ambas palabras difieren e indica el número de bits que
Ejercicios de Diseño Automático de Sistemas
pág. 1
deben invertirse para convertir una palabra en la otra. Un circuito que calcule la distancia
Hamming debe hacerlo en 2 fases. La primera, debe calcular una palabra que marque
mediante ‘1’ los bits en los que difieren las palabras de entrada. La segunda, debe contar
el número de ‘1’ resultantes en la anterior fase mediante un circuito conocido como
contador de población. Por ejemplo, dadas las palabras “00010011” y “10010010”, cuya
distancia Hamming es 2 ya que difieren en las posiciones 7 y 0, el resultado de la primera
fase será “10000001” y el de la segunda “0010”. Diseñar un circuito combinacional que
calcule la distancia Hamming entre 2 palabras de 8 bits (Pista: La primera fase se
implementa usando puertas XOR. La segunda fase se implementa mediante un árbol de
sumadores completos de 3 etapas en donde los sumadores son respectivamente de 1, 2 y
3 bits y en cada etapa se suman 2 a 2 los resultados obtenidos en la anterior etapa.
Téngase en cuenta que en cada etapa el carry-out de la suma debe concatenarse con el
resultado de la suma para formar el operando que se sumará en la etapa siguiente).
4. Diseñe un circuito combinacional que cuente el número de ceros consecutivos que hay a
la izquierda de un vector de 16 bits dado. (Pista: Usar un contador de población que
tenga una etapa previa que marque mediante ‘1’ los bits que valen ‘0’ a la izquierda del
primer ‘1’ de la palabra de entrada).
5. La multiplicación por constantes aparece en una multitud de aplicaciones de procesado
digital de señal. Para evitar el uso de un multiplicador, que es un recurso muy costoso, en
ocasiones se utiliza una implementación basada en ROM y sumadores que se basa en la
siguiente idea. Supongamos que deseamos multiplicar por una constante un número
entero sin signo codificado en binario con 8 bits, x. Dado que dicho número puede
representarse como 2 dígitos hexadecimales (los nibbles superior e inferior del byte), su
valor en notación polinomial en base 16 es: 1016×(x7..4) + (x3..0). Si multiplicamos dicha
expresión por la constante el valor nos queda una expresión que permite calcular el valor
del producto como: 1016×Cte×(x7..4) + Cte×(x3..0). Obsérvese que esta expresión requiere
2 ROM (16×12) conteniendo el resultado de multiplicar la constante por los valores del 0
al 15 (es decir, por los 16 dígitos hexadecimales posibles), un sumador de 12 bits (para
sumar los productos parciales) y 1 desplazador a derechas de 4 bits (para implementar el
producto por 1016). Diseñe un circuito que multiplique un número entero sin signo
codificado en binario con 8 bits por 47 (2F16).
Sistemas combinacionales genéricos:
6. Diseñe un conversor genérico de código binario de n bits a código Gray de n bits. (Pista:
gi = bi ⊕ bi+1).
7. Diseñe un conversor genérico de código Gray de n bits a código binario de n bits. (Pista:
bi = gi ⊕ bi+1).
8. Diseñe un conversor de código genérico que dado un número entero con signo
codificado en C2 con n bits, lo represente en MyS con n bits. (Pista: Usar un sumador
binario completo de n bits).
9. Diseñe un conversor de código genérico que dado número entero con signo codificado en
MyS con n bits, lo represente en C2 con n bits. (Pista: Usar un sumador binario
completo de n bits).
10. Diseñe un módulo genérico que calcule el valor absoluto de un número entero con signo
codificado en C2 con n bits. El resultado deberá codificarse en binario de n-1 bits.
(Pista: Usar un sumador binario completo de n bits).
11. Diseñe un sumador genérico de 2 números enteros con signo codificados en MyS de n
Ejercicios de Diseño Automático de Sistemas
pág. 2
bits. (Pista: El circuito tendrá 2 etapas. La primera ordena los números según su
magnitud y la segunda examina los signos para decidir si debe sumar o restar las
magnitudes para obtener el resultado).
12. En algunas aplicaciones de procesado digital de señal es conveniente usar sumadores con
saturación para reproducir lo que sucedería en el correspondiente circuito analógico
cuando los voltajes de salida de los amplificadores se saturan (es decir, llegan al máximo
o mínimo valor posible). Un sumador saturado se comporta como un sumador
convencional excepto cuando se desborda. En ese caso, genera a su salida el mayor o
menor valor representable en la codificación escogida según corresponda. Diseñe un
sumador saturado genérico de números enteros con signo codificados en C2 con n bits.
(Pista: El circuito tendrá 2 etapas. La primera suma normalmente los números y la
segunda deja pasar el resultado o el valor saturado que corresponda).
13. Diseñe un sumador de 2 números enteros sin signo codificados usando n dígitos BCD. El
sistema se realizará componiendo n módulos sumadores de 2 dígitos BCD, cada uno de
los cuales tendrá 2 entradas de 4 bits de datos, 1 entrada binaria de acarreo, 1 salida de 4
bits de datos y 1 salida binaria de acarreo. (Pista: La suma deberá calcularse dígito a
dígito usando sumadores binarios completos de 4 bits de manera que si el resultado
excede 9 se sume 6, lo que equivale a restar 10, y usar el acarreo resultante en la suma
del siguiente dígito).
14. Diseñe un incrementador de números enteros sin signo codificados usando n dígitos
BCD. El sistema tendrá una entrada y una salida de datos ambas de 4·n bits.
15. Realice un multiplicador por constante genérico basado en ROM y sumadores que dado
un número entero sin signo codificado en binario con 4·n bits lo multiplique por una
constante genérica de 8 bits. (Pista: Generalice el circuito de 8 bits diseñado en la
sección de sistemas combinacionales).
Sistemas secuenciales:
16. Diséñese un detector de flancos sobre una señal suficientemente lenta (su velocidad de
transmisión es notablemente inferior a la frecuencia de reloj del sistema). El sistema
tendrá una entrada binaria x y dos salidas binarias up y down de tipo Moore. La salida up
valdrá 1 durante un ciclo de reloj cada vez que detecte una transición de 0 a 1 en la
entrada x. La salida down valdrá 1 durante un ciclo de reloj cada vez que detecte una
transición de 1 a 0 en la entrada x. (Pista: Conceptualmente up detecta el patrón “01” y
down el “10” en la señal serie x).
17. Diseñe un codificador NRZI (Non-return to-zero invert-to ones) que transforma un flujo
de datos serie codificados en binario convencional en otro flujo de datos que vale ‘0’
cuando los valores actual y anterior de la entrada son distintos y ‘1’ en caso contrario.
18. Diseñe un decodificador NRZI.
19. Diseñe un conversor secuencial de números enteros sin signo codificados en binario a
BCD de 4 dígitos. El sistema tendrá 1 entrada de 13 bits de datos, 1 salida de 16 bits de
datos, y señales de inicio y fin para señalizar cuando hay datos válidos a la entrada y a la
salida respectivamente. El algoritmo general para realizar la conversión consiste en
insertar por la izquierda de 1 en 1 los bits binarios (empezando por el bit más
significativo) dentro de un registro de desplazamiento BCD especial que internamente
está divido en grupos de 4 bits, cada uno representando un dígito. Cada vez que se
desplaza la secuencia BCD un bit a la izquierda, cada uno de los dígitos resultantes deben
corregirse si son mayores que 9. El ajuste de un dígito consiste en sumar 6 (lo que
Ejercicios de Diseño Automático de Sistemas
pág. 3
equivale a restar 10) y usar el acarreo resultante en la corrección del siguiente dígito. No
obstante, en lugar de este algoritmo, resulta más eficiente ajustar primero los dígitos y
después desplazar. Para ello, primero es necesario corregir sumando 3 a aquellos dígitos
de la secuencia BCD que sean mayores que 4. Una vez corregidos, se desplaza 1 bit a la
izquierda toda la secuencia BCD insertando un nuevo bit del código binario original.
(Pista: Se requerirá un registro de desplazamiento convencional para ir obteniendo 1 a
1 los bits de la palabra binaria, un contador para saber cuándo se han procesado todos
los bits, y un registro para la secuencia BCD que en un único ciclo pueda corregir los
dígitos y desplazar 1 bit a la izquierda el resultado de la corrección).
20. Diseñar un circuito secuencial que calcule la distancia Hamming que separa 2 palabras
de 16 bits que recibe en serie. El sistema, aparte de la señal de reloj y reset, tendrá 2
entradas de datos de 1 bit, 1 salida de datos de 5 bits, 1 señal de sincronismo que indica
cuando hay datos válidos en la entrada y 1 señal de fin de cálculo que se activa cuando la
distancia ha sido calculada. (Pista: Deberá usarse 2 registros de desplazamiento y 2
contadores: uno para secuenciar los desplazamiento y otro para contar la población).
21. Diseñe un circuito secuencial que cuente el número de ceros consecutivos que hay a la
izquierda de un vector de 16 bits que llega en serie comenzando por el bit más
significativo. El sistema, aparte de la señal de reloj y reset, tendrá 2 entradas de datos de
1 bit, 1 salida de datos de 5 bits, 1 señal de sincronismo que indica cuando hay datos
válidos en la entrada y 1 señal de fin de cálculo que se activa cuando la distancia ha sido
calculada. (Pista: Deberá usarse 1 registro de desplazamiento y 2 contadores: uno para
secuenciar los desplazamiento y otro para contar la población).
22. Ídem que el anterior pero para el caso en que el vector de bits llegue en serie
comenzando por el bit menos significativo.
23. Diseñar un circuito secuencial capaz de calcular 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 señal start y otra done y una salida de 20 bits para indicar la serie. 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). (Pista: El circuito realizará el cálculo iterativamente. Tendrá 1
sumador de 20 bits, 2 registros y para almacenar los 2 últimos elementos de la serie y un
contador que llevará la cuenta del índice).
24. La máquina diferencial de Babbage fue un dispositivo mecánico de computación digital
diseñado para tabular funciones polinómicas. Fue propuesta por Charles Babbage, un
matemático inglés, en el siglo XIX. La máquina está basada en el método de diferencias
finitas de Newton y evita el uso de la multiplicación.
Por ejemplo, considérese el polinomio de segundo orden siguiente: f(n) = 2n2 + 3n + 5.
La diferencia entre f(n) y f(n-1) es: f(n) - f(n-1) = 4n + 1. Asumiendo que n es un entero
mayor o igual a 0, f(n) puede definirse recursivamente como: f(0) = 5, f(n) = f(n-1) + 4n
+ 1. Si repetimos el proceso para la expresión 4n + 1, definamos g(n) = 4n + 1. La
diferencia entre g(n) y g(n-1) es: g(n) - g(n-1) = 4. Asumiendo que n es un entero mayor
o igual a 0, g(n) puede definirse recursivamente como: g(0) = 1, g(n) = g(n-1) + 4. Así
f(n) puede reescribirse como: f(0) = 5, f(n) = f(n-1) + g(n).
Basándose en las definiciones recursivas de f y g, es posible derivar un algorimo para
calcular el valor de f(n) para un valor de n dado. Diseñar un circuito que tendrá una
entrada de 6 bits para indicar el valor del argumento, una salida de 13 bits para indicar el
valor del resultado y señales de inicio y fin. (Pista: El circuito realizará el cálculo
iterativamente. Tendrá 1 sumador de 13 bits, 2 registros para almacenar los 2 últimos
Ejercicios de Diseño Automático de Sistemas
pág. 4
valores calculados de las funciones f y g y un contador que llevará la cuenta del índice).
Sistemas secuenciales genéricos:
25. Diseñar un acumulador genérico que opere con números enteros con signo codificados
en C2 con n bits. El sistema acepta 1 operando y lo suma/resta al resultado calculado en
el ciclo anterior.
26. Diseñar un MAC (Multiply Accumulator) genérico que opere con números enteros sin
signo codificados en binario con n bits. El sistema acepta 2 operandos, los multiplica y
suma/resta el producto al resultado calculado en el ciclo anterior.
27. Diseñar un circuito secuencial genérico que calcule la distancia Hamming que separa 2
palabras de n bits que recibe en serie.
Medida del tiempo:
28. En un sistema digital es posible medir el paso del tiempo si la frecuencia del reloj del
sistema se conoce. Para ello basta con contar el número de ciclos transcurridos y
multiplicarlos por el periodo del reloj. Diséñese un temporizador que funcionando a 50
Mhz se capaz de medir 50 ms. El sistema tendrá una entrada start y una salida end que
inicialmente vale 1. Cuando el temporizador detecta que start vale 1, pone end a 0 y
comienza la cuenta del número de ciclos requerido. Cuando la cuenta finaliza, pone end a
1 y vuelve a esperar la activación de start para iniciar una nueva cuenta. Cualquier
activación de start durante la cuenta será ignorada. (Pista: Requiere un contador de
tamaño suficiente para contar el número de ciclos requerido y de un comparador para
saber cuándo finaliza la cuenta)
29. Diséñese un temporizador programable que funcionando a 50 MHz sea capaz de medir
tiempos en el rango 0-63 ms en intervalos de 1 ms. El sistema aparte de la entrada start y
end, dispondrá de una entrada de 6 bits, ms, y una entrada binaria, ld. La primera
permitirá indicar el número del ms a medir y la segunda permitirá cargar dicho valor en
el sistema. Si se le indica contar 0 ms, el sistema permanecerá inactivo. El sistema
ignorará cualquier cambio de cuenta que se produzca mientras esté contando, i.e.
mientras end valga 0. (Pista: Es un temporizador con fin de cuenta variable que
requiere de un registro adicional para almacenar los ciclos a contar y un conversor de
código que convierta ms en ciclos).
30. 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ñar un watchdog de time-out
(medido en ms) genérico. El sistema funcionará a 50 MHz y dispondrá de una entrada
para reiniciar la cuenta y una salida para indicar el time-out.
31. Diseñar un eliminador de rebotes genérico de un pulsador a lógica negativa funcionando
a 50 MHz. El sistema, tras la detección de una presión o depresión, filtrará la señal de
entrada en periodos de 1 ms. (Pista: El sistema dispondrá de un temporizador de 1 ms y
de un contador de milisegundos transcurridos).
32. Diseñar un eliminador de rebotes autoregulable que deje de filtrar la señal de entrada
cuando detecte que lleva más de 20 ms sin rebotar. El sistema funcionará a 50 MHz.
(Pista: El sistema dispondrá de un temporizador de 20 ms que reiniciará la cuenta cada
vez que detecte un rebote, alcanzado el time-out del temporizador, el sistema deja de
Ejercicios de Diseño Automático de Sistemas
pág. 5
filtrar la señal).
33. Un contador de periodos mide el periodo de una señal cuadrada periódica. Una manera
de diseñarlo es contando el número de ciclos entre 2 flancos consecutivos de una la señal
de entrada. Si dicho número es n, y la frecuencia de reloj del sistema es fclk, el periodo de
la señal de entrada es n/fclk. Diséñese un contador de periodos, que funcionando a 50
MHz, sea capaz de calcular en s el periodo de una señal de entrada cuyo periodo pueda
oscilar entre 1 Hz y 10 KHz. (Pista: El sistema dispondrá de un contador de s y de un
contador de ciclos que mida 1 s).
34. Un medidor de anchura de pulso mide el intervalo de tiempo en que una señal está a ‘1’.
Una manera de diseñarlo es contando el número de ciclos que transcurren entre el flanco
de subida y el siguiente flanco de bajada de la señal de entrada. Diséñese un medidor de
anchura de pulsos, que funcionando a 50 MHz, sea capaz de calcular en s el tiempo que
una señal está a ‘1’. El sistema, además, dispondrá de una entrada de reinicio y de una
salida de saturación que se activará cuando el pulso medido supere los 10s.
35. Diséñese un sistema que mida el desfase en s (hasta un máximo de 10s) entre 2 flancos
de subida consecutivos que ocurran en 2 señales distintas que lleguen por las entradas a y
b. Si el flanco llega primero a la entrada a, el desfase será positivo y si llega primero a la
entrada b será negativo. Si no llegase el segundo flanco transcurridos los 10 s, el sistema
se reiniciará ignorando la ocurrencia del primero.
Generación de formas de onda:
36. Diseñe un circuito que, funcionando a 1 MHz, genere una señal de 1 Hz cuadrada (i.e. en
cada ciclo, la salida está la mitad del tiempo a ‘0’ y la otra mitad a ‘1’).
37. Diseñe un divisor programable de frecuencia. El sistema tiene como entrada, además de
las señales de reloj y reset, una señal de control de 4 bits, c, codificando un número
entero sin signo. El circuito tiene una salida binaria, pulse, cuya frecuencia es controlada
por el valor de c. Si la frecuencia del reloj es f y el valor de c es m, la frecuencia de la
señal pulse será f/2m. Por ejemplo, si c es “0101”, la frecuencia de la salida será f/25.
38. Diseñar un generador programable de ondas cuadradas. El sistema tiene como entrada,
además de las señales de reloj y reset, 2 señales de control de 4 bits, m y n, codificando
números enteros sin signo. El circuito tiene una salida binaria, pulse, que periódicamente
alternará entre ‘1’ y ‘0’ siendo la duración del intervalo a ‘1’igual a m/fclk y la del
intervalo a ‘0’ igual a n/fclk.
39. Un generador de pulso único es un circuito que genera un único pulso de anchura
determinada tras la activación de una señal de disparo. El sistema dispone de 2 señales
binarias de control, go y stop, y de una salida binaria, pulse. Cuando se activa
(típicamente durante un único ciclo) la señal go, la salida pulse pasa a valer ‘1’ durante
un número de ciclos determinado. Las sucesivas activaciones de go mientras que se
genera el pulso son ignoradas. Si la señal de stop se activa durante la generación del
pulso, pulse pasa a valer nuevamente ‘0’. Las activaciones de stop mientras pulse vale ‘0’
son ignoradas (lo que implica que go es prioritaria sobre stop). Diseñar un generador de
pulso único programable, en donde la anchura en ciclos del pulso codificada en binario
se indica a través de una entrada de 4 bits.
40. Diseñar un generador de pulso único de anchura fija pero genérica (Pista: La anchura en
ciclos del pulso podrá ser de 1 a 255).
41. En una señal periódica digital, el factor de trabajo (duty cycle) se define como el
Ejercicios de Diseño Automático de Sistemas
pág. 6
porcentaje de su periodo en que vale ‘1’. Por ejemplo, el factor de trabajo de una señal
cuadrada simétrica es del 50% ya que está la mitad del tiempo a ‘0’ y la otra mitad a ‘1’.
Un circuito PWM (Pulse Width Modulation), tomando como base la frecuencia del reloj,
genera una señal periódica con un factor de trabajo ajustable.
Diseñe un circuito PWM cuyo factor de trabajo pueda ajustarse en incrementos de 1/16,
i.e. el factor de trabajo puede ser 1/16, 2/16, 3/16… 15/16, 16/16. Tendrá una señal de
control de 4 bits, c, que interpretada como un entero sin signo permita indicar el factor de
trabajo deseado. Así el factor de trabajo será de 16/16 cuando c es “0000” y c/16 en otro
caso. (Pista: Deberá utilizarse un contador módulo 16 con un circuito especial de salida
basado en un comparador que genere la señal. La frecuencia de la señal generada será
en cualquier caso 1/16 de la frecuencia de reloj del circuito PWM. Para evitar glitches
en la salida hacerla pasar por un flip-flop D).
42. Un circuito PWM puede controlar el factor de trabajo de la señal que genera, sin
embargo esta señal siempre tendrá una frecuencia fija. Así, por ejemplo, si la frecuencia
de reloj del circuito diseñado anteriormente es f, la señal generada es f/24. Adaptar el
anterior circuito para que la frecuencia de salida sea también programable de manera que
dada una señal de 4 bits codificando un entero sin signo, k, la frecuencia de la señal
generada sea f/(k*24) si k no es 0 y f/24 si k es 0.
43. La luminosidad de un LED puede regularse analógicamente cambiando la intensidad que
circula él o digitalmente mediante la técnica conocida como LED dimming. Esta técnica,
dado que la intensidad suministrada por un sistema digital para encender un led es fija y
es nula cuando para apagarlo, consiste modificar al porcentaje de tiempo durante el que
sistema digital suministra intensidad al LED cuando este 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 (PWM) cuyo factor de trabajo determinará la luminosidad del led.
Diséñese un circuito que dado una señal de encendido/apagado y un valor de
luminosidad codificado con 4 bits, genere una señal PWM (de frecuencia superior a 100
Hz para evitar el efecto parpadeo) que permita regular la luminosidad de un led.
44. Una manera sencilla de generar sonidos digitalmente es conectando uno de los terminales
de un altavoz a un valor fijo (tierra o alimentación) y el otro a una señal digital que oscile
a una frecuencia dentro del rango audible (20 – 20000 Hz). Diseñar un circuito que,
selectivamente en función de una señal de habilitación, genere una onda cuadrada de
261.6 Hz (do central). La frecuencia del reloj del circuito es 50 MHz.
45. Diseñe un circuito que, tras la activación de una señal de habilitación, genere una onda
cuadrada de 261.6 Hz (do central) durante 0,5 segundos. Al conectarlo a un altavoz
generará un pitido de 0,5 segundos. La frecuencia del reloj del circuito es 50 MHz.
Contadores no convencionales:
46. Diseñar un contador de 4 bits mod-m programable. El sistema aparte de las señales
convencionales de las que dispone un contador, tiene una entrada de 4 bits, m, que indica
el número de estados que tiene la secuencia del contador y una señal prog, que indica
cuando hay un valor válido en la entrada m. (Pista: Aparte de un contador binario
requerirá de un registro de 4 bits para almacenar el valor m).
47. Un contador en anillo es un registro de desplazamiento de n bits que realimenta por la
entrada serie el valor que sale por la salida serie. Este contador sigue una secuencia
circular de n estados distintos codificados en one-hot. Aunque es bastante ineficiente en
Ejercicios de Diseño Automático de Sistemas
pág. 7
términos de área (un contador convencional de n bits puede generar 2n estados distintos)
tiene algunas ventajas. Primero, la codificación de estados no requiere una posterior
decodificación y además la salida está libre de gitches. Segundo, si la frecuencia de reloj
es f, las n salidas generan n señales a frecuencia f/n, con factores de trabajo 1/n y
desfasadas cada una respecto a la anterior en 1/f. Finalmente este tipo de contadores son
los más rápidos, ya que la frecuencia máxima a la que pueden contar corresponde con la
máxima frecuencia a la que puede funcionar un circuito secuencial para una tecnología
dada que es 1/(tCQ + ts). Diseñe un contador en anillo de 8 bits. (Pista: El valor inicial
nunca debe ser 0).
48. Un LSFR (Linear Feedback Shift Register) es un registro de desplazamiento que utiliza
un circuito especial para determinar el valor que se realimenta por la entrada serie. Este
circuito determina el valor siguiente que almacenará el registro realizando una operación
xor sobre ciertos bits del mismo. En un circuito LSFR de n bits correctamente diseñado,
unas pocas puertas xor pueden forzar a que el registro siga una secuencia circular de 2n-1
estados sin repetir ninguno de ellos.
Seguidamente se muestra las combinaciones de bits que deben realimentarse para
construir un LFSR correcto para un número de bits dado:
LSFR n bits
2, 3, 4
5
6
7
8
16
32
64
128
realimentar
q1 ⊕ q0
q2 ⊕ q0
q1 ⊕ q0
q3 ⊕ q0
q4 ⊕ q3 ⊕ q2 ⊕ q0
q5 ⊕ q4 ⊕ q3 ⊕ q0
q22 ⊕ q2 ⊕ q1 ⊕ q0
q4 ⊕ q3 ⊕ q1 ⊕ q0
q29 ⊕ q17 ⊕ q2 ⊕ q0
Así un LFSR de 4 bits que realimente por la izquierda la xor de los 2 bits menos
significativos del registro seguirá la secuencia de 15 valores: “1000”, “0100”, “0010”,
“1001”, “1100”, “0110”, “1011”, “0101”, “1010”, “1101”, “1110”, “1111”, “0111”,
“0011”, “0001” (suponiendo que “1000” sea el estado inicial). Obsérvese que el estado
“0000” no forma parte de la secuencia y si el LSFR entra en él accidentalmente nunca
podrá salir del mismo.
Los LSFR presentan distintas propiedades que los hacen útiles en un gran número de
aplicaciones. En primer lugar, la pseudoaleatoriedad de la secuencia que siguen puede
usarse para cifrado de datos, testeo o modulación. En segundo lugar, la simplicidad de la
lógica que calcula el estado siguiente hace que sean unos contadores muy eficientes en
área y velocidad que pueden reemplazar a los contadores binarios convencionales
siempre y cuando el orden concreto en que se secuencian los estados no sea relevante.
Diséñese un LSFR de 16 bits con valor inicial tras reset (semilla de la secuencia pseudo
aleatoria) genérico.
49. Diseñar un generador de números pseudoaleatorios de 16 bits. El sistema permitirá la
carga síncrona de una semilla (a través de una entrada paralela de datos y señalizada por
una señal de carga) y en cada ciclo de reloj en que esté habilitado generará un número
distinto por su salida de 16 bits. (Pista: Bastará adaptar el LSFR diseñado
anteriormente. Téngase en cuenta que este circuito nunca generará el valor 0).
Ejercicios de Diseño Automático de Sistemas
pág. 8
50. Se denomina contador Bruijn de n bits, a un contador que siguiendo la secuencia de un
LSFR de n bits inserta el estado “00...00” entre los estados “00...01” y “10...00”. La
inserción de este estado permite que no haya estados prohibidos y que el contador sigua
una secuencia circular de 2n estados sin repetir ninguno de ellos. Diséñese un contador
Bruijn de 16 bits. (Pista: Aparte de un LSFR de 16 bits requerirá de un circuito
adicional que cuando detecte el patrón “00..01”realimente un ‘0’ y cuando detecte el
patrón “00..00” realimente un ‘1’. Obsérvese que en estos 2 estados realimenta el valor
calculado por la red de XOR pero invertido. En el resto de los estados realimenta
normalmente el valor calculado por dicha red).
Almacenes de datos:
51. Un banco de registros es un conjunto de registros que, para reducir el número de
interconexiones con el exterior, comparten un único puerto de escritura y uno o varios
puertos de lectura. Cada registro tiene asignada una dirección binaria que lo identifica.
Diseñar un banco de 16 registros de 8 bits con 1 puerto de escritura de datos, 1 puerto de
lectura de datos, 1 puerto de dirección de escritura, 1 puerto de escritura de datos y 1
puerto de capacitación de escritura.
52. Un buffer FIFO es un almacén “elástico” entre 2 subsistemas que teniendo un mismo
ancho de banda nominal, hacen el envío/recepción de datos siguiendo patrones
temporales distintos. Este tipo de buffer evita que los subsistemas tengan que
sincronizarse en cada transferencia, ya que cada uno de ellos puede hacer las
escrituras/lecturas de datos en el buffer según su disponibilidad.
La manera más simple de hacer un buffer síncrono es añadir un circuito de control a un
array genérico de elementos de almacenamiento del tipo banco de registros o RAM. El
circuito organiza los elementos de almacenamiento en forma de cola circular,
manteniendo 2 punteros que marcan el inicio y el final de datos dentro del buffer. El
primer puntero, denominado puntero de escritura, apunta al primer elemento libre del
buffer. Durante una operación de escritura, el dato se almacena en la posición indicada
por dicho puntero y después se incrementa. El segundo puntero, denominado puntero de
lectura, apunta al último elemento ocupado del buffer. Durante una operación de lectura,
el dato se lee de la posición indicada por dicho puntero y después se incrementa.
Obsérvese que un buffer FIFO no requiere señales explícitas para direccionar los
elementos de memoria. En su lugar, aparte de los puertos de entrada y salida de datos,
dispone de 2 señales de control, wr y rd, para iniciar una escritura y/o una lectura
respectivamente. Además dispone de 2 señales de estado, full y empty, para indicar
respectivamente cuándo la FIFO está completa y cuándo está vacía.
La implementación de los punteros no supone problema alguno pueden hacerse usando
cualquier tipo de contador y en particular usando aquellos de bajo coste (tipo Bruijin) ya
que el acceso a los registros no requiere que siga una secuencia binaria. La generación de
las señales full y empty es más compleja dado que ambas se activan cuando el valor de
ambos punteros es el mismo, ya sea porque el puntero de escritura ha alcanzado al de
lectura y por tanto la FIFO está completa, o porque el puntero de lectura ha alcanzado al
de escritura y por tanto la FIFO está vacía. Para implementar estas 2 señales existen 2
técnicas. La primera se basa en incrementar en 1 bit el tamaño de los contadores que
implementan los punteros: los bits menos significativos se usarán para direccionar los
elementos de memoria y el bit más significativo para implementar la lógica de estado. Es
sólo aplicable para punteros implementados con contadores binarios. La segunda, más
general, consiste en almacenar en 2 flip-flops el valor del estado y actualizar su valor en
Ejercicios de Diseño Automático de Sistemas
pág. 9
cada lectura/escritura según la operación/es solicitada/s y la comparación del valor actual
y siguiente de los punteros.
Diseñar una FIFO de 16 registros de 8 bits.
53. Un buffer LIFO es un circuito análogo a un buffer FIFO, pero en lugar de leerse los datos
en orden de escritura, el primer dato que se lee es siempre el último que se ha escrito.
Diseñar una LIFO de 16 registros de 8 bits. (Pista: El acceso solo requiere un puntero
que se incrementa/decrementa según el tipo de operación solicitada. Las señales de
estado se calculan de manera análoga al buffer FIFO).
Ejercicios de Diseño Automático de Sistemas
pág. 10