Verilog Práctico
Capitulo 11. Finite State Machines
Las máquinas de estado finito o finite state machines, son uno de los circuitos digitales más útiles a la hora de implementar circuitos secuenciales. A grandes rasgos hay dos tipos de máquinas: Moore y Mealy. En la máquina de Mealy la salida depende de las entradas y del estado actual, mientras que en la máquina de Moore, la salida solo depende del estado actual.
Este capítulo es una introducción a las máquinas de estado finito. Sin entrar en qué tipo de máquina es, veremos un par de ejemplos y aprenderemos a modelar las máquinas y convertirlas en código Verilog. Se trata de aprender conceptos básicos; entradas, salidas, estados, transiciones...Más adelante profundizaremos en esta apasionante materia y veremos ejemplos de ambas máquinas.
Cuando hablamos de autómatas finitos, quiere decir que el número de estados posibles de la máquina es limitado. La forma de representar estas máquinas es mediante un diagrama que muestra los estados, las entradas y las transiciones entre estados.
Las flechas indican las transiciones hacia el siguiente estado cuando -por ejemplo- se acciona un pulsador. Si la flecha empieza y acaba en el mismo estado, significa que permanecemos en ese estado mientras la entrada no cambie.
Un autómata finito consta de un circuito lógico y una memoria.
Ejemplo 1
La mejor forma de entender lo que acabamos de explicar es con un ejemplo práctico. Veamos un autómata finito que controla el encendido de tres ledes.
1.1 Diagrama de estados
En el estado 00 los ledes están apagados, en el estado 01 encendemos el led 1, en el estado 2 encendemos los ledes 1 y 2 y en el estado 3 encendemos los tres ledes. La transición entre estados se hace mediante el switch 1 de la Alhambra.
Con cada pulsación del switch 1 vamos encendiendo un led, si pulsamos una cuarta vez, volvemos al estado inicial y se apagan todos los ledes.
1.2. Tabla de la verdad
Lo siguiente es hacer una tabla de la verdad con todas las combinaciones posibles de nuestra máquina. Hemos dicho más arriba que las salidas de un autómata finito dependen del estado actual de la máquina y de las entradas, luego el estado actual lo consideramos una entrada y a los estados siguientes, los consideramos salidas.
Como tenemos cuatro posibles estados, necesitamos dos bits para enumerarlos: cs1 y cs0 que junto con el pulsador sw1 hacen las tres entradas de nuestra máquina y con tres bits tenemos ocho posibles combinaciones en la tabla de la verdad.
Los tres ledes dl1, dl2 y dl3 más los dos bits para enumerar el estado siguiente ns1 y ns0, forman las salidas.
Ojo que los bits para enumerar el estado actual y el estado siguiente no son entradas y salidas reales, sino que son registros de memoria donde almacenamos el valor de los estados y así poder tomar decisiones dependiendo de su valor actual y pasado.
La forma de interpretar la tabla es la siguiente: por ejemplo la primera línea dice “estando en el estado 00, si no pulso sw1, los ledes están apagados y permanezco en el estado 00”
La segunda línea sería: estando en el estado 00, si pulso sw1, enciendo el led 1 y salto al estado 01.
La tercera línea dice: si estoy en el estado 01 y no pulso sw1, el led 1 sigue encendido y permanezco en el estado 01.
La cuarta línea es: estando en el estado 01, si pulso sw1 enciendo los ledes dl1 y dl2 y paso al estado 10. Y así sucesivamente hasta completar todas las posibles combinaciones.
1.3. Expresiones lógicas
Bien, lo siguiente es obtener las expresiones lógicas a partir de la tabla de la verdad y para ello vamos a utilizar el software logisim. Es un software libre y está disponible para múltiples plataformas. Puedes descargarlo en el link anterior.
Abrimos Logisim y vamos a Window → Combinational Analysis
En la pestaña Input introducimos las entradas y en la pestaña Outputs, las salidas.
Después ir a la pestaña Table y copiar los valores de la tabla de la verdad en el lugar que están las X.
Ir a la pestaña Expression y pinchando en el desplegable Output: podemos ver las expresiones lógicas para cada una de las salidas de nuestro autómata finito.
dl1 = ~cs1 sw1 + ~cs1 cs0 + cs1 ~cs0 + cs1 ~sw1
dl2= ~cs1 cs0 sw1 + cs1 ~cs0 + cs1 ~sw1
dl3 = cs1 ~cs0 sw1 + cs1 cs0 ~sw1
ns1 = ~cs1 cs0 sw1 + cs1 ~cs0 + cs1 ~sw1
ns0 = ~cs0 sw1 + cs0 ~sw1
Con estas expresiones ya tenemos todo lo necesario para crear el código Verilog de nuestro autómata.
1.4. Código Verilog
Un autómata finito es un circuito lógico combinacional más una memoria. Para modelarlo con Verilog declaramos un módulo que llamaremos fsm.
module fsm (input clk, switch1, output reg [2:0] led);
declaramos dos registros de dos bits que llamaremos cs (current state) y ns (next state).
reg [1:0] cs, ns;
declaramos un bloque always @* donde asignamos a las salidas led[0], led[1] y led[2] el valor de las expresiones lógicas que hemos obtenido con logisim.
Hay que modificar las expresiones lógicas para que sean compatibles con Atom. Para ello sustituimos los nombres de las variables cs0 y cs1 por cs[0] y cs[1] y cambiamos los símbolos + por || y · por && además de poner las operaciones && entre paréntesis.
led[0] <= (~cs[1] && sw1)||(~cs[1] && cs[0])||(cs[1] && ~cs[0])||(cs[1] && ~sw1);
led[1] <= (~cs[1] && cs[0] && sw1) || (cs[1] && ~cs[0]) || (cs[1] && ~sw1);
led[2] <= (cs[1 && ~cs[0] && sw1) || (cs[1] && cs[0] && ~sw1);
ns[0] <= (~cs[0] && sw1) || (cs[0] && ~sw1);
ns[1] <= (~cs[1] && cs[0] && sw1) || (cs[1] && ~cs[0]) || (cs[1] && ~sw1);
en otro bloque always actualizamos el valor del registro cs con el valor de ns.
always @ (posedge clk) begin
cs <= ns;
end
Con el módulo tic generamos un tic simple con cada pulsación del switch 1, de esta manera el cambio entre estados se produce por flanco de subida del pulsador.
tic ticgenerator (clk, switch1, sw1);
No es necesario copiar el código del generador tic dentro del código Verilog principal, en lugar de eso, lo guardamos en un archivo que llamaremos tic.v
y lo invocamos desde el módulo principal.
Este módulo generador de tic simple, lo vimos en el capítulo 8, consúltalo para más información.
Ponemos todo el código junto y queda así:
module fsm (input clk, switch1, output reg [2:0] led);
reg [1:0] cs, ns;
tic ticgenerator (clk, switch1, sw1);
always @* begin
led[0] <= (~cs[1] && sw1)||(~cs[1] && cs[0])||(cs[1] && ~cs[0])||(cs[1] && ~sw1);
led[1] <= (~cs[1] && cs[0] && sw1) || (cs[1] && ~cs[0]) || (cs[1] && ~sw1);
led[2] <= (cs[1 && ~cs[0] && sw1) || (cs[1] && cs[0] && ~sw1);
ns[0] <= (~cs[0] && sw1) || (cs[0] && ~sw1);
ns[1] <= (~cs[1] && cs[0] && sw1) || (cs[1] && ~cs[0]) || (cs[1] && ~sw1);
end
always @ (posedge clk) begin
cs <= ns;
end
endmodule
Archivo .pcf
set_io led[0] 95
set_io led[1] 96
set_io led[2] 97
set_io clk 21
set_io switch1 10
Lo subimos a la Alhambra y vemos que con cada pulsación de sw1 se van encendiendo los ledes 1, 2 y 3 y al pulsar una cuarta vez se apagan todos.
Ejemplo 2
En este ejercicio vamos a modelar un controlador para automatizar la persiana de una ventana.
Diseñaremos un autómata cuyas entradas son los pulsadores sw_up y sw_dw para subir y bajar la persiana y dos microswitches fc_up y fc_dw situados en los finales de recorrido superior e inferior.
Para las entradas sw_up y sw_dw vamos a utilizar los pulsadores de la Alhambra sw1 y sw2. Los finales de carrera los simularemos con dos interruptores externos y dos resistencias pull-down de 2k2.
Las salidas del autómata son las señales IN1 e IN2 que conectadas a un driver L298 nos servirán para controlar el sentido de giro del motor.
Esquema
1.1 Diagrama de estados
El funcionamiento del autómata es el siguiente. Partimos de un estado de reposo, si accionamos el pulsador de subida pasamos al estado 001 y hacemos que el valor de la salida sea 10 (IN1=1, IN2=0), si pulsamos sw_dw pasamos al estado 011 y hacemos la salida 01 invirtiendo el sentido de giro del motor.
En cualquier momento puedo soltar el pulsador sw_up o sw_dw -no tengo porqué subir o bajar la persiana del todo si no lo deseo- y entonces vuelvo al estado de reposo haciendo la salida 00 para que se detenga el motor.
Las cuatro entradas (4 bits) que condicionan la transición entre estados son, de izquierda a derecha sw_up, sw_dw, fc_up y fc_dw.
Si estando subiendo (estado 001) se acciona fc_up significa que he llegado al final del recorrido (estado 010), entonces hago la salida 00. Nota que mientras la persiana esté arriba el final de carrera fc_up estará accionado por defecto.
Si la persiana está abierta del todo (estado 010) y no acciono ningún pulsador, o bien acciono el de subida, permanezco en el mismo estado. Desde aquí la única opción es bajar la persiana accionando sw_dw, pasando al estado 011.
Si estoy bajando la persiana (estado 011) y se acciona fc_dw significa que he llegado al final del recorrido (estado 100), entonces hago la salida 00.
Si la persiana está bajada del todo (estado 100) y no acciono ningún pulsador, o bien acciono el de bajar, permanezco en el mismo estado. Desde aquí la única opción es subir la persiana accionando sw_up, pasando al estado 001.
Lo ponemos todo junto y el diagrama de estado queda como sigue:
1.2. Tabla de la verdad
Partiendo del diagrama de estados construimos la tabla de la verdad.
1.3. Expresiones lógicas
Con logisim generamos las expresiones lógicas.
in1 = sw_up · ~fc_up
in2 = sw_dw · ~fc_dw
ns2 = ~sw_up · fc_dw
ns1 = fc_up + (sw_dw · ~fc_dw)
ns0 = (sw_dw · ~fc_dw) + (sw_up · ~fc_up)
1.4. Código Verilog
Para terminar modelamos en Verilog las expresiones anteriores
module fsm (input clk, sw_up, sw_dw,fc_up, fc_dw, output reg [1:0] dir, output [1:0] led);
reg [2:0] cs, ns;
always @* begin
dir[0] <= (sw_up && ~fc_up);
dir[1] <= (sw_dw && ~fc_dw);
ns[0] <= (sw_dw && ~fc_dw) || (sw_up && ~fc_up);
ns[1] <= (fc_up) || (sw_dw && ~fc_dw);
ns[2] <= ~sw_up && fc_dw;
end
always @ (posedge clk) begin
cs <= ns;
end
assign led[1:0] = dir[1:0];
endmodule
Archivo .pcf
set_io led[0] 95
set_io led[1] 96
set_io dir[0] 112
set_io dir[1] 113
set_io clk 21
set_io sw_up 10
set_io sw_dw 11
set_io fc_up 118
set_io fc_dw 119
Lo subimos a la Alhambra y comprobamos que al pulsar sw1 o sw2 el motor gira en un sentido o en otro, simulando subir o bajar la persiana. Si estando subiendo accionamos fc_up vemos como el motor se para y aunque pulsemos de nuevo sw1 el motor no gira, ya que ha llegado al final del recorrido. Desde esta posición solo podemos bajar pulsando sw2. Y lo mismo sucede si estando bajando accionamos fc_dw, el motor se para y aunque pulsemos de nuevo sw2 el motor no gira.
A la hora de simular el circuito tened en cuenta que si partimos desde el final del recorrido, en cuanto la persiana empieza a bajar o subir se libera el final de carrera correspondiente.
Hemos modelado un autómata finito en una FPGA ¡que pasada!
Descargas
Descarga el código Verilog de los ejemplos 1 y 2 aquí abajo.