Apuntes sobre Verilog
Tema 4. Máquinas de Estado Finito
En este tema veremos uno de los circuitos lógicos secuenciales más útiles; la máquina de estados finitos.
En una máquina de estado finito, las salidas dependen del comportamiento pasado del circuito y del valor actual de las entradas. La máquina sólo puede estar en un estado cada vez y las transiciones de un estado a otro se hacen en función de un evento, normalmente un cambio en las entradas o el flanco del reloj.
Dependiendo del estado actual y el valor de las entradas, la máquina decide a qué estado saltar. Esto permite optimizar las salidas en comparación con un simple circuito lógico combinacional cuyas salidas dependen únicamente de los valores actuales de las entradas.
Hay dos tipos de máquinas, las de Moore y las de Mealy. Ambas están formadas por tres componentes: un circuito lógico combinacional para generar el estado siguiente, la memoria para mantener el estado actual y un circuito lógico combinacional para generar las salidas.
La diferencia principal entre ambos tipos de máquinas está en que en la máquina de Moore, las salidas dependen únicamente del estado actual; el circuito combinacional genera las salidas teniendo en cuenta solamente el estado actual de la máquina.
En una máquina de Mealy el circuito combinacional que genera las salidas tiene en cuenta el estado actual y el valor de las entradas.
La forma de representar ambas máquinas difiere ligeramente. En la máquina de Moore, dentro del estado se escribe el valor de la salida y en las transiciones se escribe el valor de las entradas.
Para representar una máquina de Mealy se dibujan los estados y en las transiciones se escriben el valor de las entradas y salidas.
Ejemplo de FSM
A continuación diseñaremos una FSM y veremos paso a paso cómo implementar la máquina en Verilog, primero como FSM de Moore y seguidamente como FSM de Mealy.
Imaginar un ascensor de tres plantas. En cada planta hay un final de carrera para indicar al controlador que se ha alcanzado el piso deseado y detener el ascensor. Utilizaremos esos finales de carrera para mostrar el piso en que se encuentra el ascensor mediante un display de 7 segmentos.
Un pulsador de reset inicializa la máquina a un estado conocido en caso de fallo del sistema.
Para simplificar vamos a suponer que el ascensor arranca desde el piso 0.
Esquema
Los finales de carrera se conectan en las entradas D0, D1 y D2 de la Alhambra. Conectamos unas resistencias pull-down de 1K5 en cada pin de entrada.
Para mostrar el piso utilizamos un decodificador BCD de 7 segmentos. Como sólo vamos a mostrar los pisos 0, 1 y 2 necesitamos únicamente los bits A y B que conectamos en las salidas GP0 y GP1 de la FPGA. Los bits C y D se conectan a GND.
1. FSM de Moore
Diagrama de estados
1.1 Cómo codificar una FSM de Moore empleando tres bloques always
La mejor manera de implementar una FSM de Moore en Verilog es utilizar múltiples bloques always, cada uno para realizar una tarea concreta.
Este estilo de modelar una FSM de Moore me parece el más apropiado porque al separar las diferentes funciones en tres bloques, el código es más legible e intuitivo.
Los pasos a seguir son:
a) Declaramos el módulo principal, las entradas y las salidas.
module floor_indicator (input reset, clk, input [2:0] ffcc, output reg [1:0] BCD);
b) Codificamos los estados que vamos a utilizar y declaramos los registros cs current state y ns next state del mismo tamaño que los registros para los estados.
Es importante declarar los registros estado actual cs y estado siguiente ns a continuación de las asignaciones de parámetros.
parameter [1:0] S0=2'b00, S1=2'b01, S2=2'b10, S3=2'b11;
reg [1:0] cs, ns;
c) Un bloque always para el circuito secuencial que almacena el estado actual. Al ser un circuito secuencial utilizamos asignaciones non-blocking <=. Este bloque sería la memoria en la representación de la FSM que vimos más arriba.
always @ (posedge clk, posedge reset)
begin
if (reset)
cs <= S0;
else
cs <= ns;
end
d) Un segundo bloque always para describir el circuito combinacional que genera el estado siguiente. Las transiciones se implementan con declaraciones if-else. Debe haber tantas condiciones if-else como transiciones en el diagrama de estados.
Con los circuitos combinacionales usamos asignaciones blocking =.
Con las declaraciones case hay que poner una condición por defecto, este punto es importante.
Este bloque se corresponde con el bloque de entrada en la representación de la FSM, por lo tanto es sensible a los cambios de estado cs y a las entradas ffcc.
always @ (cs, ffcc) begin
case (cs)
S0 : if (ffcc == 3'b001) ns = S1;
else ns = S0;
S1 : if (ffcc == 3'b010) ns = S2;
else ns = S1;
S2 : if (ffcc == 3'b100) ns = S3;
else if (ffcc == 3'b001) ns = S1;
else ns = S2;
S3: if (ffcc == 3'b010) ns = S2;
else ns = S3;
default: ns = S0; // poner siempre un estado por defecto
endcase
end
e) El último bloque always se corresponde con el circuito combinacional que genera las salidas en función del estado actual. Como estamos modelando una FSM de Moore el bloque always sólo es sensible al estado actual.
Dentro de un bloque always sólo se pueden hacer asignaciones a variables tipo reg, por eso hemos declarado la salida BCD como un registro. Al ser un circuito combinacional usamos asignaciones blocking =.
Para el estado S0 y default he asignado a la salida BCD el valor XX, pero se puede asignar otro valor, si queremos que el display muestre un valor concreto.
always @ (cs)
begin
case (cs)
S0: BCD = 2'bXX; // estado inicial, la salida no importa
S1: BCD = 2'b00; // muestra el número 0
S2: BCD = 2'b01; // muestra el número 1
S3: BCD = 2'b10; // muestra el número 2
default: BCD = 2'bXX; // poner siempre un estado por defecto
endcase
end
f) El archivo. pcf queda como sigue.
set_io reset 10
set_io clk 21
set_io ffcc[0] 119
set_io ffcc[1] 118
set_io ffcc[2] 117
set_io BCD[1] 38
set_io BCD[0] 37
Lo subimos a la Alhambra y verificamos su correcto funcionamiento.
El código completo de este ejemplo y los siguientes, están disponibles para descargar al final de la página.
1.2 Cómo codificar una FSM de Moore empleando dos bloques always
Otra opción es modelar la FSM utilizando dos bloques de procedimiento always, para ello agrupamos los dos bloques combinacionales en uno, manteniendo el resto igual.
Como la salida sólo depende del estado actual, se calcula fuera de las declaraciones if-else.
// FSM de Moore con dos bloques always
module floor_indicator (input reset, clk, input [2:0] ffcc, output reg [1:0] BCD);
parameter [1:0] S0=2'b00, S1=2'b01, S2=2'b10, S3=2'b11;
reg [1:0] cs, ns;
// circuito secuencial memoria de estados.
always @ (posedge clk, posedge reset)
begin
if (reset)
cs <= S0;
else
cs <= ns;
end
// circuito combinacional para las transiciones y salidas.
always @ (cs, ffcc) begin
case (cs)
S0 : begin
BCD = 2'bXX;
if (ffcc == 3'b001) ns = S1;
else ns = S0;
end
S1 : begin
BCD = 2'b00;
if (ffcc == 3'b010) ns = S2;
else ns = S1;
end
S2 : begin
BCD = 2'b01;
if (ffcc == 3'b100) ns = S3;
else if (ffcc == 3'b001) ns = S1;
else ns = S2;
end
S3: begin
BCD = 2'b10;
if (ffcc == 3'b010) ns = S2;
else ns = S3;
end
default: ns = S0; // poner siempre un estado por defecto
endcase
end
El archivo. pcf queda igual
set_io reset 10
set_io clk 21
set_io ffcc[0] 119
set_io ffcc[1] 118
set_io ffcc[2] 117
set_io BCD[1] 38
set_io BCD[0] 37
Lo subimos a la Alhambra y verificamos su correcto funcionamiento.
Cualquiera de las dos opciones que acabamos de ver a la hora de modelar una FSM de Moore es perfectamente válida, las dos son un buen estilo de programación. Lo que se debe evitar es agrupar todo el código en un único bloque always -se puede hacer- pero no es un estilo de programación recomendado.
2. FSM de Mealy
Diagrama de estados
2.1 Cómo codificar una FSM de Mealy empleando tres bloques always
Para implementar una máquina de Mealy seguimos las mismas recomendaciones anteriores. Los puntos a, b y c no cambian.
a) Declaramos el módulo principal, las entradas y las salidas.
// FSM de Mealy con dos bloques always
module floor_indicator (input reset, clk, input [2:0] ffcc, output reg [1:0] BCD);
b) Codificamos los estados que vamos a utilizar y declaramos los registros cs current state y ns next state.
parameter [1:0] S0=2'b00, S1=2'b01, S2=2'b10, S3=2'b11;
reg [1:0] cs, ns;
c) Un bloque always para el circuito secuencial que almacena el estado actual. Al ser un circuito secuencial utilizamos asignaciones non-blocking <=.
// circuito secuencial memoria de estados.
always @ (posedge clk, posedge reset)
begin
if (reset)
cs <= S0;
else
cs <= ns;
end
d) Un segundo bloque always para describir el circuito combinacional que genera el estado siguiente. Las transiciones se implementan con declaraciones if-else. Debe haber tantas condiciones if-else como transiciones en el diagrama de estados.
Con los circuitos combinacionales usamos asignaciones blocking =.
Con las declaraciones case hay que poner una condición por defecto, este punto es importante.
Este bloque se corresponde con el bloque de entrada en la representación de la FSM, por lo tanto es sensible a los cambios de estado cs y a las entradas ffcc.
// circuito combinacional para las transiciones.
always @ (cs, ffcc) begin
case (cs)
S0 : if (ffcc == 3'b001) ns = S1;
else ns = S0;
S1 : if (ffcc == 3'b010) ns = S2;
else ns = S1;
S2 : if (ffcc == 3'b100) ns = S3;
else if (ffcc == 3'b001) ns = S1;
else ns = S2;
S3: if (ffcc == 3'b010) ns = S2;
else ns = S3;
default: ns = S0;
endcase
end
e) El tercer bloque always es el circuito combinacional que genera las salidas. Al ser una máquina de Mealy, las salidas dependen del estado actual cs y de las entradas ffcc, por eso se incluyen ambas en la lista de sensibilidades del bloque always. Además en cada estado la salida puede tomar diferentes valores en función de las entradas, eso se modela con declaraciones if-else. Y como es un circuito combinacional usamos asignaciones blocking =.
// circuito combinacional para las salidas.
always @ (cs, ffcc)
begin
case (cs)
S0 : begin
if (ffcc == 3'b001) BCD = 2'b00;
else BCD = 2'bXX;
end
S1 : begin
if (ffcc == 3'b010) BCD = 2'b01;
else BCD = 2'b00;
end
S2 : begin
if (ffcc == 3'b100) BCD = 2'b10;
else if (ffcc == 3'b001) BCD = 2'b00;
else BCD = 2'b01;
end
S3: begin
if (ffcc == 3'b010) BCD = 2'b01;
else BCD = 2'b10;
end
default: BCD = 2'bXX;
endcase
end
endmodule
f) El archivo. pcf no cambia respecto a la FSM de Moore.
set_io reset 10
set_io clk 21
set_io ffcc[0] 119
set_io ffcc[1] 118
set_io ffcc[2] 117
set_io BCD[1] 38
set_io BCD[0] 37
Lo subimos a la Alhambra y verificamos su correcto funcionamiento.
2.2 Cómo codificar una FSM de Mealy con dos bloques always
Para implementar una máquina de Mealy seguimos las mismas recomendaciones anteriores. Los puntos a, b y c no cambian.
// FSM de Mealy con dos bloques always
module floor_indicator (input reset, clk, input [2:0] ffcc, output reg [1:0] BCD);
parameter [1:0] S0=2'b00, S1=2'b01, S2=2'b10, S3=2'b11;
reg [1:0] cs, ns;
// circuito secuencial memoria de estados.
always @ (posedge clk, posedge reset)
begin
if (reset)
cs <= S0;
else
cs <= ns;
end
Al igual que en la FSM de Moore, agrupamos los dos circuitos combinacionales en un único bloque always. Sin embargo ahora la salida es función de la entrada y del estado actual, esto implica que hay que asignar las salidas dentro de las declaraciones if-else. Debe haber una declaración if-else por cada transición y al ser un circuito combinacional usamos asignaciones blocking =.
// circuito combinacional para las transiciones y salidas.
always @ (cs, ffcc) begin
case (cs)
S0 : begin
if (ffcc == 3'b001) begin
BCD = 2'b00;
ns = S1;
end
else begin
BCD = 2'bXX;
ns = S0;
end
end
S1 : begin
if (ffcc == 3'b010) begin
BCD = 2'b01;
ns = S2;
end
else begin
BCD = 2'b00;
ns = S1;
end
end
S2 : begin
if (ffcc == 3'b100) begin
BCD = 2'b10;
ns = S3;
end
else if (ffcc == 3'b001) begin
BCD = 2'b00;
ns = S1;
end
else begin
BCD = 2'b01;
ns = S2;
end
end
S3: begin
if (ffcc == 3'b010) begin
BCD = 2'b01;
ns = S2;
end
else begin
BCD = 2'b10;
ns = S3;
end
end
default: ns = S0; // poner siempre un estado por defecto
endcase
end
endmodule
El archivo .pcf es igual.
set_io reset 10
set_io clk 21
set_io ffcc[0] 119
set_io ffcc[1] 118
set_io ffcc[2] 117
set_io BCD[1] 38
set_io BCD[0] 37
Lo subimos a la Alhambra y verificamos su correcto funcionamiento.
3. Codificación de los estados
En el punto b) hemos explicado que hay que codificar los estados de la máquina asignando a cada estado un valor binario.
Esta codificación puede hacerse de tres formas principales:
1. Codificación binaria, cuando a cada estado se le asigna un valor binario. Es la que hemos utilizado en el ejemplo de FSM. Para una máquina de ocho estados sería:
parameter [2:0] S0=3'b000, S1=3'b001, S2=3'b010, S3=3'b011, S4=3'b100, S5=3'b101, S6=3'b110, S7=3'b111;
2. Gray code encoding, cuando a cada estado se le asigna un valor en binario que difiere en un único bit respecto de sus vecinos.
parameter [2:0] S0=3'b000, S1=3'b001, S2=3'b011, S3=3'b010, S4=3'b110, S5=3'b111, S6=3'b101, S7=3'b100;
3. La tercera técnica es one-hot encoding, consiste en que en cada número sólo hay un único número 1, el resto son ceros. Los códigos asignados a cada estado tienen tantos bits como estados tiene la máquina.
parameter [7:0] S0=8'b00000001, S1=8'b00000010, S2=8'b00000100, S3=8'b00001000, S4=8'b00010000, S5=8'b00100000, S6=8'b01000000, S7=8'b10000000;
Las codificaciones gray code y binaria son más eficientes que la codificación one-hot ya que con n flip-flops se pueden codificar 2n estados. La codificación gray code es muy útil cuando las transiciones son lineales porque el número de bits que cambian entre dos transiciones es sólo uno.
La codificación one-hot necesita más flip-flops para implementar la memoria, sin embargo, este estilo de codificación es el más utilizado porque minimiza los fallos entre transiciones y dado el alto número de células de que disponen las FPGA, el hecho de que necesiten más flip-flop no es un problema.
4. Comparativa entre máquina de Moore y Mealy.
5. Conclusiones
Elegir entre un tipo de máquina u otra depende de la tarea que se realice. ¿Queremos una máquina sincrónica o asincrónica? ¿la velocidad importa? ¿debe ser segura e inmune a los rebotes? La respuesta a estas preguntas determina el tipo de máquina que mejor se adapta a nuestras necesidades.
En cuanto al estilo empleado para modelar una máquina u otra, pues para gustos, los colores. En mi humilde opinión, si tuviera que modelar una FSM de Moore utilizaría tres bloques de procedimiento y para una FSM de Mealy prefiero el estilo de dos bloques always.
Links
Un excelente tutorial sobre FSM's en readthedocs.
Contiene plantillas para modelar máquinas de Moore y Mealy usando diferentes estilos.
How to write FSM in Verilog en asic-world.com
El amigo jospicant se ha currado un excelente tutorial en sobre FSM
En YouTube
FSM Mealy con Verilog, estilo de dos procesos Universidad Politécnica de Valencia
FSM Mealy con Verilog, estilo de tres procesos básico Universidad Politécnica de Valencia
MODELING FINITE STATE MACHINES, Parte 1
MODELING FINITE STATE MACHINES, Parte 2
By NPTEL Department of Computer Science & Engineering Indian Institute of Technology Kharagpur
Mealy state machine By Component Byte
Moore state machine By Component Byte
No tan bien editados como los anteriores, pero sí mejor explicado.
Diferentes estilos de implementar una FSM
Descargas
Descarga el código Verilog de los ejemplos anteriores aquí abajo.