論理回路 第9回 http://www.fit.ac.jp/~matsuki/LCB.html 今日の内容 • 前回の復習 • 論理関数の簡単化(クワイン・マクラスキー法) 論理関数の簡単化 A B C D f A B C D f 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 f = ABCD + ABCD + ABCD + ABCD f = AD 簡単化の手法 • 公式を利用する方法 • カルノー図による方法 • クワイン・マクラスキーの方法 カルノー図による簡単化 • 簡単化とは, できるだけ大きなループに対応し,しかも論理関数 全体を表すのに必要にして最小数の主項を求める こと. 簡単化1 f =ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD C D A B 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1* 1 主項 必須項 *必須項に 含まれない1 BC 簡単化1 C D A B 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1* 1 f =AC + CD + ACD + ABD f =AC + CD + ACD + ABC 主項 必須項 *必須項に 含まれない1 クワイン・マクラスキーの方法 (Quine-McClaskey) • カルノー図 ⇒ 図を使って主項を求めた • クワイン・マクラスキーの方法 ⇒ 表を使用して隣接する最小項を求める X + X = 1の関係によって変数を消去 クワイン・マクラスキー法 • カルノー図では,変数が増えると簡単化する ことが極端に難しくなる • クワイン・マクラスキー法では,変数が増えて も簡単な繰り返し操作で簡単化できる. クワイン・マクラスキー法1 f = ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF + ABCDEF 2進数ABCDEFとして表す f = 000000 + 000010 + 000110 + 000111 + 001110 + 001000 + 101001 + 001100 + 001111 + 001010 (注意)「+」は論理和の意味 クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10進 表記 0 2 各最小項に含まれる1の数 8 ごとにグループ分けする 6 12 10 7 14 41 15 クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10数 表記 0 2 8 6 12 10 7 14 41 15 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 1の 個数 2進数 ABCDEF 10数 表記 0 1 000000 000010 001000 0 2 8 第1回の比較 0, 2 (2) 0, 8 (8) E C ()内の数字は,差 隣接するグループ内の各項を比較し,数字間の大きさ が2のべき乗だけ異なる組を取り出す ポイント1: 各項で1つだけ0,1の違いがある項の組み合わせを探す クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10数 表記 0 2 8 6 12 10 7 14 41 15 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 1の 個数 1 2 10数 表記 2進数 ABCDEF 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 2 8 6 12 10 第1回の比較 2, 6 (4) 2, 10 (8) 8,12 (4) 8,10 (2) D C D E ポイント2: 8と6の比較はしなくてよい (1か所の1しか違わない組み合わせを探すため) クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10数 表記 0 2 8 6 12 10 7 14 41 15 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 1の 個数 2 3 2進数 ABCDEF 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 10進 表記 0 0 0 1 0 1 6 12 10 7 14 * 41 第1回の比較 6, 7(1) 6, 14 (8) 12,14 (2) 10,14 (4) F C E D 41は,組みになる項 がなかった ポイント3: 組み合わせがない項には「*」をつけておく クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10数 表記 0 2 8 6 12 10 7 14 41 15 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 1の 個数 3 4 2進数 10進 ABCDEF 表記 000111 7 0 0 1 1 1 0 14 1 0 1 0 0 1 41 0 0 1 1 1 1 15 第1回の比較 7, 15 (8) 14, 15 (1) C F クワイン・マクラスキー法2 1の 個数 0 1 2 3 4 2進数 ABCDEF 000000 000010 001000 000110 001100 001010 000111 001110 101001 001111 10数 表記 0 2 8 6 12 10 7 14 41* 15 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) クワイン・マクラスキー法3 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) 隣接するグループ 内の各項を比較 クワイン・マクラスキー法3 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 第2回の比較 0, 2, 8, 10 (2, 8) 0, 8, 2, 10 (8, 2) 8, 10 -) 0, 2 8, 8 同じもの = 23 ポイント4: 隣接するグループ間で,()内が同じ組みを選び, 2のべき乗の差があるものを選定する クワイン・マクラスキー法2 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 第1回の比較 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 第2回の比較 2, 6, 10, 14 (4, 8) 8, 12, 10, 14 (4, 2) 10, 14 -) 2, 6 8, 8 = 23 クワイン・マクラスキー法2 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) 隣接するグループ 内の各項を比較 クワイン・マクラスキー法2 第1回の比較 6, 7 (1) 6, 14 (8) 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) 第2回の比較 6, 7, 14, 15 (1, 8) 14, 15 -) 6, 7 8, 8 = 23 クワイン・マクラスキー法2 第1回の比較 0, 2 (2) 0, 8 (8) 2, 6 (4) 2, 10 (8) 8, 12 (4) 8, 10 (2) 6, 7 (1) 6, 14 (8) 第2回の比較 0, 2, 8, 10 (2, 8)* 2, 6, 10, 14 (4, 8) * 8, 12, 10, 14 (4, 2) * 6, 7, 14, 15 (1, 8) * 10, 14 (4) 12, 14 (2) 7, 15 (8) 14, 15 (1) ポイント5: ()内が同じ組がない⇒終了 主項の選択表 0 2 6 7 8 10 12 14 15 41 41 0, 2, 8, 10 2, 6, 10, 14 8, 12, 10, 14 6, 7, 14, 15 ポイント6: 横軸:すべての最小項 縦軸:*印をつけた主項 主項の選択表 0 41 0, 2, 8, 10 2, 6, 10, 14 8, 12, 10, 14 6, 7, 14, 15 2 6 × × 7 8 10 12 14 15 41 × × × × × × × × × × × × × × × ポイント7:縦軸の各組み合わせに対して,そ の組み合わせを含む欄に×を付ける 主項の選択表 0 41 0, 2, 8, 10 2, 6, 10, 14 8, 12, 10, 14 6, 7, 14, 15 2 6 × × 7 8 10 12 14 15 41 × × × × × × × × × × × × × × × ポイント8:必須項を見つける 最小項に対応する列に×を1つしか含まない場合 (赤○),それに対応する主項は必須項(赤□)となる 主項の選択表 0 41 0, 2, 8, 10 2, 6, 10, 14 8, 12, 10, 14 6, 7, 14, 15 2 6 × × 7 8 10 12 14 15 41 × × × × × × × × × × × × × × × ポイント9:すべての最小項を含むようなもっとも簡単 な主項の組み合わせを求める 今回の例では,4つの必須項だけで すべての最小項を含んでいた 主項の変換 • 41 ⇒ 1 0 1 0 0 1 ⇒ A B C D E F ABCDEF E • 0, 2, 8, 10 (2, 8) ⇒ C 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 ⇒ ABDF CとEの変数は消去したという意味 ポイント10:{}の中は,どの数字で消去しても同じ 主項 ABCDEF • 8, 12, 10, 14 (4, 2)⇒ 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 00 00 10 10 ⇒ ABCF ABCDEF • 6, 7, 14, 15 (1, 8)⇒ 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 10 11 10 11 ⇒ ABDE 簡単化した論理関数 f=ABCDEF+ABDF+ABCF+ABDE 注意事項 • 講義に関する質問・課題提出など: [email protected] • メールについて 件名は,学籍番号+半角スペース+氏名 (例)S09F2099 松木裕二 本文にも短いカバーレター(説明)をつける 課題はWordなどで作り,添付ファイルとして送る
© Copyright 2024 ExpyDoc