8. 順序回路の簡単化，機能的な順序回路 五島 正裕

前回の復習

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

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

(state transition table) 順序回路の例 time x 1 z 0 / 0 1 / 0 S(t) S(t +1), z(t) x = 0 x = 1 A A, 0 B, 0 B A, 1 A B 1 / 1 0 / 0 x / z 状態遷移図 (state diagram) 状態遷移表 (state transition table)

順序回路の例 D Q clock 状態 A と B （たとえば）D-FF 1個で 状態割り当て A : Q = 0 B : Q = 1

順序回路の例 S(t) S(t+1), z x = 0 x = 1 A A, 0 B, 0 B A, 1 Q D x = 0 x = 1 1 1 Q z x = 0 x = 1 1 A : Q = 0 B : Q = 1 状態遷移表 次状態関数 (next state function) の真理値表 出力関数 (output function) の真理値表 D = Q’x + Qx’ z = Qx

順序回路の例 D Q x z clock time x Q z

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

順序回路の例 その2 D Q x Q D z clock time x Q z

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 機械

順序回路の簡単化

順序回路の簡単化 状態の削除 不要な状態の削除 重複した状態の削除 状態割り当ての「最適」化

不要な状態の削除 a D Q x ad aq Q D z bd bq clk b A 00 0 / 1 B 01 0 / 0 1 / 0 初期状態 clk b A 00 0 / 1 B 01 0 / 0 1 / 0 1 / 0 1 / 1 1 / 1 C 10 D 11 0 / 0 0 / 1

不要な状態の削除 S(t) S(t+1), z(t) x = 0 x = 1 A:00 A:00, 0 C:10, 0 B:01 x : don’t care aqbq ad x = 0 x = 1 00 1 01 11 x 10 aqbq bd x = 0 x = 1 00 01 11 x 10 1 aqbq z x = 0 x = 1 00 01 1 11 x 10 ad = aq’x + aqx’ bd = aqx z = bq

不要な状態の削除 a D Q x ad aq Q D z bd bq clock b ad = aq’x + aqx’ bd = aq x z = bq

重複した状態の削除 D Q x Q D z clock b a Q D Q D x z clock

重複した状態の削除 次状態と出力が同じ状態は，同じ状態 S(t+1), z(t) S(t) : a b x = 0 x = 1 A : 00 C : 10, 0 B : 01 B : 01, 0 D : 11, 0 C : 10 D : 11 A : 00, 1 C : 10, 1 S(t+1), z(t) S(t) : a b x = 0 x = 1 A : 00 A : 00, 0 B : 10, 0 B : 01 B : 01, 0 D : 11, 0 D : 11 A : 00, 1 B : 10, 1 b a Q D Q D x z clock

重複した状態の削除 次状態と出力が同じ状態は，同じ状態 S(t+1), z(t) S(t) : a b x = 0 x = 1 A : 00 C : 10, 0 B : 01 B : 01, 0 D : 11, 0 C : 10 D : 11 A : 00, 1 C : 10, 1 S(t+1), z(t) S(t) : a b x = 0 x = 1 A : 00 A : 00, 0 B : 10, 0 B : 01 B : 01, 0 D : 11, 0 D : 11 A : 00, 1 B : 10, 1 A 00 B 01 A 00 1 / 0 B 01 0 / 0 0 / 0 0 / 0 0 / 0 1 / 1 1 / 0 1 / 0 1 / 0 0 / 0 0 / 1 0 / 1 1 / 0 C 10 D 11 D 11 1 / 1

状態割り当ての「最適」化 状態割り当て A:00, B:01, C:10, D:11 A:00, B:01, C:11, D:10 ... n 個の状態を k 個のFFで表すとき，異なる割り当て (2k − 1)! / (2k − n)! k! 通り n = 3, k = 2 ⇒ 3 通り n = 5, k = 3 ⇒ 140 通り n = 10, k = 4 ⇒ 27億+ 通り 効率のよいアルゴリズムは知られていない！ 仕様どおり，素直に設計したほうがよい（？）

機能的な順序回路

機能的な組み合わせ回路 これまでの内容 すべての組み合わせ回路 ： 論理関数（完全集合） 論理回路の簡単化 ⇒ 最小の積和形（和積型）回路 しかし，実際は… 大規模で複雑な回路に対しては困難： その論理関数を求める それを簡単化する

機能的な組み合わせ回路 階層化設計 (hierarchical design) ex) ソフトウェアのサブルーチン 機能的な組み合わせ回路 比較的単純 頻繁に使われる

機能的な組み合わせ回路の例 非演算回路 セレクタ デコーダ エンコーダ 演算回路 ALU シフタ 浮動小数点演算器

機能的な順序回路 これまでの内容 すべての順序回路 ： 状態遷移 順序回路の簡単化 ⇒ 状態遷移の簡単化 しかし，実際は… 大規模で複雑な回路に対しては困難： その状態，遷移を求める それを簡単化する

機能的な組み合わせ回路 階層化設計 (hierarchical design) ex) ソフトウェアのサブルーチン 機能的な順序回路 比較的単純 頻繁に使われる

機能的な順序回路の例 機能的な順序回路の例： レジスタ カウンタ シフト・レジスタ

レジスタ n-bit レジスタ ≒ n 個の D-FF Q D D[0] Q[0] Q D D[1] Q[1] Q D D[n−1] Q[n−1] clk

レジスタ（ライト・イネーブル付き） n-bit レジスタ ≒ n 個の D-FF Write-Enable：we 0: 保持 1: 書き込み 0:　保持 1:　書き込み Q D Q[0] D[0] Q D Q[1] D[1] Q D Q[n−1] D[n−1] we clk

レジスタ（ライト・イネーブル付き） n-bit レジスタ ≒ n 個の D-FF Write-Enable：we 0: 保持 1: 書き込み 0:　保持 1:　書き込み クロック・ゲーティング Q D D[0] Q[0] Q D D[1] Q[1] Q D D[n−1] Q[n−1] we clk

クロック・ゲーティング Q D we clk c time 下げるのが遅いと... clk we c 失敗！

リセット フリップ・フロップ 初期状態（電源投入直後の状態）：不定 (unknown) 1 1

非同期リセット付き D-FF 非同期リセット (asynchronous reset) クロックと関係なく（非同期に），出力を 0 に data D Q sync_reset’ clock R R async_reset’ D Q R

（バイナリ）カウンタ Cin 二進数を保存 入出力： キャリー入力：Cin 1 : インクリメント Q D Q[0] C0 Q D Q[1] 1 : インクリメント Q D Q[0] C0 Q D Q[1] 桁上げ (carry) C1 1 1 1 Q D +) 1 1 1 Q[2] 1 1 C2 clk

（バイナリ）カウンタ カウンタ： アップ・カウンタ ダウン・カウンタ アップ／ダウン・カウンタ

シフト・レジスタ n-bit レジスタ 入出力： Serial-In : SI Parallel-Out : PO[n−1...0] Q D clk

シフト・レジスタ（並列ロード付き） n-bit レジスタ 入出力： Serial-In : SI Parallel-Out : PO[n−1...0] Parallel-In : PI[n−1...0] Load：l 0:　シフト 1:　ロード SI Q D PO[0] PI[0] Q D PO[1] PI[1] Q D PO[n−1] PI[n−1] l clk

シフト・レジスタ 並列―直列，直列―並列変換 (parallel-serial, serial-parallel conversion) PI PO PI PO SO SO clk clk clock recovery

リング・カウンタ リング・カウンタ シフト・レジスタの FF のうち， 1つ： プリセット 残り：リセット P D Q D Q D Q D 1つ： プリセット 残り：リセット P D Q D Q D Q D Q R R R clk reset’

今日のまとめ

今日のまとめ 順序回路の簡単化 機能的な順序回路 レジスタ カウンタ シフト・レジスタ

今後の予定 12/22 演算回路 1/12 3/ 2 試験 （9:00～10:30）