FPGAにおけるステート・マシン（FSM）のエンコード方式は？

今回はステート・マシン（Finite State Machine, FSM）のステートがどのようにエンコードされるかについて解説します。注意しないと、ユーザーの想定とは異なる回路になってしまいますので、ぜひご覧ください。

各エンコード方式の違いと、XilinxのVivado、Intel (Altera)のQuartusにおけるエンコード方式の設定についても解説します。

この記事のまとめ

• ステート・マシンはRTLで記述したようにエンコードされない
• 論理合成ツールがステート・マシンを推定すると、設定されたエンコード方式でエンコードする
• エンコード方式の設定方法を解説
• エンコード方式を設定しないと、多くのデザインではワン・ホットにエンコードされる

ステート・マシンの書き方

まずは、ステート・マシンの書き方の一例を示します。

(1) まずは、ステートを定義します

parameter JANUARY   = 4'd0;
parameter FEBRUARY  = 4'd1;
parameter MARCH     = 4'd2;
parameter APRIL     = 4'd3;
parameter MAY       = 4'd4;
parameter JUNE      = 4'd5;
parameter JULY      = 4'd6;
...

(2) ステートを保持するレジスタを定義します

reg [3:0]    current_state;
reg [3:0]    next_state;

(3) ステートが遷移する条件を記述します

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

always @ (posedge CLK or posedge FSM_RST) begin
    if (FSM_RST) begin
        current_state   <=  JANUARY;
    end else begin
        current_state   <=  next_state;
    end
end
always @ (current_state or j2f_trg or trg_redg) begin
    case (current_state)
        JANUARY     : begin
                if (j2f_trg == 1'b1)
                    next_state  <=  FEBRUARY;
                else
                    next_state  <=  current_state;
            end
        FEBRUARY    : begin
                if (trg_redg == 1'b1)
                    next_state  <=  MARCH;
                else
                    next_state  <=  current_state;
            end
        ...
    endcase
end

9~15行目を見ると、現在のステート（current_state）がJANUARYのとき、

• j2f_trgが1であれば、次のステート（next_state）がFEBRUARYに遷移
• j2f_trgが0であれば、次のステート（next_state）は現在のステート（current_state）をキープ

となります。このようにして、ステートが遷移するロジックができます。

ステート・マシンのエンコードはRTLと異なる

上記の記述では、図1のように4 bitのフリップ・フロップを使った回路が出来上がるように思われます。

しかし、実際はRTLで書いたような回路にはなりません。

図2にXilinxのVivadoでの合成結果を示します。

FSM_onehot_current_state_reg[*]というフリップ・フロップ12 bit分でステートを保持しています。つまり、表1のようになっています。

このように、論理合成ツールが「あ、これはステート・マシンだね！」と思うと（ステート・マシンを推定すると）勝手にエンコード方式を変えてしまいます。

今回の合成結果のエンコード方式はワン・ホット（One-hot）といいます。

ステート・マシンのエンコード方式

代表的なステート・マシンのエンコード方式は下記になります。

• シーケンシャル（Sequential）
• グレイ（Gray）
• ジョンソン（Johnson）
• ワン・ホット（One-hot）

各エンコード方式は表2のようになります。

各エンコード方式の特徴は下記のようになります。

• シーケンシャル

ステートを保持するためのフリップ・フロップ数が最小になります。一方、組合せ回路が大きくなりやすいため、組合せ回路の遅延が大きく、動作速度が遅くなる傾向があります。ステートの遷移の際、複数のビットがトグルするため、消費電力が大きくなります。

• グレイ ＆ ジョンソン

連続したステートの遷移で変化するビットが1bitだけなので、消費電力が小さいです。図3のような、分岐の無いステート・マシンに適しています。また、ステート遷移のときのグリッチを防ぐことができます。

グリッチとは… 例えば、シーケンシャルのNo.3→No.4の遷移では、011→100で3bitが変化します。このとき、遷移ロジックの出力（フリップ・フロップの入力）が、

011 → (一瞬) 111 → 100

となることがあります。この111がグリッチです。グレイとジョンソンでは、連続したステート遷移で変化するビットは1bitなので、グリッチの発生を防ぐことができます。

• ワン・ホット

ステート遷移で変化するビットが必ず2bitなので、比較的消費電力が小さいです。また、組合せ回路が小さくなるため、動作速度は最速のエンコード方式です。一方、ステートを保持するフリップ・フロップの数が多くなるため、多くのフリップ・フロップを消費します。一般的に、FPGAはフリップ・フロップが多めなので、ワン・ホット方式はFPGAに適していると言えます。ただし、デッドロックする場合があるため注意が必要です。

エンコード方式の設定方法（Vivado）

Tools→Settingsで、Synthesisタブ内の-fsm_extranctionでエンコード方式を選択します。デフォルトはautoです。

autoにすると、Vivadoが最適なエンコード方式を選択してくれます。Xilinxのマニュアルには、32bitまではワン・ホットになるような記載があるので、多くのデザインではワン・ホットになると考えられます。

エンコード方式の設定方法（Quartus）

Assignments→Settingsで、Compiler Settings内のAdvanced Settings (Synthesis)…をクリック。これで開いた設定画面のState Machine Processingでエンコード方式を選択します。デフォルトはAutoです。

Autoでは、FPGAの場合はワン・ホットになります。

エンコード方式を設定しない場合の注意点

上記のように、Vivado、Quartusともに、エンコード方式を設定しない場合のデフォルトはAutoです。この時、多くデザインではワン・ホット方式でエンコードされます。

ワン・ホット方式はデッドロックする場合があるため、リセット系統をちゃんと設計する必要があります。

まとめ

• ステート・マシンはRTLで記述したようにエンコードされない
• 論理合成ツールがステート・マシンを推定すると、設定されたエンコード方式でエンコードする
• エンコード方式の設定方法を解説
• エンコード方式を設定しないと、多くのデザインではワン・ホットにエンコードされる