第４回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト（面積、遅延）が出せる ・カルノー図を使い，組合せ回路を簡単化できる 瀬戸 本講義のホームページ： http://www.ee.tcu.ac.jp/lectures/digital/index.html ユーザ名： tcu　　　パスワード： seto

このような論理式の簡単化を，簡単に行う方法 ⇒ カルノー図 ブール代数による論理式の変形 (復習) 次の論理式を出来るだけ簡単化せよ ∵ x・x=x, y・y=0 ∵ yz+yz=yz ∵ y+y=1 ∵ 1+z=1 このような論理式の簡単化を，簡単に行う方法　⇒　カルノー図

w=x・y・z+x・y・z+x・y・z+x・y・z 積和形＝ 組合せ回路　（復習） w=x・y・z+x・y・z+x・y・z+x・y・z x y z w ２段目 (OR) “AND-OR 二段回路” 1段目 (AND)

AND-OR 二段回路の実現コスト ゲート の個数が少ないほうがよい 回路の面積、消費電力を削減 x ゲート　の個数が少ないほうがよい 回路の面積、消費電力を削減 個々のゲートで考えると、　入力　数が少ないほうがよい 面積や遅延時間を削減 y z w 面積小 遅延小 面積大 遅延大

AND-OR 二段回路の簡単化とは？ w=xyz+xyz+xyz+xyz ANDゲート の個数 ORゲート の入力数 ANDゲート の入力数 機能を同じままで、以下を削減 ANDゲート　　の個数 ORゲート　　　の入力数 ANDゲート　　の入力数 積和形に対しては、以下に相当 　積項　　　　　数　の削減 　リテラル　　　数　の削減 x y z w

積項数とリテラル数 (1) bcd + abd + abd + abd (2) bcd + bd + abd 以下の式(1)-(3)の積項数とリテラル数を答えよ 実は、a(b+c)d + ab(c+d) + ab(cd+cd)とすべて等価 積項数 リテラル数 (1) bcd + abd + abd + abd (2) bcd + bd + abd (3) bc + bd + ad 4 3 12 8 6

(∵ xy + xy = x(y+y)=x・1=x) AND-OR 二段回路の簡単化 次の公式を繰り返し適用し、論理式を簡単化 つまり、1変数だけ反転している積項同士をまとめる 例： 　カルノー図　を使うと、図を使ってこの簡単化を行える ただし、せいぜい５，６変数の論理式まで 実際の設計ではパソコン（ＣＡＤプログラム）で簡単化 例：　Quartus II　（クオータス） xy + xy = x (∵ xy + xy = x(y+y)=x・1=x) xyz + xyz = x(y+y)z　=　xz

カルノー図 (カルノーマップ)とは何か？ 入力の配置を工夫した真理値表 「不規則」な箇所があるので注意 00 01 11 10 zw xy yz 1 y 00 01 11 10 1 x x ２入力 ３入力 ４入力

カルノー図の重要な特徴 zw xy となり合う「マス」は、入力変数が １ビット だけ異なる 1 00 01 10 y 00 01 11 10 0001 0100 0101 0111 1101 1000 1010 1 00 01 10 y zw 00 01 11 10 x xy 00 01 11 10 ２入力 00 01 11 10 001 1 100 101 111 yz x ３入力 ４入力

カルノー図のいくつかの描き方（全部同じ意味） 00 01 11 10 1 yz x y y y x x x z z z z

カルノー図と最小項の関係 （イメージ） カルノー図の１マスは、 最小項 に対応する 最小項は，積項の特殊なもの すべての変数を使用した積項 カルノー図の１マスは、　最小項　に対応する 最小項は，積項の特殊なもの すべての変数を使用した積項 00 01 11 10 xyzw zw xy 1 xy y 00 01 11 10 xyz 1 yz x x ２入力 ３入力 ４入力

xyz + xyz + xyz + xyz yz x 積和形から、カルノー図への変換 00 01 11 10 1 カルノー図では通常、　0　を省略　（見やすさのため） 例： xyz + xyz + xyz + xyz 最小項 yz 00 01 11 10 1 x

カルノー図と積項との関係 yz yz x x xyz + xyz xyz + xyz = xz = yz カルノー図中の“囲み”は、１つの 積項 に対応 ただし、２のべき乗 (　1, 2, 4, …　)の大きさ 3, 6, などはありえない yz yz 00 01 11 10 1 00 01 11 10 1 x x xyz + xyz = xz xyz + xyz = yz

カルノー図と積項との関係 yz yz x x y x 00 01 11 10 1 00 01 11 10 1 カルノー図中の“囲み”が、１つの 積項 に対応 ただし、２のべき乗(1, 2, 4, …)の大きさ yz yz 00 01 11 10 1 00 01 11 10 1 x x y x

カルノー図と積項の関係（４入力） z z y x y x y w w w 論理関数: xw + xz + xw + xyzw 00 01 11 10 1 zw xy y x y x y w w w

カルノー図による簡単化のポイント 積和形(真理値表)から、カルノー図を描き，１を埋める 「囲み」で、すべての1をおおう 「囲み」は，重なってもよい 1が無い箇所へ、はみ出したらダメ 囲みの数 を少なくする 積項、つまり ANDゲートの　個　数が減る 囲み を大きく する リテラル数、つまり ANDゲートの入力　数が減る 00 01 11 10 1 zw xy

xz + yz + xyz xz + xy yz yz x x カルノー図による簡単化の例 00 01 11 10 1 00 01 11 簡単化前の積和形 簡単化後の積和形 xz + yz + xyz xz + xy 積項 yz 00 01 11 10 1 yz 00 01 11 10 1 x x 囲みをできるだけ拡張し、 無駄な囲みを削除

カルノー図による簡単化 （例） xzw+xyzw+xyzw+xyzw = xw+yzw 00 01 11 10 1 00 01 11 10 カルノー図による簡単化　（例） xzw+xyzw+xyzw+xyzw = xw+yzw 00 01 11 10 1 00 01 11 10 1 zw zw xy xy xyzw xzw xw xyzw xyzw yzw

カルノー図の例題　 D, C, B, Aを，４ビットの２進数とする（0～15, Dが最上位ビット)。このとき，DCBAが，0を除く偶数のときに，出力がアクティブになる回路を設計せよ。 00 01 11 10 1 00 01 11 10 1 BA BA DC DC D C Y B A 積項数　７ 積項数　３

ドントケア(記号：-)の利用による，更なる簡単化 ドントケア(記号：-)の利用による，更なる簡単化　 D, C, B, Aを，４ビットの２進数とする（0～15, Dが最上位ビット)。このとき，DCBAが，0を除く偶数のときに，出力がアクティブになる回路を設計せよ。ただし，8以上の数は入力されないものとする。 00 01 11 10 1 00 01 11 10 1 - BA BA DC DC D C Y B A 積項数　３ 積項数　2

まとめ 積和形で、積項数 を削減すれば回路が簡単になる カルノー図を使えば、積項数を削減できる 宿題 (6/1(水） 中間試験開始前に回収） 宿題　(6/1(水） 中間試験開始前に回収） 第6回　「よく使われる組合せ回路」までの，小テストの問題を，再度レポート用紙に解き，提出 連絡事項 5/18(水) は休講 5/21(土) に補講 (22C) ... 2進数について