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

Finite State Machines in Verilog by Peter Mathys

Descargas

Descarga el código Verilog de los ejemplos anteriores aquí abajo.