組み合わせ回路

ディジタル回路
3. 組み合わせ回路
五島正裕
DATE :
2015/10/1
ディジタル回路
今日の内容
1. 導入問題
2. 論理関数の標準形
3. カルノー図による簡単化
4. 今日のまとめ
2
ディジタル回路
導入問題
3
ディジタル回路
例題
 Q.
 3つの入力 x，y，z に対して，
以下のいずれかの条件が成立したとき 1，
それ以外は 0 となる論理関数 F を求めよ．
 x と y がともに 1．
 x と z がともに 1．
 x と y が等しくなく，かつ，y と z が等しい．
 A.
 F = xy + xz + (x != y) · (y == z)
 ただし，· は省略，!= は XOR，== は XNOR
4
ディジタル回路
例題

A. (cont)

F = xy + xz + (x != y) · (y == z)
…………①
= xy + xz + (xy’ + x’y) · (yz + y’z’)
= xy + xz + xy’yz + xy’z’ + x’yz + x’yy’z
（展開）
= xy + xz + 0 + xy’z’ + x’yz + 0
∵ x · x’ = 0
= xy + xz + xy’z’ + x’yz
∵x+0=x
= xy (z + z’) + x (y + y’) z + xy’z’+ x’yz
∵ x (y + y’) = x · 1 = x
= xyz + xyz’ + xyz + xy’z + xy’z’ + x’yz
∵x+x=x
= xyz + x’yz + xyz’ + xy’z’ + xy’z
…………②
= xyz + x’yz + xyz’ + xy’z’ + xyz + xy’z
∵x+x=x
= (x + x’) yz + x (y + y’) z’ + x (y + y’) z
∵ x (y + y’) = x · 1 = x
= yz + xz’ + xz
∵ x (y + y’) = x · 1 = x
= yz + x (z + z’)
∵ x (y + y’) = x · 1 = x
= x + yz
…………③
5
ディジタル回路
例題
x
y
F
x
y
z
F
z
①
x
y
z
F
②
③
6
ディジタル回路
組み合わせ回路の簡単化
 物理的な最終目標：
 回路の遅延時間を短くする．
 回路の面積を小さくする．
 組み合わせ回路の簡単化の目標：
 論理ゲートの段数を少なくする．
 論理ゲートの個数を少なくする．
 論理ゲートへの入力の数を少なくする．
 工学的目標：
 その系統だった方法を見つける．
7
ディジタル回路
論理関数の標準形
8
ディジタル回路
用語の定義
 定義：
 リテラル (literal)：

x に対して，x または x’
 積項 (product term)／和項 (sum term)：
 リテラルの論理積／論理和
 n 変数の論理関数の最小項 (minterm)／最大項 (maxterm)：

n 種のリテラルからなる積項／和項
 具体例：3変数 (x, y, z) の論理関数の場合：
 リテラル
： x, x’, y, y’, z, z’ の6種
 積項
： xy, yz, zx, xyz, x’yz’, … の種
 和項
： x + y, y’ + z, x + y + z, x’ + y + z’, …
 最小項
： x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’, xyz の8種
 最大項
： x’ + y’ + z’, x’ + y’ + z, … の8種
9
ディジタル回路
用語の定義
 最小項の論理和
 積和標準形 (canonical sum-of-products form)
 加法標準形 (disjunctive canonical (normal) form)
 最小項表現 (minterm expression)
 最大項の論理積
 和積標準形 (canonical product-of-sums form)
 乗法標準形 (conjunctive canonical (normal) form)
 最大項表現 (maxterm expression)
10
ディジタル回路
標準形
 標準形 (canonical (normal) form) ：
 論理関数 F を一意に表現する論理式の「かたち」
 F1 と F2 の標準形が同じ ⇔ F1 と F2 は同じ
11
ディジタル回路
例題

A. (cont)

F = xy + xz + (x != y) · (y == z)
…………①
= xy + xz + (xy’ + x’y) · (yz + y’z’)
= xy + xz + xy’yz + xy’z’ + x’yz + x’yy’z
（展開）
= xy + xz + 0 + xy’z’ + x’yz + 0
∵ x · x’ = 0
= xy + xz + xy’z’ + x’yz
∵x+0=x
= xy (z + z’) + x (y + y’) z + xy’z’+ x’yz
∵ x (y + y’) = x · 1 = x
= xyz + xyz’ + xyz + xy’z + xy’z’ + x’yz
∵x+x=x
= xyz + x’yz + xyz’ + xy’z’ + xy’z
…………② 積和標準形
= xyz + x’yz + xyz’ + xy’z’ + xyz + xy’z
∵x+x=x
= (x + x’) yz + x (y + y’) z’ + x (y + y’) z
∵ x (y + y’) = x · 1 = x
= yz + xz’ + xz
∵ x (y + y’) = x · 1 = x
= yz + x (z + z’)
∵ x (y + y’) = x · 1 = x
= x + yz
…………③
12
ディジタル回路
例題
x
y
F
x
y
z
F
z
①
x
y
z
F
③
②
積和標準形
13
ディジタル回路
標準形と真理値表
m7
m6
m5
m4
m3
M2
M1
M0
x+y+z
x + y + z’
x + y’+ z
x’yz
xy’z’
xy’z
xyz’
xyz
#
x
y
z
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
1
0
1
0
0
0
0
0
0
2
0
1
0
1
1
0
0
0
0
0
0
0
3
0
1
1
1
1
1
1
0
0
0
0
1
4
1
0
0
1
1
1
0
1
0
0
0
1
5
1
0
1
1
1
1
0
0
1
0
0
1
6
1
1
0
1
1
1
0
0
0
1
0
1
7
1
1
1
1
1
1
0
0
0
0
1
1
F
 積和標準形
F = x’yz + xy’z’ + xy’z + xyz’ + xyz
= m3 + m4 + m5 + m6 + m7
= S (3, 4, 5, 6, 7) …ON-set
 和積標準形
F = (x + y + z) (x + y + z’) (x + y’+ z)
= M0 M1 M2
= P (0, 1, 2) … OFF-set
14
ディジタル回路
積和標準形と和積標準形
 積和標準形と和積標準形
 和積標準形の方が慣れている
 数学的には「双対」 (dual)
 説明は，積和標準形で
 和積標準形に変換することは容易
 AND ⇔ OR，0 ⇔ 1 に替えればよい
15
ディジタル回路
カルノー図
ディジタル回路
カルノー図
 カルノー図（Karnaugh Map）
 真理値表の一種
 グレイ・コード： 00 → 01 → 11 → 10
zw
xy
 0 は省略してよい
00
01
11
10
00
y
x
0
1
x
yz
00
01
11
10
01
0
0
11
1
1
10
2入力
3入力
4入力
17
ディジタル回路
カルノー図の例
y
x
0
1
0
1
1
y
x
F3(x, y) = xy
0
y
1
x
0
1
0
1
0
1
1
1
F23 (x, y) = xy + xy'
1
F2 (x, y) = xy'
18
ディジタル回路
カルノー図の例
y
x
0
1
1
1
0
1
y
x
0
F23 (x, y) = x
0
1
y
1
1
x
0
0
1
1
1
1
F02(x, y) = y'
1
1
F023 (x, y) = x + y'
19
ディジタル回路
カルノー図による簡単化
20
ディジタル回路
簡単化のキーポイント
 x y + x' y = y
 x y + x' y = (x + x') y = 1 · y = y
 x yz + x' yz = yz
 x yz + x' yz = (x + x') yz = 1 · yz = yz
セレクタ
 x □ + x' □ = □
x
21
ディジタル回路
カルノー図だと 1/2
y
x
0
1
0
1
1
y
x
0
1
y
x
0
1
F3 (x, y) = xy
0
1
0
1
y
1
1
1
1
x
0
0
1
1
F13 (x, y) = xy + x'y
F13 (x, y) = y
1
F1 (x, y) = x'y
22
ディジタル回路
カルノー図だと 2/2
x
yz
00
01
11
10
0
1
1
x
F7 (x, y, z) = x yz
yz
x
0
00
01
11
10
1
yz
00
01
11
10
x
yz
00
01
11
0
1
0
1
1
1
1
1
F37(x, y, z) = x yz + x' yz
10
F37(x, y, z) = yz
1
F3 (x, y, z) = x' yz
23
ディジタル回路
2次元超立方体による表現
S (1, 3) = m1 + m3 = x' y +x y = y
#
x
y
F
0
0
0
0
1
0
1
1
2
1
0
0
3
1
1
1
y
O
0
1
0
0
1
1
0
1
x
(0, 0)
1 (0, 1)
1
y
1
1
(1, 0)
(1, 1)
x
24
ディジタル回路
3次元超立方体による表現
F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
yz
z
x’yz
1
xz
1
xy’z
xyz
xy
1
0
1
y
x
0
1
1
xyz’
xy’
O
1
 主項 (prime implicant)：
x
0
1
xz’
xy’z’
 これ以上大きくはできない積項
 x と yz
25
ディジタル回路
4次元超立方体による表現
26
ディジタル回路
カルノー図
 カルノー図（Karnaugh Map）
 真理値表の1種
 グレイ・コード
zw
xy
 ハミング距離が 1 のマス：
図上で隣接している！
00
01
11
10
00
y
x
0
1
x
yz
00
01
11
10
01
0
0
11
1
1
10
2入力
3入力
4入力
27
ディジタル回路
グレイ・コード
#
3
2
1
0
0
0
0
 性質：
 隣接する符号語間では，
1桁のみ異なる．
1
1
0
2
1
1
3
0
0
4
0
1
 2桁なら：
5
1
1
6
0
8
1
1
0
0
…
…
…
0
…
7
…
 00 → 01 → 11 → 10 → 00
1
28
ディジタル回路
カルノー図の表現法
 トーラス状に表した４入力のカルノー図
XY=11
XY=10
(10)
(14)
XY=00
(8)
(2)
XY=01
ZW=10
(6)
(0)
(4)
ZW=00
(11)
(15)
(9)
(3)
(1)
(5)
(7)
ZW=11
ZW=01
29
ディジタル回路
カルノー図による例題の簡単化
x
y
z
F
F = x’yz + xy’z’ + xy’z + xyz’ + xyz = x + yz
M0
0
0
0
0
M1
0
0
1
0
M2
0
1
0
0
yz
x
m3
0
1
1
1
m4
1
0
0
1
m5
1
0
1
1
m6
1
1
0
1
m7
1
1
1
1
00
01
0
1
11
10
1
1
1
1
1
30
ディジタル回路
カルノー図による簡単化の手順
 手順：
1.
カルノー図の上で隣接した「1」を探し，主項を求める．
 縦横ともに 2 のべき乗の大きさ．
 できる限り大きく．
● 重なってもよい．
● はみ出してはいけない．
2.
「1」をすべてカバーする，最小の主項の組み合わせを求める．
 意味：
 ループを大きくする：
 AND ゲートの入力数を減らす
 ループを少なくする：
 AND ゲートの数を減らす
 OR ゲートの入力の数を減らす
31
ディジタル回路
カルノー図による簡単化の例（1）
zw
xy
00
00
01
11
1
1
10
zw
xy
01
11
00
01
01
11
11
10
10
x’y’w
00
10
1
1
y’zw’
32
ディジタル回路
カルノー図による簡単化の例（2）
zw
xy
00
01
11
10
zw
xy
00
1
00
01
1
01
11
1
11
10
1
10
z’w
00
01
11
10
1
1
1
1
x’y
33
ディジタル回路
カルノー図による簡単化の例（3）
zw
xy
00
01
11
00
10
zw
xy
00
01
11
10
00
01
1
1
01
1
1
1
1
11
1
1
11
1
1
1
1
10
10
yw
y
34
ディジタル回路
カルノー図による簡単化の例（4）
zw
xy
00
01
00
1
01
1
11
1
10
1
11
10
zw
xy
00
01
11
00
1
1
01
1
1
1
11
1
1
10
1
z’w + yzw
10
z’w + yw
35
ディジタル回路
5入力のカルノー図
zw
xy
00
00
1
01
11
zw
xy
00
01
11
10
00
01
11
10
01
1
10
11
1
10
v=0
v=1
v’x’y’z’w’ + xyzw
36
ディジタル回路
問題の例
 以下の問いに答えよ．答えは、ブール代数の式と MIL 記法の回路図の両方で記せ．
1. 下記の３入力関数
1.
S (0, 1, 5, 6, 7)
2.
S (0, 1, 2, 3, 5, 7)
3.
S (0, 1, 2, 4, 7)
2. 下記の４入力関数
1.
S (0, 1, 5, 7, 8, 10, 14, 15)
2.
S (1, 5, 6, 7, 10, 12, 13, 15)
3.
S (0, 2, 8, 10, 14)
3. 0 以上 15 以下の整数を 4桁の二進数として入力し，それが以下の条件を満たすならば 1 を，
満たさないならば 0 を返す
1. 素数
2. フィボナッチ数
4. 3. で，入力が 1 以上 9 以下ならどうか．
37
ディジタル回路
カルノー図を用いた簡単化
 カルノー図
 メリット：
 直感的
 ディメリット：
 入力が多いと難しい（6入力までならなんとか）
 直感的 ⇒ 発見的
 クワイン・マクラスキー法 (Quine-McCluskey)
 アルゴリズムとして定式化したもの
38
ディジタル回路
「簡単化」の限界
 カルノー図（QM 法）
 「簡単化」であって，「最小化」ではない
 最小の積和形（和積形）を与える
 積和形，和積形が最小かどうかは分からない
 積和形と和積形のどちらが小さいか分からない
 XOR が扱えない
 CAD 等では使われていない
 BDD（Binary Decision Diagram：二分決定木）
39
ディジタル回路
例題
 Q.
 3つの入力 x，y，z に対して，
以下のいずれかの条件が成立したとき 1，
それ以外は 0 となる論理関数 F を求めよ．
 x と y がともに 1．
 x と z がともに 1．
 x と y が等しくなく，かつ，y と z が等しい．
 A.
 F = xy + xz + (x != y) · (y == z)
 ただし，· は省略，!= は XOR，== は XNOR
40
ディジタル回路
例題
x
yz
00
01
0
1
1
11
10
1
1
x
1
yz
00
x
00
01
11
11
1
1
0
1
1
1
1
10
x
yz
00
01
11
0
1
xy
x
yz
y == z
0
1
10
0
x != y
yz
01
1
1
00
01
1
xz
10
1
1
(x != y)(y == z)
10
x
yz
00
01
0
1
11
1
11
10
1
1
1
1
1
xy + xz +
(x != y)(y == z)
41
ディジタル回路
例題
x
yz
00
01
0
1
11
10
1
1
1
1
x
yz
00
01
0
1
xy + xz + (x != y)(y == z)
1
11
10
1
1
1
1
1
x + yz
42
ディジタル回路
不完全指定組み合わせ回路
43
ディジタル回路
Don’t Care
 Don’t Care 「気にしない」
 出力は，0 でも 1 でもよい
 “ f ”，“ * ” などで表す
 回路が簡単になるように適当に決めてよい
その入力は
こない
その出力は
使われない
組み合わせ回路
44
ディジタル回路
Don’t Care
zw
xy
00
01
00
f
1
11
10
zw
xy
00
01
00
f
1
11
01
1
1
01
1
1
11
1
f
11
1
f
10
1
10
1
z’w + x’yw
10
z’w + yw
45
ディジタル回路
今日のまとめ
46
ディジタル回路
まとめ
 標準形
 入力パタン ⇔ 最小項，最大項
 カルノー図
 ルール：
 x □ + x' □ = □
 真理値表の1種で，ルールが適用できるマスは隣接している
47

Download Report