Download presentation
Presentation is loading. Please wait.
1
第４回 カルノー図による組合せ回路の簡単化 瀬戸 目標 ・AND-OR二段回路の実現コスト（面積、遅延）が出せる
・カルノー図を使い，組合せ回路を簡単化できる 瀬戸 本講義のホームページ： ユーザ名： tcu パスワード： seto
2
このような論理式の簡単化を，簡単に行う方法 ⇒ カルノー図
ブール代数による論理式の変形 (復習) 次の論理式を出来るだけ簡単化せよ ∵ x・x=x, y・y=0 ∵ yz+yz=yz ∵ y+y=1 ∵ 1+z=1 このような論理式の簡単化を，簡単に行う方法 ⇒ カルノー図
3
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)
4
AND-OR 二段回路の実現コスト ゲート の個数が少ないほうがよい 回路の面積、消費電力を削減
x ゲート の個数が少ないほうがよい 回路の面積、消費電力を削減 個々のゲートで考えると、 入力 数が少ないほうがよい 面積や遅延時間を削減 y z w 面積小 遅延小 面積大 遅延大
5
AND-OR 二段回路の簡単化とは？ w=xyz+xyz+xyz+xyz ANDゲート の個数 ORゲート の入力数 ANDゲート の入力数
機能を同じままで、以下を削減 ANDゲート の個数 ORゲート の入力数 ANDゲート の入力数 積和形に対しては、以下に相当 積項 数 の削減 リテラル 数 の削減 x y z w
6
積項数とリテラル数 (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
7
(∵ 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
8
カルノー図 (カルノーマップ)とは何か？ 入力の配置を工夫した真理値表 「不規則」な箇所があるので注意 00 01 11 10 zw xy
yz 1 y 00 01 11 10 1 x x ２入力 ３入力 ４入力
9
カルノー図の重要な特徴 zw xy となり合う「マス」は、入力変数が １ビット だけ異なる 1 00 01 10 y 00 01 11 10
0001 0100 0101 0111 1101 1000 1010 1 00 01 10 y zw x xy 00 01 11 10 ２入力 00 01 11 10 001 1 100 101 111 yz x ３入力 ４入力
10
カルノー図のいくつかの描き方（全部同じ意味）
00 01 11 10 1 yz x y y y x x x z z z z
11
カルノー図と最小項の関係 （イメージ） カルノー図の１マスは、 最小項 に対応する 最小項は，積項の特殊なもの すべての変数を使用した積項
カルノー図の１マスは、 最小項 に対応する 最小項は，積項の特殊なもの すべての変数を使用した積項 00 01 11 10 xyzw zw xy 1 xy y 00 01 11 10 xyz 1 yz x x ２入力 ３入力 ４入力
12
xyz + xyz + xyz + xyz yz x 積和形から、カルノー図への変換 00 01 11 10 1
カルノー図では通常、 0 を省略 （見やすさのため） 例： xyz + xyz + xyz + xyz 最小項 yz 00 01 11 10 1 x
13
カルノー図と積項との関係 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
14
カルノー図と積項との関係 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
15
カルノー図と積項の関係（４入力） 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
16
カルノー図による簡単化のポイント 積和形(真理値表)から、カルノー図を描き，１を埋める 「囲み」で、すべての1をおおう
「囲み」は，重なってもよい 1が無い箇所へ、はみ出したらダメ 囲みの数 を少なくする 積項、つまり ANDゲートの 個 数が減る 囲み を大きく する リテラル数、つまり ANDゲートの入力 数が減る 00 01 11 10 1 zw xy
17
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 囲みをできるだけ拡張し、 無駄な囲みを削除
18
カルノー図による簡単化 （例） 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
19
カルノー図の例題 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 積項数 ７ 積項数 ３
20
ドントケア(記号：-)の利用による，更なる簡単化
ドントケア(記号：-)の利用による，更なる簡単化 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
21
まとめ 積和形で、積項数 を削減すれば回路が簡単になる カルノー図を使えば、積項数を削減できる 宿題 (6/1(水） 中間試験開始前に回収）
宿題 (6/1(水） 中間試験開始前に回収） 第6回 「よく使われる組合せ回路」までの，小テストの問題を，再度レポート用紙に解き，提出 連絡事項 5/18(水) は休講 5/21(土) に補講 (22C) ... 2進数について
Similar presentations
