論理回路基礎 4. 組み合わせ回路の構成法 五島 正裕 論理回路基礎 今日の内容 1. 導入問題 2. 論理関数の標準形 3. カルノー図による簡単化 4. 今日のまとめ 論理回路基礎 導入問題 論理回路基礎 例題 Q. 3つの入力 x,y,z に対して,以下のいずれかの条件が成立したとき 1,そ れ以外は 0 となる論理関数 F を求めよ. 1. x と y がともに 1. 2. x と z がともに 1. 3. x と y が等しくなく,かつ,y と z が等しい. A. F = xy + xz + (x != y) · (y == z) ただし,· は省略,!= は XOR,== は XNOR 論理回路基礎 例題 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 + 0 + 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 …………③ 論理回路基礎 例題 x y F x y z F z ① x y z F ② ③ 論理回路基礎 組み合わせ回路の簡単化 物理的な最終目標: 回路の遅延時間を短くする. 回路の面積を小さくする. 組み合わせ回路の簡単化の目標: 論理ゲートの個数を少なくする. 論理ゲートへの入力の数を少なくする. 工学的目標: その系統だった方法を見つける. 論理回路基礎 論理関数の標準形 論理回路基礎 標準形 標準形 (canonical (normal) form) 論理関数 F を一意に表現する論理式 F1 と F2 の標準形が同じ ⇔ F1 と F2 は同じ 論理回路基礎 用語の定義 リテラル (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’, … 論理回路基礎 用語の定義 加法標準形 加法標準形 (disjunctive canonical (normal) form) 積和標準形 (canonical sum-of-products form) 最小項表現 (minterm expression) 最小項の論理和 乗法標準形 乗法標準形 (conjunctive canonical (normal) form) 和積標準形 (canonical product-of-sums form) 最大項表現 (maxterm expression) 最大項の論理積 論理回路基礎 例題 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 + 0 + 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 …………③ 論理回路基礎 例題 x y F x y z F z ① x y z F ③ ② 加法標準形 論理回路基礎 標準形と真理値表 # x y z F x+y+z 0 0 0 0 0 x + y + z’ 1 0 0 1 0 x + y’+ z x’yz 加法標準形 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = m3 + m4 + m5 + m6 + m7 2 0 1 0 0 3 0 1 1 1 = S (3, 4, 5, 6, 7) 乗法標準形 xy’z’ 4 1 0 0 1 xy’z 5 1 0 1 1 xyz’ 6 1 1 0 1 xyz 7 1 1 1 1 F = (x + y + z) (x + y + z’) (x + y’+ z) = M0 M1 M2 = P (0, 1, 2) 論理回路基礎 加法標準形 と 乗法標準形 加法標準形 と 乗法標準形 人間には,加法標準形の方が分かりやすい 数学的には「双対」 (dual) 説明は,加法標準形で 乗法標準形に変換することは容易 AND ⇔ OR,0 ⇔ 1 に替えればよい 論理回路基礎 簡単化 (1) ~カルノー図~ 論理回路基礎 簡単化のキーポイント xy + xy’ = x 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 (0, 1) (1, 1) 0 1 1 # x y F 0 0 0 0 1 0 1 0 2 1 0 1 3 1 1 1 x (0, 0) O (1, 0) x 0 1 1 xy’ ハミング距離が 1 のノード間にエッジ 論理回路基礎 3次元超立方体による表現 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz yz z 1 x’yz 1 xz 1 xy’z xyz xy 1 0 y x 0 1 1 xy’ x O 0 1 1 主項 (prime implicant) これ以上大きくはできない積項 x と yz xy’z’ xz’ xyz’ 論理回路基礎 4次元超立方体による表現 論理回路基礎 カルノー図 カルノー図(Karnaugh Map) 真理値表の1種 ハミング距離が 1 のノード:図上で隣接している! zw xy y x 0 1 x yz 00 01 11 10 00 01 11 00 0 0 01 1 1 11 10 2入力 3入力 4入力 10 論理回路基礎 カルノー図 x y z F F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz M0 0 0 0 0 M1 0 0 1 0 M2 0 1 0 0 yz x m3 0 1 1 1 m4 1 0 0 1 m5 1 0 1 1 m6 1 1 0 1 m7 1 1 1 1 00 01 0 1 11 10 1 1 1 1 1 論理回路基礎 多入力のカルノー図 E=1 BA DC 00 01 11 10 00 ○ ○ ○ ○ BA DC 00 00 01 11 10 E=0 ○ BA ○00 ○01 ○11 10 DC 01 ○ ○ ○ ○ 01 ○00 ○○ ○○ ○○ ○ 11 ○ ○ ○ ○ 11 ○01 ○○ ○○ ○○ ○ 10 ○ ○ ○ ○ 10 ○11 ○○ ○○ ○○ ○ 4入力 10 ○ ○ ○ 5入力 ○ 論理回路基礎 カルノー図の表現法 トーラス状に表した4入力のカルノー図 XY=11 XY=10 (10) (14) XY=00 (8) (2) XY=01 ZW=10 (6) (0) (4) ZW=00 (11) (15) (9) (3) (1) (5) ZW=01 (7) ZW=11 論理回路基礎 カルノー図による簡単化 1. カルノー図の上で隣接した「1」を探し,主項を求める. 縦横ともに 2 のべき乗の大きさ. できる限り大きく. 2. 「1」をすべてカバーする,最小の主項の組み合わせを求める. 重なってもよい. はみ出してはいけない. ループを大きくする: AND ゲートの入力数を減らす ループを少なくする: AND ゲートの数を減らす OR ゲートの 論理回路基礎 カルノー図による簡単化の例(1) zw xy 00 00 01 11 1 1 10 zw xy 01 11 00 01 01 11 11 10 10 x’y’w 00 10 1 1 y’zw’ 論理回路基礎 カルノー図による簡単化の例(2) zw xy 00 01 11 10 zw xy 00 1 00 01 1 01 11 1 11 10 1 10 z’w 00 01 11 10 1 1 1 1 x’y 論理回路基礎 カルノー図による簡単化の例(3) zw xy 00 01 11 00 10 zw xy 00 01 11 10 00 01 1 1 01 1 1 1 1 11 1 1 11 1 1 1 1 10 10 yw y 論理回路基礎 カルノー図による簡単化の例(4) BA DC 00 01 00 1 1 10 BA DC 00 01 11 00 1 01 01 1 1 11 11 1 1 10 1 10 1 1 CB † 11 10 CA+BA† cf. CBA+BA ループは重なっても良いから大きくとる 論理回路基礎 問題 以下の問いに答えよ.答えは、ブール代数の式と MIL 記法の回路図の両方で記せ. 1. 下記の3入力関数を簡単化せよ. 1. S (0, 1, 5, 6, 7) 2. S (0, 1, 2, 3, 5, 7) 3. S (0, 1, 2, 4, 7) 2. 下記の4入力関数を簡単化せよ. 1. 2. 3. S (0, 1, 5, 7, 8, 10, 14, 15) S (1, 5, 6, 7, 10, 12, 13, 15) S (0, 2, 8, 10, 14) 3. 0 以上 15 以下の整数を 4 ビットの 2 進数として入力し,それが以下の条件を満たすならば 1 を,満たさないならば 0 を返す回路を書け. 1. 素数 2. フィボナッチ数 4. 3. で,入力が 1 以上 9 以下ならどうか. 論理回路基礎 カルノー図を用いた簡単化 カルノー図 真理値表 ハミング距離が 1 の積項は,図上でも隣接する. メリット 直感的 ディメリット 入力が多いと描きにくい 直感的,発見的 クワイン・マクラスキー法 (Quine-McCluskey) アルゴリズムとして定式化したもの 論理回路基礎 簡単化 (2) ~クワイン・マクラスキー法~ 論理回路基礎 クワイン・マクラスキー法 ポイントは,カルノー図と同じ xy + xy’ = x そうできるところを網羅する方法 カルノー図より,システマティック 他入力にも対応可能 プログラムにしやすい 論理回路基礎 クワイン・マクラスキー法 x y z F F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz M0 0 0 0 0 M1 0 0 1 0 M2 0 1 0 0 m3 0 1 1 1 m4 x y z 1 0 0 1. 最小項を抜き出す 2. 「1」の数でソート m4 1 0 0 1 m3 0 1 1 m5 1 0 1 1 m5 1 0 1 m6 1 1 0 1 m6 1 1 0 m7 1 1 1 1 m7 1 1 1 論理回路基礎 クワイン・マクラスキー法 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz ⇒ x y z m4 1 0 m3 0 m5 ⇒ x y z 0 ☑ S (4, 5) 1 0 * ☑ 1 1 ☑ S (4, 6) 1 * 0 ☑ 1 0 1 ☑ S (3, 7) * 1 1 m6 1 1 0 ☑ S (5, 7) 1 * 1 ☑ m7 1 1 1 ☑ S (6, 7) 1 1 * ☑ x y z S (4, 5, 6, 7) 1 * * S (4, 5, 6, 7) 1 * * 論理回路基礎 今日のまとめ
© Copyright 2024 ExpyDoc