第12週目

組み合わせ回路の最適化設計
I．組み合わせ回路の設計
ディジタル電子回路
任意の論理関数は標準積和形、標準和積形のいずれに
も変換できるので、簡単にAND/OR回路が設計できる。
２０１５年度後期
第１２回
1. 論理関数を定義している論理演算を論理ゲートに対応
させる
2. 演算順位の最も高い論理演算に対応するゲートから低
いほうへ入力側から出力側へ順に配置、配線
3. 最終出力が論理関数に対応する
標準形のような論理関数では冗長性がある。
F = X(Y+Z), G = XY+XZ
II.最適化設計の目的
1. 論理回路の実装コストの低減
2. 論理回路の耐故障性が増す
F: ORゲート、ANDゲートが１個づつ
G: ORゲート１個、ANDゲート２個
論理ゲートを論理回路の構成用部品として用いるためには、
1. ハードウエア部品として一定の空間を占有する
このような冗長性（無駄）を排除して行なう論理回路
の設計を最適化設計という。
2. 電気信号がゲートを通過するのに一定の時間がかかる
最適化設計
III.論理関数の簡単化と論理回路の最適化
演算数を減らす
＝論理関数の簡単化
積和形または和積形で表現された論理関数は
２段論理回路で表現できる。
演算数を最小にする＝論理関数の最適化（最小化）
F = AB + BC + AC
IV.最適化設計の評価指標
A
1. 空間最適化：回路の論理ゲートの総数を最小にする
B
2. 時間最適化：回路の入力端から出力端までに通過す
る論理ゲートの段数を最小にする
C
F = (A+B)(B+C)(C+A)
A
F
B
C
＝クリティカルパス（最長経路）を最小にする
２段論理最適化におけるドントケアの利用
カルノー図による２段論理最小化の手順概略
ドントケア（Don’t care) とは
1. 隣接するセルは可能な限り多く囲む
2. 必要なループの個数は可能な限り少なく（最小に）
する
3. 上と下、左と右のセルは隣接するセル
4. セルは重複して使用してもよい
n 変数論理関数あるいは n 入力論理回路において
n 個の変数値の組あるいは n 本の入力信号の組に
対して、論理関数値あるいは出力信号が定義されて
いないことをドントケア(Don’t care)、組み合わせ禁
止、不完全定義という。
記号は、 d、φ、“－”で表わす
F
例題
F = AC + ABD + ABC
1. ドントケア項は、その関数値を０か１のどち
らにしても構わない。
2. 同じセルに１とｄとが重複するならば、ドント
ケアｄを優先する。
A
CD
AB
00
01
11
C
10
00
1
01
11
1
10
1
1
1
1
1
D
B
例題
F = AC + ABD + ABC
ドントケアを用いる代表例
2進化10進符号 ( Binary Coded Decimal )
A
CD
AB
00
01
11
C
10
00
1
01
11
10
d
d
d
d
1
1
1
1
B
最小積和形
F = AC + ABC
• 10進 1桁を 2進 4bit で表わす
• (10)10 ～(15)10 をドントケアとする
D
10進
0
1
2
：
9
BCD
0000
0001
0010
：
1001
10
11
：
15
1010
1011
：
1111
10進数に対応
ドントケア
ファクタリングは、「論理積項や論理和項の項数
を減らす」操作に対応する。
多段論理最小化
論理関数における空間最適化を図る方法の
ひとつにファクタリング(Factoring)法がある。
論理ゲートへの入力信号線の数を減らす
一方で、
ファクタリング：
ファクタリングは次元を増やす操作であり、
時間最適化には逆行する。
論理式から分配則を用いて共通項をくくり出す操作
X・Y + X・Z = X・(Y+Z)
AND:2個、OR：１個
AND:1個、OR：1個
論理回路が多段になることを許す前提で空間最適化
を図ることを多段論理最小化という。
例題
AND: 4個、OR:1個
2項AND:8個、2項OR:3個
多項論理演算数 (ST) = 5
２項論理演算数 = 11
ファクタリングを行なうと…
F = WX(Z+Y) + WX(Y+Z)
ファクタリングの結果
元の回路
F(W,X,Y,Z) = WXZ + WXY + WXY + WXZ
W
X
Z
W
W
X
Y
W
W
X
Y
W
X
Z
X
F
X
F
Y
Z
= (Y+Z)(WX + WX)
ST = 5、２項論理演算数 = 5
空間最適化はできているが、時間最適化とはならない。
カルノー図による多段論理最小化
カルノー図は論理関数の標準積和形すなわち最小項
の論理和と１対１に対応している。
ファクタリングは基本的に積和形論理関数F をF1、
F2という積和形論理関数の論理積（AND） F1・F2
に変形する操作である。
つまり、論理関数 F1 と F2 が与えられたとき、
例
F = F1・F2 は
「カルノー図どうしの論理積（AND）である。」
F = WX(Z+Y) + WX(Y+Z)
= (Y+Z)(WX + WX)
K1、K2の両方のカルノー図の同じ位置のセルどう
しのAND結果をカルノー図Kとすることとなる。
形式的にはK＝K1・K2と表わせる。
カルノー図による多段論理最小化の手順
１．カルノー図 K を作る。
カルノー図による多段論理最小化の手順
２．カルノー図 K を K1 と K2 にコピーする。
例： F(W,X,Y,Z) = WXZ + WXY + WXY + WXZ
K1
YZ
WX
00
01
11
10
00
01
11
10
YZ
WX
00
01
K2
11
00
10
YZ
WX
00
01
11
00
1
1
01
1
1
01
1
1
1
1
11
1
1
11
1
1
10
1
10
1
1
1
1
1
10
カルノー図による多段論理最小化の手順
カルノー図による多段論理最小化の手順
3．K1 のセルに１を「適当に」追加記入する。
K1
YZ
WX
00
01
3．K1 のセルに１を「適当に」追加記入する。
K1
K2
11
10
00
YZ
WX
00
01
11
10
00
YZ
WX
00
01
K2
11
10
YZ
WX
00
1
1
00
00
01
11
01
1
1
01
1
1
01
1
1
01
1
1
11
1
1
11
1
1
11
1
1
11
1
1
10
1
1
10
1
1
10
1
1
10
1
1
「適当に」とは、ループを作る隣接セルをできるだけ
大きく、かつ少なくするように、という意味である。
「適当に」とは、ループを作る隣接セルをできるだけ
大きく、かつ少なくするように、という意味である。
カルノー図による多段論理最小化の手順
カルノー図による多段論理最小化の手順
3．K1 のセルに１を「適当に」追加記入する。
K1
YZ
WX
00
01
4．K1 を論理最小化する。
K1
K2
11
10
YZ
WX
00
01
11
10
YZ
WX
00
01
K2
11
10
YZ
WX
00
01
11
00
1
1
00
0
0
00
1
1
00
0
0
01
1
1
01
1
1
01
1
1
01
1
1
11
1
1
11
1
1
11
1
1
11
1
1
1
10
1
10
1
10
1
1
10
1
1
10
K1に「適当に」1を記入しても、対応するK2のセルに０を
記入しておけば、ANDをとることで元のカルノー図Kには
影響を与えない。
1
F1 = WX + WX
10
カルノー図による多段論理最小化の手順
カルノー図による多段論理最小化の手順
5．3,4 の手順をK２についても同様に行なう。ただし、
K2において、K1のループ内に０を記入してはいけない。
K1
K2
YZ
WX
00
00
01
1
11
10
1
YZ
WX
00
00
0
01
11
10
0
5．K1とK2に矛盾が無ければ両者のANDをとって、
完成する。
K1
YZ
WX
00
00
1
01
K2
11
10
1
YZ
WX
00
00
0
01
11
10
0
01
1
0
1
0
01
1
1
1
1
01
1
0
1
0
01
1
1
1
1
11
1
0
1
0
11
1
1
1
1
11
1
0
1
0
11
1
1
1
1
10
1
0
1
0
10
1
1
1
1
10
1
0
1
0
10
1
1
1
1
F1 = WX + WX
F2 = Y + Z
F2 = Y + Z
F=F1・F2 =( WX + WX)(Y+Z)

Download Report