学ぶ › トピック 11

ムーア型とミーリ型のステートマシン：設計の全手順

読了時間：約 7 分 · bitGateLab チーム

有限状態機械（FSM、ステートマシン）とは、処理がいまどの段階にあるかを「覚えている」順序回路です。信号機、暗証番号式の錠、エレベータの制御装置、シリアル通信の受信回路は、どれもステートマシンです。この記事では、古典的な二つのモデルであるムーア型とミーリ型を取り上げ、101 という系列の検出器を題材に、言葉による仕様からフリップフロップの式まで、設計の全手順をたどります。

ステートマシンの構成要素

同期式の FSM は、どれも三つのブロックからなります。

状態レジスタ：現在の状態を保持する n 個のフリップフロップ（ほとんどの場合 D 型）です。最大 2ⁿ 個の状態を表せます。
次状態論理：組み合わせ回路です。現在の状態と入力から、次の状態を計算します。
出力論理：組み合わせ回路です。出力を計算します。

二つのモデルの違いは、最後のブロックにあります。

ムーア型：出力は現在の状態だけで決まります。出力は各状態の円の中に書きます（たとえば S3/1）。
ミーリ型：出力は状態と入力の両方で決まります。出力は矢印の上に書きます（入力/出力の形で、たとえば 1/1）。

ミーリ型は、たいてい状態数が少なくて済み、入力が届いたのと同じサイクルで応答しますが、入力が変化すれば出力もいつでも変化しうるという性質があります。ムーア型は応答が 1 サイクル遅れますが、出力はクロックエッジの直後にしか変化しないので、よりきれいな信号になります。

課題：101 系列検出器

直列入力 X が、クロックに同期して 1 サイクルに 1 ビットずつ届きます。出力 Z は、最後に受け取った三つのビットが 1、0、1 になるたびに 1 にならなければなりません。重なり（オーバーラップ）を許します。つまり 10101 という列では検出が二回起こります。最初の系列の最後の 1 が、次の系列の先頭を兼ねるからです。

最初のステップは、マシンが何を覚えておくべきかを決めることです。各状態は「系列のどこまで進んだか」を表します。

S0：役に立つものはまだ何も受け取っていない。
S1：最後のビットが 1 だった。
S2：最後の二つのビットが 1、0 だった。
S3：1、0、1 を受け取ったところ（Z = 1）。

状態遷移図と状態表（ムーア型）

各状態と X の各値について、こう考えます。この新しいビットを加えたとき、101 の先頭部分と一致する最も長い接尾辞（末尾の部分列）はどれか。その接尾辞が次の状態を決めます。

重なりを許すムーア型の 101 検出器。矢印の上の数字は X の値で、出力は各状態の中に書いてあります。

現在の状態	X = 0	X = 1	Z
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

間違えやすい二つの遷移に注目してください。S1 でもう一つ 1 が届いた場合、列の末尾は 11 になり、最後の 1 は引き続き系列の先頭として使えるので、マシンは S1 にとどまります。S3 で 0 が届いた場合、列の末尾は 1010 になり、その接尾辞 10 が 101 の先頭部分と一致するので、S0 ではなく S2 に進みます。これが重なりの検出を可能にしています。

状態割り当てと式

状態が 4 個なら、D フリップフロップ 2 個（Q1 Q0）で足ります。最も素直な割り当ては 2 進の割り当てで、S0 = 00、S1 = 01、S2 = 10、S3 = 11 とします。D フリップフロップでは D = Q⁺ なので、励起表は自明です。

Q1	Q0	X	Q1⁺ = D1	Q0⁺ = D0
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

簡単化：

D0 が 1 になるのは、ちょうど X = 1 の行なので、D0 = X です。これは理にかなっています。この割り当てでは、Q0 = 1 は「最後のビットが 1 だった」ことを意味するからです。
D1 = Σm(2, 5, 6) です（変数の順は Q1 Q0 X）。最小項 2（010）と 6（110）は隣接していて、Q0·X になります。5（101）には 1 の隣接セルがないので単独で残り、Q1·Q0·X です。D1 = Q0·X + Q1·Q0·X。
ムーア型の出力は状態だけで決まります。Z = Q1·Q0。

回路は、D フリップフロップ 2 個、Z 用の 2 入力 AND 一つ、そして D1 用に 2 入力 AND 一つ、3 入力 AND 一つ、2 入力 OR 一つ（加えて Q0 と X のインバータ）で構成されます。

テスト系列による検証

入力 X = 1 0 1 0 1 1 0 1 を、S0 から始めて与えます。各エッジの後の状態は次のとおりです。

エッジ	1	2	3	4	5	6	7	8
X	1	0	1	0	1	1	0	1
状態	S1	S2	S3	S2	S3	S1	S2	S3
Z	0	0	1	0	1	0	0	1

検出は三回あります。ビット 1〜3、ビット 3〜5（重なり）、ビット 6〜8 です。エッジ 4 を式で確かめましょう。状態 S3 = 11、X = 0 のとき、D1 = 1·1 + 1·0·0 = 1、D0 = 0 で、次の状態は 10 = S2 です。一致します。

ミーリ型による実現

ミーリ型では出力を遷移に書くので、状態 S3 は不要になります。検出は「S2 にいるときに 1 が届いた時点」で起こります。三つの状態 A（何もなし）、B（最後のビットが 1）、C（最後の二つのビットが 1、0）を使うと、次のようになります。

状態	X = 0	X = 1
A	A / 0	B / 0
B	C / 0	B / 0
C	A / 0	B / 1

フリップフロップはやはり 2 個必要ですが、出力 Z = 1 は最後の 1 が届いたのと同じサイクルで現れ、ムーア型より 1 サイクル早くなります。

よくある間違い

「外れた」遷移をすべて S0 に戻してしまい、系列のどの部分がまだ使えるかを確認しない。これでは重なりのある検出を取りこぼします。
ムーア型で出力を矢印の上に書く、あるいはミーリ型で状態の中に書く。
使っていないフリップフロップの組み合わせ（たとえばミーリ型でのコード 11）を忘れる。行き先を決めるか、ドントケア（X）として扱ったうえで、マシンが正規のシーケンスに戻ることを確かめる必要があります。
ミーリ型の出力を任意のタイミングで読む。入力がすでに安定している、エッジの直前にサンプリングしなければなりません。
マシンをテストするとき、クロックのエッジちょうどで入力 X を変化させる。

シミュレータで試してみよう

式さえ求まれば、検出器を組むのに数分しかかかりません。タイミング図で、遷移を一つずつ確認できます。

同じクロックにつないだ D フリップフロップを二つ置き、出力に Q1、Q0 と名前を付けます。
入力 X を D0 に直接つなぎます。
インバータ二つ、AND 二つ、OR 一つで D1 = Q0·X + Q1·Q0·X を組み、D1 につなぎます。
Q1 と Q0 の AND を、Z 用の表示 LED につなぎます。
系列 1 0 1 0 1 1 0 1 に従って各エッジの前に X を切り替え、エッジ 3、5、8 の後に Z が点灯することをタイミング図で確かめます。

練習問題

重なりを許す場合、1010101 という列の中で、マシンは 101 を何回検出しますか。
解答
三回です。ビット 1〜3、3〜5、5〜7 で検出します。
重なりを許さない場合（検出のたびに最初からやり直す）について、101 検出器のムーア型の状態表を作り直してください。
解答
変わるのは S3 の行だけです。X = 0 なら S0 に、X = 1 なら S1 に進みます。ほかの行はそのままです。
ミーリ型で A = 00、B = 01、C = 10 と割り当てたとき、Z を求めてください。
解答
Z = 1 になるのは、状態 C で X = 1 のときだけです。Z = Q1·Q0·X。コード 11 が決して現れないならドントケア（X）として扱えるので、Z = Q1·X になります。
状態が 9 個のステートマシンには、フリップフロップが最低いくつ必要ですか。
解答
4 個です。2³ = 8 では足りず、2⁴ = 16 なら足りるからです。

状態レジスタを構成するフリップフロップを復習するには、ラッチとフリップフロップを参照してください。