4. 組み合わせ回路の構成法 五島 正裕.

Presentation on theme: "4. 組み合わせ回路の構成法 五島 正裕."— Presentation transcript:

1 4. 組み合わせ回路の構成法 五島 正裕

2 今日の内容 導入問題 論理関数の標準形 カルノー図による簡単化 今日のまとめ

3 導入問題

4 例題 Q. 3つの入力 x，y，z に対して，以下のいずれかの条件が成立したとき 1，それ以外は 0 となる論理関数 F を求めよ．
x と z がともに 1． x と y が等しくなく，かつ，y と z が等しい． A. F = xy + xz + (x != y) · (y == z) ただし，· は省略，!= は XOR，== は XNOR

5 例題 A. (cont) F = xy + xz + (x != y) · (y == z) …………①
= xy + xz + (xy’ + x’y) · (yz + y’z’) = xy + xz + xy’yz + xy’z’ + x’yz + x’yy’z （展開） = xy + xz xy’z’ + x’yz + 0 ∵ x · x’ = 0 = xy + xz + xy’z’ + x’yz ∵ x + 0 = x = xy (z + z’) + x (y + y’) z + xy’z’+ x’yz ∵ x (y + y’) = x · 1 = x = xyz + xyz’ + xyz + xy’z + xy’z’ + x’yz ∵ x + x = x = xyz + x’yz + xyz’ + xy’z’ + xy’z …………② = xyz + x’yz + xyz’ + xy’z’ + xyz + xy’z ∵ x + x = x = (x + x’) yz + x (y + y’) z’ + x (y + y’) z ∵ x (y + y’) = x · 1 = x = yz + xz’ + xz ∵ x (y + y’) = x · 1 = x = yz + x (z + z’) ∵ x (y + y’) = x · 1 = x = x + yz …………③

6 例題 x x y y z F F z ① x F y ② z ③

7 組み合わせ回路の簡単化 物理的な最終目標： 回路の遅延時間を短くする． 回路の面積を小さくする． 組み合わせ回路の簡単化の目標：
論理ゲートの個数を少なくする． 論理ゲートへの入力の数を少なくする． 工学的目標： その系統だった方法を見つける．

8 論理関数の標準形

9 標準形 標準形 (canonical (normal) form) 論理関数 F を一意に表現する論理式
F1 と F2 の標準形が同じ ⇔ F1 と F2 は同じ

10 用語の定義 リテラル (literal) x に対して，x または x’ 積項 (product term)／和項 (sum term)：
リテラルの論理積／論理和 n 変数の論理関数の最小項 (minterm)／最大項 (maxterm)： n 種のリテラルからなる積項／和項 例：3変数 (x, y, z) の論理関数の場合： リテラル： x, x’, y, y’, z, z’ 積　項　： xy, yz, zx, xyz, x’yz’, … 和　項　： x + y, y’ + z, x + y + z, x’ + y + z’, … 最小項　： x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’, xyz 最大項　： x + y + z, x’ + y + z’, …

11 用語の定義 加法標準形 加法標準形 (disjunctive canonical (normal) form)
積和標準形 (canonical sum-of-products form) 最小項表現 (minterm expression) 最小項の論理和 乗法標準形 乗法標準形 (conjunctive canonical (normal) form) 和積標準形 (canonical product-of-sums form) 最大項表現 (maxterm expression) 最大項の論理積

12 例題 A. (cont) F = xy + xz + (x != y) · (y == z) …………①
= xy + xz + (xy’ + x’y) · (yz + y’z’) = xy + xz + xy’yz + xy’z’ + x’yz + x’yy’z （展開） = xy + xz xy’z’ + x’yz + 0 ∵ x · x’ = 0 = xy + xz + xy’z’ + x’yz ∵ x + 0 = x = xy (z + z’) + x (y + y’) z + xy’z’+ x’yz ∵ x (y + y’) = x · 1 = x = xyz + xyz’ + xyz + xy’z + xy’z’ + x’yz ∵ x + x = x = xyz + x’yz + xyz’ + xy’z’ + xy’z …………② 加法標準形 = xyz + x’yz + xyz’ + xy’z’ + xyz + xy’z ∵ x + x = x = (x + x’) yz + x (y + y’) z’ + x (y + y’) z ∵ x (y + y’) = x · 1 = x = yz + xz’ + xz ∵ x (y + y’) = x · 1 = x = yz + x (z + z’) ∵ x (y + y’) = x · 1 = x = x + yz …………③

13 例題 x x y y z F F z ① x F y ② 加法標準形 z ③

14 標準形と真理値表 加法標準形 F = x’yz + xy’z’ + xy’z + xyz’ + xyz
= m3 + m4 + m5 + m6 + m7 = S (3, 4, 5, 6, 7) 乗法標準形 F = (x + y + z) (x + y + z’) (x + y’+ z) = M0 M1 M2 = P (0, 1, 2) # x y z F 1 2 3 4 5 6 7 x + y + z x + y + z’ x + y’+ z x’yz xy’z’ xy’z xyz’ xyz

15 加法標準形 と 乗法標準形 加法標準形 と 乗法標準形 人間には，加法標準形の方が分かりやすい 数学的には「双対」 (dual)
説明は，加法標準形で 乗法標準形に変換することは容易 AND ⇔ OR，0 ⇔ 1 に替えればよい

16 簡単化 (1) ～カルノー図～

17 簡単化のキーポイント xy + xy’ = x xy + xy’ = x (y + y’) = x · 1 = x

18 F = S (2, 3) = m2 + m3 = xy +xy’ = x (y + y’) = x ·1 = x
2次元超立方体による表現 F = S (2, 3) = m2 + m3 = xy +xy’ = x (y + y’) = x ·1 = x y xy # x y F 1 2 3 (0, 1) (1, 1) 1 1 x (0, 0) (1, 0) x 1 O 1 xy’ ハミング距離が 1 のノード間にエッジ

19 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
3次元超立方体による表現 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz yz xz z 1 x’yz 1 1 xyz xy’z xy 1 y x 1 1 xyz’ 主項 (prime implicant) これ以上大きくはできない積項 x と yz xy’ x 1 xz’ O 1 xy’z’

20 4次元超立方体による表現

21 カルノー図 2入力 3入力 4入力 y x カルノー図（Karnaugh Map） zw 真理値表の1種 xy
ハミング距離が 1 のノード：図上で隣接している！ zw xy 00 01 11 10 y x 1 yz x 00 01 11 10 1 2入力 3入力 4入力

22 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
カルノー図 x y z F M0 M1 1 M2 m3 m4 m5 m6 m7 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz yz x 00 01 11 10 1

23 多入力のカルノー図 ４入力 ５入力 00 01 11 10 ○ 00 01 11 10 ○ 00 01 11 10 ○ Ｅ＝1 BA BA
Ｅ＝０ DC DC 00 01 11 10 ○ BA DC ４入力 ５入力

24 カルノー図の表現法 トーラス状に表した４入力のカルノー図

25 カルノー図による簡単化 カルノー図の上で隣接した「1」を探し，主項を求める． 縦横ともに 2 のべき乗の大きさ． できる限り大きく．
「1」をすべてカバーする，最小の主項の組み合わせを求める． 重なってもよい． はみ出してはいけない． ループを大きくする： AND ゲートの入力数を減らす ループを少なくする： AND ゲートの数を減らす OR ゲートの

26 カルノー図による簡単化の例（1） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 x’y’w y’zw’

27 カルノー図による簡単化の例（2） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 z’w x’y

28 カルノー図による簡単化の例（3） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 yw y

29 CA+BA† C B cf. CBA+BA カルノー図による簡単化の例（4） † ループは重なっても良いから大きくとる 00 01 11
10 1 BA 00 01 11 10 1 BA DC DC CA+BA† C B cf. CBA+BA †　ループは重なっても良いから大きくとる

30 問題 以下の問いに答えよ．答えは、ブール代数の式と MIL 記法の回路図の両方で記せ． 下記の３入力関数を簡単化せよ．
S (0, 1, 5, 6, 7) S (0, 1, 2, 3, 5, 7) S (0, 1, 2, 4, 7) 下記の４入力関数を簡単化せよ． S (0, 1, 5, 7, 8, 10, 14, 15) S (1, 5, 6, 7, 10, 12, 13, 15) S (0, 2, 8, 10, 14) 0 以上 15 以下の整数を 4 ビットの 2 進数として入力し，それが以下の条件を満たすならば 1 を，満たさないならば 0 を返す回路を書け． 素数 フィボナッチ数 3. で，入力が 1 以上 9 以下ならどうか．

31 カルノー図を用いた簡単化 カルノー図 真理値表 ハミング距離が 1 の積項は，図上でも隣接する． メリット 直感的 ディメリット
入力が多いと描きにくい 直感的，発見的 クワイン・マクラスキー法 (Quine-McCluskey) アルゴリズムとして定式化したもの

32 簡単化 (2) ～クワイン・マクラスキー法～

33 クワイン・マクラスキー法 ポイントは，カルノー図と同じ xy + xy’ = x そうできるところを網羅する方法
カルノー図より，システマティック 他入力にも対応可能 プログラムにしやすい

34 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
クワイン・マクラスキー法 最小項を抜き出す 「1」の数でソート x y z F M0 M1 1 M2 m3 m4 m5 m6 m7 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz x y z m4 1 m3 m5 m6 m7

35 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
クワイン・マクラスキー法 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz ⇒ ⇒ x y z m4 1 ☑ m3 m5 m6 m7 x y z S (4, 5) 1 * ☑ S (4, 6) S (3, 7) S (5, 7) S (6, 7) x y z S (4, 5, 6, 7) 1 *

36 今日のまとめ