東京電機大講義資料

論理回路および論理設計
2011年度（第1回）
中島克人
情報メディア学科
[email protected]
授業の概要

目的
 実世界の問題を論理の世界にマッピングし、論理回路とし

て設計するための基礎知識を学ぶ。
また、基本的・代表的な論理回路の幾つかについて理解す
る。
達成目標
 論理回路の基本的概念と設計手法の基礎知識の習得を目

指す。
教科書：柴山潔著
「コンピュータサイエンスで学ぶ論理回路とその設計」（近代科学社）


参考書：特になし
評価方法（目安）
 （期末試験）：（出席数等）＝ 8 ： 2
2
授業の概要
どんな内容？
論理代数（論理式）
... （原則） 0 か 1 だけの数学
f（A, B）＝A ・ B ＝ C
g（A, B）＝A ・ B ＋ A ・ B ＝ S
論理回路
論理変数 A, B, C, S は
0 か 1 だけの値を取る
... 論理式と（1対1に）対応（後述）
デジタル回路の設計

論理式で回路仕様を表現し，それを論理式の変形で最適化（簡略化）
して，理想的な（コンパクトな）論理回路を設計
論理式の変形や最適化


パズルのような操作！
記憶する事は少なく，とにかく「慣れ」だけ ... 練習あるのみ
「プロセッサと機械語」の知識は前提としない！
3
集合と論理代数
全世界
B
A
C＝
A・B
A・B＝C
A・B＋A・B＝S
A・B
集合（ベン図）
論理代数（論理式）
C は A かつ B である（等値）。
命題論理
4
集合と論理代数
A
B
全世界
命題論理
A ならば B である（含意）。
A・B＝0
逆命題
B ならば A である。
B・A＝0
逆（命題）は「真」ならず
対偶命題
B でないならば A でない。
B・A＝0
対偶（命題）は常に「真」である
5
論理代数と論理回路
A
A・B＝C
A・B＋A・B＝S
●
B
C
●
●
●
論理代数（論理式）
S
論理回路
6
論理代数と論理回路
 アナログ
vs デジタル＝連続 vs 離散
 論理＝2値（賛vs否、真vs偽、男vs女、左vs右）の世界
＝ 1 vs 0 （記号として使用）→ 論理値
 ビット＝1つの論理（論理値）
 2進数（デジタル値を表現可能） ≠論理＝非数値
＝2冪の各桁の有り無しを論理で示す数表現
 論理代数＝論理を扱う数学
 論理関数＝論理の関係を表現する関数
 論理回路＝論理関数の電気的実現手段
7
論理代数
 論理定数
.... 1 または 0 （論理値そのもの）
 論理変数 .... 1 または 0 を取り得る変数公理１
 論理演算記号（論理演算子）
基本は否定（NOT）、論理積（AND）、論理和（OR）の3つ
論理変数
 例：
論理演算子
X OR （（NOT Y） AND Z）
単項論理演算
２項論理演算
論理式
 本講義（本テキスト）での表記（一般的）
X＋（Y・Z）
8
基本論理演算
 定義1.1：否定（NOT）
... X
 定義1.2：論理積（AND） ... X・Y
 定義1.3：論理和（OR） ... X+Y
真理値表
真理値表
公理２
X
0
1
X
1
0
X
0
0
1
1
Y
0
1
0
1
公理３
公理４
X・Y
0
0
0
1
X+Y
0
1
1
1
9
基本論理演算の演算順位
 定義1.4
優先順位の高いものから順に、
否定（NOT） → 論理積（AND）→ 論理和（OR）
X ＋ Y ・ Z ＝（X ＋（（ Y ）・ Z ））
3
2 1
1
2 3
10
論理式と論理関数
 論理式
論理の関係を表す数式
例： X ＋（ Y ・ Z ）
n変数論理関数
n個の論理変数による関係で、値は 0 か１
ｆ（X1,X2, ... , Xn）＝｛ 0, 1 ｝
論理式、真理値表などで論理関数を表す
11
双対
 定義1.5：
双対
ある論理式Lで
論理記号・（AND） ⇔ ＋（OR）の入替え
論理定数 0 ⇔ 1 の入替え
によって得られる論理式Ldを双対と称する
 双対の例
L ＝（ 1・ Y ）＋（ 0＋（ X ・ Z））とした時、
Ld ＝（ 0 ＋ Y ）・（ 1・（ X ＋ Z））
12
演算順位と双対
 演習：
次の論理式に演算順位を示す「（）」を追加し、優
先順位の数字（最優先＝1）を付けよ
X・（Y＋Z・W）＋X・Y＝
［解］
（X・（Y＋（（Z）・W）））＋（（X・Y））
4
3
2 1 1
2 34
4 3
3 4
 演習：
論理式 L＝X・（Y＋Z・W）＋X・Y の双対Ld を求め
よ
［解］ Ld＝（X＋（Y・（Z＋W）））・（X＋Y）
13
双対性
 双対性
ある論理式Lが成立している時、双対な論理
式Ldも成立することを「双対性がある」という
 定理1.1（双対性）
論理式P,QがP＝Qならば、 Pd＝Qdである
⇒ P＝Qだけを証明すれば、 Pd＝Qdの証明は省略できる
14
種々の基本定理（1変数）
⇔：双対
 定理1.2
X・0＝0 ⇔ X＋1＝1
 定理1.3（2値の存在）
X・1＝X なるXが存在 ⇔ X＋0＝X なるXが存在
 定理1.4（同一則、ベキ等則）
X・X＝X ⇔ X＋X＝X
X・X・・・X ＝X ⇔ X＋X＋‥‥＋X ＝X （系1.5）
 定理1.6（相補則）
X・X＝0 ⇔ X＋X＝1
 定理1.7（二重否定）
X＝X
15
種々の基本定理（多変数）
⇔：双対
 定理1.8（交換則）
X・Y＝Y・X
⇔
X＋Y＝Y＋X
 定理1.9（結合則）
（X・Y）・Z＝X・（Y・Z） ⇔ （X＋Y）＋Z＝X＋（Y＋Z）
 定理1.10（分配則）
X・（Y＋Z）＝（X・Y）＋（X・Z）
⇔ X＋（Y・Z）＝（X＋Y）・（X＋Z）
 定理1.11（吸収則）
X＋（X・Y）＝X
⇔ X・（X＋Y）＝X
X＋（X・Y）＝X＋Y ⇔ X・（X＋Y）＝X・Y （系1.12）
16
種々の基本定理（ド・モルガンの定理）
 定理1.13（De
Morgan の定理）
X・Y＝X＋Y
⇔
⇔：双対
X＋Y＝ X・Y
（X1・X2 ・・・ Xn）＝ X1＋X2＋・・・＋Xn
⇔ （X1＋X2＋・・・＋Xn）＝ X1・X2 ・・・ Xn （系1.14）
X・Y＝X＋Y
⇔
X＋Y＝ X・Y （系1.15）
17
種々の基本定理（ド・モルガンと双対）
 定理1.16（拡張されたDe
Morganの定理）
L ＝ f（X1, X1 , X2, X2 ,・・・Xn, Xn, ・ ,＋）
＝ f（X1, X1 , X2, X2 ,・・・Xn, Xn,＋, ・）
 定義1.6（双対関数）
fd＝ f（X1, X1, X2, X2 ,・・・Xn, Xn, ＋, ・）
ド・モルガン
＝ f（X1, X1, X2, X2 ,・・・Xn, Xn, ・ ,＋）
 定義1.7（自己双対関数）
f＝ fd ならば、f は自己双対関数という
18
種々の基本定理（展開定理）
 定理1.17（展開定理）
Xi・f（X1, ・・, Xi, ・・,Xn）＝Xi・f（X1, ・・, 1, ・・,Xn）
Xi＋f（X1, ・・, Xi, ・・,Xn）＝Xi＋f（X1, ・・, 0, ・・,Xn）
 定理1.18（シャノンの展開定理）
f（X1, ・・, Xi, ・・,Xn）
＝ Xi・f（X1, ・・, 1, ・・,Xn）＋Xi・f（X1, ・・, 0, ・・,Xn）
展開形、肯定・否定分離形、Xi に関する積和形等と呼ぶ
f（X1, ・・, Xi, ・・,Xn）
＝（Xi＋f（X1, ・・, 0, ・・,Xn））・（Xi＋f（X1, ・・,
1, ・・,Xn ））
展開形、肯定・否定分離形、Xi に関する和積形等と呼ぶ 19
種々の基本定理（展開定理）
 例題：
f（X, Y, Z）＝ X・Y＋X・Z を Zで展開し、積和形に
［解］
f ＝ X・Y ＋ X・Z
＝ Z・（ X・Y ＋ X・1 ）＋ Z・（ X・Y ＋ X・0 ）
＝ Z・（ X・Y ＋ X ）＋ Z・（ X・Y ＋ 0 ）
吸収則（定理1.11）
＝ Z・X ＋ Z・X・Y
20
種々の基本定理（展開定理）
 演習：
f（X, Y, Z）＝ X・Y＋X・Z を Yで展開し、積和形に
［解］
f ＝ X・Y ＋ X・Z
＝ Y・（ X・1 ＋ X・Z ）＋ Y・（ X・0 ＋ X・Z ）
＝ Y・（ 0 ＋ X・Z ）＋ Y・（ X ＋ X・Z ）
＝ Y・（ X・Z ）＋ Y・（ X ）
吸収則（定理1.11）
＝ Y・X・Z ＋ Y・X
21
論理関数の表現（準備）
 同じ関数に対する異なる論理式
f（X, Y, Z）＝ X・Y＋X・Z
＝ Z・X ＋ Z・X・Y
＝ Y・X・Z ＋ Y・X
＝ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z
 同一性をどう判定する？
 最も簡単な（コンパクトな）表現は？
22
論理回路および論理設計
2011年度（第2回）
中島克人
情報メディア学科
[email protected]
論理関数の表現
 定義1.8：
リテラル（literal）
論理式を構成する論理変数、または、その否
定をリテラルと総称する。
Xのリテラルを X と表記することにする。
X = { X, X }
X0 = X,
X1 = X
⇒
Xl （l＝0, 1)
 論理積項と論理和項
論理積項：複数のリテラルをANDだけで結んだ項
論理和項：複数のリテラルをORだけで結んだ項
24
論理関数の表現
 積和形（AND－OR形）
複数の論理積項がORで結ばれた論理式
双対
 和積形（OR－AND形）
複数の論理和項がANDで結ばれた論理式
 どんな論理式も積和形又は和積形に展開できる
← 全ての変数に定理1.18（展開定理）を適用
25
論理関数の表現
 最小項（極小項）
n変数論理式において
X1l1・ … ・Xili・ … ・Xnln
（li＝0, 1)
を最小項あるいは極小項という
双対
 最大項（極大項）
n変数論理式において
l
l
l
i
1
X1 ＋ … ＋Xi ＋ … ＋Xn n
（li＝0, 1)
を最大項あるいは極大項という
26
論理関数の表現
 最小項（極小項）
f（X, Y, Z）＝ X・Y＋X・Z ＝ Y・X・Z ＋ Y・X
最小項
論理積項であるが、最小項ではない
27
論理関数の表現（標準積和形）

定義1.11（標準積和形）
ｆ（ l1, … , li, … , ln ) ＝1
となるリテラルの組による最小項
X1l1・ … ・Xili・ … ・Xnln
双対
の全てをORで結んだものを標準積和形という

定義1.12（標準和積形）
ｆ（ l1, … , li, … , ln ) ＝0
となるリテラルの組による最大項
（ X1l1＋ … ＋Xili＋ … ＋Xnln ）
の全てをANDで結んだものを標準和積形という
28
論理関数の表現（標準積和形）
 例：
標準積和形
…×
f（X, Y）＝ X・Y ＋ X
＝ X・Y ＋ X・Y ＋ X・Y … ○
 標準積和形の作り方：
f（X, Y）＝ X・f（0, Y）＋ X・f（1, Y）
＝ X・Y・f（0, 0）＋X・Y・f（0, 1）
＋X・Y・f（1, 0）＋ X・Y・f（1, 1）
＝ X・Y・1＋X・Y・1＋X・Y・0＋X・Y・1
＝ X・Y ＋X・Y
＋X・Y
4つの項から f（?, ?）=1 のものだけを残す
29
論理関数の表現（標準積和形）
 例：
標準積和形
…×
f（X, Y, Z）＝ X・Y・Z ＋ X・Y
＝ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z … ○
 標準積和形の作り方：
f（X, Y, Z）＝ X・f（0, Y, Z）＋ X・f（1, Y, Z）
＝ X・Y・f（0, 0, Z）＋ …. ＋ X・Y・f（1, 1, Z）
＝ X・Y・Z・f（0, 0, 0）＋ …. ＋ X・Y・Z・f（1, 1, 1）
8つの項から
f（?, ?, ?）=1 のものだけを残す
30
論理関数の表現（標準積和形）
 例題：
f（X, Y）＝ Y＋X・Y を標準積和形に
［解］
f ＝ X・Y・f（0,0）＋ X・Y・f（0,1）
＋ X・Y・f（1,0）＋ X・Y・f（1,1）
＝ X・Y・0 ＋ X・Y・1 ＋ X・Y・0 ＋ X・Y・1
＝ X・Y＋ X・Y
［別解］
f（0,1）＝ f（1,1）＝ 1 であるから、
f ＝ X・Y＋ X・Y
31
論理関数の表現（標準積和形）
 演習：
f（X, Y）＝ X＋X・Y を標準積和形に
［解］
f ＝ X・Y・f（0,0）＋ X・Y・f（0,1）
＋ X・Y・f（1,0）＋ X・Y・f（1,1）
＝ X・Y・0 ＋ X・Y・1 ＋ X・Y・1 ＋ X・Y・1
＝ X・Y＋ X・Y＋ X・Y
［別解］
f（0,1）＝ f（1,0）＝ f（1,1）＝ 1 であるから、
f ＝ X・Y＋ X・Y＋ X・Y
32
論理関数の表現（標準積和形）
 演習（P46,
問題1.4）：
f（X, Y, Z）＝ X・Y・Z＋X・Z＋X・Y を標準積和形に
［解］
f ＝ X・Y・Z ＋ X・Z・（Y＋Y）＋ X・Y・（Z＋Z）
＝ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z
＋ X・Y・Z ＋ X・Y・Z
33
論理関数の表現（真理値表）
真理値表
各論理変数の値に対する論理関数の値の一覧表
n=2変数関数の
真理値表の例
n
2 =2エントリ

演習：
f（X, Y）＝ X・Y＋ X・Y
の真理値表を記せ
［解］右表
X
0
0
1
1
Y
0
1
0
1
ｆ＝X・Y＋X・Y＋X・Y
0
1
1
1
X
0
0
1
1
Y
0
1
0
1
ｆ＝X・Y＋X・Y
0
1
0
1
34
論理関数の表現（カルノー図）
カルノー図（Karnough
map）
各論理変数の値に対する論理関数の値の2次元格子図
座標ラベル
n=4変数関数の
カルノー図の例
全部で 2nエントリ
AB
CD
00
01
11
10
0 0
1
1
0
0
0 1
1
1
1
0
1 1
1
0
1
0
1 0
1
0
1
1
：隣接する座標ラベルは論理変数値が1つだけ異なる
（＝ハミング（Hamming）距離が１になる）ように配置する
35
グレイコード

グレイコード（Gray code）
隣接コード（符号）間のハミング（Hamming）距離が１となる
コード列
2ビット： 00 → 01 → 11 → 10 （→ 00）
3ビット： 000 → 001 → 011 → 010 →
↑
100 ← 101 ← 111 ← 110 ←
4ビット：
5ビット：
36
論理関数の表現（カルノー図）

最小項と標準積和形
ひと枡が最小項に対応している
関数値が1の最小項をOR結合したものが標準積和形
最小項 ABCD
f の標準積和形
f（A,B,C,D）
＝ABCD＋ABCD
＋ABCD＋ABCD
AB
CD
00
01
11
10
0 0
1
1
0
0
0 1
0
0
0
0
1 1
0
0
1
0
1 0
0
0
1
0
37
論理関数の表現（カルノー図）

カルノー図による積和形の表現
隣接した2個のマス目 ⇒ （n-1）変数の論理積項
隣接した4個のマス目 ⇒ （n-2）変数の論理積項
‥‥
f の積和形
f（A,B,C,D）
＝ACD
＋ABC
論理積項 ACD
AB
CD
00
01
11
10
0 0
1
1
0
0
0 1
0
0
0
0
1 1
0
0
1
0
1 0
0
0
1
0
38
論理回路および論理設計
2011年度（第3回）
中島克人
情報メディア学科
[email protected]
論理関数の表現（カルノー図）

例題1.15（カルノー図の例）
f（X,Y,Z）＝ X・Y ＋ Y・Z
＝ X・Y・（Z＋Z）＋（X＋X）・Y・Z
X・Y・Z X・Y・Z X・Y・Z X・Y・Z
＝ X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z
0
1
1
0
1
0
1
0
0
0
00
01
11
10
0
1
1
0
1
1
0
1
0
0
0
0
XY
Z
40
論理関数の表現（カルノー図）

例題1.15（カルノー図の例）
f（X,Y,Z）＝ X・Y
0
1 －
＋
Y・Z
－ 0
0
＝ X・Y・（Z＋Z）＋（X＋X）・Y・Z
X・Y・Z X・Y・Z X・Y・Z X・Y・Z
＝ X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z
XY
Z
00
01
11
10
0
1
1
0
1
1
0
1
0
0
41
論理関数の表現（カルノー図）

カルノー図の例：3変数論理関数での1変数の項の表現
X
Y
XY
Z
XY
00
01
11
10
0
0
0
1
1
1
0
0
1
1
Z
XY
00
01
11
10
0
0
1
1
0
1
0
1
1
0
X
Z
00
01
11
10
0
0
0
0
0
1
1
1
1
1
00
01
11
10
Y
XY
Z
Z
Z
XY
00
01
11
10
0
1
1
0
0
1
1
1
0
0
Z
XY
00
01
11
10
Z
0
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
0
0
0
0
42
論理関数の表現（カルノー図）
 演習
次の関数をカルノー図に表しなさい
ACD
f（A,B,C,D）＝ AB ＋ ABCD ＋ ACD
AB
 解答
左図
CD
00
01
11
10
0 0
0
0
1
0
0 1
0
1
1
0
1 1
0
0
1
0
1 0
1
1
1
0
43
論理関数の表現（カルノー図）
 演習
次のカルノー図に表された関数の標準積和形の論理式
を示しなさい。
ABCD
ABCD
ABCD
ABCD
ABCD
 解答
AB
CD
00
01
11
10
0 0
0
0
1
0
0 1
0
1
1
0
1 1
0
0
0
0
1 0
1
1
0
0
f（A,B,C,D）＝ ABCD ＋ ABCD ＋ ABCD
＋ ABCD ＋ ABCD
44
論理関数の表現（2分決定図）

有向グラフ（木／tree）
 節点（ノード／node）と節点を結ぶ枝（リンク／link）からな
り、枝に向きを持つもの
 節点と枝にはラベルをつける
枝
節点
0
Y
1
Z
X
ラベル
45
論理関数の表現（2分決定図）

2分決定図（BDD：Binary Decision Tree）
 非終端節点：論理変数名
 終端節点：論理関数値

0終端節点、1終端節点
 枝：論理変数値、その枝が出る節点（始点）の変数が取る値

0枝、1枝
節点
0枝
枝
0
0
X
論理変数値
変数名
0終端節点
1終端節点
1枝
1
論理関数値0
1
論理関数値１
46
論理関数の表現（完全2分決定図）

定義1.13（完全（順序付き）2分決定図）
 次の手順で作成した2分決定図
1. 最小項を構成する n個の変数の出現順序を任
意に固定する
2. その順序に従って、変数をラベルとする非終端
節点相互をその始点の変数値をラベルとする
枝で結んでいく
3. 最後は論理関数値をラベルとする終端節点に
至る
47
論理関数の表現（完全2分決定図）

完全（順序付き）2分決定図の例
X・Y・Z ＋ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z
X
0
1
Y
Y
0
1
Z
0
0
0
Z
1
0
0
1
1
Z
1
0
0
0
Z
1
0
1
1
1
1
48
論理関数の表現（完全2分決定図）

演習：
次の論理式に相当する完全（順序付き）2分決定図を変数の
出現順を Z→Y→X として示せ
X・Y・Z ＋ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z
Z
0
1
Y
Y
0
1
X
0
0
0
X
1
0
0
1
1
X
1
1
0
0
X
1
1
0
0
1
1
49
論理関数の表現（完全2分決定図）

既約順序付き2分決定図
 次の規則により簡約化した2分決定図
 変数出現順を固定するとこれに対応する積和形も一意
1. 部分木共有： 2分決定図の一部分（部分木）の形状や
ラベルが完全に同一の複数の部分木は共有できる
2. 節点除去： 0枝と1枝の行き先が共に同一の節点に至
る節点は除去できる
3. 節点共有： 0枝と1枝の行き先のそれぞれがどちらも同
じ節点に至り、かつ、同じラベル（変数名）の複数個の節
点は共有（1個に簡約）できる
50
論理関数の表現（完全2分決定図）

既約順序付き2分決定図の例
X・Y・Z ＋ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z ＋ X・Y・Z
X
0
1
Y
部分木共有
Y
0
1
Z
0
Z
1
Z
X
0
Y
Y
1
0
Z
0
Z
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
1
X
1
X
Z
0
1
0
1
Z
0
0
1
Y
節点共有
0
1
0
1
1
0
1
1
1
0
1
0
Z
0
Z
1
0
1
Y
1
Z
0
0
1
Z
1
0
1
1
0
節点除去
51
論理関数の表現（n次元立方体）

定義1.14（n次元立方体）
 n次元座標で、2
n個の頂点を持ち、2個の頂点どうしを各頂
点から出る n本の辺で結んでできる幾何学図形
 nキューブ（n-cube）ともいう
 n次元立方体を総称して、超立方体またはハイパーキュー
ブ（hypercube）という
52
論理関数の表現（n次元立方体）

定義1.14（n次元立方体）
A
AB
AB
AB
AB
A
1次元
2次元
A BC
A BC
.... D
A BC
A BC
AB C
ABC
AB C
ABC
…. D
4次元
3次元
53
論理関数の表現（表現力比較）

論理式
⇒ 同一性判定が容易
 ただし、標準形でない論理式の同一性判定は難しい
 論理式の簡単化のような変形（後述）も難しい
 一意に定まる標準形に変形可能

真理値表
 変数値の組に対する関数値が一目で分かる
 変数の数が多いと表が大きい（n変数時、2

n行）
カルノー図
 「最も」簡単な積和形論理式が直感的に求まる
 変数の数が多いと描くのが難しくなり、非実用的（～6変数）

2分決定図
 論理式との対応は良いが、同一性判定も簡単化も難しい
54
論理代数と論理回路
A
A・B＝C
A・B＋A・B＝S
●
B
C
●
●
●
論理代数（論理式）
S
論理回路
55
論理関数と論理回路（論理ゲート）

論理ゲート
 ハードウェアによる1ビット（1個）の論理演算機能

対象演算項
論理演算
演算結果
入力信号
論理ゲート
出力信号
基本論理ゲート
 NOT（単項）,
AND（2項）, OR（2項）の3種類
56
論理関数と論理回路（論理ゲート）
３つの基本論理ゲート
 定義2.1（NOTゲート）：
X
X ＝ Z なる論理ゲート
（
Z＝X
 定義2.2（ANDゲート）：
X
Z＝X
）
X・Y ＝ Z なる論理ゲート
X
Y
Z＝X・Y
 定義2.3（ORゲート）：
X＋Y ＝ Z なる論理ゲート
X

Y
Z＝ X＋Y
57
論理回路（トランジスタでの実現）
 インバータ（否定）
X
Y＝ X
VCC +5V
 トランジスタ・インバータ
X
入力
RC
330Ω
Y
出力
RB
6.8KΩ
VDD
 CMOSインバータ
P
入力 X
（定常的には）どちらかのトランジスタが
OFFのため、消費電力が小さい
出力 Y
N
58
論理回路（トランジスタでの実現）
 （2入力）AND
 CMOS・（2入力）AND
X
Y
Z＝X・Y
VDD
N
入力 X
N
入力 Y
出力 Z
 CMOS・（2入力）OR
VDD
P
N
P
出力 Z
入力 X
X
Y
N
Z＝X+Y
入力 Y
P
P
59
論理回路および論理設計
2011年度（第4回）
中島克人
情報メディア学科
[email protected]
論理ゲートと論理回路

論理回路
 多数の論理ゲートを組合せて、ある一定の働きをするハー
ドウェア機構を論理回路という

定義2.4（組合せ回路）
 ある時刻の出力信号値がその時刻の入力値だけで決定す
る論理回路を組合せ回路という
【参考】

定義3.2（順序回路） … （教科書p.149）


ある時刻 t の出力が、その時刻 t の入力と状態（即ち、入力履歴）に依
存する論理回路を順序回路という … 状態を保持するメモリを持つ
定義3.3（同期（式順序）回路） … （教科書p.151）

回路動作が（同じ）クロックに同期する順序回路を同期（式順序）回路と
いう
61
組合せ回路／順序回路／同期回路

メモリ

組合せ回路 … 入力だけで出力の値が決まる
（メモリ（＝flip-flopやlatchやregister）を含まない）
順序回路 … 内部状態を持つ
（メモリを含む）
同期（式順序）回路 … 1種類のクロックで内部状態の更新を行う
順序回路
組合せ回路
メモリ

順序回路
クロック（clock）
62
論理関数と論理回路
論理関数と論理回路の関係（その1）
 下図のように、入力を
m本、出力を 1本だけ持つ組合せ回
路 f は、次の論理関数と等価である
入力
X1
X2
Xm
・・・

組合せ
論理回路
Z 出力
f
等価
f（X1, X2,・・・ , Xm）＝ Z
63
論理関数と論理回路

論理関数と論理回路の関係（その2）
 論理関数は組合せ回路における入力と出力との論理関係
を示している
 論理関数は組合せ回路の機能を論理式で表している
 論理回路（組合せ回路）は
3種類の基本論理（NOT, AND,
OR）ゲートだけで作れる
 カルノー図や真理値表は論理回路（組合せ回路）における
入力と出力との関係を示す図表である
 組合せ回路の設計では、入出力信号の時間変化や時間遅
延は考えなくてもよい
 論理ゲートは最小規模の論理回路でもある
64
論理関数と論理回路

定義2.5（ドントケア／don’t care）
 n変数論理関数（あるいは
n入力論理回路）において、n個
の変数値の組（あるいは n本の入力信号の組）に対して、
論理関数値（あるいは出力信号）が定義されていないことを
ドントケア（don’t care）、組合せ禁止、不完全定義などと
いう
後日説明予定
 ある入力の組合せを禁止する
 ある入力の組合せが生じない／冗長である／無効である
 ある入力の組合せがあろうとなかろうとどちらでも構わない
 ある入力の組合せに対応する出力が
0でも 1でもどちらでも構わない／未定義である
65
論理ゲートと組合せ回路
X
f（X）
f
f（X）
0
X
X
1
X f（X）
0
1
1
1
X＝ 0 X＝ 1
0
0
0
1
1
0
1
1
X f（X）
0
1
1
0
4通りの
論理関数
f0
f1
f2
f3
X f（X）
0
0
1
1
1変数論理関数と1入力論理ゲート
m
 4（＝ 2 ）通りの論理関数
X f（X）
0
0
1
0

m
真理値表の行数＝mの時、 2 通りの論理関数
66
論理ゲートと組合せ回路

1変数論理関数と1入力論理ゲート
 展開定理
f（X）＝X・f（0）＋X・f（1）で論理式が求まる
f0
f1
f2
f3
X＝ 0 X＝ 1
0
0
0
1
1
0
1
1
f（X）
0
X
X
1
 例： f2
f（X）＝X・f（0）＋X・f（1）＝X・1＋X・0＝X
67
論理ゲートと組合せ回路

1変数論理関数と1入力論理ゲート
 1入力論理ゲート
f0
f1
f2
f3
X＝ 0 X＝ 1
0
0
0
1
1
0
1
1
f（X）
0
X
X
1
X
X
f（X）
f
0
f
X
f
X
f
X
1
f
68
論理ゲートと組合せ回路
2変数論理関数と2入力論理ゲート
m
=4）通りの論理関数
 16（＝ 2
16通りの
論理関数
X Y g（X）
0
00
0
01
0
10
0
11

X,Y＝ 0 0
g0
0
g1
0
g2
0
:
:
g15
1
01
0
0
0
:
1
10
0
0
1
:
1
X
Y
11
0
1
0
:
1
g（X,Y）
g
g（X,Y）
0
X・Y
X・Y
:
1
m
真理値表の行数＝mの時、2 通りの論理関数
n変数論理関数の種類数は、
真理値表の行数＝＝2n なので、
22n通りの論理関数
m
69
論理ゲートと組合せ回路

2変数論理関数と2入力論理ゲート
やはり展開定理で論理式が求まる
g（X,Y）＝ X・Y・g（0,0）＋ X・Y・g（0,1）
＋ X・Y・g（1,0）＋ X・Y・g（1,1）

演習：下記に示す2変数論理関数の論理式を求めよ
（1） p.60 表2.2 の g6
解答： g（X,Y）＝ X・Y・0＋X・Y・1＋X・Y・1＋X・Y・0
＝X・Y＋X・Y
70
論理ゲートと組合せ回路

演習：下記に示す2変数論理関数の論理式を求めよ
（2） p.60 表2.2 の g11
解答： g（X,Y）＝X・Y・1＋X・Y・0＋X・Y・1＋X・Y・1
＝X・Y＋X・Y＋X・Y＝X・Y＋X・Y＋X・Y＋X・Y
＝（X＋X）・Y＋X・（Y＋Y）＝X＋Y

演習：下記に示す2変数論理関数の論理回路を求めよ
（1） p.60 表2.2 の g6
解答： g（X,Y）＝ X・Y＋X・Y であるので、下図
X
Y
X・Y＋X・Y
71
論理ゲートと組合せ回路（多入力論理ゲート）

定義2.6（n入力ANDゲート）
f（X1, X2, ・・, Xn）＝X1・X2・ ‥‥ ・Xn
を実現する n入力1出力のANDゲート（下図）を
n入力ANDゲートという
n本
:
X1・X2・X3＝（X1・X2）・X3＝X1・（X2・X3）なので、
X1
X2
X3
X1
＝ X2
X3
X1
＝ X2
X3
72
論理ゲートと組合せ回路（多入力論理ゲート）

定義2.7（n入力ORゲート）
f（X1, X2, ・・, Xn）＝X1＋X2＋ ‥‥ ＋Xn
を実現する n入力1出力のORゲート（下図）を
n入力ORゲートという
n本
:
73
論理ゲートと組合せ回路
（その他の論理ゲート）

定義2.8（排他的論理和, EXOR（Exclusive ORゲート）
0、異なるとき 1 を演算結果とす
る 2項論理演算を排他的論理和あるいはEXOR（あるいは
XOR）という
 2個の演算項が等しいとき
 本講義では演算記号として、
○
+ を使う
 2個の論理値が等しいかを調べる「比較演算」の意味がある
 論理式は

g6 ＝ X ○
+ Y ＝ X・Y＋X・Y
定義2.9（EXORゲート）
 定義2.8のEXOR演算を実現する2入力
論理ゲートをEXORゲートという
 回路図では右図の記号を用いる
74
論理ゲートと組合せ回路
（その他の論理ゲート）

定理2.1（EXORと結合則）
 EXORについては次のように結合則が成立する
（X ○
+ Y） ○
+Z＝X○
+ （Y ○
+ Z）

演習：定理2.1を証明せよ
解答：
（左辺）＝X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z＝（右辺）

演習：上記論理式にはもはや「比較演算」としての意味はない
が、どのような意味があるか考察せよ
解答：
X,Y,Zの内、論理値＝1 のものが奇数個のとき 1となる
75
論理ゲートと組合せ回路
（その他の論理ゲート）

定義2.10（否定論理積, NAND（Not AND）
AND を取り、その結果に NOT を施し、最
終の演算結果とする 2項論理演算を否定論理積あるいは
NAND という
 2個の演算項の
 演算記号には
｜をあてる
 NANDを「シェファー（Sheffer）の縦棒演算」ともいう
 論理式は
定義2.11（NANDゲート）
 定義2.10のNAND演算を実現する2入
力論理ゲートをNANDゲートという
 回路図では右図の記号を用いる
＝

X｜Y ＝（X・Y）＝ X ＋ Y ＝ g14
76
論理ゲートと組合せ回路
（その他の論理ゲート）

定義2.12（否定論理和, NOR（Not OR）
OR を取り、その結果に NOT を施し、最終
の演算結果とする 2項論理演算を否定論理和あるいは
NOR という
 2個の演算項の
 演算記号には
↓ をあてる
 NORを「ピアース（Pierce）演算」ともいう
 論理式は
定義2.13（NORゲート）
 定義2.10のNOR演算を実現する2入力
論理ゲートをNORゲートという
 回路図では右図の記号を用いる
＝

X↓Y ＝（X＋Y）＝ X・Y ＝ g8
77
論理ゲートと組合せ回路
（その他の論理ゲート）

定理2.2（NANDと結合則）
 NANDについては次のように結合則が成立しない
（X｜Y）｜Z ≠ X｜（Y｜Z）
 証明：
（左辺）＝（X｜Y）｜Z＝X・Y ・Z＝X・Y＋Z
（右辺）＝X｜（Y｜Z）＝X・ Y・Z＝X＋Y・Z

定理2.3（NORと結合則）
 NORについては次のように結合則が成立しない
（X↓Y）↓Z ≠ X↓（Y↓Z）
 証明：
（左辺）＝（X↓Y）↓Z＝X＋Y＋Z＝X・Z＋Y・Z
（右辺）＝X↓（Y↓Z）＝X＋Y＋Z＝X・Y＋X・Z
78
論理ゲートと組合せ回路

定義2.14（双対回路）
 ある論理関数
（その他の論理ゲート）
f に対応する論理回路 F が存在する．
従って、 f と双対な論理関数 fd に対応する論理回路 Fd
は論理回路として F と双対である．
F

と Fd を双対回路あるいは「双対な論理回路」という
演習： L ＝（X＋Y）＋X・Z に対応する論理回路、
双対な論理式、および双対な論理回路を示せ

X
Y
解答：
対応する論理回路
双対な論理式
双対な論理回路
Ld ＝（X・Y）・（X＋Z）
Z
X
Y
Z
79
万能論理関数集合と論理回路

定義2.15（万能論理関数集合）

その要素を組合せると、任意の論理関数が表現できる論理関
数の集合を万能論理関数集合という

本講義では、万能論理関数集合を Ui （i＝0, …）と表記する

Ui の要素を「万能論理関数」あるいは「万能性がある論理関
数」という

どんな論理式も標準形に変換し、NOT, AND, OR だけで表
せるので、
U0 ＝｛ NOT, AND, OR ｝
80
万能論理関数集合と論理回路
定義2.16（AND／OR形式）

U0 によって表した論理関数（論理式）をAND／OR形式という
ド・モルガンの定理およびANDとORの双対性により、
U1 ＝｛ NOT, AND ｝
U2 ＝｛ NOT, OR ｝

定理1.13（De Morganの定理）
X・Y＝X＋Y
X・Y＝X＋Y
⇔
⇔
X＋Y＝ X・Y
X＋Y＝ X・Y （系1.15）
AND／OR形式の中の全てのORにこれを適用するとAND（とNOT）だけになる
AND／OR形式の中の全てのANDにこれを適用するとOR（とNOT）だけになる
81
万能論理関数集合と論理回路
論理回路上でのド・モルガンの定理

定理1.13（De Morganの定理）
X・Y＝X＋Y
（1）
（1） X
Y
（2）
⇔
双対
X＋Y＝ X・Y
（3）
（4）
（3）
Z
（2）
X
Y
Z
X
Y
（4）
Z
X
Y
Z
X
Y
Z
82
万能論理関数集合と論理回路
論理回路上でのド・モルガンの定理

定理1.13（De Morganの定理）
X・Y＝X＋Y
（1）
（2）
⇔
双対
X＋Y＝ X・Y （系1.15）
（3）
（4）
演習：点線の中を埋めよ
（1）
（2）
X
Y
X
Y
（3）
Z
（4）
Z
X
Y
Z
X
Y
Z
83
万能論理関数集合と論理回路
定義2.17（NOT－AND形式）

U1 によって表した論理関数（論理式）を NOT－AND形式ある
いは単に AND形式という
定義2.18（NOT－OR形式）

U2 によって表した論理関数（論理式）を NOT－OR形式ある
いは単に OR形式という
84
万能論理関数集合と論理回路
定理2.4（NANDの万能性）

任意の論理関数は NAND だけで表せる．従って、次の U3 も
万能論理関数集合である、
U3 ＝｛ NAND ｝
証明： NAND演算（“｜”）によって NOT,AND,OR が表せればよい
→ 教科書 p.68 l.6
別証明： NAND演算（“｜”）によって NOT,ANDが表せればよい
定義2.19（NAND形式）

U3 によって表した論理関数（論理式）を NAND形式という
85
万能論理関数集合と論理回路
定理2.5（NORの万能性）

任意の論理関数は NOR だけで表せる．従って、次の U4 も万
能論理関数集合である、
U4 ＝｛ NOR ｝
定義2.20（NOR形式）

U4 によって表した論理関数（論理式）を NOR形式という
NAND形式やNOR形式は

論理式表現としては分かりにくい

NANDゲート、もしくは、 NORゲートだけで全ての論理回路を
実現できることを意味する
86
Gate Array（ゲートアレイ） LSI

セミカスタムLSIの一種
 NANDゲートあるいはNORゲートのいずれかになり得る基本ハード
ウェア部品をICの中に規則正しく敷き詰めたもの
 未配線のゲートアレイを予め大量生産しておき（＝安価）、配線情報
は回路設計者が後で指定する（＝開発納期短縮）
チップ
IOパッド
セル領域
配線領域
チャネル型Gate Array
チャネルレス型Gate Array
87
万能論理関数集合と論理回路

NANDゲートによる基本ゲートの実現
 NOT：
X＝Z → X・X＝X＝Z
 AND：
X・Y＝Z→ （X・Y）・（X・Y）＝X・Y＝X・Y＝Z
 OR：
X
X
X＋Y＝Z → （X・X）・（Y・Y）＝X・Y＝X＋Y＝Z
X
Y
Z
Z
X
Y
X
Y
Z
Z
X
Z
NORゲートによる基本ゲートの実現も同様
Z
Y
88
万能論理関数集合と論理回路
定義2.21（AND／OR回路）

NOT, AND, OR の3種類の基本論理ゲートだけで構成する論
理回路を AND／OR回路という

AND／OR形式の（U0による）論理関数に対応する論理回路で
ある

AND－OR回路：積和型論理式に対応する回路
（NOT－AND－OR回路とも言える）
→ 教科書 p.71 図2.21 のような回路

OR－AND回路：和積型論理式に対応する回路
（NOT－OR－AND回路とも言える）
→ 教科書 p.71 図2.22 のような回路
89
万能論理関数集合と論理回路
定義2.22（AND回路）

NOT, AND の2種類の基本論理ゲートだけで構成する論理回
路を AND回路という

AND形式の（U1による）論理関数に対応する論理回路である
定義2.23（OR回路）

NOT, OR の2種類の基本論理ゲートだけで構成する論理回路
を OR回路という

OR形式の（U2による）論理関数に対応する論理回路である
90
万能論理関数集合と論理回路
定義2.24（NAND回路）

NANDゲートだけで構成する論理回路を NAND回路という

NAND形式の（U3による）論理関数に対応する論理回路である
定義2.25（NOR回路）

NORゲートだけで構成する論理回路を NOR回路という

NOR形式の（U4による）論理関数に対応する論理回路である
91
万能論理関数集合と論理回路

万能論理関数集合
U0 ＝｛ NOT, AND, OR ｝
 AND／OR形式：
U0 によって表した論理関数（論理式）
 AND／OR回路：AND／OR形式の論理関数に対応する論
理回路
 AND－OR回路：
積和形論理式に対応する回路
 OR－AND回路：
和積形論理式に対応する回路
U1 ＝｛ NOT, AND ｝ ... AND形式、AND回路
U2 ＝｛ NOT, OR ｝ ... OR形式、OR回路
U3 ＝｛ NAND ｝ ... NAND形式、NAND回路
U4 ＝｛ NOR ｝ ... NOR形式、NOR回路
92
組合せ回路の最適化設計
定義2.26（論理回路の解析）

論理回路図が与えられて、それを元にその論理回路を表現す
る論理関数を求めることを、「論理回路の解析」という

「論理回路の解析」は「論理回路⇒論理関数変換」である
定義2.27（論理回路の設計）

解析とは逆に、論理関数が与えられて、それを元にその論理関
数を実現する論理回路を求めることを、「論理回路の設計ある
いは合成」という

「論理回路の設計（合成）」は「論理関数⇒論理回路変換」で
ある
93
組合せ回路の最適化設計
組合せ回路の解析
AND／OR回路の解析手順
1. 各論理ゲート（NOT,AND,OR）の出力を入力による論理式で
表す
2. 1の操作を最前段の入力端子（＝論理変数）から最後段の出
力端子（＝論理関数値）に向かって順に行う
3. 途中結果のNOTは適宜ド・モルガンの定理により、リテラルに
展開する
例題2.3
例題2.4
AND／OR回路の解析（教科書 p.76）参照
NAND回路の解析（教科書 p.77）参照
94
組合せ回路の最適化設計

例題：
下記の回路を解析し、積和形（AND－OR形）論理式で表現しな
さい
X
ｆ（X,Y）

解答：
α
Y
α＝X・Y
f ＝X＋α＝X＋X・Y ＝X・（X・Y）＝X・（X・Y）＝X・Y

例題：
上記の回路を変形して、回答を求めて見よう
X
X
X
Y
Y
Y
X
Y
95
組合せ回路の最適化設計

演習：
下記の回路を解析し、積和形（AND－OR形）論理式で表現しな
さい
X
Y
Z

解答：
α
ｆ（X,Y,Z）
γ
β
α＝X＋Y、 β＝X・Z、 γ＝α＋β
f ＝Y・γ＝Y・（（X＋Y）＋X・Z）＝Y・（（X＋Y）＋X・Z）
＝Y＋（X＋Y＋X・Z）＝Y＋（X・Y・（X・Z））
＝Y＋（X・Y・X・Z）＝Y＋X・Y・Z＝Y＋X・Z
96
組合せ回路の最適化設計

演習：ｆ＝Y＋X・Y・Z＝Y＋X・Z
吸収則は回路変形では見つけにくい
回路を AND－OR回路に変形して、解を求めてみよう
X
Y
Z
X
Y
Z
X
Y
Z
X
Y
Z
X
Y
X
Y
Z
Z
97
組合せ回路の最適化設計


演習：ｆ（X,Y,Z）＝Y＋X・Z の標準積和形論理式を求めよ
解答：ｆ（X,Y,Z）＝Y＋X・Z
＝（X・Z＋X・Z＋X・Z＋X・Z）・Y＋（Y＋Y）・X・Z
＝X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z
010
011
110
111
001
011

＝X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z＋X・Y・Z
演習：上記の標準積和形論理式に対応する論理回路を求めよ

解答：
X
Y
Z
98
組合せ回路の最適化設計

演習：ｆ（X,Y,Z）＝Y＋X・Z に対応する論理回路を求めよ

解答：
X
Y
Z
99
論理回路および論理設計
2011年度（第5回）
中島克人
情報メディア学科
[email protected]
組合せ回路の最適化設計

最適化の目的

論理ゲートの個数が減り、配線が簡単になる
⇒論理回路の実装コストが安くなる
⇒空間的に小さくできる
⇒高速に動作する
⇒故障し難くなる

論理関数の簡単化 vs. 論理回路の最適化

論理演算の個数を減らす ⇒ 論理ゲートの個数を減らす
論理関数の簡単化
⇒
論理回路の最適化
論理関数の最小化
⇒
論理回路の最適化
101
組合せ回路の最適化設計

最適化設計の具体的目的
A. 空間サイズの削減
B. 時間サイズの削減

両立するのか？
定義2.28（段数）

論理回路の入力端子から出力端子に至るまでに通過する
論理ゲート数を段数という

入力端子に近い方を前段、それから遠い方を後段という
特に断りがない場合には、多入力論理（ANDとOR）ゲートも
「1個」、「1段」と数え、NOTゲートは数えなくともよい
 断り書きの例：

『4入力までのANDゲートまたはORゲートは「1段」と数えてよい』
102
組合せ回路の最適化設計

最適化設計の評価指標
A. 空間最適化
「論理回路を構成するのに必要な論理ゲートの総数」を最
小にする
B. 時間最適化
「論理回路の入力端子から出力端子に至るまでに通過する
論理ゲートの段数」を最小にする
即ち、
入力端子から出力端子に至るまでの経路（パス（path））は
普通複数あるが、最も多い段数（最長）の経路（＝クリティカ
ルパス（critical path））の段数を最小にする
103
組合せ回路の最適化設計

演習：
下記の３つの回路のそれぞれのクリティカルパスを求めなさい

解答：左記
X
Y
Z
3段
X
X
Y
Y
Z
Z
2段
2段
104
組合せ回路の最適化設計

多入力論理ゲートと2入力論理ゲート
n入力ANDゲートは（n－1）個の2入力ANDゲートで実現で
きる
 その時の段数は、 log2（n）（ log2（n）を最も近い整数に
CEILING（＝切り上げ））

入力数
n=7
＝
ゲート段数 log2（7）

n入力ORゲートも同様
105
組合せ回路の最適化設計

n入力NANDゲートやn入力NORゲートではどうか？
⇒結合則が成り立たないため、上記は不成立
⇒n入力NANDゲートは、n入力ANDゲートと1個のNOT
ゲートからなり、n入力ANDゲートの部分は上記が成り立
つ
入力数
n=7
＝
ゲート段数 log2（7）
⇒n入力NORゲートも同様
106
組合せ回路の最適化設計

論理回路の段数を論理関数に適用したのが次元

定義2.29（次元）
論理関数の論理積（AND）項と論理和（OR）項を、多項演
算も許して、1つずつ括弧でくくると、括弧の重なり（ネスト
（nest））ができる．多重の括弧のそれぞれは、最内側を最
優先とし、外側へ向かって低くなる演算順位を示す
 最内側から外側に向かって、1, 2, … と演算順位を付けたと
き、これを次元あるいはレベル（level）という


その論理式における最大次元を単に次元ということがある
（なお、次元は、実際には冗長で省略できる括弧も数える）

例：（（X・Y・Z）・（Y＋（Z・X）））は 3次元

演習：（（（X＋Y）＋ Z・X ）・（Y＋Z・X））の次元は 3次元
107
組合せ回路の最適化設計

演習：（（X＋ Y・Z ）・Z）＋（Y＋Z・X）の次元は

解答：（（（X＋（Y・Z））・Z）＋（Y＋Z・X））なので 4次元

演習：（（X＋ Y・Z ）・Z）＋（Y＋Z・X）を忠実に実現す
る論理回路を示し、クリティカルパスの段数を求めよ

解答：
X
Y
Z
クリティカルパス
4段
108
論理関数と論理回路の最小化

論理関数の最小化とそれに連動する論理回路の最小化
を併せて論理最小化という

論理最小化された論理関数や論理回路を最小形あるい
は最簡形という

定義2.30（包含）


ある論理積項Qの値を“1”にする変数値の組合せ全てに対
して、別の論理積項Pが“1”になるとき、「PはQを包含する」
あるいは「QはPに包含される」という
例： P＝X・Z は Q＝X・Y・Z を包含する

PがQを包含するとき、Pに現れるリテラルは必ずQにも現れ
る

Pを表すリテラル数の方がQを表すリテラル数よりも少ない
109
論理関数と論理回路の最小化

カルノー図による積和形の表現（復習）
隣接した2個のマス目 ⇒ （n-1）変数の論理積項
隣接した4個のマス目 ⇒ （n-2）変数の論理積項
‥‥

例： P＝X・Z は Q＝X・Y・Z を包含する
論理積項 Q＝XYZ
論理積項 P＝XZ
XY
ZW
00
01
11
10
0 0
0
0
1
1
0 1
0
0
1
1
1 1
0
1
1
0
1 0
0
0
1
0
110
論理関数と論理回路の最小化

演習
1. 次の関数をカルノー図に表しなさい
f（A,B,C,D）＝ AB ＋ ACD ＋ BCD ＋ ABCD ＋ ABC
2. この関数の論理積項の内、包含関係にあるものを列挙し
なさい

解答
1. 右図
2. ABCはABに、また、
ABCDはACDに
包含される
AB
CD
00
01
11
10
0 0
0
0
1
0
0 1
0
1
1
0
1 1
0
0
1
0
1 0
1
1
1
0
111
論理回路および論理設計
2011年度（第6回）
中島克人
情報メディア学科
[email protected]
論理関数と論理回路の最小化

定義2.31（主項）

任意の論理関数 f において、相異なる変数によって構成する
論理積項を ti とする.
 ti＝1
となる論理積項 ti の全て（n個）を論理和（OR)で結んだ
積和形によって f を表すと下記となる.
f ＝ t1 ＋ t2 ＋ ‥‥ ＋ tn （ i＝1, ‥ , n ）

即ち、ti ＝1 の時、f ＝1 である. この時、ある論理積項 ti がそ
れ以外の論理積項 tj （ j≠i ）のいずれにも包含されない時、こ
の ti を主項という

主項 ti を構成する変数の内から任意の1個を取り除いて出来
る論理積項で、 ti’ ＝1 となるものは存在しない
113
論理関数と論理回路の最小化

積和形論理式において、主項でない論理積項は主項に吸収され
るので、任意の論理関数 f は主項だけの論理和で表現できる

定理1.11（吸収則）
X＋ X・Y ＝X
⇔ X・（X＋Y）＝X
X＋ X・Y ＝X＋Y ⇔ X・（X＋Y）＝X・Y （系1.12）

主項の例：
f ＝ X・Z＋X・Y＋X・Y・Z
において、X・Z と X・Y が主項
（X・Y・Z は X・Z に包含される）
 即ち、 f ＝ X・Z＋X・Y＋X・Y・Z ＝ X・Z＋X・Y
主項
主項
主項ではない
主項
主項
114
論理関数と論理回路の最小化

定義2.32（最小積和形）


主項だけで構成する積和形の内、主項（論理積項）の総数
が最小のものを最小積和形という
例： f ＝ X・Y＋X・Z＋X・Y・Z＋Y・Z
主項
Y・Z 主項
Z＼X Y 0 0
0
0
1
0
01
1
0
11
1
1
X・Z
10
0
1
X・Y
X・Y・Z
X・Zに包含される
ため、主項ではない
主項
f ＝ X・Y＋X・Z＋X・Y・Z＋Y・Z ...... 主項以外を含む
...... 主項のみを含む
＝ X・Y＋X・Z＋Y・Z
＝ X・Z＋Y・Z ...... 主項の数が最小 ⇒ 最小積和形
115
論理関数と論理回路の最小化


定義2.33（必須主項と特異最小項）

任意の論理式において、ある主項 P だけが、標準積和形を
構成する最小項（論理積項）m を包含する時、P を必須主
項（あるいは必須項）という

また、m を特異最小項という
例： f ＝ X・Y＋X・Z＋X・Y・Z＋Y・Z
必須主項必須主項
Z＼X Y 0 0
0
0
1
0
01
1
0
特異最小項
11
1
1
10
0
1
特異最小項
必須ではない主項
116
論理関数と論理回路の最小化

最小積和形を求める手順

ポイント：



最小積和形に現れる論理積項は必ず主項である
必須主項は最小積和形を構成する主項として必須である
手順：
1. 論理関数を展開して標準積和形にする
2. 主項の決定：全ての主項を見つける
3. 必須主項の決定： 2で求めた主項の中から全ての必須主項を見つ
ける
4. 主項の選択： 3で求めた必須主項が包含しない最小項を包含する
主項を、2で求めた主項の中から選択する. ただし、必要な主項数
が最小になるように選択する
5. 3の必須主項と 4で選択した主項とを OR で結んだものが最小積
和形である
117
論理関数と論理回路の最小化

例：1. 標準積和形
⇒ 代わりにカルノー図を作成にする
2. 主項の決定：全ての主項を見つける ⇒ 出来るだけ大きく囲う
3. 必須主項の決定： 2で求めた主項の中から全ての
必須主項を見つける
⇒ 最小項を単独で囲う主項
4. 主項の選択： 3で求めた必須主項が包含しない最
小項を包含する主項を、2で求めた主項の中から選
択する. ただし、必要な主項数が最小になるように
選択する
⇒ 最小項を複数の主項で囲う場
合に、そのどれか一つを選ぶ
5. 3の必須主項と 4で選択した主項とを OR で結んだ
ものが最小積和形である ⇒ 選ばれた主項のORが解
Z＼X Y 0 0
0
1
1
0
01
1
1
11
0
1
10
0
1
118
論理関数と論理回路の最小化

演習：下記のカルノー図において、特異最小項、必須主
項を論理積項で示せ
CD＼AB 0 0
00
0
01
1
11
1
10
0
01
1
0
0
1
11
0
0
0
1
10
1
1
1
1
：特異最小項
必須主項

解答：特異最小項は A・B・C・D、A・B・C・D、A・B・C・D、A・B・C・D
必須主項は A・B、 B・D、 A・B・D

演習：上記のカルノー図の最小積和形の論理式を求めよ

解答： f ＝ A・B＋B・D＋A・B・D＋A・C・D
119
論理関数と論理回路の最小化

論理回路の2段論理最小化

最小積和形は、積和形を空間最適化した論理式であるから、
それに対応する論理回路は空間最適化された、AND－OR
回路である. 従って、時間サイズは 2段である

最小積和形は空間最適化した2段論理回路の表現法といえ
る
120
論理関数と論理回路の最小化

カルノー図による2段論理最小化（＝最小積和形を求める）
1. 任意の積和形をカルノー図として表現する
2. 1 のカルノー図によって2段論理最小化を行う
3. 2のカルノー図から最小積和形を読み取る

演習：下記のカルノー図の2段論理最小化を行い、
最小積和形の論理式を求めよ
CD＼AB 0 0
00
1
01
0
11
0
10
1

01
1
1
1
1
11
1
1
1
1
10
1
0
1
0
：特異最小項
解答： f ＝ B＋C・D＋A・C・D＋A・D
121
論理関数と論理回路の最小化

演習：次の関数の2段論理最小化を行い、最小積和形
の論理式を求めよ
f ＝ A・B・C＋A・B・C＋A・B・C＋A・B・C＋A・B・C＋A・B・C

解答：カルノー図は下記となる
C＼AB 0 0
0
0
1
1
01
1
1
11
1
1
10
1
0
カルノー図で主項を求めると上記３つとなり、これらは全て必
須主項である。また、他に選択すべき主項はない。
故に、
f ＝ B＋A・C＋A・C
122
論理関数と論理回路の最小化

演習： f ＝ A・B・C・D＋A・C＋A・B・D＋A・B・D＋A・C・D
のカルノー図を示せ

解答：左図
CD＼AB 0 0
1
00
0
01
0
11
1
10
01
0
1
1
1
11
1
1
0
0
10
1
1
0
1
：特異最小項
演習：特異最小項に
印を付け、必須主項を挙げよ
 解答：特異最小項は上図の
印
必須主項は B・D、 A・C
 演習：上記の論理式の最小積和形の論理式を求めよ
 解答： f ＝ B・D＋A・C＋A・B・D＋A・B・C


演習：上記も含め、計何種類の解答があるか？

解答：3種類
123
論理関数と論理回路の最小化
 復習：カルノー図による
論理関数の最小化
1. 標準積和形を求める
2. 全ての主項を見つける
Z＼X Y 0 0
0
1
1
0
01
1
1
11
0
1
10
0
1
⇒ カルノー図を作成にする
⇒ 出来るだけ大きく囲う
3. 2で求めた主項の中から全ての必須主項を見つける
⇒ 最小項を単独で囲う主項
4. 3で求めた必須主項が包含しない最小項を包含する
主項を、2で求めた主項の中から選択する. ただし、必
要な主項数が最小になるように選択する
⇒ 最小項を複数の主項で囲う場
合に、そのどれか一つを選ぶ
5. 3の必須主項と 4で選択した主項とを OR で結んだも
のが最小積和形である
⇒ 選ばれた主項のORが解
124
論理関数と論理回路

定義2.5（ドントケア／don’t care）
 n変数論理関数（あるいは
n入力論理回路）において、n個
の変数値の組（あるいは n本の入力信号の組）に対して、
論理関数値（あるいは出力信号）が定義されていないことを
ドントケア（don’t care）、組合せ禁止、不完全定義などと
いう
 ある入力の組合せを禁止する
 ある入力の組合せが生じない／冗長である／無効である
 ある入力の組合せがあろうとなかろうとどちらでも構わない
 ある入力の組合せに対応する出力が
0でも 1でもどちらでも構わない／未定義である
125
論理関数と論理回路の最小化
2段論理最小化におけるドントケアの利用

関数値がドントケアを含む場合、論理最小化に有効であるな
らば、ドントケアを “1” と見なす
カルノー図による最小化の時のドントケアの利用例
カルノー図上の「－（ドントケア）」は、
（“1”のます目を）より大きく囲むために有効であれば、“1”と見なす
あるいは、（“1”のます目を）囲む個数をより少なく出来るならば
“1”と見
なす
＼ AB
CD＼ 0 0 0 1 1 1 1 0
00
01
11
10
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
B・D
が
don’t
care
＼ AB
CD＼ 0 0 0 1 1 1 1 0
00
01
11
10
0
0
0
0
1
－
－
1
1
－
－
1
0
1
1
0
126
論理関数と論理回路の最小化
演習：
ドントケアを利用したカルノー図による論理最小化

（1）ｆ＝A・C＋A・B・D＋A・B・C （ドントケアなし）

（2）ｆ＝A・C＋A・B・D＋A・B・C （ A・B・Cはドントケア）
 解答（1）
 解答（2）
＼ AB
CD＼ 0 0 0 1 1 1 1 0
＼ AB
CD＼ 0 0 0 1 1 1 1 0
00
01
11
10
00
01
11
10
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
－
－
1
1
（1）ｆ＝A・C＋A・B・D＋A・B・C
（2）ｆ＝A・C＋A・D＋B・C
127
論理関数と論理回路の最小化
演習：
ドントケアを利用したカルノー図による論理最小化

（3）ｆ＝A・C＋A・B・D＋A・B・C （ C・Dはドントケア）

（4）ｆ＝A・C＋A・B・D＋A・B・C （ Cはドントケア）
 解答（3）
 解答（4）
＼ AB
CD＼ 0 0 0 1 1 1 1 0
＼ AB
CD＼ 0 0 0 1 1 1 1 0
00
01
11
10
00
01
11
10
1
－
0
0
0
－
0
0
0
－
1
1
0
－
1
1
－
－
0
0
－
－
0
0
－
－
1
1
－
－
1
1
（3）ｆ＝A・C＋A・B・C
（4）ｆ＝A
128
練習問題

カルノー図で主項を求める（出来るだけ大きく 1 を囲う）のを間違うと以降
の設問に正しく答えられないので，主項を正しく求める事は最重要！！

問題：以下のカルノー図の主項を全て求めよ
（他の人と答え合わせをして見よう！）
XY
Z
0
1
AB
00
0
1
AB
CD
00
0 0
0
0 1
0
1 1
1
1 0
1
01
0
0
01
0
0
1
0
11
0
1
11
0
1
1
1
10
1
1
10
1
0
1
1
C
0
1
00
1
1
01
0
1
11
1
0
10
1
1
XY
ZW
0 0
0 1
1 1
1 0
00
1
0
0
1
01
0
0
1
0
11
1
10
1
1
0
－
－
1
1
129
論理回路および論理設計
2011年度（第7回）
中島克人
情報メディア学科
[email protected]
論理関数と論理回路の最小化

カルノー図による2段論理最小化の特徴
長所：


手順が直感的で分かり易い
必要な主項の選択が容易にできる
短所：


5変数以上になると隣接関係が分かり難くなるため、
上記長所はなくなる
教科書 p.94 図2.38 参照
変数が多い場合
⇒ クワイン－マクラスキ法（Q-M法）による2段論理最小化
131
論理関数と論理回路の最小化
 クワイン－マクラスキ法（Q-M法）
最小項表（真理値表の「関数値が１の行」だけのもの）から
出発する
真理値表
X Y Z
ｆ
0
0
0
0
1
1
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
最小項表
X Y Z
ｆ
0
0
1
1
1
1
1
1
1
1
0
1
0
0
1
1
1
0
1
0
最小項
X・Y・Z
X・Y・Z
X・Y・Z
X・Y・Z
X・Y・Z
 各行（最初は最小項を表す）の併合を、リテラル消去表と
主項－最小項表を作成しながら行い、最小積和形を求める
132
論理関数と論理回路の最小化
 Q-M法の準備
最小項表の例
（教科書 p.96表2.3）
X Y Z
ｆ
0
0
1
1
1
1
1
1
1
1
0
1
0
0
1
1
1
0
1
0
最小項
X・Y・Z
X・Y・Z
X・Y・Z
X・Y・Z
X・Y・Z
併合の例（教科書 p.96表2.4）
併合
X Y Z 最小項
1 1 1 X・Y・Z
1 1 0 X・Y・Z
積項
1 1 － X・Y
XYZ
ドントケア
（ don’t care ）
併合
X Y Z 最小項
1 1 1 X・Y・Z
1 1 0 X・Y・Z
0 1 0 X・Y・Z
積項
1 1 － X・Y
－ 1 0 Y・Z
XYZ
ドントケア
（ don’t care ）
133
論理関数と論理回路の最小化
 Q-M法による
2段論理最小化の手順
1. 主項の決定
（a）最小項表を元に、初期表を構成する
（b）初期表を行の併合によって更新する
（更新後の表を「リテラル消去表」という）
（c）併合できる行がなくなるまで、リテラル消去表の更新を繰り返す
（d） 1（c）を繰り返して最後に残った各行が主項にあたる
2. 必須主項の決定と主項の選択
（a）主項と最小項との対応表（「主項－最小項表」という）を作成する
（b）主項－最小項表によって必須主項の決定と必要な主項の選択
を行う
3. 必須主項を含む選択した主項全てを OR で結んだものが
最小積和形である
134
Q-M法による 2段論理最小化の手順
1. 主項の決定
ラベル
1
（a）初期表の構成
4
最小項表の左にラベル欄、
8
右に主項欄を設ける
3
6
9
10
11
14
 関数値の列は不要

B
0
1
0
0
1
0
0
0
1
C
0
0
0
1
1
0
1
1
1
D 主項
1
0
0
1
0
1
0
1
0
行グループ
1が1つ
1が2つ
1が3つ
ラベルは任意


A
0
0
1
0
0
1
1
1
1
ここでは変数値の組を10進数読み
「行グループ」分けすることにより、併合の相手が見つけやすい

併合相手の候補行は隣接グループ（ハミング距離1）の中に！
135
Q-M法による 2段論理最小化の手順
1. 主項の決定
（b）行の併合
初期表／リテラル消去表（1）
ラベル
1
4
8
3
6
9
10
11
14
A
0
0
1
0
0
1
1
1
1
B
0
1
0
0
1
0
0
0
1
C
0
0
0
1
1
0
1
1
1
D 主項
1
0
0
1
0
1
0
1
0
リテラル消去表（2）
ラベル
1,3（2）
1,9（8）
4,6（2）
8,9（1）
8,10（2）
3,11（8）
6,14（8）
9,11（2）
10,11（1）
10,14（4）
A B C D 主項
0 0 － 1
－ 0 0 1
0 1 － 0
1 0 0 －
1 0 － 0
－ 0 1 1
－ 1 1 0
1 0 － 1
1 0 1 －
1 － 1 0

併合した行を新しいリテラル消去表に転記し、主項欄に
を入れる

隣接した「行グループ」の各行どうしの全ての組合せを吟味する
136
Q-M法による 2段論理最小化の手順
1. 主項の決定
（c）併合が出来なくなるまで、リテラル消去表の更新を続ける
リテラル消去表（2）
ラベル
1,3（2）
1,9（8）
4,6（2）
8,9（1）
8,10（2）
3,11（8）
6,14（8）
9,11（2）
10,11（1）
10,14（4）
A B C D
0 0 － 1
－ 0 0 1
0 1 － 0
1 0 0 －
1 0 － 0
－ 0 1 1
－ 1 1 0
1 0 － 1
1 0 1 －
1 － 1 0
主項
主項
リテラル消去表（3）
＊p
ラベル
主項
1,3,9,11（2,8）－ 0 － 1 ＊s
8,9,10,11（1,2） 1 0 －－＊t
A B C D
＊q
主項
＊r
（d）併合されなかった行は主項
主項
137
Q-M法による 2段論理最小化（演習）

演習：ｆ＝A・B・C＋B・C・D＋A・C・D＋A・B・C＋B・C・D
のQ-M法のための初期表からリテラル消去表を用いて
リテラル消去表（2）
主項を求めよ

解答：
初期表／リテラル消去表（1）
ラベル
2
4
3
5
10
11
13
15
A
0
0
0
0
1
1
1
1
B
0
1
0
1
0
0
1
1
C
1
0
1
0
1
1
0
1
D 主項
0
0
1
1
0
1
1
1
ラベル
A B C D 主項
2,3（1）
2,10（8）
4,5（1）
3,11（8）
5,13（8）
10,11（1）
11,15（4）
13,15（2）
0
－
0
－
－
1
1
1
ラベル
0
0
1
0
1
0
－
1
1 －
1 0
0 －
1 1
0 1
1 －
1 1
－ 1
＊p
＊q
主項
＊r
＊s
A B C D 主項
2,3,10,11（1,8）－ 0 1 －＊t
138
Q-M法による 2段論理最小化の手順
2. 必須主項の決定と主項の選択
（a）「主項－最小項表」を作成する
（「どの最小項を元にして、その主項を構成したか」を示す表）
主項－最小項表
（b）-1 必須主項の決定

特異最小項を含む
主項が必須主項
必須主項
選択した
主項
最小項（ラベル）
主項（ラベル） 1 3 4 6 8 9 10 11 14
4,6 p
◎
○ ○
6,14 q
○
○
10,14 r
○
○
1,3,9,11 s ◎
○ ◎
○
○
○
8,9,10,11 t
◎
○ ○ ○ ○
（b）-2 必要な主項の選択を行う

◎ ：特異最小項
必須主項に含まれない最小項（残り）を含む主項を選択する
残りの最小項を多く含む主項を優先する
○の多い（ラベルが長い＝リテラル数が少ない）主項を優先する
139
Q-M法による 2段論理最小化の手順
3. 最小積和形を求める
必須主項を含む選択した主項全てを OR で結んだものが最小積和形で
ある
主項－最小項表
必須主項
選択した
主項
最小項（ラベル）
主項（ラベル） 1 3 4 6 8 9 10 11 14
4,6 p
◎
○ ○
6,14 q
○
○
10,14 r
○
○
1,3,9,11 s ◎
○ ◎
○
○
○
8,9,10,11 t
◎
○ ○ ○ ○
A
0
－
1
－
1
B C D
1 － 0
1 1 0
－ 1 0
0 － 1
0 －－
論理積項
A・B・D
B・C・D
A・C・D
B・D
A・B
◎ ：特異最小項
 最小積和形は、
ｆ（A,B,C,D）＝A・B・D ＋ B・C・D ＋ B・D ＋ A・B
 または、
ｆ（A,B,C,D）＝A・B・D ＋ A・C・D ＋ B・D ＋ A・B
140
Q-M法による 2段論理最小化（演習）

演習：ｆ＝A・B・C＋B・C・D＋A・C・D＋A・B・C＋B・C・D
のQ-M法により求めた主項から主項－最小項表を作成
して必須主項を求め、最後に最小積和形を求めよ

解答：
必須主項
選択した
主項
主項－最小項表
主項（ラベル）
4,5 p
5,13 q
11,15 r
13,15 s
2,3,10,11 t
最小項（ラベル）
2 3 4 5 10 11 13 15
◎ ○
○
○
○
○
○
○ ○
◎
◎
○ ◎
○
○ ○
A B
0 1
－ 1
1 －
1 1
－ 0
C D
0 －
0 1
1 1
－ 1
1 －
論理積項
A・B・C
B・C・D
A・C・D
A・B・D
B・C
◎ ：特異最小項
 最小積和形は、
ｆ（A,B,C,D）＝A・B・C ＋ A・B・D ＋ B・C
141
Q-M法による 2段論理最小化（演習）

演習：ｆ＝A・C＋A・B・C・D＋A・B・C・D＋A・B・C
のQ-M法のための初期表からリテラル消去表を用いて
リテラル消去表（2）
主項を求めよ

ラベル
解答：
初期表／リテラル消去表（1）
ラベル
0
1
10
11
13
14
15
A
0
0
1
1
1
1
1
B
0
0
0
0
1
1
1
C
0
0
1
1
0
1
1
D 主項
0
1
0
1
1
0
1
A B C D 主項
0 0 0 －＊p
0,1（1）
10,11（1） 1 0 1 －
10,14（4） 1 － 1 0
11,15（4） 1 － 1 1
13,15（2） 1 1 － 1 ＊q
14,15（1） 1 1 1 －
ラベル
主項
A B C D 主項
10,11,14,15（1,4） 1 － 1 －
故に、主項は A・C、A・B・D、A・B・C の3つ
＊r
142
Q-M法による 2段論理最小化（演習）

演習：ｆ＝A・C＋A・B・C・D＋A・B・C・D＋A・B・C
のQ-M法により求めた主項から主項－最小項表を作成
して必須主項を求め、最後に最小積和形を求めよ

解答：
必須主項
主項－最小項表
主項（ラベル）
0,1 p
13,15 q
10,11,14,15 r
最小項（ラベル）
0 1 10 11 13 14 15
◎ ◎
○
○
◎
○
○
◎
◎
○ ◎
○
○ ○
A
0
1
1
B
0
1
－
C D 論理積項
0 － A・B・C
－ 1 A・B・D
1 －
A・C
◎ ：特異最小項
 最小積和形は、
ｆ（A,B,C,D）＝A・B・C ＋ A・B・D ＋ A・C
143
Q-M法による 2段論理最小化（演習）

演習：ｆ＝A・B・C＋B・C・D＋A・C・D＋A・B・C＋B・C・D
のQ-M法により求めた主項から主項－最小項表を作成
して必須主項を求め、最後に最小積和形を求めよ

解答：
必須主項
選択した
主項
主項－最小項表
主項（ラベル）
4,5 p
5,13 q
11,15 r
13,15 s
2,3,10,11 t
最小項（ラベル）
2 3 4 5 10 11 13 15
◎ ○
○
○
○
○
○
○ ○
◎
◎
○ ◎
○
○ ○
A B
0 1
－ 1
1 －
1 1
－ 0
C D
0 －
0 1
1 1
－ 1
1 －
論理積項
A・B・C
B・C・D
A・C・D
A・B・D
B・C
◎ ：特異最小項
 最小積和形は、
ｆ（A,B,C,D）＝A・B・C ＋ A・B・D ＋ B・C
144
論理関数と論理回路の最小化
 Q-M法による
2段論理最小化の特徴
長所：


数値化が簡単で、コンピュータ処理に向く
即ち、多変数論理関数にも適用可
短所：


手順が少々面倒（特に主項の選択操作が手間）
カルノー図に比し、人間が行う最適化としては直感性で
劣る
145
論理回路および論理設計
2011年度（第8回）
中島克人
情報メディア学科
[email protected]
論理関数と論理回路の最小化
多段論理最小化
ファクタリング（factoring）
 定理1.10（分配則）を用いて、論理式から共通項をくくり出す
操作
 2項論理演算数SB（ANDとORの総数）は減り、場合によって
は多項論理演算数 ST も減る

例1：（（X・Y）＋（X・Z））＝（X・（Y＋Z））
SB＝3, ST＝3

SB＝2, ST＝2
例2：（（X・Y）＋（X・Z）＋（X・W））＝（X・（Y＋Z＋W））
SB＝5, ST＝4

SB＝3, ST＝2
ファクタリングは次元を増やす操作であり、時間最適化とは逆
行する
147
論理関数と論理回路の最小化
 2項論理演算数SB
と多項論理演算数 ST およびゲート数の関係
例2：（（X・Y）＋（X・Z）＋（X・W））＝（X・（Y＋Z＋W））
SB＝5, ST＝4
SB＝3, ST＝2
f1 ＝（（X・Y）＋（X・Z）＋（X・W））
f2 ＝（X・（Y＋Z＋W））
X
Y
Z
W
X
Y
Z
W
f1
ST＝4ゲート
X
Y
Z
W
f1
SB＝5ゲート
X
Y
Z
W
f2
ST＝2ゲート
f2
SB＝3ゲート
148
論理関数と論理回路の最小化
定義2.34（多段論理最小化）


「論理回路が多段になる（時間サイズが増大する）ことを許
す」という前提で論理回路の空間最適化を図ることを多段論
理最小化という

論理式に対しては「次元が増えることを犠牲にして、多項論理
演算数ST あるいは 2項論理演算数SBを減らす操作」に相当
例：
f（W,X,Y,Z）＝W・X・Z＋W・X・Y＋W・X・Y＋W・X・Z
SB＝11
ST＝5
＝（（W・X・（Y＋Z））＋（W・X・（Y＋Z）））
＝（（（W・X）＋（W・X））・（Y＋Z））

SB＝5
ST＝5
ST は 5で変わらないが、SB は 6だけ減少し、次元は 2 から 3
に増えている
149
論理関数と論理回路の最小化
演習（多段論理最小化）

次の論理式の多項論理演算数ST および 2項論理演算数SB
はそれぞれ幾つか？
f ＝X・Y・Z＋Y・Z・Q＋X・Y・Z＋Y・Z・W＋X・Y・W
解答： SB＝14, ST＝6

上記論理式をファクタリングした論理式を求め、その ST およ
び SB をそれぞれ求めよ。
解答：論理式は下記で、SB＝ 8 , ST＝ 5
f ＝X・Y・（Z＋W）＋Y・Z・（X＋W＋Q）
150
論理関数と論理回路の最小化
 ファクタリングは「共通項のくくり出し」という明確な操作である
 それ以外の式変形操作を用いて、任意の論理式に対して空間最
適化あるいは時間最適化を行うのは難しい
 理由は、

最適化の限界が分かりにくい

適用する変形操作を見つける一定の規則がない

変形過程が異なると最適化結果が異なる場合がある
 例：
F＝X・W＋Y・W＋Z・W＋Z・V＋X・Y・Z
SB＝ 10
ST＝ 6
＝（X＋Y＋Z）・W＋（V＋X・Y）・Z
SB＝ 7
ST＝ 6
＝（X＋Y）・W＋（W＋V＋X・Y）・Z
SB＝ 7
ST＝ 6
151
中間試験
試験日時：
11月18日（金）
18:30～19:30
持込み可：
教科書、講義プリント、ノート
持込み不可：
試験用紙：
あらゆる電子機器（PC, 電卓, 携帯...）、
問題用紙，解答用紙共に回収します
コツ！：出来る問題から慎重かつ素早く解く
152
中間試験の注意
最初に20分程度講義をしてから中間試験
試験時の使用座席（自由席）
試験時間
で
18:30～19:30
教壇
持込み可：
教科書、講義プリント、ノート
持込み不可：
あらゆる電子機器（PC, 電卓, 携帯...）
試験用紙：
問題用紙B4 1枚
… 学籍番号・氏名記入、試験後回収
解答用紙A4 1枚
… 学籍番号・氏名記入、試験後回収
153
組合せ回路設計の実際
AND／OR回路の時間最適化設計
 時間最適化設計、即ち
2段論理最小化した AND／OR回路
は、積和形を AND－OR回路にテクノロジマッピングして得る

最小積和形からテクノロジマッピングするのが普通

同様に、OR－AND回路は（最小）和積形から得る
154
論理回路および論理設計
2011年度（第9回）
中島克人
情報メディア学科
[email protected]
中間試験の解答
問１．次の関数の双対な論理式を示せ（展開などは不要である。定数もそのまま記せ。）。（7点）
f(X,Y,Z)＝ ( Z・X ＋ 0 ＋ Y )・( 1・Y ＋ X )
解
答
fd＝((Z＋X)・1・Y))＋((0＋Y)・X)
問２．下記の論理式の両辺が等しいものには○、
等しくないものには×を付けよ。（各7点）
(1)
A・B ＋ A ○
＋ C ＋ C・A ＝ A・( B ＋ C ) ＋ C
(2)
( X ＋ Y ＋ Z ) ＋ Y・Z ＝ ( X ＋ Y )・( Y ＋ Z )
解答
(1)
○
(2)
○
問３．次の関数 f(A,B,C) の関し、次の設問に解答せよ。
f(A,B,C)＝ A・( B ＋ C ) ＋ B・C
(a) この論理式を忠実に表す
AND/OR回路を示せ。（7点）
(b) 標準積和形論理式を示せ。（7点）
解答 (b) 標準積和形論理式
f＝ABC＋ABC＋ABC＋ABC＋ABC
解答 (a) 回路図
A
B
ｆ
C
156
中間試験の解答
問４．下図のAND/OR回路に関し、次の設問に解答せよ。
(a) この回路を忠実に表す論理式を示せ。（7点）
(b) この回路のクリティカルパスの段数を答えよ。（7点）
A
B
解答 (a) 論理式
●
F
C
●
F＝（ A・（ B・C ））＋（ A ＋ C ）
(b) 解答(段数)
3 段
157
中間試験の解答
解答 (a) 真理値表
問５．次の関数 f(X,Y,Z) の最小積和形をカルノー図を
用いて求めたい。
f(X,Y,Z)＝ X・Y・Z ＋ X・Y ＋ X・Y・Z ＋ X・Y
(a) まず、真理値表を示せ。（7点）
(b) 次に、カルノー図を示せ。（7点）
(c) 主項は幾つあるか答えよ。（7点）
(d) 必須主項を全て挙げよ。（7点）
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
F
1
0
1
1
1
1
0
0
(e) 最小積和形論理式を示せ。（7点）
(b) 解答(カルノー図)
＼ XY
Z＼
00
0
1
1
0
01
1
1
11
0
0
(c) 解答(主項の数)
10
1
1
4
(d) 解答(必須主項)
X・Y ， X・Y
(e) 解答(最小積和形論理式)
f＝ X・Y ＋ X・Y ＋ X・Z
または
X・Y ＋ X・Y ＋ Y・Z
158
中間試験の解答
問６．次の関数 f(A,B,C,D) の最小積和形を
カルノー図を用いて求めたい。
f(A,B,C,D)＝ B・C・D ＋ A・C・D
＋A・B・C・D ＋ B・C・D ＋ A・C・D
（ただし、 B・C・D はドントケア）
(a) まず、カルノー図を示せ。（8点）
(b) 最小積和形論理式を示せ。（8点）
解答 (a) カルノー図
＼ AB
CD＼
00
01
11
10
00
0
1
1
0
01
0
0
1
11
0
0
1
10
1
1
1
0
解答 (b) 最小積和形論理式
f＝B・C＋B・D＋A・B・C
159
中間試験の結果（1/2）
中間試験得点分布
人
平均66.9点
14
12
10
8
6
4
2
0
＜30
30
40
単位取得への道は
険しいです。
今から心を入れ
替えてやり直しです。
50
60
70
理解できていない
部分や計算ミスが
多いです。
復習が必要です。
80
90
100
点
よく出来ました。
これからも頑張って
ついて来て下さい。
160
組合せ回路設計の実際
テクノロジマッピング

論理関数を指定された形式の論理回路として設計（合成）す
ることをテクノロジマッピングという

与えられた論理関数を対応する形式の論理式に変換すれば、
それから直ちに指定された形式の回路を得ることが出来る

論理式（論理関数形式）と対応する論理回路の関係は下表
論理関数形式
論理回路形式
使用論理ゲート
（1） AND／OR形式
（a）積和形
（b）和積形
AND／OR回路
AND－OR回路
OR－AND回路
NOT, AND, OR
（2） AND形式
（3） OR形式
AND回路
OR回路
NOT, AND
NOT, OR
（4） NAND形式
（5） NOR形式
NAND回路
NOR回路
NAND
NOR
161
組合せ回路設計の実際
AND／OR回路の空間最適化設計
 多段を許して空間最適化（多段論理最小化）した
AND／OR
回路は、ファクタリングやカルノー図を用いて多段論理最小化
した論理式を求めた後、次の手順の操作で得ることができる
1. 演算順序が最高の演算（＝最内側）から、より低い演算（＝
外側）へ順に次元番号をふる
2. 各演算を多入力ANDゲートか多入力ORゲートに合成し、1
で付けた次元番号に従って、入力側（最小次元）→出力側（最
大次元）の順にそれらを結線していく。
その際、変数の否定（リテラル）がある場合には、（それが演
算順位が一番高いので）入力（端子）の直後に NOTゲートを
挿入する
162
組合せ回路設計の実際
例題：
次の論理式に対応した AND／OR回路を合成せよ
ｆ＝（A・B＋A・B）・（C＋D）
解答：
演算順序を明示するため、次元番号をカッコ右下に付与すると
次のようになる
ｆ＝（（（A・B）1＋（A・B）1）2・（C＋D）2）3
故に、
論理回路は右図となる
A
B
1
2
C
D
1
3
2
f
163
組合せ回路設計の実際
多出力組合せ回路の最適化設計（空間最適化）

2本以上（n本）の出力 Oi （i＝1, ... , n）を持つ組合せ回路

対応する論理関数は fi（I1, ・・, Im）＝Oi （i＝1, ... , n）
論理最小化
I1
I1
Im
:
:
Im
:
f1
m入力
:
n出力
I1論理回路
Im
:
fn
O1
それぞれを論理最小化
することによって、
全体の最小化
をできるであろうか？
:論理最小化
On
164
組合せ回路設計の実際
 多出力組合せ回路の2段論理最小化設計（空間最適化）の手順
1. まず、各出力 Oi に対応する論理関数 fi の2段論理最小化
を行い、n個の最小積和形を得る
2. テクノロジマッピングによって、各々を AND／OR回路にする。
その際、論理関数（最小積和形）表現で同一の演算（NOT,
AND, OR）項は同一の論理ゲートを当てる（出力を共有する）
例： f1 ＝ X・Y＋Z・X
f2 ＝ X・Y＋Z・X
X
Y
Z
f1
f2
165
組合せ回路設計の実際
 多出力組合せ回路の多段論理最小化設計（空間最適化）も同様
1. まず、各出力 Oi に対応する論理関数 fi の多段論理最小化
を行い、n個の最小形を得る
2. テクノロジマッピングによって、各々を AND／OR回路にする。
その際、論理関数（最小積和形）表現で同一の演算（NOT,
AND, OR）項は同一の論理ゲートを当てる（出力を共有する）

ただし、最小の保証はない ... 何故か？
166
組合せ回路設計の実際
 多出力組合せ回路の多段論理最小化設計が困難な例
f1 ＝X・Z ＋ X・W＝X・（Z＋W）
f2 ＝X・Y ＋ X・Z ＋ Y・Z ＋ X・W ＋ Y・W
＝X・（Y＋Z＋W）＋Y・（Z＋W） ... （1）
＝X・（Z＋W）＋Y・（X＋Z＋W） ... （2）
f2 を（１）にファクタリングすれば、（Z＋W）を f1 と共有できるが、
（2）にファクタリングすれば共有項（共有ゲート）がない
167
組合せ回路設計の実際
NAND回路の設計
AND－OR回路からNAND回路に変換する
1. 最後段の ORゲートを等価な NANDゲートに変換する
2. 1の操作の際、変換した NANDゲートの入力に付けた NOT
は、前段の ANDゲートの出力位置に移動すればそれが
NANDゲートになる。
3. 最前段に必要な（入力の否定に対応する）NOTゲートは等価
な NANDゲートで置き換える
X
X
Y
Y
ｆ
ｆ

X
Y
ｆ
X
Y
ｆ
168
組合せ回路設計の実際
NAND回路の設計
AND／OR回路からNAND回路に変換する
1. 最後段のゲートを等価な NANDゲートに変換する
2. 1の操作の際、変換した NANDゲートの入力に付けた NOT
は、前段のゲートの出力位置に移動した上で、それを等価な
NANDゲートに変換する。
3. 2の操作を最前段のゲートまで繰り返し行う。

169
組合せ回路設計の実際
演習：
解答：
下図のAND／OR回路を NAND回路に変換せよ
X
Y
ｆ
Z
W
ｆ
Z
W
X
Y
Z
W
X
Y
X
Y
ｆ
ｆ
Z
W
170
組合せ回路設計の実際
多出力NAND回路の設計

AND／OR回路からNAND回路に変換する際、変換した
NANDゲートの入力に付けた NOTは、前段のゲートの出力
位置に移動するが、その主力が共有されている場合、その
NOTは共有先にも配置しなくてはならない
例：
NOR回路の設計

OR－AND回路からNOR回路に変換する操作は、
AND－OR回路からNAND回路に変換する操作と双対

AND／OR回路からNOR回路に変換する操作も、上記の
NAND回路への変換と同様
171
組合せ回路設計の実例
マルチプレクサ（multiplexer）
selector ともいう
 通常 2k-to-1マルチプレクサ

例：
4／
2-to-1マルチプレクサ
（2-to-1 MUX）
A1
S
束線表示
B1 A2
●
●
A4
B2
●
●
●
●
A1～4
B4
4／
●
●
S
●
●
=
B1～4
4／
S 2-to-1 MUX
●
4／
Z1
Z2
Z4
Z1～4
172
組合せ回路設計の実例
例：
4-to-1マルチプレクサ
（4-to-1 MUX）
 演習：
真理値表
ではない！
機能定義表
S1 S0 Z
0 0 A
0 1 B
1 0 C
1 1 D
右表の機能を持つ
4-to-1マルチプレクサ（1ビット）
のAND／OR回路を設計せよ
 解答：論理関数は、
Z ＝ S1・S0・A＋S1・S0・B＋S1・S0・C＋S1・S0・D
故に、右図となる
A
B C
D
S1
●
●
●
●
●
S0
●
これでもOK
A
B C
D
S1 ●
●
S0
●
●
●
●
Z
173
組合せ回路設計の実例
 2k-to-1
マルチプレクサ（nビット）
2k
n／
k
／
S
●
●
●
n／
2k-to-1 MUX
n／
174
組合せ回路設計の実例

演習： 4-to-1マルチプレクサ（1ビット） 2個と 2-to-1マルチプレ
クサ（1ビット）1個使って 8-to-1マルチプレクサ（1ビット）を設計
せよ。（データ入力：A～H, 選択制御信号を S0, S1, S2 とする）

解答：
S0
S1
S2
A B C D
E F G H
S0
S1 4-to-1 MUX
S0
S1 4-to-1 MUX
●
●
S
2-to-1 MUX
8-to-1 MUX
175
組合せ回路設計の実例
デコーダ（decoder）
デマルチプレクサ
n本の信号を2進数列の
コードと見なし、それに対応
する単一出力（2n本のデー
タ出力のうち1本だけ「1」と
し、他を「0」とする）を生成
するものを n×m（＝2n）デ
コーダという
2×4デコーダの機能定義表
D1 D0
0 0
0 1
1 0
1 1
Q3
0
0
0
1
Q2
0
0
1
0
Q1
0
1
0
0
Q0
1
0
0
0
（demultiplexer）
n本の選択制御線によって、
2n本のデータ出力のうちから
対応する1本を選んで、それだ
けに1本の入力データを分配
（接続）するものを 1×m（＝
2n）デマルチプレクサという
1×4デマルチプレクサの機能定義表
S1 S0
0 0
0 1
1 0
1 1
Q3
0
0
0
D
Q2 Q 1
0 0
0 D
D 0
0 0
Q0
D
0
0
0
176
組合せ回路設計の実例
演習：

演習：
前頁の機能定義表に対応
する 2×4デコーダを設計
せよ

前頁の機能定義表に対応
する 1×4デマルチプレクサ
を設計せよ
解答：
解答：
D
D1
D0
●
●
●
●
●
●
Q0
Q1
Q2
●
S1
S0
Q3
●
●
●
Q3
●
●
●
●
●
Q0
Q1
Q2
177
組合せ回路設計の実例
エンコーダ（encoder）
プライオリティエンコーダ
（priority encoder）
m本の信号の内、1つだけ
「1」となり、「1」となった入
力に対応する「n本の出力
の組（コード）」を生成する
m（＝2n）×nエンコーダと
いう
4×2エンコーダの機能定義表
D3 D2 D1 D0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
（上記以外）
Q1
0
0
1
1
－
Q0
0
1
0
1
－
m本の信号の内、優先度の高
い信号の「1」に対応する「n本
の出力の組（コード）」を生成
する
 優先度付きエンコーダともいう

4×2優先度付きエンコーダの機能定義表
D3 D2 D1 D0
0 0 0 1
0 0 1 －
0 1 －－
1 －－－
0 0 0 0
Q1
0
0
1
1
－
Q0
0
1
0
1
－
178
組合せ回路設計の実例
演習：
Q1
前頁の機能定義表に対応する
4×2優先度付きエンコーダを
設計せよ
解答：カルノー図は右図となる
ので、論理関数は、
Q1 ＝ D3＋D2
Q0 ＝ D3＋D2 ・D1
故に、論理回路は下図

D1
●
D3
Q0
●
D2
D3D2
D1D0
00
00
01
11
10
－
0
0
0
01
1
1
1
1
11
1
1
1
1
10
1
1
1
1
11
1
1
1
1
10
1
1
1
1
Q0
D3D2
D1D0
00
00
01
11
10
－
0
1
1
01
0
0
0
0
Q1
179
(用語解説)
 fan-in
 1ゲートへの入力
信号数
 通常、ゲートごと
に上限あり
例： fan-in = 4
 fan-out
1ゲートからの出力
信号数
やはり、ゲートごとに
上限あり
例：
●
●
●
fan-out = 4
180
組合せ回路設計の実例
演習：

下図の
4×1マルチプレクサを
fan-out ≦2, fan-in≦2
のAND／OR回路に変
更せよ
S1
S0
●
A
B
●
C
解答：
A
S1
S0
B
●
C
D
●
●
●
●
●
D
●
●
●
●
Z
Z
181
論理回路および論理設計
2011年度（第10回）
中島克人
情報メディア学科
[email protected]
組合せ回路設計の実例

半加算器（HA: Half Adder）
A
0
0
1
1

B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
A
2進数1ビット
の加算
A
+ B
CS
B
HA
C S
S : 和（Sum）
C : 桁上げ
（Carry）
全加算器（FA: Full Adder）
A
0
0
1
1
B
0
1
0
1
Ci S
0 0
0 1
0 1
0 0
Co
0
0
0
1
A
0
0
1
1
B
0
1
0
1
Ci S
1 1
1 0
1 0
1 1
Co
0
1
1
1
2進数1ビット
（途中桁）
の加算
‥ Ai
+ ‥ Bi
Co Ci
‥ Si
Ai-1
Bi-1
‥
‥
Ci : Carry-in
S : 和（Sum）
Co : Carry-out
A
B Ci
FA
Co S
183
組合せ回路設計の実例
演習：


演習：
半加算器の論理回路を
AND／OR回路で設計
せよ
解答：
A

B
●
半加算器の論理回路を
AND, OR, NOT, XOR
ゲートで設計せよ A B
●
S
0
0
1
1
解答：
A
●
●
C

B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
●
●
C
S
184
組合せ回路設計の実例
演習：


演習：
全加算器の論理回路を
AND／OR回路で設計
せよ
解答：
A

B
Ci
●
●
●
Co

●
●
●
●
解答：
A
●
●
●
全加算器の論理回路を
AND, OR, NOT, XOR
ゲートで設計せよ
●
S
B
Ci
●
●
●
Co
●
●
S
185
組合せ回路設計の実例

全加算器（1ビット）をカスケード（＝縦つなぎ）
接続して構成した n ビット加算器
An-1
Bn-1
A1
B1
A0
B0 Ci
・・・
A
B Ci
FA
Co S
Co
A
・・・
Sn-1
nビット加算器

B Ci
FA
Co S
Co
S1
A
B Ci
FA
Co S
S0
2ビット加算器
空間サイズは良いが、時間サイズはビット数に比例して悪くなる
⇒ 桁上げ予見回路の付加（コンピュータアーキテクチャ）
186
組合せ回路設計の実例
多数決回路
n入力の内の過半数が1の場合に出力を1とする回路
C
0
1
0
1
0
1
0
1
M
0
0
0
1
0
1
1
1
解答：カルノー図から求めた関数は下記
C＼AB 0 0
0
0
1
0
01
0
1
11
1
1
10
0
1
M ＝ A・B＋A・C＋B・C
従って、AND／OR回路は下記
A
B
M
C
●
B
0
0
1
1
0
0
1
1

●
A
0
0
0
0
1
1
1
1
演習： AND／OR回路を設計せよ
●
多数決関数（3入力）

187
組合せ回路設計の実例
重み付き多数決回路
入力によって重みが異なる多数決回路
重み付き多数決回路の例


4入力の内、Aは 4票、Bは 3票、
Cは 2票、Dは 1票を持つ
延べ10票の内、5票以上が
賛成（＝1）の場合、
出力Mを賛成（＝1）とする
 演習：
真理値表を示せ
 解答：
右図
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 M
0 0
1 0
0 0
1 0
0 0
1 0
0 1
1 1
0 0
1 1
0 1
1 1
0 1
1 1
0 1
1 1
188
組合せ回路設計の実例
演習：
例題2.26の重み付き多数決関数に対し、
カルノー図によってその関数を求め、
ファクタリングによって多段論理最小化を行い、
その結果に対応するAND／OR回路を設計せよ
⇒ 教科書p.142～p.144を自習せよ
189
同期式順序回路とその設計
組合せ回路
 入力値のみで出力値が決まる
順序回路
 順序回路とは組合せ回路に
状態保存のためのメモリ
（memory）を付加した論理
回路である
 クロックで状態を遷移させる
（変更する）
 同一クロックで一斉に状態遷
移させる回路が同期式順序
回路（cf. 非同期式）
入力
：
入力
：
組合せ回路
組合せ回路
：
：
出力
：
出力
：
：
メモリ
：
クロック
190
同期式順序回路とその設計
定義3.1（状態）
論理回路の入力が時間経過と共に変化しても構わないとき、
その入力（変化）の履歴を状態という
定義3.2（順序回路）
ある時刻（タイミング（timing））
t の出力がその時刻 t の入力
と状態（＝入力履歴）に依存する論理回路を順序回路という
ビットタイム（bit
time）
今扱っているのはデジタル情報であるので、一定周期（時間間
隔）の時刻ごとに出力と状態（の変化）を考えればよい
この一定周期をビットタイムという
（前）（現）（次）
時間
‥‥ t-1
ビットタイム
t t+1 t+2 ‥‥
時刻
191
同期式順序回路とその設計
クロック（clock）
入力
ビットタイムを刻むタイミ
ング信号をクロックという
（クロックによりビットタイ
ムが経過）
：
：
組合せ回路
：
出力
：
：
メモリ
：
クロック
時間
ビットタイム ‥ t-1
t
t+1 t+2 ‥‥
定義3.3（同期式順序回路）
回路動作がクロックに同期する順序回路
同期式順序回路では、クロックごとにメモリに保存している状
態が変わり得る（状態遷移し得る）。
以降、単に順序回路というと、同期式順序回路の事をいうこと
にする
192
同期式順序回路とその設計
状態遷移

連続する2つのビットタイムにおける状態の変化
同期
クロックは、入力と出力と状態遷移のそれぞれをチェックする
タイミング合わせの信号であるが、このタイミング合わせの事
を同期という
定義3.3（同期式順序回路）
回路動作がクロックに同期する
順序回路
同期式順序回路では、クロックごとにメモリに保存している
状態が変わり得る（状態遷移し得る）。
以降、単に順序回路というと、同期式順序回路の事をいうこと
にする
193
同期式順序回路とその設計
順序回路の論理関数表現（準備）
以降の表記法
 ある時刻（ビットタイム）
t の状態（現状態） Q（t）を Q と
表すとき、次の時刻（ビットタイム） t+1 の状態（次状態）
Q（t+1）を Q+ と表記する
 入力（の組）は I、出力（の組）は O と表す
定義3.4（状態遷移関数）
Q+は入力（の組） I と現状態 Qに
よって決定する。即ち、次状態は、入力と現状態を変数とする
論理関数の値（関数値）として、
Q+＝f（Q, I）
と表せる。この論理関数 f を状態遷移関数という
順序回路において、次状態
194
同期式順序回路とその設計
定義3.5（順序回路の出力関数）
順序回路において、出力（の組）
O も入力（の組） I と現状
態 Q によって決定する
即ち、順序回路の出力は、入力と現状態を変数とする論理
関数の値（関数値）として、
O＝g（Q, I）
と表せる。この論理関数 g を出力関数という
組合せ回路では「状態」がなく、出力関数は
O＝h（I）である
195
同期式順序回路とその設計
順序回路の論理関数表現
順序回路では、
状態遷移関数 Q+＝f（Q, I）、出力関数 O＝g（Q, I）
の両方を対にして論理関数表現される
入力
I
組合せ回路
：
：
g
：
出力
O
：
f
組合せ回路
：
：
g
：
：
f
Q+
：
メモリ Q
：
ビットタイム t
1ビットタイム後
：
メモリ Q+
：
ビットタイム t＋1
196
同期式順序回路とその設計
順序回路の一般形
m本の入力、lビットのメモリ、n本の出力を持つ順序回路は
状態遷移関数 fk（Q1, ... ,Ql, I1, ... ,Im）＝Q+k （k＝1, ... ,l）
出力関数
gj（Q1, ... ,Ql, I1, ... ,Im）＝Oj （j＝1, ... ,n）
で表される
I1
入力 m本
Ii
Im
：
：
lビットのメモリ
Qk→Q+k
Q+k＝fk（Q, I）
（k＝1, ... ,l）
：
：
O1
Oj
出力 n本
On
なお、Qk→Q+k
は Qk の状態遷移を表す
また、lビットのメモリであるので、2l個の状態を表現できる
197
同期式順序回路とその設計
ミーリマシン（Mealy
machine）
現状態と入力とで出力が決まる順序回路で、
出力関数
入力
I
O＝g（Q, I）
組合せ回路
：
：
g
：
出力
O
：
f
Q+
：
メモリ Q
：
以後、特に断りがなければ、ミーリマシンを扱う
198
同期式順序回路とその設計
ムーアマシン（Moore
machine）
現状態だけで出力が決まり、入力は出力には無関係である
る順序回路で、
出力関数 O＝g（Q）
組合せ回路
：
入力
I
：
g
出力
O
組合せ回路
：
●
：
：
f
●
Q+
：
メモリ Q
：
199
同期式順序回路とその設計
順序回路の数学モデル
有限個の状態を持ち、その上で状態遷移規則を定義した計
算機構を有限状態機械という
有限状態機械は、「有限個の状態と状態遷移（状態遷移関
数）を扱う模式的な機械、即ち、数学モデル」といえる
200
同期式順序回路とその設計
定義3.6（有限オートマトン）
有限個の状態、有限個の入力、状態遷移関数、初期状態、
最終状態の5項によって定義する計算機械（数学モデル）を
有限オートマトンという
入力
入力
I
組合せ回路
：
：
：
f
Q+
状態遷移関数
：
メモリ Q
初期状態
＝メモリの初期内容
：
最終状態
＝状態遷移後の内容
状態＝メモリ
201
同期式順序回路とその設計
定義3.7（順序機械）
有限オートマトンを定義する5項の内、最終状態を出力に置
き換え、新たに出力関数を加えた6項で定義する計算機械
（数学モデル）を順序機械という
入力
入力
I
出力関数
状態遷移関数
組合せ回路
：
：
g
：
出力
O
：
f
出力
Q+
：
メモリ Q
初期状態
＝メモリの初期内容
：
状態＝メモリ
202
同期式順序回路とその設計
フリップフロップ（Flip-flop:FF）（1ビットのメモリ）の仕組み
S
双安定（2状態）
... 状態変化（入力）がない
R
●
NOTをNORに
●
Q

Q
●
2個のNOTによるループ
●

Q
NOR型SR-FF
S=R=0 のとき双安定（2状態）
S=0→1→0 とすると
Q=?→1→1 となる（Set）
R=0→1→0 とすると
Q=?→0→0 となる（Reset）
203
同期式順序回路とその設計

SRフリップフロップ（SR-FF）
最も簡単なフリップフロップ回路
 セット（S）とリセット（R）の機能を持つ

SRフリップフロップの
回路図記号
S
R
Q
Q
SRフリップフロップの
特性表
Qの次状態
S R
Q+
0
0
1
1
Q
0
1
－
0
1
0
1
不変
リセット
セット
（ドントケア＝不定）
204
同期式順序回路とその設計
（クロック入力無し）SR-FF
S
R
●
AND／OR回路構成
Q
●

Q
SR-FFの特性表
R
●
S
●
NOR型 SR-FF
NAND型SR-FF
Q
Q
S R
Q+
0
0
1
1
Q
0
1
－
0
1
0
1
不変
リセット
セット
（ドントケア＝不定）
演習
S, R, Q に 0, 1 の値を当て
はめて、左記回路の動作を確
認せよ

205
同期式順序回路とその設計
クロック入力付きSR-FF
同期式順序回路ではクロックで
（1）入力の取り込み、（2）状態遷移、（3）出力の決定
の3つを行う
そのためには、クロック信号が“1”の時だけ（1）を行い、“0”の
時は現状態を保持するようにすれば良い
⇒入力にクロックとのANDゲートを挿入する
AND／OR回路構成
●
Q
●
S
（クロック入力付き）
SRフリップフロップ
Q
S
R
CK
●
R
クロック
CK
Q
Q
206
同期式順序回路とその設計

Dフリップフロップ（D-FF）
現状態が何であっても D入力を次状態とする
 データ信号（D入力）の取り込み・保存（ラッチ（latch））を
行うため、Dラッチ、もしくは、単にラッチとも言う
 コンピュータの最も基本的な部品である
特性表
D
Q
CK
Q
D
0
1
Q+
0
1
D
●
●
CK
●
回路図記号
Q
●

Q
SR-FF
207
同期式順序回路とその設計

T フリップフロップ（T-FF）
T入力が “0” の時、現状態は不変である
 T入力が “1” の時、現状態の否定（NOT）を次状態とする
 現状態の否定が次状態になることを反転あるいはトグル
（toggle）という

回路図記号
T
CK
特性表
Q
T
Q+
Q
0
1
Q
Q
208
同期式順序回路とその設計

（クロック入力無し／入力付き）JK フリップフロップ（JK-FF）
 J、K入力共 “0” の時、現状態は不変である
 J入力が “0”、K入力が “1” の時、リセットされる
 J入力が “1”、K入力が “0” の時、セットされる
 J、K入力共 “1” の時、現状態を反転（トグル）する
回路図記号
J
Q
K
Q
J
Q
K
CK
JKフリップフロップの
特性表
Q
J K
Q+
0
0
1
1
Q
0
1
Q
0
1
0
1
SRフリップフロップ
と同じ
不変
Tフリップフロッ
リセット
プの機能
セット
反転（トグル）
209
同期式順序回路とその設計

定義3.9（入力要求）

フリップフロップの現状態 Q がある状態 Q+ へ遷移するため
に、入力をどのように設定すればよいかを示すことを入力要
求という

入力要求を論理関数（論理式）として表現したものを
入力条件式、入力方程式、あるいは、励起関数という

入力要求を真理値表として表現するものを
入力要求表、逆真理値表、あるいは、励起表という
SRフリップフロップの
入力要求表
Q → Q+ S R
0
0
0 －
0
1
1 0
1
0
0 1
1
1 － 0
不変またはリセット
セット
リセット
不変またはセット
210
同期式順序回路とその設計

FFの特性表（～真理値表）と入力要求表（＝逆真理値表）

SRフリップフロップでの比較
入力要求
入力
特性表
S
0
0
1
1
R
0
1
0
1
Q+
Q
0
1
－
結果
不変
リセット
セット
（不定）
結果
入力要求表
Q → Q+
0
0
0
1
1
0
1
1
S R
0 －
1 0
0 1
－ 0
211
同期式順序回路とその設計

演習：下記のTフリップフロップの特性表から入力要求
表を作成せよ
特性表
T
0
1
Q+
Q
Q

解答：特性表が分かり難い場合は、
展開特性表を作成してから入力要
求表を作成すると良い
展開特性表
T
0
0
1
1
Q
0
1
0
1
Q+
0
1
1
0
不変
不変
反転
反転
入力要求表
Q → Q+
0
0
0
1
1
0
1
1
T
0
1
1
0
212
期末試験の注意
試験日時：
12月16日（金） 6限（年内最後の授業日）
持込み可：
教科書、講義プリント、ノート
持込み不可：
試験用紙：
あらゆる電子機器（PC, 電卓, 携帯...）、
問題用紙、解答用紙を配布
コツ！：中間試験と同様問題が多めに出題される
持込み可であるが、その場で調べながらやっても
絶対に時間不足になる
（1）事前に練習、（2）出来る問題から解く
213
論理回路および論理設計
2011年度（第11回（最終回））
中島克人
情報メディア学科
[email protected]
期末試験
試験日時：
12月16日（金）（年内最後の授業日）
18:20～19:40
持込み可：
教科書、講義プリント、ノート
持込み不可：
試験用紙：
あらゆる電子機器（PC, 電卓, 携帯...）、
問題用紙，解答用紙共に回収します
コツ！：出来る問題から慎重かつ素早く解く
215
同期式順序回路とその設計
タイミングチャート
時間経過と共に（入力、出力を含む）各信号の論理値の遷移を
図示する方法
横軸：時間（1目盛＝1ビットタイム）
縦軸：論理値（ここでは上位＝“1”, 下位＝“0”）
nビットシフトレジスタのタイミングチャート例
Dはこの場合、
「クロックCKに非同期」
という
D
Q1
Q2
CK
1ビットタイム
時間
216
同期式順序回路とその設計
状態遷移図
順序回路のクロックごとの動作を定める入力、状態（遷移）、
出力を図に表したもの
ミーリマシンの場合
状態
ムーアマシンの場合
状態
出力
入力／出力
入力
状態
状態
出力
例：D-FFの（ミーリマシンとして表現した）状態遷移図
D=1／Q+=1
0／0
Q=0
0／0
Q=1
1／1
217
同期式順序回路とその設計
演習：
次の機能を持つ順序回路を設計したい
a. 40円の商品（1種類）を販売する自動販売機である
b. 10円玉と50円玉のみを受付る
c. 40円以上になると即座に商品とお釣りを出し，0円状態に戻る
40円以上
上記の回路の状態遷移図を（ミーリマシンとして）示せ
解答：
（1）状態遷移図は左図
10
50
10円
10
20円
10
50
X
20
＝ 10円玉
＝商品
＝ 50円玉
＝釣銭X円
50
30
0円
30円
50
50
10
40
10
10
218
同期式順序回路とその設計
演習：T-FFの（ミーリマシンとして表現した）状態遷移図を示せ
解答：下図の通り
Ｔ= 1／Q+= 1
0／0
Q=0
Q=1
0／1
1／0
219
同期式順序回路とその設計
演習：初期状態から入力値に「1」が合計3回入ると「1」を
出力し、初期状態に戻る順序回路の状態遷移図を示せ
解答：下図の通り
0／0
1／0
Q=00
1／1
Q=01
Q=10
0／0
1／0
0／0
220
同期式順序回路とその設計
 演習：入力Aの論理値が反転する時に出力Mが「1」を出力する
「ビット反転検出回路」の状態遷移図を示せ
解答：状態遷移図
1／1
0／0
Q=0
0／1
Q=1
1／0
 演習：この回路への入力Aがタイミングチャート上で下記である時
の出力Mのチャートを示せ
解答：タイミングチャート
入力A
0
0
1
1
0
1
0
出力M
0
0
1
0
1
1
1
CK
221
ソフトウェアによる論理設計
コンピュータハードウェア設計の流れ
（1）方式設計
コンピュータのハードウェア構成の概略（機能ブロック）を決定
ハードウェア機構とソフトウェア機能との機能分担方式（＝コン
ピュータアーキテクチャ）を設計することに当たる
（２）論理設計
（1）で決めたハードウェア機構を論理回路として合成
（３）実装設計
（2）で合成した論理回路の実装部品へのテクノロジマッピング
機能・構成
決定
機能ブロック
分割
（1）方式設計
論理関数
標準形
論理式
（2）論理設計
論理
最小化
テクノロジ
マッピング
（3）実装設計
222
ソフトウェアによる論理設計
コンピュータによるハードウェア設計支援
CAD（Computer
Aided Design）
 論理回路の合成や最小化
 論理ゲート／ブロック間の配線経路探索
 設計した回路の検証のためのシミュレーション（ソフトウエアによる模
擬）やテストパターン生成
機能・構成
決定
機能ブロック
分割
（1）方式設計
論理関数
標準形
論理式
（2）論理設計
論理
最小化
テクノロジ
テスト
マッピング
（3）実装設計
 方式設計をプログラミングのように行えれば、方式設計の能率も向
上するし、論理設計以降の下流にスムーズに繋げられる
223
ソフトウェアによる論理設計
ハードウェア記述言語
論理回路やハードウェアの動作をプログラムとして記述す
るプログラミング言語をハードウェア記述言語（HDL：
Hardware Description Language）という
具体的には、論理回路やハードウェアの動作を回路図で
はなく、方式設計した後のプログラムとして与えると、CAD
システムが自動的にそれを最適化し、論理回路を合成して
くれる機能である
回路動作をビヘイビア（behavior）というので、HDLの事を
ビヘイビア記述言語とも言う
224
ソフトウェアによる論理設計
HDLでの記述例（半加算器）
VHDL
library ieee;
use ieee.std_logic_1164.all;
entity half_adder is
port (
a, b: in std_logic;
s, co: out std_logic);
end half_adder;
VerilogHDL
module half_adder (s, co, a, b);
input a, b;
output s, co;
wire w0, w1, w2;
assign w0 = a & b,
w1 = w0,
w2 = a | b,
architecture arch of half_addrer is
s = w1 & w2,
signal w0, w1, w2: std_logic;
co = w0;
begin
endmodule
w0 <= a and b;
...........
225
HDL
HDLの生い立ち
VHDL



設計仕様のドキュメント言語として米国国防省（DoD：
Department of Defense）のプロジェクトで‘81に提案
‘83年から標準化作業 ⇒ IEEE-1076（‘87）, IEEE-1164（‘92）
あいまいさを排除した厳格な言語（ADA言語ベース）
Verilog-HDL



Gateway社の Verilog-XLシミュレータ専用言語として‘83に
開発
‘89にGateway社を買収した Cadence社が言語仕様を公開
し、やがて IEEE-1364 として標準化
LSI設計における記述性を重視した言語（C言語ベース）
226
VHDL
下図の回路をテキスト（言語）で記述したい
この回路に名前をつける（entity）
a
b
c
x
入出力の信号の名前と、属性や
取り得る値を宣言する（port）
回路の中の構成を記述する（architecture）
上図の回路を部品として用いた回路を記述したい
a
b
●
k
s
部品（component）として呼び出す
x
z
c
p
●
g
a
b
c
x
部品内外の信号線の対応を
記述する（port map）
227
VHDL
構文
entity ... 1つの設計単位を表し、回路名と外部インタ
フェースを定義する
別途 architecture 宣言で内部を定義する
entity エンティティ名 is
< generic （ジェネリック宣言）>
< port （ポート宣言）>
end <エンティティ名>
port ... 外部インタフェース
の宣言
（generic .. 省略）
port
入出力を
宣言する
entity
回路ブロックに
名前をつける
エンティティ名
1つの設計単位＝回路ブロック
228
VHDL
port ... ポート宣言
port （
< ポート名：モードポートタイプ
｛ ; ポート名：モードポートタイプ｝ >
）;
port の種類
in ... entity への入力, out ... entity からの出力
buffer ... entity からの出力（ entity内部でも使用）
inout ... entity との双方向
entity内部
in
●
inout
●
●
buffer
out
229
VHDL
構文
entity
architecture 1
... 動作レベル記述
architecture 2
... RTLレベル記述
architecture 3
... ゲートレベル記述
architecture ... entity内部の回路構成や動作を定義
記述レベルごとにアーキテクチャ名を
付して、複数定義可能
architecture アーキテクチャ名 of エンティティ名 is
｛アーキテクチャ宣言部
:= 信号宣言、定数宣言、コポーネント宣言、
データタイプ宣言、サブプログラム｝
begin
｛同時処理文
:= 信号代入文、プロセス文、コンポーネント呼出、
並行プロシージャ、等｝
end <アーキテクチャ名>
230
VHDL
記述例：HA（半加算器）
A
B
B
HA
S
Co
S
Co
入力ポート
A
●
必ず宣言
A
S
●
出力ポート
library ieee;
Co
use ieee.std_logic_1164.all;
B
entity HA is
port （ A, B : in std_logic;
S, Co : out std_logic ）;
外部インタフェースを記述
end HA;
architecture RTL of HA is
begin
S <= A xor B;
Co <= A and B;
end;
データタイプに相当
内部の論理を記述
231
VHDL
 記述例：FA（全加算器）
library ieee;
use ieee.std_logic_1164.all;
entity FA is
port （ A, B, Ci : in std_logic;
S, Co : out std_logic ）;
end FA;
architecture RTL of FA is
component HA
port （ A, B : in std_logic;
S, Co : out std_logic ）;
end component;
signal S0, S1, Co1, Co0 : std_logic;
begin
HA0: HA port map （ A, B, S0, Co0 ）;
HA1: HA port map （ S0, Ci, S1, Co1 ）;
S <= S1;
Co <= Co0 or Co1;
end;
A
B
Ci
A
B FA S
Co
Ci
A
A
B
B
A
Ci
B
HA
S
Co
S
Co
HA
S
Co
S
Co
HAを部品として呼び出す
（使う）ための宣言
HAの呼び出し
（）内は外側に接続する信号名
232
VHDL
Din
4
／
D
Q
4
／
Qout
D-FF
例：4ビットレジスタ
となる時に reset = 1
であると，Dinの値に関わらず
内容Q が 0 にリセットされる
タイプ
 CLK=1
CLK
>C
R
reset
reset機能付
0/1 の1ビット線
entity REG4 is
降順の4ビット線
port （ reset : in std_logic ;
CLK : in std_logic ;
Din : in std_logic_vector（3 downto 0）;
Qout : out std_logic_vector（3 downto 0））;
end REG4;
233
VHDL
例：4ビットレジスタ（続）
Register Transfer Level
（RTL）の記述
architecture RTL of REG4 is
もし CLK が変化し、
begin
かつその値が 1 ならば
REG: process（CLK）
＝ CLK の立ち上がり時
begin
if CLK’event and CLK=‘1’ then
クロック同期の
if reset = ‘1’ then Qout <= 0;
reset
else
Qout <= Din;
（通常の）
end if;
データセット
end if;
end process;
end RTL;
234
本講義の最後に
 3年次（前期）
「コンピュータアーキテクチャ」（選択）
（担当：尾崎（非常勤））
にて、論理回路の知識を前提に，コンピュータの内部の
「様々な仕組み・巧妙な作り」を学べます
 4年次（前期）
「デジタルシステム設計・実装論」（選択）
（担当：竜田）
にて、論理設計に必要な実際的な技術を学べます
235
（終わり）
授業評価をお願いします
236
論理回路および論理設計
2011年度（期末試験）
中島克人
情報メディア学科
[email protected]
期末試験
試験日時：
12月16日（金）
18:20～19:40
持込み可：
教科書、講義プリント、ノート
持込み不可：
試験用紙：
あらゆる電子機器（PC, 電卓, 携帯...）、
問題用紙，解答用紙共に回収します
コツ！：出来る問題から慎重かつ素早く解く
238
論理関数と論理回路の最小化
 Q-M法による
2段論理最小化の特徴
長所：


数値化が簡単で、コンピュータ処理に向く
即ち、多変数論理関数にも適用可
短所：


手順が少々面倒（特に主項の選択操作が手間）
カルノー図に比し、人間が行う最適化としては直感性で
劣る
主項の選択を正確に行いたい
必須主項の決定と主項の選択」に代えて、論
理数学を用いた方法を適用する
 Q-M法の「2.
239
論理関数と論理回路の最小化
論理数学の活用
 道具・材料を持ち寄りで，グループでバーベキューに行きたい
 メンバごとに持ち寄れるものが異なる
 アイテム（道具・材料）が全部揃うには誰と誰が参加すべきか？
S4＝ p＋q
S9＝ q＋r
メンバ別
バーベキュー道具・材料
持ち寄り可能
アイテム
1 m21 m
32 m
43 m
54 m
6 5 m76 m
87 m98 m9
メンバ p
○ ○
メンバ q
○
○
メンバ r
○
○
メンバ s ○ ○
○
○
メンバ t
○ ○ ○ ○
m1 : 鉄板
m2 : 網
m3 : コンロ
m4 : 燃料
：：：：
m9 : 肉
m8 : 油
Si ：アイテムi が揃うために参加すべきメンバ
アイテムが全部揃うための条件 U = S1・S2・ … ・S9
= ｓ・s・p・（p＋q）・ … ・（q＋r）
240
論理関数と論理回路の最小化
定理2.6（ある最小項の包含条件）

n個の最小項からなる最小積和形の論理関数 fm において、
ある最小項 mi （i＝1, ... , n）を包含する主項全ての論理和を
Si とすると、 fm のある論理積項が最小項 mi を包含する条
件 Ui は Si＝ 1 である

証明： Si は、最小項 mi を包含する主項(論理積項）全ての論
理和であるから、Si＝ 1 ならば、それらの主項のいずれかが
mi を包含する
例： n＝９個の最小項から
なる論理関数の
主項－最小項表
S4＝ p＋q
S6＝ s＋t
最小項（ラベル）
m1 m2 m3 m4 m5 m6 m7 m8 m9
主項（ラベル） 1 3 4 6 8 9 10 11 14
4,6 p
○ ○
6,14 q
○
○
10,14 r
○
○
1,3,9,11 s ○ ○
○
○
8,9,10,11 t
○ ○ ○ ○
主項－
最小項表
241
論理関数と論理回路の最小化
定理2.7（全ての最小項の包含条件）

最小積和形 fm の論理積項が n個の最小項を全て包含する
条件は、 U ＝ S1・S2・ ‥ ・Si・ ‥ ・Sn ＝ 1 である

証明：定理2.6より、最小項 mi （i＝1, ... , n）を包含する条件
は Si＝ 1 であり、それらが同時に成り立つ条件（U）は
S1・S2・ ‥ ・Si・ ‥ ・Sn ＝ 1 である
最小積和形 fm
の正確な求め方
1. 条件 U を展開して、積和形とする
2. 1のうちから主項数が最小の論理積項を選択する
3. 2を構成する主項を OR で結ぶ
（この方法では「必須主項の決定」や「主項の選択」が必要ない）
242
論理関数と論理回路の最小化
 条件
U を展開して主項を選択する例
最小項（ラベル）
m1 m2 m3 m4 m5 m6 m7 m8 m9
主項（ラベル） 1 3 4 6 8 9 10 11 14
4,6 p
○ ○
6,14 q
○
○
10,14 r
○
○
1,3,9,11 s ○ ○
○
○
8,9,10,11 t
○ ○ ○ ○
主項－
最小項表
S4＝ p＋q
S6＝ s＋t
A
0
－
1
－
1
B C D
1 － 0
1 1 0
－ 1 0
0 － 1
0 －－
U ＝ S1・S2・ ‥‥ ・S9
＝ s・s・p・（p＋q）・t・（s＋t）・（r＋t）・（s＋t）・（q＋r）
＝ s・p・t・（q＋r）＝ p・q・s・t ＋ p・r・s・t
従って、最小積和形 fm は、
fm＝A・B・D ＋ B・C・D ＋ B・D ＋ A・B
または、 fm＝A・B・D ＋ A・C・D ＋ B・D ＋ A・B
論理積項
A・B・D
B・C・D
A・C・D
B・D
A・B
243