【Stateflow】 状態遷移図設計の基礎1 ~ Mealy/Moore ~

はじめに

状態遷移設計のワークフローについてハードウェア的、ソフトウェア的、仕様検討の観点でまとめを行っています。最終的に仕様書からStateflow®で記述してCやHDLコードを生成するところまで検討します。
そこで、自分用メモを兼ねて記事にしておきます。色々と見直しをしているので、将来的に修正を行う場合もあります。(生成コードの抜粋は折りたたんでおります)

作成環境

・Windows 10 (プラットフォーム)
・MATLAB R2020b
・Simulink
・Stateflow
・HDL Coder
・Embedded Coder
・Vivado 2018.2 (Xilinx)

歴史

偉人は歴史を残しました(謎)。詳細はWikipedia等で調べて頂ければと思います。
[1]. A Method for Synthesizing Sequential Circuits : George H. Mealy(1955)
[2]. Gedanken-experiments on Sequential Machines : Edward F. Moore(1956)
[3]. Statecharts: A visual formalism for complex systems : David Harel(1984)

[1] 現在の状態と入力(遷移条件)によって出力が決定される。
[2] 出力が（入力によらず）現在の状態によってのみ決定される。
[3] 状態遷移図表記に於いて、状態階層、並列状態などを取り入れる。

現在は、[3] を拡張したものをステートチャート(Statechart)とし、[1]、[2]と併せてJIS X 0131やISO/IEC 11411で表記が謳われています。

状態遷移図設計ワークフロー

ざっくりとしたワークフローは次のように考えています。
今回は、状態遷移図を作成する際に使用するツール(Stateflow)において、[1],[2]のMealy/Mooreのセマンティクスを適用させてみたいと思います。

取り扱う状態遷移の例

[状態遷移表] *p : priority
x0とx1は排反とします

状態	条件(*p1)	条件(*p2)
Q0	x1	x0
遷移先状態	Q1	Q0
Q1	x1	x0
遷移先状態	Q0	Q1

[状態毎の出力表]

状態	出力
Q0	z0
Q1	z1

ミーリ チャート (Mealy Chart)

遷移ラベルの記法 : 遷移条件 / 条件アクション(遷移条件が成立時つまり信号エッジ)
状態ラベルの記法 : 状態名

振る舞いの説明 : 入力(x0/x1)が決まったときに出力(z0/z1)が実行され、次の状態(Q0/Q1)へ遷移する

入出力の集合を次のように定義すると、下図のような組み合わせロジック(条件判定)とD-フリップフロップのハードウェアと見做されます。(Qが確定する前にGの値が確定します。)

\{x0,x1\} \quad \in\quad\ S \\

\{z0,z1\} \quad \in\quad G \\

ムーア チャート (Moore Chart)

遷移ラベルの記法 : 遷移条件
状態ラベルの記法 : 状態名/状態アクション(状態がアクティブになったときつまり信号レベル)

振る舞いの説明 : 入力(x0/x1)が決まったとき状態(Q0/Q1)へ遷移し、出力(z0/z1)が決まる

入出力の集合を次のように定義すると、下図のような組み合わせロジック(条件判定)とD-フリップフロップのハードウェアと見做されます。(Qが確定した後にGが確定します。)

\{x0,x1\} \quad \in\quad\ S \\

\{z0,z1\} \quad \in\quad G \\

Stateflowを使ったモデリング

Stateflowを使ってモデリングを行います。
MATLAB/Simulinkとの製品、Stateflowのセマンティクス、アクション言語(条件、出力を実行する際の記述に使用するプログラミング言語)による構成を図で示します。(MATLAB R2020b時点)

今回、Stateflowを使うにあたり、製品、セマンティクス、アクション言語の組み合わせをどの様に説明しようか？悩みに悩んでこの図にたどり着きました。結果的にはサッパリした図ですが、以外と上手くまとまったと思っています。(例えば、MATLAB上でStateflowを使う場合は、Classicタイプでアクション言語はMATLABのみがサポートされているなど)
StateflowはMATLAB上で使う、若しくはSimulink上で使うの何れか選択ができます。
本投稿ではMelay/Mooreのセマンティクスについて記載し、Simulink上で使用する事とします。

1.Stateflow Mealy モデル

MealyチャートをStateflowでモデリングします。アクション言語はMATLABです。
Mealyチャートでは、条件アクションのみが使用可能です。
x0とx1は排反なので、x0の真偽で判定可能です。

シミュレーション結果

入力が変化したタイミング(エッジ)で出力が変化しています。遷移条件が満たされたときに出力するため期待通りの出力タイミングと考えられます。

状態S1へ遷移が確定する直前(緑色)にGが1を出力しています。

Mealy チャート生成Cコード(一部抜粋)

状態量はDW構造体変数(サフィックス _DW)として生成されます。Cコードはあまり面白みが無い(綺麗なコード)ですね。。。
外側のif-elseで状態の判定。入れ子のif-elseで入力値の判定。よって、現在の状態がわかれば入力値によって出力が決まる処理になっています。

// 省略
void mealy0_step(void)
{
  if (mealy0_DW.is_c2_mealy0 == mealy0_IN_S0) {
    if (mealy0_U.X) {
      mealy0_Y.G = true;
      mealy0_DW.is_c2_mealy0 = mealy0_IN_S1;
    } else {
      mealy0_Y.G = false;
      mealy0_DW.is_c2_mealy0 = mealy0_IN_S0;
    }
  } else {
    if (mealy0_U.X) {
      mealy0_Y.G = false;
      mealy0_DW.is_c2_mealy0 = mealy0_IN_S0;
    } else {
      mealy0_Y.G = true;
      mealy0_DW.is_c2_mealy0 = mealy0_IN_S1;
    }
  }
}

Mealy チャート生成 Verilog-HDLコード(一部抜粋)

最初のalways文で状態を初期化
2つ目のalways文で入力と現在の状態の値で条件判定し出力Gを決定。その際、遷移先状態を格納するD-フリップフロップ(is_mealy_next)にパラメータ値を代入。

  // 省略
  parameter is_mealy_IN_S0 = 1'd0, is_mealy_IN_S1 = 1'd1;
  // 省略
  always @(posedge CLK)
    begin : mealy_1_process
      if (RST == 1'b0) begin
        is_mealy <= is_mealy_IN_S0;
      end
      else begin
        is_mealy <= is_mealy_next;
      end
    end

  always @(X, is_mealy) begin
    is_mealy_next = is_mealy;
    G_1 = 1'b0;
    case ( is_mealy)
      is_mealy_IN_S0 :
        begin
          if (X) begin
            G_1 = 1'b1;
            is_mealy_next = is_mealy_IN_S1;
          end
          else begin
            G_1 = 1'b0;
            is_mealy_next = is_mealy_IN_S0;
          end
        end
      default :
        begin
          if (X) begin
            G_1 = 1'b0;
            is_mealy_next = is_mealy_IN_S0;
          end
          else begin
            G_1 = 1'b1;
            is_mealy_next = is_mealy_IN_S1;
          end
        end
    endcase
  end
  assign G = G_1;

Verilog-HDLの実装結果

FPGA実装をしたので、組み合わせロジックはLookup Tableに割り当てられます。出力の組み合わせロジックのデシジョンテーブルを見ると、論理は確かに合っています。想定したイメージ図通りですね。

2.Stateflow Moore モデル

MooreチャートをStateflowでモデリングします。アクション言語はMATLABです。

シミュレーション結果

出力GがMealyと比べて1サンプル遅れます。状態遷移が確定したとき(レベル)に出力するため期待通りの出力タイミングと考えられます。

Moore チャート生成Cコード(一部抜粋)

外側のif-elseにて、現在の状態がS0/S1の何れかを判定。状態が決まれば、出力が決まる。入れ子のifにて入力の値を判定し状態を遷移(次回の判定で用いる状態が決まる)

// 省略
void moore0_step(void)
{
  if (moore0_DW.is_c2_moore0 == moore0_IN_S0) {
    moore0_Y.G = false;
    if (moore0_U.X) {
      moore0_DW.is_c2_moore0 = moore0_IN_S1;
    }
  } else {
    moore0_Y.G = true;
    if (moore0_U.X) {
      moore0_DW.is_c2_moore0 = moore0_IN_S0;
    }
  }
}

Moore チャート生成 Verilog-HDLコード(一部抜粋)

最初のalways文で入力Xによって状態を判定。
2つ目のalways文で状態毎の出力を決定。

  // 省略
  parameter is_moore_IN_S0 = 1'd0, is_moore_IN_S1 = 1'd1;
  // 省略
  always @(posedge CLK)
    begin : moore_1_process
      if (RST == 1'b0) begin
        is_moore <= is_moore_IN_S0;
      end
      else begin
        is_moore_temp = is_moore;
        case ( is_moore)
          is_moore_IN_S0 :
            begin
              if (X) begin
                is_moore_temp = is_moore_IN_S1;
              end
            end
          default :
            begin
              if (X) begin
                is_moore_temp = is_moore_IN_S0;
              end
            end
        endcase
        is_moore <= is_moore_temp;
      end
    end

  always @(is_moore) begin
    case ( is_moore)
      is_moore_IN_S0 :
        begin
          G_1 = 1'b0;
        end
      default :
        begin
          G_1 = 1'b1;
        end
    endcase
  end
  assign G = G_1;

Verilog-HDLの実装結果

RSTは自動生成されたリセット信号です。赤枠はLookup TableなのでD-フリップフロップ(状態相当)をリセットするわけではありません。RSTが1(真)のときXとGの値でLookup Tableの出力が決まると考えるとわかりやすいかと思います。こちらも想定したイメージ図通りです。

おわりに (Next Step)

MathWorks社のStateflowに関連するドキュメントの殆どはClassicタイプにおける記述です。Classsicタイプは状態アクション(entry/during/exit)、条件アクション、遷移アクションで出力を記述できます。一方、Mealy/Mooreは使用可能なアクションに制限があり、Mealyは条件アクションのみ、Mooreは状態アクション(during/exit)のみ使用可能です。

では、一体どのタイプを使えば良いのでしょうか? ドキュメントは次のような記述や、ガイドラインでタイプ設定に関する記述があります。その辺りを次回紐解いてみたいと思います。

参考

JIS X 0131:1995 ソフトウェアの状態遷移の構成及びその表記方法
ISO/IEC 11411:1995 情報技術－ソフトウェアの状態遷移の人間通信の表現
JIS X 0125:1986 決定表 Decision tables
ISO 5806:1984 情報処理－シングルヒット決定表 Information processing -- Specification of single-hit decision tables