ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28

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

ディジタル回路 導入問題

例題 Q. 3つの入力 x，y，z に対して， 以下のいずれかの条件が成立したとき 1， それ以外は 0 となる論理関数 F を求めよ． ディジタル回路 例題 Q. 3つの入力 x，y，z に対して， 以下のいずれかの条件が成立したとき 1， それ以外は 0 となる論理関数 F を求めよ． x と y がともに 1． x と z がともに 1． 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 x y y z F F z ① x F y ② z ③

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

ディジタル回路 論理関数 の 標準形

用語の定義 定義： リテラル (literal)： x に対して，x または x’ ディジタル回路 用語の定義 定義： リテラル (literal)： x に対して，x または x’ 積項 (product term)／和項 (sum term)： リテラルの論理積／論理和 n 変数の論理関数の 最小項 (minterm)／最大項 (maxterm)： n 種のリテラルからなる積項／和項 具体例：3変数 (x, y, z) の論理関数の場合： リテラル ： x, x’, y, y’, z, z’ の6種 積　項 ： 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 の8種 最大項 ： x’ + y’ + z’, x’ + y’ + z, … の8種

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

標準形 標準形 (canonical (normal) form) ： 論理関数 F を一意に表現する論理式の「かたち」 ディジタル回路 標準形 標準形 (canonical (normal) form) ： 論理関数 F を一意に表現する論理式の「かたち」 F1 と F2 の標準形が同じ ⇔ F1 と F2 は同じ

例題 ディジタル回路 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 x y y z F F z ① x F y ② 積和標準形 z ③

ディジタル回路 標準形 と 真理値表 積和標準形 F = x’yz + xy’z’ + xy’z + xyz’ + xyz = m3 + m4 + m5 + m6 + m7 = S (3, 4, 5, 6, 7) …ON-set 和積標準形 F = (x + y + z) (x + y + z’) (x + y’+ z) = M0 M1 M2 = P (0, 1, 2) … OFF-set # x y z M0 M1 M2 m3 m4 m5 m6 m7 F x + y + z x + y + z’ x + y’+ z x’yz xy’z’ xy’z xyz’ xyz 1 2 3 4 5 6 7

積和標準形 と 和積標準形 積和標準形 と 和積標準形 和積標準形の方が慣れている 数学的には「双対」 (dual) 説明は，積和標準形で ディジタル回路 積和標準形 と 和積標準形 積和標準形 と 和積標準形 和積標準形の方が慣れている 数学的には「双対」 (dual) 説明は，積和標準形で 和積標準形に変換することは容易 AND ⇔ OR，0 ⇔ 1 に替えればよい

ディジタル回路 カルノー図

カルノー図 2入力 3入力 4入力 カルノー図（Karnaugh Map） 真理値表の一種 ディジタル回路 カルノー図 カルノー図（Karnaugh Map） 真理値表の一種 グレイ・コード： 00 → 01 → 11 → 10 0 は省略してよい zw xy 00 01 11 10 y x 1 yz x 00 01 11 10 1 2入力 3入力 4入力

カルノー図の例 F3(x, y) = xy F23 (x, y) = xy + xy' F2 (x, y) = xy' y x y x y ディジタル回路 カルノー図の例 y x 1 y x 1 F3(x, y) = xy y x 1 F23 (x, y) = xy + xy' F2 (x, y) = xy'

カルノー図の例 F23 (x, y) = x F023 (x, y) = x + y' F02(x, y) = y' y x y x y x ディジタル回路 カルノー図の例 y x 1 y x 1 F23 (x, y) = x y x 1 F023 (x, y) = x + y' F02(x, y) = y'

ディジタル回路 カルノー図 による 簡単化

簡単化のキーポイント セレクタ x y + x' y = y x y + x' y = (x + x') y = 1 · y = y ディジタル回路 簡単化のキーポイント x y + x' y = y x y + x' y = (x + x') y = 1 · y = y x yz + x' yz = yz x yz + x' yz = (x + x') yz = 1 · yz = yz x □ + x' □ = □ セレクタ x

カルノー図だと 1/2 F3 (x, y) = xy F13 (x, y) = xy + x'y F13 (x, y) = y ディジタル回路 カルノー図だと 1/2 y x 1 y x 1 y x 1 F3 (x, y) = xy y x 1 F13 (x, y) = xy + x'y F13 (x, y) = y F1 (x, y) = x'y

カルノー図だと 2/2 F7 (x, y, z) = x yz F37(x, y, z) = x yz + x' yz ディジタル回路 カルノー図だと 2/2 yz x 00 01 11 10 1 yz x 00 01 11 10 1 yz x 00 01 11 10 1 F7 (x, y, z) = x yz yz x 00 01 11 10 1 F37(x, y, z) = x yz + x' yz F37(x, y, z) = yz F3 (x, y, z) = x' yz

2次元超立方体による表現 S (1, 3) = m1 + m3 = x' y +x y = y 1 O y x 1 y 1 1 x # x ディジタル回路 2次元超立方体による表現 S (1, 3) = m1 + m3 = x' y +x y = y # x y F 1 2 3 1 O (0, 0) (0, 1) y x 1 1 y 1 1 (1, 0) (1, 1) x

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 x’yz 1 1 xyz xy’z xy 1 1 y x 主項 (prime implicant)： これ以上大きくはできない積項 x と yz 1 1 xyz’ xy’ x 1 xz’ O 1 xy’z’

ディジタル回路 4次元超立方体による表現

カルノー図 2入力 3入力 4入力 カルノー図（Karnaugh Map） 真理値表の1種 グレイ・コード ディジタル回路 カルノー図 カルノー図（Karnaugh Map） 真理値表の1種 グレイ・コード ハミング距離が 1 のマス： 図上で隣接している！ zw xy 00 01 11 10 y x 1 yz x 00 01 11 10 1 2入力 3入力 4入力

グレイ・コード 性質： 隣接する符号語間では， 1桁のみ異なる． 2桁なら： 00 → 01 → 11 → 10 → 00 # 3 2 1 ディジタル回路 グレイ・コード 性質： 隣接する符号語間では， 1桁のみ異なる． 2桁なら： 00 → 01 → 11 → 10 → 00 # 3 2 1 4 5 6 7 8 …

ディジタル回路 カルノー図の表現法 トーラス状に表した４入力のカルノー図

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

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

カルノー図による簡単化の例（1） x’y’w y’zw’ zw xy zw xy 00 01 11 10 1 00 01 11 10 1 ディジタル回路 カルノー図による簡単化の例（1） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 x’y’w y’zw’

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

ディジタル回路 カルノー図による簡単化の例（3） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 yw y

カルノー図による簡単化の例（4） z’w + yzw z’w + yw zw xy zw xy 00 01 11 10 1 00 01 11 ディジタル回路 カルノー図による簡単化の例（4） zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 z’w + yzw z’w + yw

5入力のカルノー図 v = 0 v = 1 v’x’y’z’w’ + xyzw zw xy zw xy 00 01 11 10 1 00 ディジタル回路 5入力のカルノー図 zw xy 00 01 11 10 1 zw xy 00 01 11 10 1 v = 0 v = 1 v’x’y’z’w’ + xyzw

問題 の 例 以下の問いに答えよ．答えは、ブール代数の式と MIL 記法の回路図の両方で記せ． 下記の３入力関数 ディジタル回路 問題 の 例 以下の問いに答えよ．答えは、ブール代数の式と 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桁の二進数として入力し，それが以下の条件を満たすならば 1 を， 満たさないならば 0 を返す 素数 フィボナッチ数 3. で，入力が 1 以上 9 以下ならどうか．

カルノー図を用いた簡単化 カルノー図 メリット： 直感的 ディメリット： 入力が多いと難しい（6入力までならなんとか） 直感的 ⇒ 発見的 ディジタル回路 カルノー図を用いた簡単化 カルノー図 メリット： 直感的 ディメリット： 入力が多いと難しい（6入力までならなんとか） 直感的 ⇒ 発見的 クワイン・マクラスキー法 (Quine-McCluskey) アルゴリズムとして定式化したもの

「簡単化」の限界 カルノー図 （QM 法） 「簡単化」であって，「最小化」ではない 最小の積和形（和積形）を与える ディジタル回路 「簡単化」の限界 カルノー図 （QM 法） 「簡単化」であって，「最小化」ではない 最小の積和形（和積形）を与える 積和形，和積形が最小かどうかは分からない 積和形 と 和積形 のどちらが小さいか分からない XOR が扱えない CAD 等では使われていない BDD（Binary Decision Diagram：二分決定木）

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

例題 x != y y == z (x != y)(y == z) xy xz xy + xz + (x != y)(y == z) yz ディジタル回路 例題 yz x 00 01 11 10 1 yz x 00 01 11 10 1 yz x 00 01 11 10 1 x != y y == z (x != y)(y == z) yz x 00 01 11 10 1 yz x 00 01 11 10 1 yz x 00 01 11 10 1 xy xz xy + xz + (x != y)(y == z)

例題 xy + xz + (x != y)(y == z) x + yz yz x yz x 00 01 11 10 1 00 01 11 ディジタル回路 例題 yz x 00 01 11 10 1 yz x 00 01 11 10 1 xy + xz + (x != y)(y == z) x + yz

ディジタル回路 不完全指定 組み合わせ回路

Don’t Care Don’t Care 「気にしない」 出力は，0 でも 1 でもよい “ f ”，“ * ” などで表す ディジタル回路 Don’t Care Don’t Care 「気にしない」 出力は，0 でも 1 でもよい “ f ”，“ * ” などで表す 回路が簡単になるように 適当に決めてよい その入力は こない その出力は 使われない 組み合わせ回路

Don’t Care z’w + x’yw z’w + yw zw xy f 1 zw xy f 1 00 01 11 10 00 01 ディジタル回路 Don’t Care zw xy 00 01 11 10 f 1 zw xy 00 01 11 10 f 1 z’w + x’yw z’w + yw

ディジタル回路 今日のまとめ

まとめ 標準形 入力パタン ⇔ 最小項，最大項 カルノー図 ルール： x □ + x' □ = □ ディジタル回路 まとめ 標準形 入力パタン ⇔ 最小項，最大項 カルノー図 ルール： x □ + x' □ = □ 真理値表の1種で，ルールが適用できるマスは隣接している