A+B+C

1
論理回路学
4. カルノー図とゲート回路
佐藤証⻄9-613
[email protected]
ベン図
３変数
４変数
５変数
６変数
4変数を超えるともう無理・・・
3
カルノー図
 1950年代に⽶ATTベル研究所のMaurice Karnaughが考案
した論理式を視覚的に表現する⽅法で論理圧縮に⽤いる
 多変数へ簡単に拡張できるが、実際には5変数程度が⼈⼿
では限界
A
A
B
A･B
A･B
B
A･B
A･B
A
A
C
A･B･C
A･B･C
A･B･C
A･B･C
C
A･B･C
A･B･C
A･B･C
A･B･C
B
B
B
C
C
A･B･C･D A･B･C･D A･B･C･D A･B･C･D B
A
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
B
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
A
A･B･C･D A･B･C･D A･B･C･D A･B･C･D B
D
D
D
4
２変数のカルノー図
B
B
A A･B A･B
A A･B A･B
 対応する部分に1を書き込む
 隣接する1をループで囲む
 ループの和や共通部分(積)が論理式を表す
F=A
B B
A
A
A
1
1
F=A＋B
B B
F=A
B B
1
1
A
F=B
B B
A
A
1
F=A･B
B B
1
A
1
A
F=A+B
B B
F=B
B B
A
1
A
1
A
A
1
A
1
A
1
1
1
1
F=A･B
B B
1
A
1
1
A
1
1
加法標準形と乗法標準形
 単純積
- A･B や A･B･C のような論理積
 加法標準形
- 次のように単純積の和で表される論理式
- F=単純積＋単純積＋･･･＋単純積
F=A･B＋A･B＋A･B･C
 単純和
- A+B や A+B+C のような論理和
 乗法標準形
- 次のように単純和の積で表される論理式
- F=単純和･単純和･････単純和
F=(A+B)･(A+B+C)･(A+B+C)
カルノー図で論理式の簡単化(論理圧縮)は加法標準形を使う
5
6
カルノー図による論理圧縮
①
②
③
④
論理式を加法標準形にする
単純積に対応するカルノー図の領域に1を書き込む
隣接した1の領域をループで囲む
ループで⽰された領域を読みとる
F＝A･B＋B･(A+B)
① F＝A･B＋A･B+B･B＝A･B＋A･B
② B B
③ B B
B B
A A･B A･B
A
1
A
1
A A･B A･B
A
1
A
1
④
F＝B
F＝A･B＋A･B+B･B＝A･B＋A･B＝(A+A)･B＝B
7
３変数のカルノー図
C
A･B･C
A
A･B･C
A･B･C
A
A･B･C
C
A･B･C B
A･B･C
B
A･B･C
A･B･C B
C
A
A
1
1
1
1
B
B
B
C
1
A
1
1
A
1
F=B
A
A
C
1
C
1 B
B =
1
1
B
C
B
B
B
C
A
A
A
A
1
1
C
1
1
1
1
1
C
1
1
1
B
B
B
A
A
F=B＋C
F=B
C
F=A･B
F=A＋B
F=C
F=A
C
 3変数以上はBのように⾶び地
が出てくることに注意
B
B
B
C
A
A
1
1
1
C
1 B
1
B
1
1 B
C
C
1
1
1
1
1
1
F=B･C
C
A
A
1
1
1
B
B
B
C
1 B
1
B
1
1 B
カルノー図による論理圧縮
F =A･B･C+A･B･C+ A･B･C+ A･B･C
C
A･B･C
A
A･B･C
A･B･C
A
A･B･C
C
A･B･C B
A･B･C
B
A･B･C
A･B･C B
C
C
1
1
1
1
A
A
B
B
F=A
B
F =A･C+A･B+ A･C+ A･B･C
C
A･B･C
A
A･B･C
A･B･C
A
A･B･C
C
A･B･C B
A･B･C
B
A･B･C
A･B･C B
A
A
C
1
1
1
1
C
1
1
B
B
F=B＋C
B
ループが重なってもよい理由は同⼀則（A＝A+A)に基づく
8
3変数のカルノー図
 図を少し簡略化します
C
C
A･B･C A･B･C B
A
A･B･C A･B･C
B
A･B･C A･B･C
A
A･B･C A･B･C B
00
01
AB
11
10
C
C
A･B･C･D A･B･C･D A･B･C･D A･B･C･D B
A
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
B
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
A
A･B･C･D A･B･C･D A･B･C･D A･B･C･D B
D
D
D
C
CD
0
1
A･B･C A･B･C
A･B･C A･B･C
A･B･C A･B･C
A･B･C A･B･C
00
01
11
10
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
A･B･C･D A･B･C･D A･B･C･D A･B･C･D
00
01
AB
11
10
9
10
分配則の証明
A
0
00
01
AB
11
10
1
1
+
1
1
1
1
1
1
･
00
01
AB
11
10
=
1
1
1
1
1
1
1
00
01
AB
11
10
C
0
1
1
1
1
1
1
(A+B)･
C
(A+C) 0 1
C
0
1
1
1
1
1
1
1
1
A+C
C
0
00
01
AB
11
10
A+B･C
C
0
1
1
1
A+B
00
01
AB
11
10
B･C
C
=
00
01
AB
11
10
1
1
1
1
1
11
分配則の証明
A
0
00
01
AB
11
10
1
1
･
1
1
1
1
1
1
+
00
01
AB
11
10
1
1
=
00
01
AB
11
10
C
0
1
1
1
1
A･B+A･C
C
0
1
1
1
1
1
1
1
1
A･C
C
0
00
01
AB
11
10
A･(B+C)
C
0
1
1
1
A･B
00
01
AB
11
10
B+C
C
1
1
1
1
1
=
00
01
AB
11
10
C
0
1
1
1
1
12
演習１（解答）
 次の真理値表をカルノー図を⽤いて簡単にしなさい
 またこの演算は何を意味するものか
10進
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
F
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
CD
00 01 11 10
00
01
AB
11
10
1
1
1
1
1
F=A･B･C＋A･B･D＋A･B･C
 10進数の0~9を4ビットの2進
数で表したものをBCD(Binary
Code Decimal)符号と呼ぶ
 BCD符号で四捨五⼊を⾏う演算
13
演習２（解答）
 四捨五⼊回路では10進数の10~15に対する演算結果
は無視して(0でも1でも)よい．これを利⽤して四捨
五⼊演算をさらに簡単にしなさい
10進
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
F
0
0
0
0
0
1
1
1
1
1
X
X
X
X
X
X
CD
00 01 11 10
00
01
AB
11 X
10 1
1
X
1
1
X
X
1
X
X
F=A＋B･D＋B･C
Quine-McCluskey(QM)法
 カルノー図は直感的だが多変数の表現
が難しくコンピュータ処理にもあまり
向かない
 Quine法はアメリカの哲学者･論理学者
のが考案した論理圧縮法
 QM法はアメリカの数学者McCluskey
が改良したもの
 多変数への拡張性が⾼い
 算法が⼀定
 コンピュータ処理に向いている
14
Quine法
主加法標準展開
1. 与えられた論理式を最⼩項の和で表す
2.各最⼩項を2進数の順に配列する (ABC→010，ABC→101)
圧縮表の作成
3. 各項を⽐較し A(B+B)=A の形に簡略化する(1次圧縮）
4. 圧縮を2次以上について可能な限り繰り返す
主項図の作成
5. 圧縮で残った項(主項)を左に,最⼩項を上に書く
6. 各主項が最⼩項を含むとき, 交点に○をつける
7. 各最⼩項が少なくとも1つの○を含む主項の組み合わせを求める
15
16
主加法標準展開と主乗法標準展開
 最⼩項
A
0
0
0
0
1
1
1
1
- ⼊⼒数n場合、n個の変数の積で
表されたもの
- n⼊⼒の場合2 n種類存在
 最⼤項
- n個の変数の和で表されたもの
 主加法標準展開(最⼩項和表⽰)
- 最⼩項の和で表現
 主乗法標準展開(最⼤項積表⽰)
- 最⼤項の積で表現
A
B
A
B
C
＋
B
0
0
1
1
0
0
1
1
A
B
C
C
0
1
0
1
0
1
0
1
＋
最小項 F
A･B･C 1
A･B･C 1
A･B･C 1
A･B･C 1
A･B･C 1
A･B･C 1
A･B･C 1
A･B･C 1
最大項 F
A+B+C 0
A+B+C 0
A+B+C 0
A+B+C 0
A+B+C 0
A+B+C 0
A+B+C 0
A+B+C 0
A
B
A
C
＋
B
C
A･B･C
A･B･C
A･B･C
A･B･C
A
A
A
A
C
B
C
A+B+C
・
B
C
A+B+C
・
B
C
A+B+C
・
B
C
A+B+C
17
Quine法～主加法標準展開
 次式をQuine法で圧縮する
F=A･C＋A･B･C＋A･B･D＋A･B･C･D＋A･B･C･D＋A･B･C･D
1. 与えられた論理式を最⼩項の和で表す
F=A･B･C･D＋A･B･C･D＋A･B･C･D＋A･B･C･D+
A･B･C･D＋A･B･C･D＋
A･B･C･D＋A･B･C･D＋
A･B･C･D＋A･B･C･D＋A･B･C･D
2. 各最⼩項を2進数の順に配列
F=A･B･C･D＋A･B･C･D＋A･B･C･D＋A･B･C･D+
(0000)
(0001)
(0010)
(0100)
(0110)
(0111)
(1000)
(1001)
(1011)
A･B･C･D＋A･B･C･D＋A･B･C･D+
(0011)
A･B･C･D＋A･B･C･D＋A･B･C･D＋A･B･C･D
(1111)
A･C
A･B･C
A･B･D
Quine法～圧縮表の作成
3. 各項を⽐較し A(B+B)=A の形に簡略化する(1次圧縮）
4. 圧縮を2次以上について可能な限り繰り返す
18
Quine法～主項図の作成
5. 圧縮で残った項(主項)を左に,最⼩項を上に書く
6. 各主項が最⼩項を含むとき, 交点に○をつける
7. 各最⼩項が少なくとも1つの○を含む主項の組み合わせを求める
最⼩項に⼀つだ●の
付いた主項は省けない
３つの主項で全ての
最⼩項を包含できる
F=B･C＋A･D＋C･D
19
Quine-McCluskey法
 各項を2進数で表現し，距離1(1ビットだけ0/1の違いがある)項を圧縮
して“ー”をつける
 後はQuine法と同じ
20
Quine-McCluskey法
 論理圧縮は表を上からスキャンして1ビット違うものを探す
 nビットの場合はn個⾒つかれば終了
 ⼆進数表現によりコンピュータでの処理が簡単
4つ⾒つかれば終了
21
22
演習３（解答）
 次式をQuine法で圧縮しなさい
F=A･C･D＋A･C･D＋B･C･D
最⼩項
１時圧縮
F=B･D＋C･D
２時圧縮
QM法の参考文献
 井澤祐司著
 プレアデス出版
 ISBN978-4-903814-13-1
 2,520円
「12章簡単な電卓を作る」
も授業で参照しますが特に
購⼊の必要はありません
23
24
ゲート回路
 デジタル回路の基本構成要素をゲート(gate)と呼ぶ
 ⼊⼒0/1によって出⼒0/1が決まる論理回路
 基本ゲートはOR, AND, NOT
スイッチによる表現
A B F
0
0
1
1
F=A＋B
0
1
0
1
A B C F
F=A＋B+C
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
0
1
1
1
A
B
F
A
B
C
D
F
E
F
G
F=A＋B+C+D+E+F+G
ゲート回路
スイッチによる表現
A B F
0
0
1
1
F=A･B
0
1
0
1
0
0
0
1
A B C F
F=A･B･C
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
1
F=A･B･C･D･E･F･G
25
ゲート回路
 NOT回路はインバータ(inverter)とも呼ばれる
スイッチによる表現
A F
0
1
1
0
F=A
 バッファは信号を増幅したり遅延したりさせる⽬的で⽤
いるが、論理的には⼊⼒をそのまま出⼒し何もしない
スイッチによる表現
A F
0
1
F=A
0
1
26
27
ゲート回路
A B F
A
B
F
F=A+B
0
0
1
1
0
1
0
1
スイッチによる表現
1
0
0
0
A B C F
A
B
C
F
F=A＋B+C
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
28
ゲート回路
A B F
A
B
F=A･B
0
F 0
1
1
0
1
0
1
スイッチによる表現
1
1
1
0
A
B
F
A B C F
A
B
C
F
F=A＋B+C
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
29
ゲート回路
A B F
F=AB
F=ABC
0
0
1
1
0
1
0
1
A B F
A
0
1
1
0
F
B
F=AB
0
0
1
1
0
1
0
1
1
0
0
1
A B C F
A B C F
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
A
B
C
F=ABC
F
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
0
３入力XORとXNOR
＝
≠
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
X
1
1
0
0
0
0
1
1
F
0
1
1
0
1
0
0
1
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
1
0
0
1
1
0
0
1
F
0
1
1
0
1
0
0
1
⼊⼒の１の数が奇数個か偶数個(0個も含む)に注⽬する
31
演習４（解答）
 2~3⼊⼒のXORとXNORをスイッチで表現しなさい
A
B
A
B
A B F
0
0
1
1
F
0
1
0
1
0
1
1
0
A
B
A
B
A B F
F
0
0
1
1
0
1
0
1
1
0
0
1
A B C F
A B C F
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
0
32
演習４（解答）
これも共有可
A共有
C共有
A
A
B
B
B
B
C
C
C
F
これも共有可
A
A共有
C共有
A
B
B
B
B
C
C
C
AやCの代わりにBを共有することもできる
F
33
ドモルガンの定理
 回路設計では０/1を偽/真とする正理論と逆に、1/0を偽
/真とする負理論を⽤いることもあり、⼊⼒に○のついた
ゲートを⽤いる
A+B=A ･ B
A
B
A
F
=
F
=B
F
F
=B
F
B
A
A ･ B=A+B
A
B
A
F
=
B
A
34
負理論での表現
=
=
=
A
B
C
F
=
A
B
C
F
=
=
=
=
35
演習（解答）
 次のXORとXNORを負論理のゲートに直しなさい
ABCABC
=
=
=
=
0
A B A B ABAB 0
0
0 0 1 1 0
0
0
0 1 1 0 1
1
1
1 0 0 1 1
1
1
1 1 0 0 0
0
1
1
AB=AB
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
A B A B
C C
0
1
1
0
1
0
0
1
AB=AB
ABC = A(BC)
= A(BC)
= A(BC)
= ABC
1
0
0
1
0
1
1
0
36
ゲート回路（MIL記号）のまとめ
F=A＋B
A B F
A B F
0
0
1
1
0
0
1
1
0
1
0
1
0
1
1
1
F=A+B
A B F
F=A･B
F=AB
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
F=A･B
0
0
1
1
0
1
0
1
1
1
1
0
A B F
0
0
1
1
0
0
1
1
0
1
1
0
0 1
1 0
F=A
A B F
A B F
0
1
0
1
A F
F=AB
0
1
0
1
1
0
0
1
A F
0 0
1 1
F=A
ゲート回路（MIL記号）のまとめ
ここが⼆重線
ここが鋭⾓
ここが直⾓

Download Report