第11週目

組み合わせ回路の最適化設計
I．組み合わせ回路の設計
ディジタル電子回路
任意の論理関数は標準積和形、標準和積形のいずれ
にも変換できるので、簡単にAND/OR回路が設計でき
る。
２０１５年度後期
1. 論理関数を定義している論理演算を論理ゲートに対
応させる
第１０回
2. 演算順位の最も高い論理演算に対応するゲートから
低いほうへ入力側から出力側へ順に配置、配線
3. 最終出力が論理関数に対応する
例題 F = ABC + BCD + ACD + ABC + BCD + ABC
ABC
A
CD
AB
00
00
01
11
C
10
BC
01
1
11
1
1
10
1
1
1
1
1
4個セルは２つ
D 2個セルは３つ
ABC, BCD, ABD
主項は５つ
AC
必須主項は
特異最小項は４つ
F = BC + AC + ABC + BCD
= BC + AC + ABC + ABD
BC, AC
1
B
従って、最小積和形は
BC, AC, ABC の３つ
必須主項
CD
AB
00
00
01
11
10
BC
01
1
11
1
1
10
ABC
1
1
1
1
1
1
B
AC
a1 a0 b1 b0
演習
まず、真理値表を作成する
２ビットの加算回路の設計
２bit 上の桁 a1
２bit 下の桁 a0
c 桁上がり信号
f1 ２bit 上の桁
f0 ２bit 下の桁
２bit 上の桁 b1
２bit 下の桁 b0
例：(01)2 + (11)2 = ?
まず、真理値表を作成する
ＡＮＤ
ＯＲ
ＸＯＲ
A
B
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
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
a1 a0 b1 b0
使用できる論理ゲート
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B 論理関数Ｆ
F = AB + AB
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
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
0
1
1
0
0
1
1
c f1 f 0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
c f1 f 0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
演習問題解答例
演習問題解答例
c について
f1 について
a1
a0
a1
1
1
f0について
1
1
b0
1
a0
1
a1
1
1
1
1
1
1
1
1
b1
a0
b0
b1
演習問題解答例
c = a 1b 1 + a 1a 0b 0 + a 0b 1b 0
1
1
1
1
1
1
1
1
b0
b1
2bit 加算回路の例（キャリー付）
f 1 = a 1a 0b 1b 0 + a 1a 0b 1b 0 + a 1a 0b 1 + a 1a 0b 1
+ a 1b 1b 0 + a 1b 1b 0
c
f 0 = a 0b 0 + a 0b 0
f 0 = a 0b 0 + a 0b 0 = a 0
b0
f1 = (a1b1+a1b1)a0b0 + (a1b1+a1b1)a0 + (a1b1+a1b1)b0
= (a1
b1)a0b0 + (a1
b1)a0 + (a1
= (a1
b1)a0b0 + (a1
b1)(a0 + b0)
= (a1
b1)(a0b0) + (a1
= (a1
b 1)
(a0b0)
b1)(a0b0)
a1
b1
f1
b1)b0
a0
b0
f0
２段論理最適化におけるドントケアの利用
1. ドントケア項は、その関数値を０か１のどち
らにしても構わない。
ドントケア（Don’t care) とは
n 変数論理関数あるいは n 入力論理回路において
n 個の変数値の組あるいは n 本の入力信号の組に
対して、論理関数値あるいは出力信号が定義されて
いないことをドントケア(Don’t care)、組み合わせ禁
止、不完全定義という。
2. 同じセルに１とｄとが重複するならば、ドント
ケアｄを優先する。
記号は、 d、φ、“－”で表わす
例題
例題
F = AC + ABD + ABC
F = AC + ABD + ABC
A
CD
AB
00
01
11
C
10
00
1
01
11
1
A
10
1
1
1
1
1
CD
D
AB
00
01
11
C
10
B
00
1
01
11
10
d
d
d
d
1
1
1
1
B
最小積和形
F = AC + ABC
D
多段論理最小化
ドントケアを用いる代表例
2進化10進符号 ( Binary Coded Decimal )
前回は、２段論理最小化
• 10進 1桁を 2進 4bit で表わす
• (10)10 ～(15)10 をドントケアとする
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個
例題
F(W,X,Y,Z) = WXZ + WXY + WXY + WXZ
AND: 4個、OR:1個
多項論理演算数 (ST) = 5
2項AND:8個、2項OR:3個
２項論理演算数 = 11
ファクタリングを行なうと…
F = WX(Z+Y) + WX(Y+Z)
論理回路が多段になることを許す前提で空間最適化
を図ることを多段論理最小化という。
= (Y+Z)(WX + WX)
ST = 5、２項論理演算数 = 5
ファクタリングの結果
元の回路
W
X
Z
W
W
X
Y
W
W
X
Y
W
X
Z
X
F
X
F
Y
Z
空間最適化はできているが、時間最適化とはならない。

Download Report