Palabras clave: máquina de estados, máquina expendedora

Una máquina de estados finitos (Finite-State Machine, FSM), abreviada como máquina de estados, es un modelo matemático que representa un número finito de estados, así como las transiciones y acciones entre esos estados. La máquina de estados no es solo una herramienta de descripción de circuitos, sino también un método de pensamiento, ampliamente utilizado en el diseño de circuitos a nivel de sistema y a nivel RTL.

Tipos de máquinas de estados

En Verilog, las máquinas de estados se utilizan principalmente en el diseño de lógica secuencial síncrona, y pueden conmutar los estados de un circuito secuencial entre un número finito de estados según ciertos requisitos y reglas. La dirección de la conmutación de estados depende no solo de los valores de entrada, sino también del estado actual. Las máquinas de estados se pueden dividir en 2 tipos: máquina de estados de Moore y máquina de estados de Mealy.

Máquina de estados tipo Moore

La salida de una máquina de estados tipo Moore solo depende del estado actual, no de la entrada actual.

La salida se mantiene estable durante un ciclo de reloj completo; incluso si la señal de entrada cambia en ese momento, la salida no cambia. El efecto de la entrada sobre la salida solo se refleja en el siguiente ciclo de reloj. Esta es también una característica importante de la máquina de estados tipo Moore: la entrada y la salida están aisladas.

Máquina de estados tipo Mealy

La salida de una máquina de estados tipo Mealy no solo depende del estado actual, sino también de la señal de entrada actual.

La salida de la máquina de estados tipo Mealy cambia inmediatamente después de que cambia la señal de entrada, y el cambio de entrada puede ocurrir en el ciclo de reloj de cualquier estado. Por lo tanto, bajo la misma lógica, la respuesta de la salida a la entrada de una máquina de estados tipo Mealy es un ciclo de reloj antes que la de una máquina de estados tipo Moore.

Proceso de diseño de máquinas de estados

Según los requisitos de diseño, dibuje el diagrama de transición de estados, determine el tipo de máquina de estados a utilizar y marque varias señales de entrada y salida, lo que facilita la programación. Generalmente, la máquina de estados de 3 secciones tipo Mealy es la más utilizada. A continuación, se ilustra el proceso de diseño de una máquina de estados mediante el ejemplo concreto del diseño de una máquina expendedora automática.

Máquina expendedora automática

La descripción funcional de la máquina expendedora automática es la siguiente:

El precio unitario de la bebida es de 2 yuanes, y esta máquina expendedora solo acepta monedas de 0,5 yuanes y 1 yuan. Se deben considerar el cambio y la dispensación. Tanto el proceso de inserción de monedas como el de dispensación se realizan una vez a la vez; no ocurre que se inserten varias monedas de una sola vez o se despachen varias botellas de bebida de una sola vez. Solo después de que cada ronda de la máquina expendedora complete la inserción de monedas, la dispensación y el cambio, puede entrar en un nuevo estado de venta automática.

El diagrama de transición de estados de trabajo de esta máquina expendedora se muestra a continuación, e incluye los estados de las señales de entrada y salida.

Aquí, coin = 1 significa que se ha insertado una moneda de 0,5 yuanes, y coin = 2 significa que se ha insertado una moneda de 1 yuan.

Diseño de la máquina de estados: estilo de 3 secciones (recomendado)

El diseño de la máquina de estados es el siguiente:

  • (0) Primero, determine la codificación de la máquina de estados según el número de estados. Asignar valores al registro de estados mediante la codificación mejora la legibilidad del código.
  • (1) Primera sección de la máquina de estados: lógica secuencial, asignación no bloqueante, transfiere el estado del registro.
  • (2) Segunda sección de la máquina de estados: lógica combinacional, asignación bloqueante, determina el siguiente estado de la máquina de estados según el estado actual y la entrada actual.
  • (3) Tercera sección de la máquina de estados: lógica secuencial, asignación no bloqueante; como es una máquina de estados tipo Mealy, determina la señal de salida según el estado actual y la entrada actual.

Ejemplo

// vending-machine
// 2 yuan for a bottle of drink
// only 2 coins supported: 5 jiao and 1 yuan
// finish the function of selling and changing

module  vending_machine_p3  (
    input           clk ,
    input           rstn ,
    input [1:0]     coin ,     //01 for 0.5 jiao, 10 for 1 yuan

    output [1:0]    change ,
    output          sell    //output the drink
    );

    //machine state decode
    parameter            IDLE   = 3'd0 ;
    parameter            GET05  = 3'd1 ;
    parameter            GET10  = 3'd2 ;
    parameter            GET15  = 3'd3 ;

    //machine variable
    reg [2:0]            st_next ;
    reg [2:0]            st_cur ;

    //(1) state transfer
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            st_cur      <= 'b0 ;
        end
        else begin
            st_cur      <= st_next ;
        end
    end

    //(2) state switch, using block assignment for combination-logic
    //all case items need to be displayed completely    
    always @(*) begin
        //st_next = st_cur ;//Si las condiciones no se consideran por completo, se puede asignar un valor inicial para eliminar el latch
        case(st_cur)
            IDLE:
                case (coin)
                    2'b01:     st_next = GET05 ;
                    2'b10:     st_next = GET10 ;
                    default:   st_next = IDLE ;
                endcase
            GET05:
                case (coin)
                    2'b01:     st_next = GET10 ;
                    2'b10:     st_next = GET15 ;
                    default:   st_next = GET05 ;
                endcase

            GET10:
                case (coin)
                    2'b01:     st_next = GET15 ;
                    2'b10:     st_next = IDLE ;
                    default:   st_next = GET10 ;
                endcase
            GET15:
                case (coin)
                    2'b01,2'b10:
                               st_next = IDLE ;
                    default:   st_next = GET15 ;
                endcase
            default:    st_next = IDLE ;
        endcase
    end

    //(3) output logic, using non-block assignment
    reg  [1:0]   change_r ;
    reg          sell_r ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            change_r       <= 2'b0 ;
            sell_r         <= 1'b0 ;
        end
        else if ((st_cur == GET15 && coin ==2'h1)
               || (st_cur == GET10 && coin ==2'd2)) begin
            change_r       <= 2'b0 ;
            sell_r         <= 1'b1 ;
        end
        else if (st_cur == GET15 && coin == 2'h2) begin
            change_r       <= 2'b1 ;
            sell_r         <= 1'b1 ;
        end
        else begin
            change_r       <= 2'b0 ;
            sell_r         <= 1'b0 ;
        end
    end
    assign       sell    = sell_r ;
    assign       change  = change_r ;

endmodule

El testbench se diseña de la siguiente manera. En la simulación se simulan 4 escenarios, que son:

case1 corresponde a la inserción consecutiva de 4 monedas de 5 jiao; case2 corresponde al orden de inserción de 1 yuan - 5 jiao - 1 yuan; case3 corresponde al orden de inserción de 5 jiao - 1 yuan - 5 jiao; case4 corresponde a la inserción de 3 monedas de 5 jiao consecutivas y luego una de 1 yuan.

Ejemplo

`timescale 1ns/1ps

module test ;
    reg          clk;
    reg          rstn ;
    reg [1:0]    coin ;
    wire [1:0]   change ;
    wire         sell ;

    //clock generating
    parameter    CYCLE_200MHz = 10 ; //
    always begin
        clk = 0 ; #(CYCLE_200MHz/2) ;
        clk = 1 ; #(CYCLE_200MHz/2) ;
    end

    //motivation generating
    reg [9:0]    buy_oper ; //store state of the buy operation
    initial begin
        buy_oper  = 'h0 ;
        coin      = 2'h0 ;
        rstn      = 1'b0 ;
        #8 rstn   = 1'b1 ;
        @(negedge clk) ;

        //case(1) 0.5 -> 0.5 -> 0.5 -> 0.5
        #16 ;
        buy_oper  = 10'b00_0101_0101 ;
        repeat(5) begin
            @(negedge clk) ;
            coin      = buy_oper[1:0] ;
            buy_oper  = buy_oper >> 2 ;
        end

        //case(2) 1 -> 0.5 -> 1, taking change
        #16 ;
        buy_oper  = 10'b00_0010_0110 ;
        repeat(5) begin
            @(negedge clk) ;
            coin      = buy_oper[1:0] ;
            buy_oper  = buy_oper >> 2 ;
        end

        //case(3) 0.5 -> 1 -> 0.5
        #16 ;
        buy_oper  = 10'b00_0001_1001 ;
        repeat(5) begin
            @(negedge clk) ;
            coin      = buy_oper[1:0] ;
            buy_oper  = buy_oper >> 2 ;
        end

        //case(4) 0.5 -> 0.5 -> 0.5 -> 1, taking change
        #16 ;
        buy_oper  = 10'b00_1001_0101 ;
        repeat(5) begin
            @(negedge clk) ;
            coin      = buy_oper[1:0] ;
            buy_oper  = buy_oper >> 2 ;
        end
    end

   //(1) mealy state with 3-stage
    vending_machine_p3    u_mealy_p3     (
        .clk              (clk),
        .rstn             (rstn),
        .coin             (coin),
        .change           (change),
        .sell             (sell)
        );

   //simulation finish
   always begin
      #100;
      if ($time >= 10000)  $finish ;
   end

endmodule // test

El resultado de la simulación es el siguiente:

Como se puede ver en la figura, la señal sell, que representa la acción de dispensación, puede elevarse a nivel alto normalmente después de completar la inserción de monedas, y la señal change, que representa la acción de cambio, también puede generar correctamente la señal de si se debe dar cambio o no según el escenario de monedas de entrada.

Modificación de la máquina de estados: estilo de 2 secciones

Si se combinan las descripciones de la segunda y la tercera sección de la máquina de estados de 3 secciones, manteniendo el resto sin cambios, la máquina de estados se convierte en una descripción de 2 secciones.

La parte modificada es la siguiente:

Ejemplo

//(2) state switch, and output logic
//all using block assignment for combination-logic
reg  [1:0]   change_r ;
reg          sell_r ;
always @(*) begin //all case items need to be displayed completely
    case(st_cur)
        IDLE: begin
            change_r     = 2'b0 ;
            sell_r       = 1'b0 ;
            case (coin)
                2'b01:     st_next = GET05 ;
                2'b10:     st_next = GET10 ;
                default:   st_next = IDLE ;
            endcase // case (coin)
        end
        GET05: begin
            change_r     = 2'b0 ;
            sell_r       = 1'b0 ;
            case (coin)
                2'b01:     st_next = GET10 ;
                2'b10:     st_next = GET15 ;
                default:   st_next = GET05 ;
            endcase // case (coin)
        end

        GET10:
            case (coin)
                2'b01:     begin
                    st_next      = GET15 ;
                    change_r     = 2'b0 ;
                    sell_r       = 1'b0 ;
                end
                2'b10:     begin
                    st_next      = IDLE ;
                    change_r     = 2'b0 ;
                    sell_r       = 1'b1 ;
                end
                default:   begin
                    st_next      = GET10 ;
                    change_r     = 2'b0 ;
                    sell_r       = 1'b0 ;
                end
            endcase // case (coin)

        GET15:
            case (coin)
                2'b01: begin
                    st_next     = IDLE ;
                    change_r    = 2'b0 ;
                    sell_r      = 1'b1 ;
                end
                2'b10:     begin
                    st_next     = IDLE ;
                    change_r    = 2'b1 ;
                    sell_r      = 1'b1 ;
                end
                default:   begin
                    st_next     = GET15 ;
                    change_r    = 2'b0 ;
                    sell_r      = 1'b0 ;
                end
            endcase
        default:  begin
            st_next     = IDLE ;
            change_r    = 2'b0 ;
            sell_r      = 1'b0 ;
        end

    endcase
end

Instancie el nuevo módulo modificado anteriormente en el testbench de 3 secciones para realizar la simulación; el resultado es el siguiente:

Como se puede ver en la figura, la señal de dispensación sell y la señal de cambio change se adelantan un ciclo de reloj con respecto a la salida de la máquina de estados de 3 secciones. Esto se debe a que las señales de salida se asignan con asignación bloqueante.

Como se muestra en las partes del círculo rojo en la figura, las señales de salida presentan pulsos de interferencia. Esto se debe a que las señales de entrada son asíncronas y las señales de salida son salidas de lógica combinacional, sin que el reloj las impulse.

En la práctica, si todas las señales de entrada están sincronizadas con el reloj, estos pulsos de interferencia no aparecerán. Si las señales de entrada son asíncronas, primero se deben sincronizar las señales.

Modificación de la máquina de estados: estilo de 1 sección (usar con precaución)

Si se combinan las descripciones de la primera, segunda y tercera secciones de la máquina de estados de 3 secciones, la máquina de estados se convierte en una descripción de 1 sección.

La parte modificada es la siguiente:

Ejemplo


    //(1) using one state-variable do describe
    reg  [1:0]   change_r ;
    reg          sell_r ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            st_cur     <= 'b0 ;
            change_r   <= 2'b0 ;
            sell_r     <= 1'b0 ;
        end
        else begin
            case(st_cur)

            IDLE: begin
                change_r  <= 2'b0 ;
                sell_r    <= 1'b0 ;
                case (coin)
                    2'b01:     st_cur <= GET05 ;
                    2'b10:     st_cur <= GET10 ;
                endcase
            end
            GET05: begin
                case (coin)
                    2'b01:     st_cur <= GET10 ;
                    2'b10:     st_cur <= GET15 ;
                endcase
            end

            GET10:
                case (coin)
                    2'b01:     st_cur   <=  GET15 ;
                    2'b10:     begin
                        st_cur   <= IDLE ;
                        sell_r   <= 1'b1 ;
                    end
                endcase

            GET15:
                case (coin)
                    2'b01:     begin
                        st_cur   <= IDLE ;
                        sell_r   <= 1'b1 ;
                    end
                    2'b10:     begin
                        st_cur   <= IDLE ;
                        change_r <= 2'b1 ;
                        sell_r   <= 1'b1 ;
                    end
                endcase

            default:  begin
                  st_cur    <= IDLE ;
            end

            endcase // case (st_cur)
        end // else: !if(!rstn)
    end

Instancie el nuevo módulo modificado anteriormente en el testbench de 3 secciones para realizar la simulación; el resultado es el siguiente:

Como se puede ver en la figura, las señales de salida son exactamente iguales a las de la máquina de estados de 3 secciones.

La desventaja de la máquina de estados de 1 sección es que muchos tipos de lógica se mezclan, lo que dificulta el mantenimiento posterior. Cuando el número de estados y señales de salida es pequeño, se puede intentar este método de descripción.

Modificación de la máquina de estados: tipo Moore

Si se utiliza una máquina de estados tipo Moore para describir el flujo de trabajo de la máquina expendedora, es necesario agregar 2 códigos de estado más para describir las señales de entrada y el estado de la máquina de estados en el momento en que la máquina de estados Mealy genera su salida.

El código Verilog de la máquina expendedora automática descrita con una máquina de estados de 3 secciones tipo Moore es el siguiente:

Ejemplo

module  vending_machine_moore    (
    input           clk ,
    input           rstn ,
    input [1:0]     coin ,     //01 for 0.5 jiao, 10 for 1 yuan

    output [1:0]    change ,
    output          sell    //output the drink
    );

    //machine state decode
    parameter            IDLE   = 3'd0 ;
    parameter            GET05  = 3'd1 ;
    parameter            GET10  = 3'd2 ;
    parameter            GET15  = 3'd3 ;
    // new state for moore state-machine
    parameter            GET20  = 3'd4 ;
    parameter            GET25  = 3'd5 ;

    //machine variable
    reg [2:0]            st_next ;
    reg [2:0]            st_cur ;

    //(1) state transfer
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            st_cur      <= 'b0 ;
        end
        else begin
            st_cur      <= st_next ;
        end
    end

    //(2) state switch, using block assignment for combination-logic
    always @(*) begin //all case items need to be displayed completely
        case(st_cur)
            IDLE:
                case (coin)
                    2'b01:     st_next = GET05 ;
                    2'b10:     st_next = GET10 ;
                    default:   st_next = IDLE ;
                endcase
            GET05:
                case (coin)
                    2'b01:     st_next = GET10 ;
                    2'b10:     st_next = GET15 ;
                    default:   st_next = GET05 ;
                endcase

            GET10:
                case (coin)
                    2'b01:     st_next = GET15 ;
                    2'b10:     st_next = GET20 ;
                    default:   st_next = GET10 ;
                endcase
            GET15:
                case (coin)
                    2'b01:     st_next = GET20 ;
                    2'b10:     st_next = GET25 ;
                    default:   st_next = GET15 ;
                endcase
            GET20:         st_next = IDLE ;
            GET25:         st_next = IDLE ;
            default:       st_next = IDLE ;
        endcase // case (st_cur)
    end // always @ (*)

   // (3) output logic,
   // one cycle delayed when using non-block assignment
    reg  [1:0]   change_r ;
    reg          sell_r ;
    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            change_r       <= 2'b0 ;
            sell_r         <= 1'b0 ;
        end
        else if (st_cur == GET20 ) begin
            sell_r         <= 1'b1 ;
        end
        else if (st_cur == GET25) begin
            change_r       <= 2'b1 ;
            sell_r         <= 1'b1 ;
        end
        else begin
            change_r       <= 2'b0 ;
            sell_r         <= 1'b0 ;
        end
    end
    assign       sell    = sell_r ;
    assign       change  = change_r ;

endmodule

Instancie la máquina de estados Moore modificada anteriormente en el testbench de 3 secciones para realizar la simulación; el resultado es el siguiente:

Como se puede ver en la figura, las señales de salida se retrasan un ciclo de reloj en comparación con la máquina de estados de 3 secciones tipo Mealy. Esto se debe a que entrar en los estados codificados recién agregados requiere un retraso de un ciclo de reloj. En este momento, si la salida usa asignación no bloqueante, la señal de salida final se retrasará un ciclo de reloj. Esta también es una característica de la máquina de estados tipo Moore.

Si al asignar las señales de salida se usa asignación bloqueante, se puede adelantar un ciclo de reloj.

La lógica de salida modificada es la siguiente.

Ejemplo


    // (3.2) output logic, using block assignment
    reg  [1:0]   change_r ;
    reg          sell_r ;
    always @(*) begin
        change_r  = 'b0 ;
        sell_r    = 'b0 ; //not list all condition, initializing them
        if (st_cur == GET20 ) begin
            sell_r         = 1'b1 ;
        end
        else if (st_cur == GET25) begin
            change_r       = 2'b1 ;
            sell_r         = 1'b1 ;
        end
    end

El resultado de la simulación con asignación bloqueante de las señales de salida es el siguiente:

Como se puede ver en la figura, las señales de salida ya son consistentes con la máquina de estados de 3 secciones tipo Mealy.

Descargar código fuente

Download