4. 順序回路 五島 正裕

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

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

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

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

状態機械 (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)

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

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

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

次状態関数 と 出力関数 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) の真理値表

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

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

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

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

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

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

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

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

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 等価

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 等価

状態割り当て

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

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

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

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

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

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