コンピュータアーキテクチャI #5 カルノー図による論理式の簡単化平成２７年５月１５日教科書：p.40～49，p.60～62 本日の講義内容論理関数の簡単化  論理演算による方法 – ミスしやすい – 見通しが悪い – 項の選び方により，簡単化が行き詰まる  カルノー図による方法 – 減らせる項を視覚的に選ぶことが可能 – 機械的に作業でき，ミスが少ない – 論理変数が多くなると対応できない論理関数の簡単化とは  論理式の項数を少なくすること – ド・モルガンの定理や各種ブール代数の公理・定理を駆使して項数を減らす  論理式で使われている演算子を統一すること – 完全系を成すNANDやNORのみで論理式を記述し，必要な部品の種類を減らす論理式の簡単化の例（１）  与えられた論理式： 𝑍 = 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 – 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 = 𝐴𝐵𝐷 𝐶 + 𝐶 = 𝐴𝐵𝐷 – 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 = 𝐴𝐵𝐶 𝐷 + 𝐷 = 𝐴𝐵𝐶 – 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 = 𝐴 + 𝐴 𝐵𝐶𝐷 = 𝐵𝐶𝐷 𝑍 = 𝐴𝐵𝐷 + 𝐴𝐵𝐶 + 𝐵𝐶𝐷 論理式の簡単化の例（２）与えられた論理式 𝑍 = 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵 𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵 𝐶 𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴 𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 𝑍 = 𝐴𝐵𝐶 + 𝐴𝐶𝐷 + 𝐴𝐵 𝐶 + 𝐴𝐵𝐶 𝑍 = 𝐴𝐶 + 𝐴𝐵 + 𝐴𝐶𝐷 カルノー図とは何かカルノー図  論理式を図（表）で表す一つのやり方  論理変数の数が6程度までの論理式に対応可能 B A ００１ 0 0 0 1 １ 2変数のカルノー図 AND（F=A・B）を示すカルノー図 3変数のカルノー図 C A B 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 3変数のカルノー図  3変数論理関数： 𝑍 = 𝐴𝐵 + 𝐴 𝐵 𝐶 + 𝐶 – 対応するA,B,Cの個所に１を書く – それ以外のマス目には0を入れる  式中の積項に含まれない論理変数には，１を入れる 4変数のカルノー図 CD  00 01 11 10 AB 00 01 11 10 1 1 1 4変数のカルノー図 4変数の論理関数 𝑍 = 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷  1  3変数の場合と同様の手順で１を埋めていく 0は入れても入れなくても良いカルノー図作成時のルール１  論理変数の数がnのカルノー図 – 2n個のマス目をもつ   各マス目一つは，加法標準形で表された論理式の「最小項」に対応する隣り合うマス目は，論理変数1つだけが反転した値に対応している． – 2進数の1ビットだけが反転している – これを「ハミング距離が１」である，という  2ビット反転していれば，「ハミング距離は2」カルノー図作成時のルール２  カルノー図の上下端，左右端はそれぞれ「隣り合っている」と考える – ハミング距離が1だから  と言うか，1になるように設定するカルノー図の作成練習１  2進数4ビットで表される10進数（0～15）について，入力が4の倍数（０を含む）のときだけ１を出力するような論理関数のカルノー図を書け．隣り合うマス目の意味  隣り合う2つのマス目に“1”が入っている – 対応する2つの積項中，1つだけビットが反転している論理変数がある   つまり，2つの積項ではその論理変数は0でも1でも良い． 0でも1でも良い論理変数なら，わざわざ式中に書く必要なし． – 2つの項を，当該論理変数を省いた形でまとめてしまう隣接する3つのマス目に１!? C A B 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 1 3変数のカルノー図  左のようなカルノー図 – 隣接する３つのマス目に１  この3つの積項を１つにまとめられるか否か？ – まとめられない – 0と1の両方を含まないとまとめられない – まとめるマス目の数は，必ず2n個カルノー図による簡単化 1. 論理式や真理値表からカルノー図を書く 2. カルノー図中，「1」と記入したマス目をグループ化する • • 一つのグループに入るマス目の数は2n個 1つのグループができるだけ大きくなるようにグループを作る 3. 各グループ内で値が「0」と「1」の両方を取る論理変数を除き，常に「0」となる論理変数は否定の形で，「1」となる論理変数はそのままに，論理積で結ぶ 4. 得られた積項を論理和で結ぶ練習次の論理式をカルノー図を用いて簡単化せよ 1. Z = AB + ABC + AB + ABC 2. Z = B ⋅ C ⋅ D + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A⋅B⋅C⋅D 完全定義論理式と不完全定義論理式  完全定義論理式 – すべての入力の組合せに対し，０か１の出力がすべて決まっている論理式  不完全定義論理式 – – – – 決して入力とはならない入力の組合せを持つ論理式当該入力に対する出力は，0でも1でも良いカルノー図ではφや＊を書いておく φや＊を「ドントケア（Don’t care）」というドントケアを含むカルノー図  CD 00 01 11  01 1 1 1 1 11 𝜑 𝜑 1 𝜑 AB 10 𝑍 = 𝐴𝐵 + 𝐴𝐵𝐶𝐷 10 00 𝜑 次の論理式を考える (ABCD)=(1110),(1011), (1100),(1101)は起こりえないと想定する – 上記4パターンの入力に対しては，ドントケアとなるドントケアを含むカルノー図による簡単化ドントケアは0としても，1として考えても良い CD 00 01 11 10 00 01 1 1 1 1 11 𝜑 𝜑 1 𝜑 AB 10 𝜑 – (1100),(1101),(1110)は1として考える – (1011)は無視する – A，C，Dは”0”と”1”が両方含まれているので省略可 𝑍=𝐵 本日のまとめ  カルノー図 – 入力論理変数間のハミング距離が１となるように配置した，一種の真理値表  カルノー図による論理式の簡単化 – 「1」または「𝜑」が記述された，2n個のマス目を矩形にまとめてグループ化 – グループ内で０と１の両方を取る入力論理変数を取り除いた積項を作成 – 作成した積項を論理和で結合 – ドントケア（「𝜑」）は０でも１でも都合の良いほうに解釈可来週の予定  論理式の簡単化演習 – ブール代数を用いる場合 – カルノー図を用いる場合 – 得点アップの機会ですので，予習をしっかりと！