状態遷移図と状態遷移表

切符の自動販売機，つまり券売機を例に，シークエンス回路を作ってみよう。 いくらでも複雑な券売機でも設計可能であるが， ここでは簡単な例として，10円玉3枚で切符を1枚出す券売機を考える。 キャンセルはないものとする。 機械からはシークエンス回路への入力として，コイン受けに 10円玉があるかどうかを検出するセンサ（この出力を$In$とする）がある。 また出力としては，コイン受けからコインを取り込む$Take$，切符を発券する $Ticket$がある。 簡単のために，$Take$を出力すると，$In$は直ちに0になるものとする。

内部状態としては，機械が1円も受け取っていない0円状態，10円を受け取った 10円状態，20円受け取った20円状態の3状態がある。 次の10円を受け取ると，発券して0円状態に戻ればよいから， 30円状態は不要である。 これらの内部状態も2進表現にする必要があるので，それぞれ00，01，10 としよう。

0円状態で$In=0$のときには，ずっと0円状態にいる。 $In=1$となると，10円が入ったので，$Take=1$として10円を取り込み， 同時に自身は10円状態となる。 同様に10円状態でも，$In=0$のときにはずっと10円状態に居続ける。 $In=1$で$Take=1$を出力して，自身は20円状態となる。 20円状態でも，$In=0$のときにはずっと20円状態である。 $In=1$で$Take=1$を出力するが，同時に$Ticket=1$を出力して， 自身は0円状態に復帰する。

Figure 5.2: 券売機の状態遷移図

この流れを， 図 5.2に示す状態遷移図（transition diagram）と呼ばれるグラフで示す。 状態遷移図では遷移を決める入力とその際の出力を， 「入力/出力」の形で記載する。 また出力が0の場合には，ここにあるように記載を省くことが多い。 意味は明らかであろう。

さて， 図 5.1の論理回路はどのように設計したらよいのであろうか。 それは図 5.2の状態遷移図から容易に求めることができる。 例えば，同図の（00）状態から（01）状態への矢印グラフを見ると， $In=1/Take=1$と記載されている。 したがって，現在の内部状態が（00）で入力の$In$が1の場合， 次の状態が（01）で出力は $Take=1, Ticket=0$となる論理回路を作ればよいことになる。

Figure 5.3: 券売機の状態遷移表

図 5.3のように，各矢印ごとに， 遷移前の状態とそのときの入力を左に， 遷移先の状態とすべての出力を右に書いたものを状態遷移表（transition table）と呼ぶ。 この表は， 図 5.1の上の四角の論理回路の入出力関係を表しているから， この表の形の組合せ論理回路を作成し，各$S'_i$を，単位遅延を介して $S_i$に戻せばよい。

問題1

10円玉2枚で1枚のチケットを発券する券売機の状態遷移表を書け。

問題2

$Take=1$を出力すると$In$は自動的に0になるとしたが， クロックが速いと，この間の時間遅れが無視できなくなる。 つまり$Take=1$を出力しても，$In$はすぐには0にはならない。 こうしたときには$In=0$になるまで待つ必要が出てくる。 上記20円券売機に対し，そのときの状態遷移図および状態遷移表を書け。

ヒント　それぞれの内部状態に移行する前に， 待つための内部状態を用意する必要がある。