Document

第４回
カルノー図による組合せ回路の簡単化
目標
・AND-OR二段回路の実現コスト（面積、遅延）が出せる
・カルノー図を使い，組合せ回路を簡単化できる
瀬戸
本講義のホームページ：
http://www.ee.tcu.ac.jp/lectures/digital/index.html
ユーザ名： tcu
パスワード： seto
1
ブール代数による論理式の変形 (復習)
次の論理式を出来るだけ簡単化せよ
yx  yz  xxy  xz  yxy  yz
 yx  yz  xy  xz  0  yz
 yx  yz  xy  xz  yz
 yx  yz  xy  xz
 x( y  y )  xz  yz
 x 1  xz  yz
 x  xz  yz
 x(1  z )  yz
 x 1  yz
 x  yz
∵ x・x=x, y・y=0
∵ yz+yz=yz
∵ y+y=1
∵ 1+z=1
このような論理式の簡単化を，簡単に行う方法 ⇒ カルノー図
2
積和形＝組合せ回路（復習）
w=x・y・z+x・y・z+x・y・z+x・y・z
x
y
z
w
２段目 (OR)
“AND-OR 二段回路”
1段目 (AND)
3
AND-OR 二段回路の実現コスト
x
ゲートの個数が少ないほうがよい y
z
回路の面積、消費電力を削減
w
個々のゲートで考えると、入力数が少ないほうがよ
い
面積や遅延時間を削減
面積小
遅延小
面積大
遅延大
4
AND-OR 二段回路の簡単化とは？
w=xyz+xyz+xyz+xyz
機能を同じままで、以下を削減
x
y
z
ANDゲート
ORゲート
ANDゲート
の個数
の入力数
の入力数
w
積和形に対しては、以下に相当
積項
リテラル
数の削減
数の削減
5
積項数とリテラル数
以下の式(1)-(3)の積項数とリテラル数を答えよ
実は、a(b+c)d + ab(c+d) + ab(cd+cd)とすべて等価
積項数
リテラル数
(1) bcd + abd + abd + abd
4
12
(2) bcd + bd + abd
3
8
(3) bc + bd + ad
3
6
6
AND-OR 二段回路の簡単化
次の公式を繰り返し適用し、論理式を簡単化
xy + xy = x
(∵ xy + xy = x(y+y)=x・1=x)
つまり、1変数だけ反転している積項同士をまとめる
例： xyz + xyz = x(y+y)z = xz
カルノー図を使うと、図を使ってこの簡単化を行える
ただし、せいぜい５，６変数の論理式まで
実際の設計ではパソコン（ＣＡＤプログラム）で簡単化
例： Quartus II （クオータス）
7
カルノー図 (カルノーマップ)とは何か？
入力の配置を工夫した真理値表
「不規則」な箇所があるので注意
zw 00 01 11 10
xy
00
x
0
y 0
1
1
yz 00 01 11 10
x
0
11
10
1
２入力
01
３入力
４入力
8
カルノー図の重要な特徴
となり合う「マス」は、入力変数が１ビットだけ異なる
y 0 1
zw 00 01 11 10
x
xy
0 00 01
00
0001
1 10
２入力
x
0
1
yz 00
01
11
01 0100
0101
11
1101
10
001
100
101
111
３入力
0111
10 1000
1010
４入力
9
カルノー図のいくつかの描き方（全部同じ意味）
yz 00 01 11 10
x
0
1
y
y
y
x
x
x
z
z
z
z
10
カルノー図と最小項の関係（イメージ）
カルノー図の１マスは、最小項に対応する
最小項は，積項の特殊なもの
すべての変数を使用した積項 zw
00 01 11 10
xy
00 xyzw xyzw xyzw xyzw
x
0
1
01
xyzw
xyzw
xyzw
xyzw
xy xy
yz 00 01 11 10
x
0 xyz xyz xyz xyz
11
xyzw
xyzw
xyzw
xyzw
xy xy
1 xyz xyz xyz xyz
10
xyzw
xyzw
xyzw
xyzw
y 0
1
２入力
３入力
４入力
11
積和形から、カルノー図への変換
カルノー図では通常、 0 を省略（見やすさのため）
例：
xyz + xyz + xyz + xyz
最小項
yz 00 01 11 10
x
0
1
1
1
1
1
12
カルノー図と積項との関係
カルノー図中の“囲み”は、１つの積項に対応
ただし、２のべき乗 ( 1, 2, 4, … )の大きさ
3, 6, などはありえない
yz 00 01 11 10
x
yz 00 01 11 10
x
0
1
0
1
1
1
xyz + xyz
= yz
1
1
xyz + xyz
= xz
13
カルノー図と積項との関係
カルノー図中の“囲み”が、１つの積項に対応
ただし、２のべき乗(1, 2, 4, …)の大きさ
yz 00 01 11 10
x
yz 00 01 11 10
x
0
1
1
0
1
1
1
1
y
1
1
1
1
x
14
カルノー図と積項の関係（４入力）
論理関数: xw + xz + xw + xyzw
z
x
x
z
zw 00 01 11 10
xy
00 1 1 1 1
01
1
11
1
1
10
1
1
w
1
1
w
y
y
y
w
15
カルノー図による簡単化のポイント
積和形(真理値表)から、カルノー図を描き，１を埋める
「囲み」で、すべての1をおおう
「囲み」は，重なってもよい
1が無い箇所へ、はみ出したらダメ
囲みの数を少なくする
zw 00 01 11 10
xy
積項、つまり
1 1
ANDゲートの個数が減る 00
囲みを大きくする
01
1 1
リテラル数、つまり
11
1
ANDゲートの入力数が減る
10
16
カルノー図による簡単化の例
簡単化前の積和形
簡単化後の積和形
xz + yz + xyz
xz + xy
積項
yz 00 01 11 10
x
yz 00 01 11 10
x
0
0
1
1
1
1
1
1
1
1
1
1
囲みをできるだけ拡張し、
無駄な囲みを削除
17
カルノー図による簡単化（例）
xzw+xyzw+xyzw+xyzw = xw+yzw
zw 00 01 11 10
xy
00
1 1 xyzw
01 xzw 1
11
10
1
xyzw
1 xyzw
zw 00 01 11 10
xy
00
1 1
01 xw
1
11
1
10
yzw
1
18
カルノー図の例題
D, C, B, Aを，４ビットの２進数とする（0～15, Dが最上
位ビット)。このとき，DCBAが，0を除く偶数のときに，出
力がアクティブになる回路を設計せよ。
BA 00
DC
D
C
B
A
01 11 10
00
Y
BA 00
DC
1
00
01 11 10
1
01
1
1
01
1
1
11
1
1
11
1
1
10
1
1
10
1
1
積項数７
積項数３
19
ドントケア(記号：-)の利用による，更なる簡単化
D, C, B, Aを，４ビットの２進数とする（0～15, Dが最上
位ビット)。このとき，DCBAが，0を除く偶数のときに，出
力がアクティブになる回路を設計せよ。ただし，8以上の
数は入力されないものとする。
BA 00
DC
D
C
B
A
01 11 10
00
Y
BA 00
DC
1
00
01 11 10
1
01
1
1
01
1
11
1
1
11
-
-
-
-
10
1
1
10
-
-
-
-
積項数３
1
積項数 2
20
まとめ
積和形で、積項数を削減すれば回路が簡単になる
カルノー図を使えば、積項数を削減できる
宿題 (6/1(水）中間試験開始前に回収）
第6回「よく使われる組合せ回路」までの，小テストの
問題を，再度レポート用紙に解き，提出
連絡事項
5/18(水) は休講
5/21(土) に補講 (22C) ... 2進数について
21

Download Report