El tema de esta lección son las máquinas de estados finitos.
De hecho, las máquinas de estados finitos no son más que un modelo matemático de
los circuitos secuenciales que hemos estado viendo hasta ahora.
De modo que algunas partes de este tema ha podido sonar como que you lo hemos visto,
pero a pesar de todo es un tema importante.
Lo que pretendemos con esta lección es en primer lugar, formalizar matemáticamente
los circuitos secuenciales definiendo las máquinas de estados finitos.
Pretendemos también ver cómo se pueden especificar las máquinas de
estados finitos en un lenguaje de descripción hardware como el VHDL.
Y entre tanto, aprovecharemos para comentar algunos aspectos de la
implementación de circuitos secuenciales que no hemos tratado hasta ahora,
sobre todo aspectos directamente relacionados con las señales de
sincronización y la frecuencia de funcionamiento.
Una máquina de estados finitos o MEF o FSM en inglés,
porque son las siglas de Finite State Machine,
se define por un conjunto sigma de estados de entrada que
contiene todos los posibles valores que pueden tomar las señales de entrada.
Si el número de entradas es k, sigma contiene dos elevado a k ítems.
Un conjunto omega de estados de salida que contiene todos los posibles valores que
pueden tomar las señales de salida.
Un conjunto S de estados internos que contiene todos los posibles valores de las
variables almacenadas en la memoria en los biestables del circuito secuencial.
Y dos funciones f y h, que definen el funcionamiento de un circuito.
La función estado siguiente f,
asocia un estado interno a cada conjunto de estado interno y entrada.
La función de salida h,
pues también asocia una salida a cada pareja de estado y estado de entrada.
Hemos dicho que las máquinas de estado finito no son más que una
formalización matemática de un circuito secuencial y por tanto, cualquier circuito
secuencial podemos modelarlo por medio de una máquina de estados finitos, ¿no?
Vamos a ver un ejemplo, un contador binario ascendente de tres bits,
con una única entrada chip enable, recordad que esta entrada si es cero el
contador se queda siempre en el mismo estado y
cuando es uno a cada pulso de reloj el contador incrementa en uno su valor.
Pues un contador binario de estas características podemos modelarlo por una
máquina de estados finitos cuyo conjunto de entradas será el conjunto cero,
uno porque hay una única entrada Chip Enable.
El conjunto de estados internos viene dado por todos los posibles estados del
contador cero, uno, dos, tres, hasta siete.
El conjunto, el conjunto de salidas coincide exactamente con
el conjunto de estados internos, porque dijimos que en
un contador las salidas eran directamente los estados del circuito.
Y finalmente dos funciones para modelar el comportamiento del contador,
las funciones estado siguiente que dice que cuando estoy en el estado interno S,
si la entrada es cero el Count Enable es cero me queda el mismo estado y
si estoy en el estado S y me, Count Enable está uno,
al siguiente pulso de reloj pasaré al estado S más uno.
Módulo ocho porque el contador llega hasta a siete y vuelve a inicializarse en cero.
Y la función de salida que simplemente es muy sencilla porque dice,
si estoy en el estado S, me venga lo que me venga por la entrada la salida es S.
La salidas insisto coinciden con los estados internos en un contador.
Aquí tenemos una implementación muy sencilla y
muy directa del contador ascendente ¿no?
. Tenemos un registro dónde se guarda el
estado interno, una salida que hemos dicho que coincide con el estado interno y un
circuito combinacional, que sería esta parte que le calcula el estado siguiente.
¿Y cómo me lo calcula?
Pues, en función del estado actual y de la entrada Count Enable.
Si Count Enable es cero, el estado siguiente será directamente el estado
actual, es decir, el circuito se mantiene en el mismo estado en el que estaba.
Por el contrario, si Count Enable es uno el estado siguiente será el estado
actual más uno, dónde este bloque
representa un pequeño circuito que lo que hace es sumar uno al estado interno.
Bueno pues, you hemos visto que las máquinas de estado finito se
pueden ver simplemente como otro nombre distinto para los circuitos secuenciales.
Hay una ligera diferencia de matiz entre ambos.
Una diferencia que no se refleja en la definición y es que,
se suele utilizar el nombre de máquina de estados finitos cuando hablamos de
máquinas o de circuitos cuyo objetivo es principalmente controlar secuencias de
operaciones, más que implementar operaciones.
Pero insisto esto es una, es un matiz del uso que se le da a los dos términos,
que no tiene ningún reflejo la definición formal de las mismas.
Vamos a pasar ahora a estudiar qué pasa con la frecuencia de reloj.
La pregunta sería, ¿el reloj lo utilizamos?,
¿tiene algún limite?
¿Podemos utilizar un reloj de cualquier frecuencia y
la máquina siempre nos seguirá funcionando?
Obviamente la respuesta es que no, porque los circuitos son
dispositivos físicos que tienen unos tiempos de respuesta que nos
van a limitar la frecuencia de funcionamiento de la máquina.
Vamos a estudiarlo y vamos a estudiarlo primero, en una máquina de Moore.
¿Qué podemos representar con este esquema que tenemos aquí?
Tenemos un registro dónde vamos a guardar como you hacíamos antes el estado interno,
controlado por la señal de reloj, vamos a tener un circuito combinacional uno que
nos va a generar en función del estado interno y del estado de entrada
nos va a dar el estado siguiente, este circuito combinacional va a ser un
dispositivo físico y vamos a suponer que tiene un tiempo de respuesta t sub uno.
Y otro circuito combinacional al que hemos llamado dos, que en función
del estado interno no va a calcular, nos va a generar el estado de salida.
Y vamos a suponer que éste circuito tiene un retardo t sub dos,
un tiempo de respuesta t sub dos.
Además, estas entradas en general van a venir de alguna otra
parte de un circuito que también estará controlado por la misma señal de reloj.
Este circuito que habría aquí previamente también tiene su
tiempo de retardo y vamos a suponer que desde que la señal de reloj sube a uno,
pasa un tiempo que vamos a llamar s u input, tiempo de set up
de la entrada hasta que esta entrada no se ha estabilizado.
¿Vale?
Y vamos a calcular ahora,
¿qué tiempo necesito para que se hagan todas estas operaciones?
Fijaros, la idea es que en un ciclo de reloj en el intervalo de tiempo que viene
de aquí a aquí, yo voy a necesitar que tanto este circuito como el registro,
como el circuito combinacional dos me
haya respondido para que las cosas funcionen bien ¿no?
Entonces supongamos que llega un flanco de reloj, estamos en este punto la función
estado siguiente, ¿cuándo estaremos seguros de que you se ha estabilizado?
Dice pues en principio, vamos a necesitar primero un tiempo de set up
el t s u input, para asegurarnos de que las entradas son las correctas.
Y a partir de ese momento, necesitamos t sub uno unidades de tiempo
para que el circuito combinacional uno responda, es decir, a partir del flanco de
subida de reloj necesitaremos t sub uno más t s u inputs,
para estar seguros de que el estado siguiente está estable.
Por otro lado, a partir del estado interno,
¿cuánto tiempo necesitamos para calcular el estado de salida?
Pues, desde el flanco de subida necesitaremos simplemente t sub dos,
que es el tiempo de respuesta de este circuito.
Para que todo vaya bien,
en el intervalo de tiempo que va de flanco a flanco en un ciclo de reloj,
necesitamos que hayamos podido calcular tanto el estado siguiente como el
estado de salida, es decir, necesitamos que este intervalo de tiempo el período
del reloj sea o bien mayor que t sub uno más t set up o bien
mayor que t sub dos dependiendo de cuál de estos valores sea el mayor de ambos.
Es decir, necesitamos que el período de la señal del reloj sea mayor
que el máximo entre t set up input, más t sub uno y t sub dos.
Y por lo tanto, la frecuencia máxima de reloj de funcionamiento de
este circuito será uno partido por el
valor máximo entre tiempo de set up más t sub uno y t sub dos.
En el caso de una máquina de Mealy,
podríamos hacer un análisis totalmente análogo.
Aquí tenemos representado una máquina de Mealy dónde la única diferencia es que el
circuito combinacional dos para calcular el estado de salida necesita el estado
interno pero también necesita las entradas de la máquina de estados finitos.
El análisis insisto es el mismo, sea t sub uno el tiempo de respuesta del circuito
combinacional uno, t sub dos el tiempo de respuesta del circuito combinacional
dos y el t s u input, el tiempo que necesitan las entradas para estabilizarse.
Otra vez desde el momento que llega el flanco de subida,
¿cuánto tiempo necesitamos para calcular el estado siguiente?
Pues, el análisis es totalmente análogo al que hemos hecho antes.
Para calcular el estado siguiente necesitamos t s u input intervalos
de tiempo, unidades de tiempo para que las entradas se hayan estabilizado,
más t sub dos perdón, perdón t
sub uno para que el circuito combinacional uno tenga tiempo de responder.
En cuanto al tiempo que necesitamos para calcular el estado de salida,
aquí es ligeramente distinto porque necesitamos por un lado
tener estables las entradas, es decir, necesitamos que
haya pasado un tiempo t s u input, más el tiempo que
necesita el circuito combinacional dos para responder, más t sub dos.
De manera que ahora, el período de reloj debe ser
mayor que el máximo entre el tiempo de setup de las señales de
entrada más t sub uno o el tiempo de setup de las señales de entrada más t sub dos.
Y por tanto la frecuencia máxima del reloj será uno partido por
el máximo entre estos dos valores.
Elena ValderramaProfessor
Jean-Pierre DeschampsProfessor
Lluis TerésProfessor
Merce RullanProfesoraTitular
Joaquín Saiz AlcaineIngeniero Informático
David BañeresProfesor Agregado
Juan Antonio MartínezCollaborator
