INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

PRACTICA 13: MAQUINAS DE ESTADO (FSM: Finite State Machine)

13.1 MAQUINAS DE ESTADO MEALY Y MOORE:

Una red canónica secuencial puede ser representada por un diagrama que se muestra en la figura
13.1. La entrada presente es descrita por x(t) y la salida presente por z(t). Note que el estado
presente s(t) es la salida de un registro de estado, pudiendo ser una serie de flip-flops. La red
combinacional en la figura 13.1 ene 2 salidas: la salida z(t) y el próximo estado s(t+1).

Figura 13.1 Red canónica secuencial

Es frecuentemente conveniente dividir la red combinacional en dos partes, C1 y C2, como se

muestra en la figura 13.2. El módulo combinacional C1 ene a la entrada presente x(t) y al estado
presente s(t) como entradas, y salidas al próximo estado s(t+1). El módulo combinacional C2 ene
a la entrada presente x(t) y al estado presente s(t) como entradas, y salidas a la salida presente
z(t). Esta máquina en la cual la salida presente z(t) depende tanto del estado presente s(t) y la
entrada presente x(t) es llamada “maquina Mealy”.

Figura 13.2 Maquina de estado po Mealy Figura 13.3 Maquina de estado po Moore

Si la salida presente z(t) depende únicamente del estado presente s(t) como se muestra en la
figura 13.3, nos referimos a la máquina de estado conocida como “maquina Moore”
ING MIGUEL ANGEL PEREZ SOLANO Página 46
INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

13.2 DETECTOR DE SECUENCIA CON MAQUINA MOORE.

En esta sección se mostrará como diseñar una maquina Moore para detectar la secuencia 1101.
( se analiza desde el bit mas significa vo).En la próxima sección u lizaremos una maquina Mealy
para detectar la misma secuencia.

El primer paso es dibujar un diagrama de estado para detectar la secuencia 1101 usando una
maquina Moore. La salida z, de esta máquina Moore será 1 cuando la secuencia 1101 sea
detectada. Tomaremos al estado S0 como el estado inicial o de reset.

En la medida de lo posible, como esta es una maquina Moore en la cual las salidas dependen
únicamente del estado presente, desplegaremos el valor de la salida dentro del circulo en el
diagrama de estado bajo el nombre del estado como se muestra en la figura 13.4. Si se está en
estado S0 y la entrada es 0 el circuito se quedará en el estado S0 indicándolo por una flecha
arqueada en la figura 13.4 donde se ha escrito el valor de la próxima entrada sobre el arco.

empo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11

Ent: x(t) 0 0 1 0 1 1 0 1 1 0 1 1
Sal: z(t) 0 0 0 0 0 0 0 0 1 0 0 1
Nota: cada tn es un borde de clock (ascendente o descendente), por lo que la correspondiente salida se
presentara en el siguiente ciclo de clock .

Figura 13.4 Diagrama de estado para detectar la secuencia 1101.

Si la entrada es 1, entonces el circuito se moverá al estado S1 como se muestra en la figura 13.4,

lo que indica que un único 1 se ha sido recibido. Si se está en el estado S1 y la entrada es 0, se
debe regresar al estado S0. Por otro lado, si se está en S1 y se recibe un 1, el circuito se moverá a
S2, lo cual indica que ya se han recibido consecu vamente dos 1´s. Si se está en S2 y la entrada
es un 1, el circuito permanecerá en S2, pero si la entrada es un 0, entonces se moverá a S3, lo

ING MIGUEL ANGEL PEREZ SOLANO Página 47

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

cual indica que se ha recibido la secuencia 110. En este punto (s3), si se recibe un 0, el circuito se
debe regresar a S0.

Finalmente, si se está en el estado S3 y le llega a la entrada un 1, entonces se moverá al estado

S4 como se muestra en la figura 13.4, lo cual indica que ha sido recibida la secuencia 1101. Por lo
tanto, la salida z(t) se fijara en 1. Note que si estamos en S4 y la entrada es 0 entonces el circuito
deberá irse al estado S0, pero si estando en s4 le llega a la entrada un 1, el circuito se deberá
mover al estado s2, lo cual indica que se ha recibido dos 1´s consecu vos. Esta es la transición
que permite solapar bits para ser reu lizados. El úl mo en la secuencia detectada, puede ser
usado como el primer 1 de la próxima secuencia que está siendo buscada.

Si no queremos permi r el reuso del ul mo bit, para ser el posible primer bit de la siguiente
secuencia, la máquina de estado deberá modificada de S4 a S1, para reusar el primer bit, o de S4
a S0 si no queremos reusar ninguno.

13.3 DETECTOR DE SECUENCIA MEDIANTE UNA MAQUINA MEALY

El diagrama de estado de la maquina Moore de la figura 13.4 ene 5 estados. La salida z, en esta
máquina Moore es 1 cuando está en el estado s4. Otra forma de implementar este detector de
secuencia, es u lizando una maquina Mealy, donde la salida z será 1, cuando este en el estado
S3 y la entrada x(t) sea 1. El diagrama de estado para esta máquina Mealy usado para
implementar el detector de secuencia 1101 se muestra en la figura 13.5 (note que solo ene
cuatro estados).

empo t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11

Ent: x(t) 0 0 1 0 1 1 0 1 1 0 1 1
Sal: z(t) 0 0 0 0 0 0 0 1 0 0 1 0
Nota: cada tn es un borde de clock (ascendente o descendente), por lo que la correspondiente salida se
presentara en el mismo ciclo de clock cuando se cumple la secuencia .

Figura 13.5 Diagrama de estado para detectar la secuencia 1101 con una maquina Mealy.

ING MIGUEL ANGEL PEREZ SOLANO Página 48

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

En la figura 13.5 los valores de salida son mostradas sobre las transiciones a lo largo de las
condiciones de entrada. Transiciones desde el present_state (PS) son e quetadas con
“present_input /present_output”. Es importante entender que el valor de salida desplegado es
la salida combinacional que depende de la entrada presente y del estado presente como se
muestra en la figura 13.2. Por ejemplo, cuando el estado presente es S3 (significando que se ha
recibido 110) y la entrada presente es 1, la sálida z cambia a 1en ese misma transición. En la
próxima transición de clock el estado cambia a s1 y la salida cambiara a 0. Esto significa que la
salida z nunca latcheara el 1.

Si queremos que z sea una salida registrada (esto es sostener su valor cuando haya la transición
a S1), se tendría que agregar un flip-flop a la salida z(t) en la figura 13.2. Esto es, la salida del
módulo combinacional C2 en la figura 13.2 será conectada a la entrada D de un flip-flop po D.
Por lo que, si en la figura 13.5 el estado es S3 y la entrada presente se vuelve 1, la salida z será 1,
y sobre la próxima transición de clock este valor de salida 1 será latcheado a la salida del flip-flop
el estado cambiará a S1.

PROBLEMAS RESUELTOS

ER13_1.- En este ejemplo se implementará la maquina Moore diseñada en sección 13.2 para
detectar la secuencia 1101. A con nuación, se muestra el modelado en VHDL para implementarlo
en la tarjeta Nexys 3. El primer paso es definir los cinco estados; S0, S1, S2, S3, S4. Estos estados
son las salidas de los registros de estado en la figura 13.3. ¿De qué tamaño debe ser este registro?
Debido a que hay 5 estados, se necesitan al menos 3 bits para representar a los 5 estados (22=4,
y 23= 8 siendo ú l para representas 5 estados) si se codifican los estados como números binarios
como se muestra en la tabla 13.1. Un esquema alterno de codificación llamado codificación one-
hot. El cual u liza un flip-flop por estado. En este caso necesitaríamos 5 flip-flop, uno por bit como
se muestra en la tabla 13.1. Se podría pensar que es un desperdicio de flip-flops, pero los FPGAs
donde los flip-flops son suficientes, codificación one-hot es frecuentemente u lizado debido a
que usualmente reduce la complejidad de la lógica combinacional requerida para producir el
próximo estado. Otro esquema de codificación que también es posible es con el código Gray.

Tabla 15.1 Esquemas de codificación del estado.

En el modelado que se muestra a con nuación, para definir los estados (en este caso 5; S0, S1,
S2,S3,S4) se u liza la declaración type y entonces se define las dos señales; present_state y
next_state como sigue:

ING MIGUEL ANGEL PEREZ SOLANO Página 49

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

Note que el modelado del circuito se separa en tres procesos separados; uno para el registro de
estado y dos módulos combinacionales para C1 y C2. El proceso del registro de estado setea el
presente estado a S0 si clr está ac vo alto. De otra manera este mueve el present_state (PS) al
next_state (NS) en la transición del clock. El proceso C1 u liza una sentencia case para
implementar el diagrama de estado de la figura 13.5. El proceso C2 define la salida z dependiente
del present_state.

library IEEE;
use IEEE.STD_LOGIC_1164.all;

entity seqdeta_moore is
port (clk: in STD_LOGIC;
clr: in STD_LOGIC;
w: in STD_LOGIC;
z: out STD_LOGIC);
end seqdeta_moore;

architecture seqdeta of seqdeta_moore is

type state_type is (s0, s1, s2, s3, s4);

signal present_state, next_state: state_type;
begin

sreg: process(clk, clr)

begin
if clr = '1' then
present_state <= s0;
elsif clk'event and clk = '1' then
present_state <= next_state;
end if;
end process;

C1: process(present_state, w)
begin
case present_state is
when s0 =>
if w = '1' then
next_state <= s1;
else
next_state <= s0;
end if;
when s1 =>
if w = '1' then
next_state <= s2;
else

ING MIGUEL ANGEL PEREZ SOLANO Página 50

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

next_state <= s0;

end if;
when s2 =>
if w = '0' then
next_state <= s3;
else
next_state <= s2;
end if;
when s3 =>
if w = '1' then
next_state <= s4;
else
next_state <= s0;
end if;

when s4=>
if w = '0' then
next_state <= s0;
else
next_state <= s2;
end if;

when others =>

null;
end case;
end process;

C2: process(present_state)
begin
if present_state = s4 then
z <= '1';
else
z <= '0';
end if;

end process;
end seqdeta;

ER13_2.- El listado siguiente muestra el modelado en VHDL para implementar la maquina Moore
definido por el diagrama de estado de la figura 13.3. Compare el modelado Moore con el
modelado Mealy. Note que la maquina Mealy necesita únicamente cuatro estados, donde su
codificación binaria puede ser hecho con un numero binario de 2 bits. También note que la salida
del módulo C2 ene que volverse un circuito secuencial en el cual z se latchea a 1 en la transición
del clock cuando el present_state es S3 y w = 1.

library IEEE;
use IEEE.STD_LOGIC_1164.all;

ING MIGUEL ANGEL PEREZ SOLANO Página 51

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

en ty seqdeta_moore is
port (clk: in STD_LOGIC;
clr: in STD_LOGIC;
w: in STD_LOGIC;
z: out STD_LOGIC);
end seqdeta_moore;

architecture seqdeta of seqdeta_moore is

type state_type is (s0, s1, s2, s3);
signal present_state, next_state: state_type;
begin
sreg: process(clk, clr)
begin
if clr = '1' then
present_state <= s0;
elsif clk'event and clk = '1' then
present_state <= next_state;
end if;
end process;

C1: process(present_state, w)
begin
case present_state is
when s0 =>
if din = '1' then
next_state <= s1;
else
next_state <= s0;
end if;
when s1 =>
if din = '1' then
next_state <= s2;
else
next_state <= s0;
end if;
when s2 =>
if din = '0' then
next_state <= s3;
else
next_state <= s2;
end if;
when s3 =>
if din = '1' then
next_state <= s1;
else
ING MIGUEL ANGEL PEREZ SOLANO Página 52
INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

next_state <= s0;

end if;

when others =>

null;
end case;
end process;

C2: process(clk, clr)

begin
if clr=’1’ then
z<= ‘0’,
ELSIF CLK’event and clk = ‘1’ then
If present_state = S3 and w = ‘1’ then
z= ‘1’;
else
z = ‘0’;
end if;
end process;

ER13_3.- Es frecuentemente ú l habilitar una secuencia a través de un numero arbitrario de

estados, dejando en cada estado una can dad arbitraria de empo. Por ejemplo, considere un
grupo de semáforos mostrados en la figura 13.7. Estas luces se considera que estén en una
intersección con una calle que va de norte a sur y la otra carretera de este a oeste.

Figura 13.7 Norte-sur Este-oeste

Para simular estos semáforos u lizaremos 6 leds de la Nexys4 (led16_r, led16_b, led16_g y
led17_r, led17_b, led17_g ) y ciclar los 6 estados mostrados en la tabla 13.2. El diagrama de
estado para controlar estos semáforos se muestra en la figura 13.8. Si u lizamos un clock de 3 Hz
para manejar este diagrama, entonces un delay de 1 segundo se logrará permaneciendo en un
estado de tres ciclos. Similarmente, un delay de 5 segundos se logrará permaneciendo en un

ING MIGUEL ANGEL PEREZ SOLANO Página 53

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

estado 15 ciclos de clock. La variable “count” en la figura 13.8 se reseteará a cero cuando este
moviéndose al siguiente estado después de un meout.

El listado que se muestra a con nuación es un modelado VHDL que implementa el diagrama de
estado de la figura 13.8. Debido a que necesitamos un contador para el conteo de delays, es más
conveniente en este caso combinar el registro de estado y módulo combinacional C1 en la
maquina Moore en la figura 13.3 en un único proceso secuencial mostrado en el siguiente
modelado. Note que en este caso usaremos únicamente una única variable “state”.

Para generar la señal de 3 Hz u lizaremos un clock divisor. El modelado top-level se da en el

listado.

Tabla 13.2 Estado de los semáforos

Figura 13.8 Diagrama de estado para

controlar los semáforos

ING MIGUEL ANGEL PEREZ SOLANO Página 54

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

DIAGRAMA A BLOQUES DEL CIRCUITO

MODELADO DEL DIVISOR DE CLK

library IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_unsigned.all;

en ty ER13_a is
port(
mclk : in STD_LOGIC;
clr : in STD_LOGIC;
clk3 : out STD_LOGIC
);
end ER13_a;

architecture behavioral of ER13_a is

signal q: STD_LOGIC_VECTOR(24 downto 0);
begin

ING MIGUEL ANGEL PEREZ SOLANO Página 55

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

-- clock divider
process(mclk, clr)
begin
if clr = '1' then
q <= (others =>'0');
elsif mclk'event and mclk='1' then
q <= q + 1;
end if;
end process;
clk3 <= q (24); -- 3 Hz
end behavioral;

MODELADO DEL SEMAFORO

ibrary IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_unsigned.all;

en ty ER13_3b is
port (clk: in STD_LOGIC;
clr: in STD_LOGIC;
lights: out STD_LOGIC_VECTOR(5 downto 0));
end ER13_3b;

architecture traffic of ER13_3b is

type state_type is (s0, s1, s2, s3, s4, s5);
signal state: state_type;
signal count: STD_LOGIC_VECTOR(3 downto 0);
constant SEC5: STD_LOGIC_VECTOR(3 downto 0) := "1111";
constant SEC1: STD_LOGIC_VECTOR(3 downto 0) := "0011";
begin
process(clk, clr)
begin
if clr = '1' then
state <= s0;
count <= X"0";
elsif clk'event and clk = '1' then
case state is
when s0 =>
if count < SEC5 then
state <= s0;
count <= count + 1;
else
state <= s1;
ING MIGUEL ANGEL PEREZ SOLANO Página 56
INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

count <= X"0";

end if;
when s1 =>
if count < SEC1 then
state <= s1;
count <= count + 1;
else
state <= s2;
count <= X"0";
end if;
when s2 =>
if count < SEC1 then
state <= s2;
count <= count + 1;
else
state <= s3;
count <= X"0";
end if;
when s3 =>
if count < SEC5 then
state <= s3;
count <= count + 1;
else
state <= s4;
count <= X"0";
end if;
when s4 =>
if count < SEC1 then
state <= s4;
count <= count + 1;
else
state <= s5;
count <= X"0";
end if;
when s5 =>
if count < SEC1 then
state <= s5;
count <= count + 1;
else
state <= s0;
count <= X"0";
end if;
when others =>
state <= s0;
end case;
ING MIGUEL ANGEL PEREZ SOLANO Página 57
INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

end if;
end process;

C2: process(state)
begin
case state is
when s0 => lights <= "100001";
when s1 => lights <= "010001";
when s2 => lights <= "001001";
when s3 => lights <= "001100";
when s4 => lights <= "001001";
when s5 => lights <= "100001";
when others => lights <= "100001";
end case;
end process;
end traffic;

TOP_DEL SEMAFORO CON DIVISOR DE CLK.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

en ty TOP_ER13_4 is
Port ( mclk : in STD_LOGIC;
btn : in STD_LOGIC_VECTOR (0 downto 0);
led16_r : out STD_LOGIC;
led16_b : out STD_LOGIC;
led16_g : out STD_LOGIC;
led17_r : out STD_LOGIC;
led17_b : out STD_LOGIC;
led17_g : out STD_LOGIC);
end TOP_ER13_4;

architecture Behavioral of TOP_ER13_4 is

SIGNAL aux1: STD_LOGIC;
begin
clk_divider: en ty work.ER13_4a PORT MAP(
mclk => mclk ,
clr => btn(0),
clk3 => aux1
);

Inst_ER13_4b: en ty work.ER13_4b PORT MAP(

ING MIGUEL ANGEL PEREZ SOLANO Página 58

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

clk => aux1,

clr => btn(0) ,
lights(0) =>led16_r,
lights(1) =>led16_b,
lights(2) =>led16_g,
lights(3) =>led17_r,
lights(4) =>led17_b,
lights(5) =>led17_g

);
end Behavioral;

ER13_4

EP13_1 Obtener el modelado de un circuito contador ascendente binario/gray de módulo 8 (3

salidas), con una entrada reset en ac vo bajo. Esto es, una señal de entrada llamada sel
determinara; siendo “0” seguirá una secuencia en binario, pero si es ‘1’ avanzara contando en
gray. A con nuación, se indican las secuencias:

binario: 000, 001, 010, 011, 100, 101, 110, 111

Gray: 000, 001, 011, 010, 110, 111, 101, 100

A con nuación, se presenta el diagrama de estados que seguirá el circuito dependiendo del valor
de sel; o en binario o en gray. Así también el diagrama a bloques. Mediante instanciación
agregarle un clock de 1 Hz para implementarlo en la Nexys 3.

ING MIGUEL ANGEL PEREZ SOLANO Página 59

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

EP13_2 Obtener el Modelado de una máquina de estado que se muestra en el diagrama de

estados siguiente, u lizando una máquina secuencial (Modelo de Mealy) que produce una salida
alta cada vez que se detecta la secuencia 0101 en la entrada; y salida cero en el resto de los
casos. Se muestra un tabla con un ejemplo para la siguiente secuencia de entrada: 010110011...

EP13_3 Dado el siguiente modelado, obtenga el diagrama de estado y su diagrama a bloques.

Implementarlo en la Nexys 3 agregando un clock de 1 Hz.

library ieee;
use ieee.std_logic_1164.all;
en ty mealy_4s is
port ( clk : in std_logic;
data_in : in std_logic;
reset : in std_logic;
data_out : out std_logic_vector(1 downto 0)
);
end en ty;

architecture rtl of mealy_4s is

type state_type is (s0, s1, s2, s3);

ING MIGUEL ANGEL PEREZ SOLANO Página 60

INSTITUTO TECNOLOGICO DE OAXACA DISEÑO DIGITAL CON FPGAs Y VHDL

signal state : state_type;

begin
process (clk, reset)
begin
if reset = '1' then
state <= s0;
elsif (rising_edge(clk)) then

case state is
when s0=>
if data_in = '1' then
state <= s1;
else
state <= s0;
end if;
when s1=>
if data_in = '1' then
state <= s2;
else
state <= s1;
end if;
when s2=>
if data_in = '1' then
state <= s3;
else
state <= s2;
end if;
when s3=>
if data_in = '1' then
state <= s3;
else
state <= s1;
end if;
end case;
end if;
end process;

ING MIGUEL ANGEL PEREZ SOLANO Página 61