有限狀態機的都會傳奇

タイトルが中国語なのは気まぐれです。
一応、『ステートマシンの都市伝説』と書いたつもりですがあってるかな？

さて、ステートマシンのエンコーディング方法について
それぞれ長所短所があって云々などといったことを
読んだり聞いたりしたことがあると思います。

実際のところどうなんでしょう？

FPGAをターゲットとして、ISEでちょっと実験してみました。

まずテストのコードはこれ。

module StateTestA (/*AUTOARG*/
// Outputs
DAT_O,
// Inputs
CLK_I, RST_I, DAT_I
);

input CLK_I;
input RST_I;

input [7:0] DAT_I;
output [7:0] DAT_O;

reg [7:0] DAT_O;

parameter [3:0]
STATE_A = 4'hA,
STATE_B = 4'hB,
STATE_C = 4'hC,
STATE_D = 4'hD,
STATE_E = 4'hE,
STATE_F = 4'hF;

reg [3:0] state_r;
reg [3:0] nxState;

reg [7:0] dataOut;

always @(posedge CLK_I or posedge RST_I) begin
if (RST_I)
state_r <= STATE_A;
else
state_r <= nxState;
end

always @* begin
nxState = state_r;
dataOut = 8'h00;
case (state_r)

STATE_A: begin
dataOut = 8'h00;
if (DAT_I==8'h03)
nxState = STATE_B;
end

STATE_B: begin
dataOut = 8'h05;
if (DAT_I==8'h0F)
nxState = STATE_C;
end

STATE_C: begin
dataOut = 8'h0A;
if (DAT_I==8'h3F)
nxState = STATE_D;
end

STATE_D: begin
dataOut = 8'h50;
if (DAT_I==8'hFF)
nxState = STATE_E;
end

STATE_E: begin
dataOut = 8'hA0;
if (DAT_I==8'hFC)
nxState = STATE_F;
end

STATE_F: begin
dataOut = 8'hFF;
if (DAT_I==8'hF0)
nxState = STATE_A;
end

default:; // No recovery

endcase
end

always @(posedge CLK_I)
DAT_O <= dataOut;

endmodule



６つのステートを作り、それをぐるっと１周させる単純なものです。
ステートのエンコーディングは適当。

まずは合成のプロパティの HDL Options で FSM Encoding Algorithm を One-Hot に設定。



合成結果のステートマシンの部分を View RTL Schematic で確認するとこんな感じ。



細かいところは見えないと思いますが、FFがステート数分の6つできていることは確認できると思います。

続いて、設定を Gray に変更してみると次のように変わりました。



こちらはFFの数は３つです。
回路の印象もずいぶん違うように見えます。

では次に、合成のレポートを見てみましょう。
主要な部分のみ抜粋します。

まずはワンホット。


[One-hot]

Optimizing FSM on signal with one-hot encoding.
-------------------
State | Encoding
-------------------
1010 | 000001
1011 | 000010
1100 | 000100
1101 | 001000
1110 | 010000
1111 | 100000
-------------------

Device utilization summary:
---------------------------

Selected Device : 3s500efg320-5

Number of Slices: 11 out of 4656 0%
Number of Slice Flip Flops: 10 out of 9312 0%
Number of 4 input LUTs: 21 out of 9312 0%
Number of IOs: 18
Number of bonded IOBs: 18 out of 232 7%
Number of GCLKs: 1 out of 24 4%

Timing Summary:
---------------
Speed Grade: -5

Minimum period: 3.012ns (Maximum Frequency: 331.956MHz)
Minimum input arrival time before clock: 6.108ns
Maximum output required time after clock: 4.063ns
Maximum combinational path delay: No path found



続いてグレイコード。


[Gray]

Optimizing FSM on signal with gray encoding.
-------------------
State | Encoding
-------------------
1010 | 000
1011 | 001
1100 | 011
1101 | 010
1110 | 110
1111 | 111
-------------------

Device utilization summary:
---------------------------

Selected Device : 3s500efg320-5

Number of Slices: 12 out of 4656 0%
Number of Slice Flip Flops: 7 out of 9312 0%
Number of 4 input LUTs: 21 out of 9312 0%
Number of IOs: 18
Number of bonded IOBs: 18 out of 232 7%
Number of GCLKs: 1 out of 24 4%

Timing Summary:
---------------
Speed Grade: -5

Minimum period: 3.078ns (Maximum Frequency: 324.839MHz)
Minimum input arrival time before clock: 6.843ns
Maximum output required time after clock: 4.063ns
Maximum combinational path delay: No path found



どうですか？
あなたのイメージと一致しているでしょうか？

ちなみにVHDLで似たようなことをやっているものを見つけたので紹介しておきます。
State machine encoding (Gray, Binary and One-hot)

他もいくつか試してみましたのでその結果も載せておきます。

ユーザーエンコードそのまま。


[User]

Optimizing FSM on signal with user encoding.
-------------------
State | Encoding
-------------------
1010 | 1010
1011 | 1011
1100 | 1100
1101 | 1101
1110 | 1110
1111 | 1111
-------------------

Device utilization summary:
---------------------------

Selected Device : 3s500efg320-5

Number of Slices: 16 out of 4656 0%
Number of Slice Flip Flops: 7 out of 9312 0%
Number of 4 input LUTs: 29 out of 9312 0%
Number of IOs: 18
Number of bonded IOBs: 18 out of 232 7%
Number of GCLKs: 1 out of 24 4%

Timing Summary:
---------------
Speed Grade: -5

Minimum period: 3.904ns (Maximum Frequency: 256.144MHz)
Minimum input arrival time before clock: 6.834ns
Maximum output required time after clock: 4.063ns
Maximum combinational path delay: No path found



ジョンソン。


[Johnson]

Optimizing FSM on signal with johnson encoding.
-------------------
State | Encoding
-------------------
1010 | 000
1011 | 001
1100 | 011
1101 | 111
1110 | 110
1111 | 100
-------------------

Device utilization summary:
---------------------------

Selected Device : 3s500efg320-5

Number of Slices: 11 out of 4656 0%
Number of Slice Flip Flops: 7 out of 9312 0%
Number of 4 input LUTs: 21 out of 9312 0%
Number of IOs: 18
Number of bonded IOBs: 18 out of 232 7%
Number of GCLKs: 1 out of 24 4%

Timing Summary:
---------------
Speed Grade: -5

Minimum period: 3.012ns (Maximum Frequency: 331.956MHz)
Minimum input arrival time before clock: 6.467ns
Maximum output required time after clock: 4.063ns
Maximum combinational path delay: No path found



オート。


[Auto]

Optimizing FSM on signal with sequential encoding.
-------------------
State | Encoding
-------------------
1010 | 000
1011 | 001
1100 | 010
1101 | 011
1110 | 100
1111 | 101
-------------------

Device utilization summary:
---------------------------

Selected Device : 3s500efg320-5

Number of Slices: 13 out of 4656 0%
Number of Slice Flip Flops: 7 out of 9312 0%
Number of 4 input LUTs: 24 out of 9312 0%
Number of IOs: 18
Number of bonded IOBs: 18 out of 232 7%
Number of GCLKs: 1 out of 24 4%

Timing Summary:
---------------
Speed Grade: -5

Minimum period: 4.038ns (Maximum Frequency: 247.620MHz)
Minimum input arrival time before clock: 6.441ns
Maximum output required time after clock: 4.063ns
Maximum combinational path delay: No path found



適当（いい加減）なエンコーディングをしているので
ユーザーエンコーディングそのままのものが結果が悪いのは予想がつきますが
なぜかAutoの場合もそれほど良くないですね。

Autoではバイナリエンコーディングされているようですが
FPGAの場合、グレイとバイナリではそれほど変わらないと思っていたのですが意外でした。

まあでも、この結果は今回たまたまで、他のオプションを変えたりもっと複雑なステート遷移のものだとまた違った結果が得られるかもしれません。

この結果が大きいと
感じるか感じないかはあなた次第です。