有限状態機械
MooreマシンとMealyマシン、状態のエンコード方法、2プロセス記述と1プロセス記述、そして初心者が最初のFSMで必ず引っかかるバグを解説します。
このレッスンで学ぶこと
- 制御問題の状態遷移図を描き、MooreマシンとMealyマシンを見分けられる
- 安全なデフォルト値を備えた2プロセス記述で、FSMをVerilogとVHDLで書ける
- バイナリ、Gray、ワンホットの各エンコードから選択し、その選択に対して合成が何をするかを説明できる
- ラッチ、デフォルトの欠落、到達不能状態など、よくあるFSMのバグを見分けられる
FPGA内の制御ロジックはほぼすべて有限状態機械（FSM）です。書いた本人がそう呼んでいるかどうかにかかわらず、です。スタートビットを待つUART受信器、リフレッシュを順に進めるメモリコントローラ、押下が短いか長いかを判定するボタンハンドラ。いずれも、名前の付いた少数の状態、状態間を移動する規則、そして現在どこにいるかに依存する出力で構成されています。このレッスンでは、状態遷移図の描き方、合成ツールが認識できるようにVerilogとVHDLで書く方法、そして落とし穴がどこにあるかを示します。レッスン04のレジスタとレッスン06のシミュレーションの内容が必要です。
状態機械とは何か
状態機械は3つの部分からなります。状態レジスタは現在の状態、つまり名前の付いた小さな集合のうちの1つの値を保持します。次状態ロジックは現在の状態と入力を見て、次のクロックエッジで状態レジスタに何を取り込むかを決めます。出力ロジックは出力を生成します。状態レジスタが唯一の記憶要素です。それ以外はすべて組み合わせ論理です。つまりFSMとは、すでに知っている「レジスタ＋ロジック」のパターンに、レジスタが取りうる各値へ名前を付けたものにすぎません。
このレッスンの例は、歩行者用横断ボタン付きの交通信号機です。状態は4つあります。赤、緑、黄、そして誰かがボタンを押したときだけ現れる歩行フェーズです。レッスン08のタイマーのような、1秒に1パルスの遅いtick入力が保持カウンタを進め、各灯が妥当な秒数だけ点灯し続けるようにします。
MooreかMealyか
古典的な2つの流儀の違いはただ1点、出力が何に依存するかです。
Mooreマシンでは、出力は状態のみの関数です。交通信号機はMooreマシンです。赤が点灯しているのは状態がS_REDだからで、その状態の間に入力が何をしてもランプは変わりません。Moore出力は、状態レジスタから直接駆動すればグリッチフリーで、クロックエッジでのみ変化し、動作を追いやすいという利点があります。代償はレイテンシです。入力イベントがあるエッジで状態を変え、出力はその次のエッジで追従します。
Mealyマシンでは、出力は状態と現在の入力に依存します。出力は入力と同じサイクルで応答できるため1クロック分のレイテンシを節約できますが、出力は入力からの組み合わせ論理になるので、入力がグリッチすれば出力もグリッチします。以下はMealyマシンとして書いた小さなシーケンス検出器です。シリアル入力上のパターン101を探し、最後の1が到着したのと同じサイクルでfoundを上げます。
// Mealy detector: `found` pulses in the same cycle as the last bit of "101".
module seq_mealy (
input wire clk,
input wire rst,
input wire din,
output reg found
);
localparam [1:0] S_IDLE = 2'd0, S_1 = 2'd1, S_10 = 2'd2;
reg [1:0] state;
// One-process style: next state and output in one block.
always @(posedge clk) begin
if (rst)
state <= S_IDLE;
else
case (state)
S_IDLE: state <= din ? S_1 : S_IDLE;
S_1: state <= din ? S_1 : S_10;
S_10: state <= din ? S_1 : S_IDLE;
default: state <= S_IDLE;
endcase
end
// Mealy output depends on input as well as state, so it is combinational.
always @(*)
found = (state == S_10) && din;
endmodule実際には、ほとんどのFPGA設計者はデフォルトでMooreマシンを書き、必要なMealy出力はモジュールから出る前にレジスタで受けます。「最後のビットが到着した」という信号が欲しく、かつクリーンであってほしいなら、レジスタで受けてください。その結果は、状態がひとつ増えたMooreマシンが姿を変えたものにほかなりません。
2プロセス記述
HDLでFSMを構成する方法は数多くあります。ここで教えるのは2プロセス記述です。1つのクロック同期プロセスが状態レジスタを保持し、1つの組み合わせプロセスが次状態と出力を計算します。Verilogによる交通信号機です。
// Traffic-light controller, Moore machine, two-process style.
// `tick` is a slow enable (for example once per second) from a timer.
// `walk_req` asks for a pedestrian phase at the next red.
module traffic_fsm (
input wire clk,
input wire rst,
input wire tick,
input wire walk_req,
output reg red,
output reg amber,
output reg green,
output reg walk
);
// State encoding. Synthesis may recode this; see the lesson text.
localparam [1:0] S_RED = 2'd0,
S_GREEN = 2'd1,
S_AMBER = 2'd2,
S_WALK = 2'd3;
reg [1:0] state, state_next;
reg [2:0] hold, hold_next; // ticks remaining in the current state
// Process 1: state register.
always @(posedge clk) begin
if (rst) begin
state <= S_RED;
hold <= 3'd0;
end else begin
state <= state_next;
hold <= hold_next;
end
end
// Process 2: next-state and output logic (combinational).
always @(*) begin
// Defaults first, so every path assigns every signal.
state_next = state;
hold_next = hold;
red = 1'b0; amber = 1'b0; green = 1'b0; walk = 1'b0;
case (state)
S_RED: begin
red = 1'b1;
if (tick) begin
if (hold == 3'd0) begin
if (walk_req) begin
state_next = S_WALK;
hold_next = 3'd3;
end else begin
state_next = S_GREEN;
hold_next = 3'd4;
end
end else
hold_next = hold - 3'd1;
end
end
S_GREEN: begin
green = 1'b1;
if (tick) begin
if (hold == 3'd0) begin
state_next = S_AMBER;
hold_next = 3'd1;
end else
hold_next = hold - 3'd1;
end
end
S_AMBER: begin
amber = 1'b1;
if (tick) begin
if (hold == 3'd0) begin
state_next = S_RED;
hold_next = 3'd2;
end else
hold_next = hold - 3'd1;
end
end
S_WALK: begin
red = 1'b1;
walk = 1'b1;
if (tick) begin
if (hold == 3'd0) begin
state_next = S_RED;
hold_next = 3'd2;
end else
hold_next = hold - 3'd1;
end
end
default: state_next = S_RED;
endcase
end
endmodule組み合わせブロックの3つの細部が、重みの大部分を担っています。
駆動するすべての信号に、冒頭でデフォルト値を与えています。これにより、caseがどの経路を辿っても、各出力と各_next信号が値を持つことが保証されます。どこかの経路で未代入のものがあれば、合成ツールは前の値を記憶しなければならず、組み合わせ論理でそれを実現する唯一の方法はラッチです。FPGAにおけるラッチは遅く、タイミング解析が難しく、ほぼ常に誤りです。
caseにはdefaultアームがあります。状態ビットが2つで状態が4つなら全パターンが使われますが、この習慣は3ビットで5状態の機械において重要です。余った3つのコードはグリッチや放射線イベントによって到達可能であり、機械はロックアップするのではなく回復すべきだからです。
組み合わせブロックの代入は=を、クロック同期ブロックの代入は<=を使います。混ぜても文法上は合法で、たいていは正しくシミュレーションされますが、この規則を守ることで意図が見え、正しく動かない少数のケースも避けられます。
保持カウンタは状態に入るときにロードされるため、その状態で費やすtickの数はロードした値より1つ多くなります。hold_next = 4でS_GREENに入ると、緑は5 tickになります。こうしたオフバイワンの疑問こそ、前回のレッスンのテストベンチの出番であり、このモジュールのテストベンチは演習にあります。
VHDLで同じ機械を書く
VHDLはFSMに本当の利点をひとつもたらします。列挙型です。状態は数値エンコードをまったく持たない型の名前付きの値であり、合成ツールがエンコードを選びます。
-- Traffic-light controller, Moore machine, two-process style.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity traffic_fsm is
port (
clk : in std_logic;
rst : in std_logic;
tick : in std_logic;
walk_req : in std_logic;
red : out std_logic;
amber : out std_logic;
green : out std_logic;
walk : out std_logic
);
end entity;
architecture rtl of traffic_fsm is
type state_t is (s_red, s_green, s_amber, s_walk);
signal state, state_next : state_t := s_red;
signal hold, hold_next : unsigned(2 downto 0) := (others => '0');
begin
-- Process 1: state register.
regs : process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
state <= s_red;
hold <= (others => '0');
else
state <= state_next;
hold <= hold_next;
end if;
end if;
end process;
-- Process 2: next state and outputs.
comb : process (all)
begin
state_next <= state;
hold_next <= hold;
red <= '0'; amber <= '0'; green <= '0'; walk <= '0';
case state is
when s_red =>
red <= '1';
if tick = '1' then
if hold = 0 then
if walk_req = '1' then
state_next <= s_walk;
hold_next <= to_unsigned(3, 3);
else
state_next <= s_green;
hold_next <= to_unsigned(4, 3);
end if;
else
hold_next <= hold - 1;
end if;
end if;
when s_green =>
green <= '1';
if tick = '1' then
if hold = 0 then
state_next <= s_amber;
hold_next <= to_unsigned(1, 3);
else
hold_next <= hold - 1;
end if;
end if;
when s_amber =>
amber <= '1';
if tick = '1' then
if hold = 0 then
state_next <= s_red;
hold_next <= to_unsigned(2, 3);
else
hold_next <= hold - 1;
end if;
end if;
when s_walk =>
red <= '1';
walk <= '1';
if tick = '1' then
if hold = 0 then
state_next <= s_red;
hold_next <= to_unsigned(2, 3);
else
hold_next <= hold - 1;
end if;
end if;
end case;
end process;
end architecture;process (all)はVHDL-2008の構文で、「内部で読まれるすべてに感度を持つ」という意味です。2008より前はすべての信号を手で列挙する必要があり、列挙漏れはシミュレーションと合成の不一致の古典的な原因でした。when othersアームがないのは、列挙型に対するcaseはすべての値を網羅しなければならず、コンパイラがそれを検査するからです。
1プロセスか2プロセスか
1プロセス記述では、seq_mealyがそうしたように、次状態ロジックと出力をクロック同期ブロックに入れます。短く書け、クロック同期ブロック内のものはすべてレジスタになるのでラッチを生じません。欠点は、すべての出力がレジスタ出力になり、望まない1サイクルのレイテンシが加わることと、Verilogではある分岐でstate <= S_GREENと書きながら、離れようとしている状態の出力がまだ駆動されていることを忘れやすいことです。それでも多くの経験豊富なエンジニアはこの記述を使い、満足しています。ここで2プロセス記述を教えるのは、状態遷移図に一対一で対応するからです。プロセス1が円、プロセス2が弧とラベルです。
レジスタ出力用に別のブロックを持つ3プロセス記述は、機械の出力が数個を超えたときによく使われる改良です。
状態のエンコードと合成が行うこと
Verilog版では状態に手で番号を割り当てました。0、1、2、3です。これはバイナリエンコードで、フリップフロップ数が最少です。ほかに2つの方式が一般的です。
| エンコード | N状態に必要なフリップフロップ | 長所 | 短所 |
|---|---|---|---|
| バイナリ | ceil(log2 N) | レジスタが最少 | 次状態ロジックが最も深く、遷移ごとに複数ビットが変化 |
| Gray | ceil(log2 N) | 単純なリングでは遷移ごとに1ビットだけ変化 | 分岐のある機械には不向き |
| ワンホット | N | ロジックが最も浅く最速、出力が状態ビットからそのまま得られることが多い | N個のフリップフロップ、うちN-1個は0 |
FPGAではフリップフロップが豊富にあり、ロジックの深さがクロック速度を決めるため、数十状態までの機械ではワンホットが通常の選択です。自分で選ぶ必要はめったにありません。Vivado、Quartus Prime、Radiant、Gowin EDA、YosysはいずれもFSM抽出を行います。値が定数との比較と定数からの代入にしか使われないレジスタを見つけ、状態遷移図を再構築し、到達不能状態を取り除き、再エンコードするのです。Vivadoはこれを合成ログに報告し、デフォルトのauto設定では小さな機械に対して通常ワンホットを選びます。fsm_encoding属性で上書きでき、他のツールにも同等のsyn_encodingやfsm_encoding属性があります。
抽出を妨げるものが2つあります。状態レジスタがどこかで数値として読まれる場合、たとえばインデックスとして使われたりモジュールの外へ出されたりする場合、ツールは書かれたエンコードを維持しなければなりません。また、リセット値が定数でない場合、既知の開始状態がありません。どちらの場合も機械は動きますが、書いたとおりのエンコードになります。
よくあるバグ
出会う可能性の高い順に、短く挙げます。
組み合わせプロセスのデフォルト欠落によって推論されたラッチ。合成ツールが警告します。警告を読んでください。
リセットの欠落。機械は、フリップフロップの電源投入時の値がたまたま示す状態から始まります。ほとんどのFPGAはビットストリームからレジスタを0に初期化するため、後でソフトリセットが追加されるまで問題が隠れます。
ボタンなど、同期化回路（シンクロナイザ）なしにピンから直接サンプリングされた入力。状態レジスタは2〜3ビットあり、準安定状態（メタステーブル）の入力は一部のビットを一方へ、残りを他方へ送り、機械を決して訪れるはずのなかった状態に着地させます。レッスン08が示すように、非同期入力はまずすべて同期化してください。
1サイクルだけ真であってほしいのに、複数サイクルにわたって真になる遷移条件。btnのようなレベル信号は、機械を複数の状態に連続して歩かせます。欲しいのは通常1サイクルのパルスであり、これもまたエッジ検出器の仕事です。
シミュレーションでは動くのにボードでは動かない機械。出力が入力のMealy関数で、グリッチするためです。レジスタで受けてください。
演習
レッスン06のスタイルでtraffic_fsmのテストベンチを書いてください。4クロックごとにtickパルスを生成し、リセットを2サイクル保持し、tickごとに4つのランプ出力を表示します。walk_reqをLowにしたまま信号を2周させ、次にHighにして、次の赤の後に歩行フェーズが現れ、4 tick続くことを確認してください。redとgreenが同時にHighにならないことを検査し、その検査は目で読むのではなく自動の$display("FAIL")にしてください。
次に、機械を手でワンホットに変換してください。状態ビット4つ、状態ごとに1つです。出力ロジックがどれだけ消えるかに注目してください。
まとめ
- FSMは状態レジスタと、次状態ロジックおよび出力ロジックからなります。まず遷移図を描き、そこからコードを書きます。
- Moore出力は状態のみに依存し、クロックエッジで変化します。Mealy出力は入力にも依存し、1サイクル早く応答しますが、グリッチすることがあります。
- 2プロセス記述はレジスタとロジックを分離します。ラッチを避けるため、組み合わせプロセスの冒頭ですべての信号にデフォルト値を与えてください。
- 合成ツールはFSMを抽出して再エンコードし、通常はワンホットにします。ただし状態が数値として読まれる場合や定数のリセットがない場合は除きます。
- よくあるバグは、ラッチ、リセットの欠落、同期化されていない入力、レベルトリガの遷移、グリッチするMealy出力です。