うさぎでもわかる論理回路　Dフリップフロップを用いた順序回路の設計

こんにちは、ももやまです。

前回は、順序回路を設計する前段階として、状態遷移図と状態遷移表を設計する方法について説明していきました。

うさぎでもわかる論理回路 - 順序回路の設計編　状態遷移図・状態遷移表の書き方

2022.7.11

こんにちは、ももやまです。 前回は 順序回路に関する基礎知識（フリップフロップなど）順序回路の読み方 など、順序回路を「よむ」練習をしましたね。 https://www.momoy...

今回は、設計した状態遷移図や状態遷移表から、実際にDフリップフロップを用いて順序回路を設計する方法を、2問の例題＋2問の練習問題で学習していきましょう。

スポンサードリンク

[復習] Dフリップフロップとは

まずは、今回使うDフリップフロップについて軽く復習しましょう。

(1) Dフリップとは

Dフリップフロップは、入力 \( D \) の値をそのまま次状態 \( Q_{n+1} \) として保持する最も基本的なフリップフロップです。

現状態 \( Q_{n} \) が0, 1のどちらであろうが、入力 \( D \) の値によって次状態 \( Q_{n+1} \) が決まるのが特徴です。

(2) Dフリップフロップの励起表

(1)では、入力 \( D \) と現状態 \( Q_n \) から次状態 \( Q_{n+1} \) がどのようになるかを表にして表しましたね。この状態遷移表のことを特性表と呼びます。

一方、順序回路の設計をする際には「現状態 \( Q_n \) から次状態 \( Q_{n+1} \) に遷移させるためには、フリップフロップにどんな値を入力すればよいか」を考える必要があります。この、「現状態 \( Q_n \) から次状態 \( Q_{n+1} \) に遷移させるためには、どんな値をフリップフロップに入力すべきか」を列挙した表を励起表（れいきひょう）と呼びます。

ここで、Dフリップフロップの場合、現状態 \( Q_n \) に関係なく、入力値 \( D \) の値がそのまま次状態 \( Q_{n+1} \) となるのでしたね。そのため、次状態 \( Q_{n+1} \) の値をそのまま \( D \) の入力部分に持ってくるだけで、簡単にDフリップフロップの励起表が完成します。

※ 現状態 \( Q_n \) の値は0だろうが1だろうが関係ないので、Don't Care（どうでもいい）を表す X を表の中に書いています。

実際にDフリップフロップを用いた順序回路を設計する際には、複数のフリップフロップやAND, OR, XORゲートが含まれた回路に対して、励起表を書いていきます。

（実際にどのように書くかは例題や練習問題で確認していきましょう。）

スポンサードリンク

[例題1] カウンタの設計

まずは、最も基本的な順序回路であるカウンタをDフリップフロップを使って設計してみましょう。

例題を用意したので、例題を踏まえながら設計手順を確認しましょう。

[1] 状態遷移図・状態遷移表の設計

順序回路を書くために、まずは与えられた問題の処理を実現するために状態遷移図・状態遷移表を設計していきましょう。

(i) 入力変数・出力変数を考える

まず最初に考えることは、与えられた問題から必要な入力変数・出力変数を考え、さらに定義することです。

今回の場合、与えられた問題文を詳しく書くと、「1つの入力変数の値が1であるかどうかをカウントし、1がカウントされた回数が偶数回になるごとに、1つの出力変数から1を出力する」となりますね。

よって、

• 入力変数 … 1つ（\( x \) と定義）
• 出力変数 … 1つ（\( z \) と定義）

となります。

(ii) 内部状態を考える

つぎは内部状態を定義しましょう。

ここで、必要な内部状態を考える際には、与えられた問題文を満たす回路を作るためにどんな状態を記憶すればよいかを考えます。

今回の場合は、1の数をカウントして偶数か奇数かを判定するため、

• 1のカウント回数が偶数の状態
• 1のカウント回数が奇数の状態

の2つさえ記憶できてしまえばOKです^[2]偶数に1を足すと必ず奇数に、奇数に1を足すと偶数になるため、具体的に1が何回入力されたかをカウントする必要はない。。

そのため、必要な内部状態は2個です。

(iii) 状態遷移図を考える

状態遷移図を書く際には、

1. 考えた状態に \( q_0 \) などの名前をつける
2. 状態を並べる
3. 状態遷移を書く（各入力ごとの状態遷移先[次状態]、および出力を書く）

の3ステップで書いてきましょう。

まずは、下のように(2)で考えた状態に名前をつけます。

今回は、最後に商品が出てから

• 1のカウント回数が偶数の状態 → \( q_0 \)
• 1のカウント回数が奇数の状態 → \( q_1 \)

とつけることにします。

つぎに、名前をつけた各状態を並べます。

あとは、各状態ごとに各入力 \( x = 0 \), \( x = 1 \) における遷移先（次状態）を書いていけばOKです。

今回の場合は、

• 入力 \( x = 0 \) のときは、1の数のカウントは変化しない
  → 偶数個 \( q_0 \) のときは偶数個 \( q_0 \)、奇数個 \( q_1 \) のときは奇数個 \( q_1 \)aa
  → 1が入力されてないときは、「1の入力回数は増えない」ので、出力は \( z = 0 \)
• 入力 \( x = 0 \) のときは、1の数のカウントが1増える
  → 偶数個 \( q_0 \) のときは奇数個 \( q_1 \)、奇数個 \( q_1 \) のときは偶数個 \( q_0 \)
  → 偶数個から奇数個になるときは、「1の入力回数が偶数回」とはならないため、出力は \( z → 奇数個から偶数個になるときに、「1の入力回数が偶数回」となるため、出力は \( z = 1 \)

を状態遷移図に落とし込んで矢印を追記していけばOKです。

[余談] 状態数の最小化

もし、「順序回路の状態数最小化」を習っている場合は、ここで「順序回路の状態数最小化」を適用することで、より簡単な状態遷移表、および順序回路を設計できる可能性があります。

(iv) 状態遷移表

状態遷移図を書き終わったら、つぎは状態遷移表を書いていきましょう。状態遷移図からたどれば、あっという間に書くことができます。

※ 自信があれば、状態遷移図を書かずにいきなり状態遷移表を書いてもOKです。

ここまで出来たら、状態遷移図・状態遷移表の設計の完了です。

ここからは、実際に順序回路を作成するための作業をしていきましょう。

[2-i] 必要なフリップフロップの数を考える

まずは定義した内部状態を記憶するために必要なフリップフロップの数を考えます。

今回の場合は、\( q_0 \), \( q_1 \) の2状態を記憶すればOKなので、必要なフリップフロップは1個となります^[3]1個のフリップフロップで2つの状態、2個のフリップフロップで4つの状態、3個のフリップフロップで8つの状態、…、\( n \) 個のフリップフロップで … Continue reading。

ここで、定義した内部状態の数 \( a \) と必要なフリップフロップの数 \( n \) について復習しましょう。

[2-ii] 励起表と出力値を合体させた表を書く

必要なフリップフロップの数を考えたあとは、つぎに、「フリップフロップの現状態 \( Q \) ・各入力」から「フリップフロップの次状態 \( Q \)」 に遷移させるためには、FFの入力値をどのようにすればよいかを考えていきます。

FFの入力値を考える際には、下のように「各フリップフロップの現状態・入力」に対して、「次状態と、次状態を満たすためのFFの入力（と順序回路の出力）」を表にして書いていきます。

※ この表のことを励起表（れいきひょう）と呼びます^[4]「[基礎] Dフリップフロップとは？」で励起表については説明しましたが、定着度を高めるために同じことを2回説明しています。。「励起表を書きなさい。」と言われたら、下のように、「現状態・各入力 → 次状態への遷移」の変化と、そのときのFFの入力値を明記した表を書いていけばいいんだなと思ってください。

[余談] 励起表は、「与えられた現状態→次状態の変化をさせるためには、どんなFFの入力をさせればよいか」を書くためのものなので、厳密には「順序回路の出力値」は励起表には含まれません。しかし、順序回路を書く際には出力値についても考える必要があるため、この記事には「励起表＋順序回路の出力方程式」まで1つの表として書くスタイルで解説をしています。

Step1. 定義した状態を、フリップフロップの状態の値に割り当てる

まずは、[1]で定義した状態を実際にフリップフロップの値状態に割り当てます。

今回の場合は、フリップフロップは1つなので、1つのフリップフロップを各状態に割り当てていきましょう。

• 状態 \( q_0 \) → \( Q = 0 \)
• 状態 \( q_1 \) → \( Q = 1 \)

※ フリップフロップの数が複数のときは、各状態を複数個のフリップフロップの組み合わせで割り当てます。（割り当ての例: 状態 \( q_0 \) → \( (Q_1,Q_2) = (0,0) \)。）

Step2. 状態遷移表から励起表の次状態・出力を埋める

つぎに、「[1](4) 状態遷移表の設計」で作成した状態遷移表から励起表を作り上げていきます。

Step3. 次状態からFFの入力値を求める

あとは、励起表の空欄部分である、FFの入力値を埋めればOKです。

※ Dフリップフロップの場合は、次状態 \( Q \) がそのままDフリップフロップの入力 \( D \) となるので簡単に埋めることができます。

[2-iii] 励起関数(FFの入力方程式)・順序回路の出力方程式を作る

完成した励起表（と出力値）が含まれた表から、FFの入力方程式（励起関数）、および順序回路の出力方程式を考えていきましょう。

※ 主加法標準形にした後に、\( D \) にブール代数の公式を適用しています。

今回は2変数なので（主加法標準形への変形とブール代数の公式を使うだけで）簡単に励起関数と出力方程式ができましたが、3変数以上になったり、Don't Care が出てくるとカルノー図などを使った簡略化が必要となります。[次の例題2で出てくるのでお楽しみに！]

[2-iv] 順序回路を設計する

いよいよ順序回路を設計していきましょう！

[2-iii]で作った励起関数 \( D = Q \oplus x \) と、出力方程式 \( z = Q \cdot x \) を使って、順序回路を作れば設計完了です！

※ 順序回路内に出てきたANDゲート、XORゲートの入力値を明記してわかりやすくしたバージョンも書いたので、参考にしてください。

スポンサードリンク

[例題2] 自動販売機の設計

カウンタと同じくらい試験で頻出するのが自動販売機の設計です。こちらも、例題を使って順序回路の設計の流れを見ていきましょう。

[1] 状態遷移図・状態遷移表の設計

順序回路を書く前に、与えられた問題の処理を実現するために状態遷移図・状態遷移表を設計していきましょう。

(i) 入力変数・出力変数を考える

最初に、回路を設計する際に必要な入力変数と出力変数を考えます。

• 入力変数（2個）
  • 100円硬貨が投入されたかを表す変数 \( x \)
    （投入されていない → 0、投入された → 1）
  • 500円硬貨が投入されたかを表す変数 \( y \)
    （投入されていない → 0、投入された → 1）
• 出力変数（2個）
  • 商品が出たかを表す変数 \( z \)
    （出なかった → 0、出た → 1）
  • おつりが出たかを表す変数 \( c \)
    （出なかった → 0、出た → 1）

※ 各変数に何を割り当てるかは自由なので、上の例の通りに割り当てなくてもOKです。
（例: 100円硬貨が投入された状態を0、投入されていない状態を1）

よって、答えは

• 入力変数: 2個
• 出力変数: 2個

となります。

(ii) 内部状態を考える

内部状態 = 記憶すべき状態、でしたね。

今回は、最後に商品が出てから投入された合計金額を100円単位^[5]100円硬貨以外の硬貨は入ってこないため、合計金額は必ず100円単位となる。で記憶すればOKですね。
（さらに商品が出る or 返却ボタンが押されると、投入金額の合計は0円にリセットされる）

そのため、

• 最後に商品が出てから合計0円投入された状態（硬貨が投入されていない状態）
• 最後に商品が出てから合計100円投入された状態

の2種類の状態を記憶すれば、回路が表せますね^[6]合計200円投入すると商品が出てくるため、「最後に商品が出てから合計300円投入された状態」を記憶する必要はありません。。

よって、必要な内部状態は最低2個であることがわかります。

(iii) 状態遷移図の設計

まずは、(ii)で考えた状態に名前を付けましょう。

今回は、最後に商品が出てから

• 合計0円投入された状態 → \( q_0 \)
• 合計100円投入された状態 → \( q_1 \)

としましょうか。

つぎに、（名前を付けた）状態を並べましょう。

あとは、各状態からの遷移先（次状態）と、そのときの入出力を矢印で表せばOKです。

今回の場合は、

• \( x = 0 \), \( y = 0 \) が入力された場合
  • 硬貨も投入されておらず、返却ボタンも押されていないため、合計金額（状態）が変わらない。
    → 商品が出ず、硬貨の返却もないためので出力は \( z = 0 \), \( r = 0 \)。（現状態と次状態が同じ）
• \( x = 1 \), \( y = 0 \) が入力された場合（100円硬貨が投入された場合）
  • \( q_0 \) : 合計金額が100円アップ
    → \( q_0 \) から \( q_1 \) に遷移
  • \( q_1 \): 合計が200円になるので、商品が出てくる。投入金額も0円にリセットされる。
    → \( z = 1 \) を出力し、次状態は \( q_0 \) に遷移
• \( x = 0 \), \( y = 1 \) が入力された場合（返却ボタンが押された場合）
  → 硬貨が投入されないため、投入合計金額が200円になることは絶対にない。よって、商品は出てこないため、出力 \( z \) は \( z = 0 \) となる。状態遷移・返却については、場合分けが必要。
  • 投入金額が0円 \( q_0 \) のとき→ お金が投入されていないので、お金が返却されない（何も起こらない）。よって、\( r = 0 \) で、状態は \( q_0 \) のまま
  • 投入金額が100円 \( q_1 \) のとき → お金が投入されているため、お金が返却され、投入金額が0円（状態 \( q_0 \)）にリセットされる。よって、\( r = 1 \) で、状態は \( q_0 \) に遷移

を満たすように矢印を追加すればOKです。

※ 入力・出力がともに複数あるので、変数をどの順番で書くかも明記しましょう。今回は「入力 / 出力 = \( xy \) / \( zr \)」で表すことにします。

(iv) 状態遷移表の設計

(iii)で書いた状態遷移図を元に、状態遷移表を書いていきましょう。

自信がある人は、状態遷移図を書かずに状態遷移表を書くのもありです。

これで、状態遷移図・状態遷移表の設計の完了です。ここからは、実際に順序回路を作成するための作業をしていきましょう。

[2-i] 必要なフリップフロップの数を考える

今回は、作成した状態が2つなので、1つのフリップフロップでこの2状態を記憶させることができますね。

よって、必要なフリップフロップの数は1つです。

[2-ii] 励起表と出力値を合体させた表（励起出力表）を書く

つぎに、

• 「Dフリップフロップの現状態 \( Q \) ・各入力」からどの「Dフリップフロップの次状態 \( Q \)」 に遷移すればよいか
  （[1]で作った状態遷移表を見ながら）
• 現状態 \( Q \) から次状態 \( Q \) に遷移させるためには、Dフリップフロップの入力をどうすればよいか

の2つを下のように、励起表に出力値 \( z \), \( r \) を含んだ表を書くことで示します。

Step1. 定義した状態を、フリップフロップの状態の値に割り当てる

まずは、[1]で定義した状態を実際にフリップフロップの値状態に割り当てます。

今回、フリップフロップは1つなので、1つのフリップフロップを各状態に割り当てていきましょう。

• 状態 \( q_0 \) → \( Q = 0 \)
• 状態 \( q_1 \) → \( Q = 1 \)

※ 割り当て方は自由なので、\( q_0 \) → \( Q = 1 \)、\( q_1 \) → \( Q = 0 \) としてもOKです。

Step2. 状態遷移表から励起表の次状態・出力を埋める

つぎに、「[1](4) 状態遷移表の設計」で作成した状態遷移表から励起表を作り上げていきます。

ここで、硬貨が投入されるとき \( x = 1 \) と、返却ボタンが押されるとき \( y = 1 \) が同時に起こること、つまり入力が \( (x,y) = (1,1) \) のときは考えなくてよいのでしたね。したがって、このときは次状態、出力をともにDon't Care（つまりX）とします。

Step3. 次状態からFFの入力値を求める

あとは、励起表の空欄部分である、FFの入力値を埋めればOKです。

※ Dフリップフロップの場合は、次状態 \( Q \) がそのままDフリップフロップの入力 \( D \) となるので簡単に埋めることができます。

[2-iii] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

完成した励起表（と出力値）が含まれた表から、FFの入力方程式（励起関数）、および順序回路の出力方程式を考えていきましょう。

ただし、今回は現状態 \( Q \) と入力 ( x \), \( y \) の3変数を最小化する必要があること、およびDon't Careである X が含まれているので、カルノー図を使って励起関数（FFの入力方程式）\( D \) と順序回路の出力方程式 \( z \), \( r \) を簡略化することを考えましょう。

[\( D \) の簡略化結果] [\( z \) の簡略化結果] [\( r \) の簡略化結果]

※ カルノー図を使う復習をしたい人は、このリンクの記事をご覧ください。
（例題などで使い方をわかりやすく解説しています！）

[2-iv] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

最後に、[2-iii]で作成した励起関数 \( D \)、出力方程式 \( z \), \( r \) の式\[\begin{align*}
D & = \bar{Q} x + Q \bar{x} \bar{y} \\
z & = Q x \\
r & = Q y
\end{align*}\]を用いて、順序回路を作れば設計完了です！

※ 少し回路が複雑なので、順序回路内に出てきたANDゲート、ORゲートの入力値を明記したバージョンも下に載せております。参考までにどうぞ。

[練習問題1] 4進アップカウンタの設計

実際に2問例題を解くことで、なんとなくDフリップフロップを用いた順序回路の設計の流れを理解することはできましたか？

ここからは、例題より少し複雑な練習問題を解くことで、順序回路の設計についてより深めていきましょう。

[1] 状態遷移図・状態遷移表の設計

(i) 入力変数・出力変数を考える

最初に、回路を設計する際に必要な入力変数と出力変数を考えます。

• 入力変数（1個）
  • 0, 1を入力する変数 \( x \)
• 出力変数（1個）
  • 1が4回入力されたかを判定する変数 \( z \)
    （4回入力されていない → 0、4回入力された → 1）

(ii) 内部状態を考える

内部状態 = 記憶すべき状態、を考えます。

今回は「1が4回入力されるごとに1を出力する」回路を作りたいので、最後に1が出力されてからの入力の数を記憶（＝内部状態として定義）しましょう。

よって、最低でも

• 最後に1が出力されてから1が0回入力された状態
  （1が入力されていない状態）
• 最後に1が出力されてから1が1回入力された状態
• 最後に1が出力されてから1が2回入力された状態
• 最後に1が出力されてから1が3回入力された状態

の4個を定義する必要があります^[7] … Continue reading。

(iii) 状態遷移図の設計

まずは、(ii)で考えた状態に名前を付けましょう。

今回は、最後に商品が出てから

• 最後に1が出力されてから1が0回入力された状態: \( q_0 \)
• 最後に1が出力されてから1が1回入力された状態: \( q_1 \)
• 最後に1が出力されてから1が2回入力された状態: \( q_2 \)
• 最後に1が出力されてから1が3回入力された状態: \( q_3 \)

とします。

つぎに、（名前を付けた）状態を並べましょう。

あとは、各状態からの遷移先（次状態）と、そのときの入出力を矢印で表せばOKです。

今回の場合は、

• 0が入力された場合：1が入力された回数が変化しないため、状態が変わらず、出力は0
  （現状態と次状態が同じ）
• 1が入力された場合：
  • \( q_0 \) ～ \( q_2 \): 1の数が1個増えた状態に遷移
  • \( q_3 \): 1の数が5個になるので、1を出力し、1の回数を0回にリセット。

を満たすように矢印を追加すればOKです。

(iv) 状態遷移表の設計

(iii)で書いた状態遷移図を元に、状態遷移表を書いていきましょう。

※ 自信がある人は、状態遷移図を書かずに状態遷移表を書くのもありです。

これで、状態遷移図・状態遷移表の設計の完了です。

ここからは、実際に順序回路を作成するための作業をしていきましょう。

[2-i] 必要なフリップフロップの数を考える

今回は、作成した状態が4つですね。

4つの状態を記憶させるためには、最低でも2ビットの記憶領域が必要ですね。そのため、最低でも2つのフリップフロップが必要です。

※ 公式 \( 2^{\textcolor{red}{n}-1} < 4 \leqq 2^{\textcolor{red}{n}} \) を使って \( \textcolor{red}{n = 2} \) と判断してもOKです。

[2-ii] 励起表と出力値を合体させた表を書く

つぎに、

• 「Dフリップフロップの現状態 \( Q \) ・各入力」からどの「Dフリップフロップの次状態 \( Q \)」 に遷移すればよいか
  （[1]で作った状態遷移表を見ながら）
• 現状態 \( Q \) から次状態 \( Q \) に遷移させるためには、Dフリップフロップの入力をどうすればよいか

の2つを下のように、励起表に出力値 \( z \)を含んだ状態遷移表で示します。

Step1. 定義した状態を、フリップフロップの状態の値に割り当てる

まずは、[1]で定義した状態を実際にフリップフロップの値状態に割り当てます。

今回、フリップフロップは2つなので、2つのフリップフロップの値 \( Q_1 \), \( Q_2 \) を組み合わせて各状態に割り当てていきましょう。

• [1の数0回] 状態 \( q_0 \) → \( (Q_1,Q_2) = (0,0) \)
• [1の数1回]状態 \( q_1 \) → \( (Q_1,Q_2) = (0,1) \)
• [1の数2回] 状態 \( q_2 \) → \( (Q_1,Q_2) = (1,1) \)
• [1の数3回] 状態 \( q_3 \) → \( (Q_1,Q_2) = (1,0) \)

※ 1の数2回の状態 \( q_2 \) を \( (Q_1,Q_2) = (1,0) \)、1の数3回の状態 \( q_3 \) を \( (Q_1,Q_2) = (1,1) \) と定義しそうになりますが、あえて \( q_2 \) を \( (Q_1,Q_2) = (1,1) \)、\( q_3 \) を \( (Q_1,Q_2) = (1,0) \) と定義するのがポイントです。このように定義することで、\( q_2 \) → \( q_3 \) の状態変化、および \( q_3 \) → \( q_0 \) の状態変化をフリップフロップ1ビットを変えるだけで済むため、励起関数（FFの入力方程式）を簡略化させることができます^[8]\( q_2 \) を \( (Q_1,Q_2) = (1,1) \)、\( q_3 \) を \( (Q_1,Q_2) = (1,0) \) と工夫した場合、\[\begin{align*}D_1 & = Q_1 \bar{x} + Q_2 x \\ D_2 & =\bar{Q_1} x + Q_2 \bar{x} … Continue reading。

Step2. 状態遷移表から励起表の次状態・出力を埋める

つぎに、「[1](4) 状態遷移表の設計」で作成した状態遷移表から励起表を作り上げていきます。

Step3. 次状態からFFの入力値を求める

あとは、励起表の空欄部分である、FFの入力値を埋めればOKです。

※ Dフリップフロップの場合は、次状態 \( Q \) がそのままDフリップフロップの入力 \( D \) となるので簡単に埋めることができます。

[2-iii] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

完成した励起表（と出力値）が含まれた表から、FFの入力方程式（励起関数）、および順序回路の出力方程式を考えていきましょう。

今回は現状態 \( Q_1 \), \( Q_2 \) と入力 ( x \) の3変数を最小化する必要があるので、1が多い \( D_1 \), \( D_2 \) についてはカルノー図を使って簡略化することをおすすめします。

一方、\( z \) は 1 がある部分が \( Q_1 \overline{Q_2} x \) の1箇所なので、わざわざカルノー図を書く必要はありません^[9]\( z = Q_1 \overline{Q_2} x \) はどう考えても簡略化できない。。よって、\( z = Q_1 \bar{Q_2} x \) とすぐに求められます。

[\( D_1 \) の簡略化結果] [\( D_2 \) の簡略化結果]

[2-iv] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

最後に、[2-iii]で作成した励起関数 \( D_1 \)、出力方程式 \( z \) の式\[\begin{align*}
D_1 & = Q_1 \bar{x} + Q_2 x \\
D_2 & = Q_2 \bar{x} + \overline{Q_1} x \\
z & = Q_1 \bar{Q_2} x
\end{align*}\]を用いて、順序回路を作れば設計完了です！

※ CLKの線は省略しています

※ 少し回路が複雑なので、順序回路内に出てきたANDゲート、ORゲートの入力値を明記したバージョンも下に載せております。参考までにどうぞ。

練習問題2. 自動販売機の設計

最後に、例題とはちょっと違う仕様の自動販売機をDフリップフロップを用いて設計する問題を解いて、「Ｄフリップフロップを用いた順序回路の設計」をマスターしましょう。

[1] 状態遷移図・状態遷移表の設計

(i) 入力変数・出力変数を考える

まずは、回路を設計する際に必要な入力変数と出力変数を考えましょう。

• 入力変数（2個）
  • 100円硬貨が投入されたかを表す変数 \( x \)
    （投入されていない → 0、投入された → 1）
  • 500円硬貨が投入されたかを表す変数 \( y \)
    （投入されていない → 0、投入された → 1）
• 出力変数（2個）
  • 商品が出たかを表す変数 \( z \)
    （出なかった → 0、出た → 1）
  • おつりが出たかを表す変数 \( c \)
    （出なかった → 0、出た → 1）

※ 0と1の割り当て方法は、上の方法以外でもOKです。
（例: 100円硬貨が投入された状態を0、投入されていない状態を1とする）

よって、答えは

• 入力変数: 2個
• 出力変数: 2個

となります。

(ii) 内部状態を考える

内部状態 = 記憶すべき状態、でしたね（いつものやつ）。

今回は、最後に商品が出てから投入された合計金額を100円単位で記憶すればOKなので、

• 最後に商品が出てから合計0円投入された状態（硬貨が投入されていない状態）
• 最後に商品が出てから合計100円投入された状態

の2種類の状態を記憶すれば、回路が表せます。
（200円以上なら商品を出す＋必要であればおつりを出すだけなので、200円以上の状態を記憶する必要はない）

よって、必要な内部状態は最低2個であることがわかります。

(iii) 状態遷移図を考える

(ii)で考えた状態に

• 合計投入金額が0円: \( q_0 \)
• 合計投入金額が100円: \( q_1 \)

と名前を付けましょう。そして、これらの状態を並べます。

あとは、各状態からの遷移先（次状態）と、そのときの入出力を矢印で表せばOKです。

今回の場合は、

• \( x = 0 \), \( y = 0 \) が入力された場合（硬貨が投入されなかった場合）
  • 投入が入力されていないため、合計金額（状態）が変わらない。
    → 商品もおつりも出ないので出力は \( z = 0 \), \( c = 0 \)。（現状態と次状態が同じ）
• \( x = 1 \), \( y = 0 \) が入力された場合（100円硬貨が投入された場合）
  • \( q_0 \) : 合計金額が100円に（\( q_0 \) から \( q_1 に遷移）
  • \( q_1 \): 合計が200円になるので、商品が出てくる。投入金額が0円にリセットされる。
    → \( z = 1 \) を出力し、次状態は \( q_0 \) に遷移
• \( x = 0 \), \( y = 1 \) が入力された場合（500円硬貨が投入された場合）
  • 500円硬貨が投入されるため、現在の合計金額（状態）に関わらず必ず合計金額300円を超えるし、おつりも発生する。
    → どんな場合でも出力は \( z = 1 \), \( c = 1 \) となり、合計金額は0円にリセットされる（次状態は \( q_0 \) となる）。

を満たすように矢印を追加すればOKです。

(iv) 状態遷移表を考える

(iii)で考えた状態遷移図を表にすればOKです。

状態遷移図・状態遷移表ができたので、ここからは順序回路の設計に入っていきましょう。

[2-i] 必要なフリップフロップの数を考える

今回は、作成した状態が2つですね。

2つであれば、1個のフリップフロップで記憶ができるので、必要なフリップフロップの数は最低1個です。

[2-ii] 励起表と出力値を合体させた表を書く

つぎに、

• 「Dフリップフロップの現状態 \( Q \) ・各入力」からどの「Dフリップフロップの次状態 \( Q \)」 に遷移すればよいか
  （[1]で作った状態遷移表を見ながら）
• 現状態 \( Q \) から次状態 \( Q \) に遷移させるためには、Dフリップフロップの入力をどうすればよいか

の2つを下のように、励起表に出力値 \( z \), \( c \) を含んだ表を書くことで示します。

Step1. 定義した状態を、フリップフロップの状態の値に割り当てる

まずは、[1]で定義した状態を実際にフリップフロップ（1つ）の値状態に割り当てます。

• 状態 \( q_0 \) → \( Q = 0 \)
• 状態 \( q_1 \) → \( Q = 1 \)

※ 割り当て方は自由なので、\( q_0 \) → \( Q = 1 \)、\( q_1 \) → \( Q = 0 \) としてもOKです。

Step2. 状態遷移表から励起表の次状態・出力を埋める

つぎに、「[1](4) 状態遷移表の設計」で作成した状態遷移表から励起表を作り上げていきます。

Step3. 次状態からFFの入力値を求める

あとは、励起表の空欄部分である、FFの入力値を埋めればOKです。

※ Dフリップフロップの場合は、次状態 \( Q \) がそのままDフリップフロップの入力 \( D \) となるので簡単に埋めることができます。

[2-iii] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

完成した励起表（と出力値）が含まれた表から、FFの入力方程式（励起関数）、および順序回路の出力方程式を考えていきましょう。

今回も現状態 \( Q_1 \), \( Q_2 \) と入力 ( x \) の3変数を最小化する必要があり、3つとも 1 がついている箇所が多いので、カルノー図による簡略化をしましょう。

[\( D \) の簡略化結果] [\( z \) の簡略化結果] [\( c \) の簡略化結果]

[2-iv] 励起関数(FFの入力方程式)・順序回路の出力方程式を作り、簡略化する

最後に、[2-iii]で作成した励起関数 \( D \)、出力方程式 \( z \), \( r \) の式\[\begin{align*}
D & = \bar{Q} x + Q \bar{x} \bar{y} \\
z & = y + Q x \\
c & = y
\end{align*}\]を用いて、順序回路を作れば設計完了です！

※ CLKの線は省略しております

※ 今までの例題・練習問題と同じように、順序回路内に出てきたANDゲート、ORゲートの入力値を明記したバージョンも下に載せております。参考までにどうぞ。

[まとめ] Dフリップフロップを用いた順序回路の設計手順

最後に、Dフリップフロップを用いた順序回路の設計手順を確認しましょう。