キーワード:ステートマシン,自動販売機
有限状態機械(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型ステートマシンであるため、現在の状態と現在の入力に基づいて出力信号を決定する。
例
// 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元を投入する順序に対応する。
例
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段式の記述になる。
変更部分は次のとおりである:
例
//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コードは次のとおりである:
例
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


