4. 順序回路 五島 正裕.

Presentation on theme: "4. 順序回路 五島 正裕."— Presentation transcript:

1 4. 順序回路 五島 正裕

2 組み合わせ回路 と 順序回路 組み合わせ回路 (combinational circuit) 無記憶 現在の入力 ⇒ 出力 ex)
0101…0…0 ⇒ 0 0101…1…0 ⇒ 0 順序回路 (sequential circuit) 記憶 入力の履歴 ⇒ 出力 0101…1…0 ⇒ 1

3 順序回路の例 Q 自動販売機 使える硬貨は100円のみ 200円の商品1種のみ 100円が 2個投入されると，商品を送り出す その順序機械：
入力 x：100円が投入されると，1サイクルの間だけ 1 出力 z：1 のとき，商品が送り出される

4 順序回路の例 x 1 z time clock x z

5 状態 状態 S： S0 : 100円を受け取っていない S1 : 100円を1個受け取っている time x 1 S S0 S1 z

6 状態機械 (State Machine) の表現
time x 1 S S0 S1 z 0 / 0 1 / 0 S(t) S(t +1), z x = 0 x = 1 S0 S0, 0 S1, 0 S1 S0, 1 S0 S1 1 / 1 0 / 0 x / z 状態遷移図 (state diagram) 状態遷移表 (state transition table)

7 状態機械の構成 入力 組み合わせ 回路 出力 現状態 次状態 記憶素子

8 記憶素子の例 D-FF（フリップ・フロップ） デ ー タ 入 力： d デ ー タ 出 力： q
clk

9 状態割り当て 状態 S0 と S1 （たとえば）D-FF 1個で表現 状態割り当て：D-FF の出力 q S0 : q = 0

10 次状態関数 と 出力関数 S(t) S(t+1), z x = 0 x = 1 S0 S0, 0 S1, 0 S1 S0, 1 q d
1 Q z x = 0 x = 1 1 S0 : q = 0 S1 : q = 1 状態遷移表 次状態関数 (next state function) の真理値表 出力関数 (output function) の真理値表

11 順序回路の構成 d q x z clock time q 1 x d z

12 順序回路の例 その2 Q 自動販売機 使える硬貨は100円のみ 200円の商品1種のみ
100円が 2個投入されると，次のサイクルに 商品を送り出す その順序機械： 入力 x：100円が投入されると，1サイクルの間だけ 1 出力 z：1 のとき，商品が送り出される

13 順序回路の例 その2 d q x q d z clk time q 1 x d z 1

14 Mealy マシン と Moore マシン d q d q x x q d z z clk clk Mealy マシン Moore マシン

15 Mealy マシン と Moore マシン 出力関数 出力関数 出力 出力 入力 次状態関数 入力 次状態関数 q d q d 現状態
clk clk Mealy マシン Moore マシン

16 状態機械の最小化 順序回路の例

17 状態の等価性 状態 Si と Sj に同じ入力系列を与えて，異なる出力系列が得られる ⇒ この入力系列を， Si と Sj の識別系列という
等価： あらゆる長さのあらゆる系列を与えても，出力が異ならない

18 状態の等価性 Si と Sj に，長さ k の識別系列が存在する ⇒ Si と Sj は k 識別可能 という

19 k 等価性による状態分割 現状態 次状態, 出力 x = 0 x = 1 S0 S1, 0 S2, 0 S1 S0, 0 S3, 0 S2
π1 状態 次ブロック x = 0 x = 1 B01 S0 B11 S1 S2 S3 S4 S5 π2 状態 次ブロック x = 0 x = 1 B02 S0 B12 S1 S2 B22 S3 S4 S5 1 等価 2 等価

20 k 等価性による状態分割 現状態 次状態, 出力 x = 0 x = 1 S0 S1, 0 S2, 0 S1 S0, 0 S3, 0 S2
π2 状態 次ブロック x = 0 x = 1 B02 S0 B12 S1 S2 B22 S3 S4 S5 π3 状態 次ブロック x = 0 x = 1 B03 S0 B13 S1 S2 B23 B33 S3 S4 S5 2 等価 3 等価

21 状態割り当て

22 状態割り当て と 状態機械の構造 S(t + 1):Y1Y2, z S(t):y1y2 x = 0 x = 1 S0:00 S0:00, 0

23 状態割り当ての「最適化」 n 個の状態を k 個のFFで表すとき，異なる割り当て (2k − 1)! / (2k − n)! k! 通り
効率のよいアルゴリズムは知られていない！ 仕様どおり，素直に設計したほうがよい？

24 今日のまとめ 今日のまとめ

25 今日のまとめ 順序回路の表現 状態遷移図 状態遷移表 順序回路の構成 状態機械 ：状態遷移表 ⇒ 状態割り当て 次状態関数，出力関数 ⇒
状態機械 ：状態遷移表 ⇒ 状態割り当て 次状態関数，出力関数 ⇒ 組み合わせ回路の簡単化（カルノー図，etc）

26 今日のまとめ 状態機械の最小化 k 等価性による状態分割 状態割り当て 順序回路の大きさ 状態割り当てに依存
状態割り当ての「最適化」は難しい

27 今後の予定など 次回 ロジックの構成 教科書 年末に発売予定