キーワード:ステートマシン,自動販売機

有限状態機械(Finite-State Machine、FSM)、略してステートマシンは、有限個の状態およびこれらの状態間の遷移や動作などの振る舞いを表す数学のモデルである。ステートマシンは回路の記述ツールであるだけでなく、思考方法でもあり、回路設計のシステムレベルおよびRTLレベルで広く応用されている。

ステートマシンの種類

Verilogにおけるステートマシンは主に同期順序論理の設計に使用され、有限個の状態間で一定の要求と規則に従って順序回路の状態を切り替えることができる。状態の切り替え方向は、各入力値だけでなく、現在の状態にも依存する。ステートマシンは2種類に分類できる:Moore型ステートマシンとMealy型ステートマシン。

Moore型ステートマシン

Moore型ステートマシンの出力は現在の状態のみに関係し、現在の入力には関係しない。

出力は1つの完全なクロック周期の間安定に保持され、このとき入力信号に変化があっても出力は変化しない。入力が出力に与える影響は次のクロック周期になって初めて反映される。これもMoore型ステートマシンの重要な特徴である:入力と出力は分離されている。

Mealy型ステートマシン

Mealy型ステートマシンの出力は、現在の状態だけでなく、現在の入力信号にも依存する。

Mealy型ステートマシンの出力は入力信号の変化後すぐに変化し、入力の変化は任意の状態のクロック周期内で発生する可能性がある。したがって、同じ論理の下では、Mealy型ステートマシンの出力の入力に対する応答はMoore型ステートマシンより1クロック周期早い。

ステートマシン設計フロー

設計要件に基づいて状態遷移図を描き、使用するステートマシンの種類を決定し、各種の入出力信号を記入すると、プログラミングに役立つ。一般に最も多く使用されるのはMealy型3段式ステートマシンである。以下では自動販売機を設計する具体例を通して、ステートマシンの設計過程を説明する。

自動販売機

自動販売機の機能説明は次のとおりである:

飲料の単価は2元で、この自動販売機は0.5元と1元の硬貨のみを受け付ける。釣り銭と商品の払い出しを考慮する。硬貨の投入と商品の払い出しは毎回1つずつ行われ、一度に複数の硬貨を投入したり、一度に複数の飲料を払い出したりする現象は発生しない。毎回の自動販売機の硬貨投入、商品払い出し、釣り銭の処理が完了して初めて、新しい自動販売状態に入ることができる。

この自動販売機の動作状態遷移図を次に示す。入力、出力信号の状態を含む。

ここで、coin = 1 は0.5元硬貨の投入を表し、coin = 2 は1元硬貨の投入を表す。

ステートマシン設計:3段式(推奨)

ステートマシンの設計は次のとおりである:

  • (0) まず、ステートマシンの状態数に基づいてステートマシンエンコーディングを決定する。エンコーディングを使用して状態レジスタに値を代入すると、コードの可読性が向上する。
  • (1) ステートマシンの第1段は、順序論理、非ブロッキング代入であり、レジスタの状態を伝達する。
  • (2) ステートマシンの第2段は、組み合わせ論理、ブロッキング代入であり、現在の状態と現在の入力に基づいて、次のステートマシンの状態を決定する。
  • (3) ステートマシンの第3段は、順序論理、非ブロッキング代入であり、Mealy型ステートマシンであるため、現在の状態と現在の入力に基づいて出力信号を決定する。

例

// 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 ;//条件の選択肢がすべて考慮されていない場合、初期値を代入して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

testbench の設計は次のとおりである。シミュレーションでは4つのシナリオを模擬している。それぞれ次のとおりである:

case1 は0.5元硬貨を4回連続で投入する場合に対応する;case2 は1元 - 0.5元 - 1元の投入順序に対応する;case3 は0.5元 - 1元 - 0.5元の投入順序に対応する;case4 は0.5元を3回連続して投入し、その後1元を投入する順序に対応する。

例

`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

シミュレーション結果は次のとおりである:

図からわかるように、払い出し動作を表す信号 sell は硬貨の投入完了後に正常にハイになる。一方、釣り銭動作を表す信号 change も入力された硬貨のシナリオに応じて、正しい釣り銭が必要かどうかの信号を出力している。

ステートマシン変更:2段式

3段式ステートマシンの第2段と第3段の記述を結合し、他の部分はそのままにすると、ステートマシンは2段式の記述になる。

変更部分は次のとおりである:

例

//(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

上記で変更した新しいモジュールを3段式の testbench にインスタンス化するとシミュレーションが実行できる。結果は次のとおりである:

図からわかるように、払い出し信号 sell と釣り銭信号 change は、3段式ステートマシンの出力より1クロック周期早い。これは出力信号がすべてブロッキング代入であるために生じる。

図中の赤い丸の部分のように、出力信号にグリッチパルスが発生している。これは入力信号がすべて非同期であり、かつ出力信号が組み合わせ論理出力でクロック駆動がないためである。

実際には、入力信号がすべてクロックと同期していれば、このようなグリッチパルスは発生しない。非同期入力信号の場合は、まず信号を同期させるべきである。

ステートマシン変更:1段式(慎重に使用)

3段式ステートマシンの第1段、第2段、第3段の記述を結合すると、ステートマシンは1段式の記述になる。

変更部分は次のとおりである:

例


    //(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

上記で変更した新しいモジュールを3段式の testbench にインスタンス化するとシミュレーションが実行できる。結果は次のとおりである:

図からわかるように、出力信号は3段式ステートマシンと完全に一致している。

1段式ステートマシンの欠点は、多くの種類の論理が混在しているため、後のメンテナンスが容易ではないことである。ステートマシンと出力信号が少ない場合は、この記述方式を試すことができる。

ステートマシン変更:Moore型

Moore型ステートマシンを使用して自動販売機の動作フローを記述する場合、Mealy型ステートマシンの出力時の入力信号とステートマシンの状態を記述するために、さらに2つの状態エンコーディングを追加する必要がある。

3段式Moore型ステートマシンで記述した自動販売機のVerilogコードは次のとおりである:

例

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

上記で変更したMooreステートマシンを3段式の testbench にインスタンス化するとシミュレーションが実行できる。結果は次のとおりである:

図からわかるように、出力信号はMealy型3段式ステートマシンと比較して1クロック周期遅延している。これは、追加されたエンコーディング状態のステートマシンに入るときに1クロック周期の遅延が必要なためである。このとき、出力に非ブロッキング代入を使用すると、最終的な出力信号が1クロック周期遅延することになる。これもMoore型ステートマシンの特徴である。

出力信号の代入時にブロッキング代入を使用すると、1クロック周期早めることができる。

出力ロジックの変更は次のとおりである。

例


    // (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

出力信号をブロッキング代入した場合のシミュレーション結果は次のとおりである:

図からわかるように、出力信号は3段式Mealy型ステートマシンと一致している。

ソースコードのダウンロード

Download