組合せ論理回路の設計 - Yukihiro Iguchi,

スイッチング理論と論理設計
明治大学理工学部情報科学科
井口幸洋
[email protected]
2015/9/30
1
スイッチング理論と論理設計I
自己紹介
• 明治大学理工学部情報科学科助教授
• 専門：
– リコンフィギャブル・アーキテクチャ
（再構成可能アーキテクチャ）
– メモリのテスティングに関する研究
– 論理関数の表現法に関する研究
– ハードウェアの設計
– 雑談をするコンピュータ・システム
• 担当科目：論理設計，Ｃ言語，
コンピュータ設計実習
2015/9/30
2
スイッチング理論と論理設計I
講義の目的
• ディジタル回路の基礎
• スイッチング理論
– 論理関数の表現方法
– 論理式の簡単化
• ハードウェア記述言語を用いた論理設計
– Verilog-HDL
– C言語
2015/9/30
3
スイッチング理論と論理設計I
今回の目的
• 論理素子
• 論理関数の表現法
–
–
–
–
–
真理値表
論理和形
リードマラー標準形
多段論理回路
ＢＤＤ（binary decision diagram)
2015/9/30
4
スイッチング理論と論理設計I
ミニテスト１．常識は？
• 乾電池の電圧は？答：１．５
• 壁のコンセントに来ている電源の
[V]
– 電圧は？答：１００
[V]
– 交流ですか？直流ですか？答：交流
• パソコンの心臓部マイクロプロセッサにはトラン
ジスタが何個位入っていると思いますか？
数千，数万，数十万，数百万，数千万，数億？
答：数百万～数千万
2015/9/30
学籍番号
氏名
スイッチング理論と論理設計I
5
VLSIとスイッチ回路
2015/9/30
6
スイッチング理論と論理設計I
VLSIとは
• Very Large Scale Integrated Circuitsの略
• 数ミリ角のシリコンチップ上に数百～数千万個の
トランジスタが詰め込まれたもの
• 大規模・複雑なシステムがワンチップで実現可能
例．マイクロプロセッサのチップ写真
Intel Pentium 4
約4200万トランジスタ
2015/9/30
7
スイッチング理論と論理設計I
論理素子と論理回路
• 二つの物理的状態を０と１に対応
– 電圧低い ⇔ 高い
– 電流小 ⇔ 大
– 磁化の方向Ｎ ⇔ Ｓ
• 多値論理素子：物理的状態が3つ以上ある
素子
– 半導体メモリに利用
2015/9/30
8
スイッチング理論と論理設計I
スイッチ
• メイク接点
押
開（opened)
ＯＦＦ
閉（closed)
b
a
ＯＮ
開（opened) 押
a
ＯＮ
b
• ブレイク接点
閉（closed)
a
b
2015/9/30
a
ＯＦＦ
b
9
スイッチング理論と論理設計I
スイッチ
• トランスファ接点
x
b
x  0 の時
a
x
c
2015/9/30
10
スイッチング理論と論理設計I
スイッチ
• トランスファ接点
x
b
x  1の時
a
x
c
2015/9/30
11
スイッチング理論と論理設計I
リレー
• メイク接点
x
(a) メイク接点
2015/9/30
12
スイッチング理論と論理設計I
リレー
• メイク接点
電磁石
(a) メイク接点
2015/9/30
13
スイッチング理論と論理設計I
接点回路網
• 接点の直列接続
x
y
a
b
x  1 かつ y  1 の時 a  b間が接続
f  x y
2015/9/30
x
14
スイッチング理論と論理設計I
接点回路網
• 接点の並列接続
x
x  1 または y  1 の時
a  b間が接続
f  x y
y
a
b
2015/9/30
15
スイッチング理論と論理設計I
ミニテスト2. スイッチ回路
• 次の直並列回路網を表す論理式を求めな
さい。
x
f 
z
y
a
2015/9/30
学籍番号
b
氏名
スイッチング理論と論理設計I
16
ミニテスト2. スイッチ回路
• 次の直並列回路網を表す論理式を求めな
さい。
x
f  ( x  y)  z
z
y
a
2015/9/30
学籍番号
b
氏名
スイッチング理論と論理設計I
17
非直並列回路網
f 
x
y
v
a
u
b
z
2015/9/30
18
スイッチング理論と論理設計I
非直並列回路網
f  xy 
x
y
v
a
u
b
z
2015/9/30
19
スイッチング理論と論理設計I
演習3. スイッチ回路
• 次の非直並列回路網を表す論理式を求め
なさい。
f 
x
y
v
a
u
b
z
2015/9/30
20
スイッチング理論と論理設計I
演習4．応用問題（スイッチ回路）
• 階段の電灯は、階段の上下についてます
よね。そのスイッチ回路を描いてみましょう。
• ヒント：トランスファ接点を使います。
ＡＣ
2015/9/30
21
スイッチング理論と論理設計I
演習4．応用問題（スイッチ回路）
解答は以下のとおり.
点灯時１となる論理式 f は
f  xy  x y
y
ＡＣ
y
x
階段上
スイッチ
階段
2015/9/30
階段下
スイッチ
x
スイッチング理論と論理設計I
22
ディジタル回路とトランジスタ回路
2015/9/30
23
スイッチング理論と論理設計I
ディジタル回路
0（偽）と1（真）の２つの値のみ取り扱う
実際にハードウェアで実現するときには、例えば
0を低い電圧：０[V]で
1を高い電圧：５[V]で
表現できる。
2015/9/30
24
スイッチング理論と論理設計I
MOSトランジスタとは
(Metal Oxide Semiconductor Field Effect Transistor)
金属ー酸化物ー半導体電界効果トランジスタ
ドレイン
ゲート
ｎ
ソース
ｎ
p形にドープされた半導体基板
NMOS
2015/9/30
25
スイッチング理論と論理設計I
MOSトランジスタとは
(Metal Oxide Semiconductor Field Effect Transistor)
金属ー酸化物ー半導体電界効果トランジスタ
ドレイン
ゲート
ｐ
ソース
ｐ
ｎ形にドープされた半導体基板
PMOS
ポイント：NMOSとPMOS
の構造（組成）に注目
2015/9/30
26
スイッチング理論と論理設計I
MOSトランジスタの回路記号
ゲート
NMOS
ドレイン
ソース
ゲート
PMOS
ドレイン
ソース
2015/9/30
27
スイッチング理論と論理設計I
MOSトランジスタの動作原理
（NMOSの場合）
off
2015/9/30
28
スイッチング理論と論理設計I
MOSトランジスタの動作原理
（NMOSの場合）
3.3V
5V
電流
off
2015/9/30
29
スイッチング理論と論理設計I
MOSトランジスタの動作原理
（NMOSの場合）
5V
5V
電流
on
2015/9/30
30
スイッチング理論と論理設計I
MOSトランジスタの動作原理
（NMOSの場合）
3.3V
5V
電流
off
2015/9/30
31
スイッチング理論と論理設計I
NMOS
D
D
G
0
off
S
S
2015/9/30
32
スイッチング理論と論理設計I
NMOS
D
D
G
on
1
S
S
2015/9/30
33
スイッチング理論と論理設計I
NMOS
D
D
G
S
0
1
on
1
S
低い電圧を伝えるのは得意。高い電圧を伝えるのは苦手。
2015/9/30
34
スイッチング理論と論理設計I
PMOS
D
D
G
1
off
S
S
2015/9/30
35
スイッチング理論と論理設計I
PMOS
D
D
G
on
0
S
S
2015/9/30
36
スイッチング理論と論理設計I
PMOS
D
D
G
on
S
0
0
1
S
低い電圧を伝えるのは苦手。高い電圧を伝えるのは得意。
2015/9/30
37
スイッチング理論と論理設計I
NOT回路
x
x x
x
0
1
2015/9/30
1
0
38
スイッチング理論と論理設計I
NOT回路
5[V]
上側のトランジスタは
ディプリーション型トラ
ンジスタで抵抗の役目
をする。
5[V]
x
x
1
5[V]
0
OFF
0[V]
MOSトランジスタ回路図
2015/9/30
スイッチング理論と論理設計I
0[V]
等価回路
39
NOT回路
5[V]
5[V]
x
x
0
0[V]
1
ON
0[V]
2015/9/30
0[V]
40
スイッチング理論と論理設計I
演習5．NMOS Tr.でNOT回路を作ろう
• NOT回路をNMOSトランジスタを使って構
成しなさい。また、その動作を等価回路を
使って説明しなさい。
• この回路では、消費電力や発熱などの点
で問題があると思われる。それはなぜか。
2015/9/30
41
スイッチング理論と論理設計I
ANDとOR回路
ANDゲート
X
x y
Y
MOSでは、不向き！
ORゲート
x y
X
Y
2015/9/30
42
スイッチング理論と論理設計I
NANDゲートとNORゲート
NANDゲート
x
y
x y
NORゲート
x
y
x y
x
y
0 0
0 1
1 0
1 1
2015/9/30
x y x y
1
1
1
0
1
0
0
0
43
スイッチング理論と論理設計I
5[V]
NAND回路
5[V]
x y
x
0
0[V]
1
ON
y
1
ON
0[V]
スイッチの
直列接続
0[V]
2015/9/30
44
スイッチング理論と論理設計I
5[V]
NAND回路（問題）5[V]
x=0,y=1 の時のスイッチの状態
を等価回路の図中に書き込み
出力を求めなさい。
x y
x
y
0[V]
?
0
?
1
?
0[V]
2015/9/30
45
スイッチング理論と論理設計I
演習6．NMOS Tr.でNOR回路を作ろう
NOR回路をNMOSトランジスタで実現した場合の回路図を
描きなさい。また、等価回路を描き、その動作を例を用いて
簡潔に説明しなさい。
2015/9/30
46
スイッチング理論と論理設計I
NMOSのみで構成した
NOT回路の問題点 5[V]
5[V]
x
x=1の時, 右図のように+5V
の電源側からGNDに向
かって定常的に電流が流
れる。
これによる消費電力の増加
と発熱の問題が生じる。
x
電流
0
0[V]
1
OFF
0[V]
2015/9/30
0[V]
47
スイッチング理論と論理設計I
CMOS回路
• MOSトランジスタ製造技術の歴史.
– PMOS Tr.をSi（シリコン）基板上に作る技術.
– NMOS Tr.をSi（シリコン）基板上に作る技術.
– PMOS Tr.とNMOS Tr.の両方をSi基板上に作り込む技術
の開発.
• PMOSとNMOSとを相補的 (complementary）に組合
せた回路がCMOS回路．
• CMOS回路により低消費電力回路が実現可能．
2015/9/30
48
スイッチング理論と論理設計I
CMOS回路で実現したNOT回路
5[V]
IN
右図のように定常的に
+5Vから0Vに流れる電 5[V]
流は存在しない。
ON
OUT
1
0
OFF
0[V]
0[V]
2015/9/30
49
スイッチング理論と論理設計I
CMOS回路で実現したNOT回路
5[V]
IN
右図のように定常的に
+5Vから0Vに流れる電 5[V]
流は存在しない。
OFF
OUT
０
1
ON
0[V]
0[V]
2015/9/30
50
スイッチング理論と論理設計I
NORゲートをCMOSで構成
０
ON
０
ON
5[V]
真理値１
OFF
OFF
2015/9/30
51
スイッチング理論と論理設計I
NORゲートをCMOSで構成
０
ON
1
OFF
0[V]
真理値0
OFF
ON
2015/9/30
52
スイッチング理論と論理設計I
演習7．CMOS構成でNAND回路を作ろう
• NAND回路をPMOSトランジスタとNMOSト
ランジスタとを組合せてCMOS構成で実現
し、トランジスタ回路図を描きなさい。また、
その動作を等価回路を使って説明しなさい。
2015/9/30
53
スイッチング理論と論理設計I
論理関数の表現
2015/9/30
54
スイッチング理論と論理設計I
論理和形と論理積形
• 論理関数は論理式で実現可能．
– 表現法は多数存在．
– 本節では標準的な表現法を例を用いて学ぶ．
• 語句とその意味
– 定義3.1 リテラル(literal)
– 定義3.2 最小項(minterm)と論理和標準形，
最大項(maxterm)と論理積標準形.
2015/9/30
55
スイッチング理論と論理設計I
多数決関数（３入力）
２人以上が賛成の時は可決となり、
逆に
２人以上が反対の時は否決となる。
賛成：1
反対：0
論理関数として扱える
可決：1
否決：0
2015/9/30
56
スイッチング理論と論理設計I
真理値表・最小項・論理和標準形
A B C
f
0
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
f=
＿
A・B・C
＿
A・B・C
＿
A・B・C
A・B・C
2015/9/30
57
スイッチング理論と論理設計I
真理値表・最大項・論理積標準形
A B C
f
0
0
0
0
1
1
1
1
0 f  A B C  A B C  A BC  AB C
0 f  f  A B C  A B C  A BC  AB C
0
 (A  B  C )(A  B  C )(A  B  C )(A  B  C )
1
 ( A  B  C)  ( A  B  C )  ( A  B  C)  ( A  B  C)
0
1
ド・モルガンの法則を利用
1
すると簡単に求められる
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
2015/9/30
58
スイッチング理論と論理設計I
トランジスタ数の見積もり
#PMOS =
少ない方がいい
#NMOS =
2015/9/30
59
スイッチング理論と論理設計I
トランジスタ数の削減
１．論理式の簡単化
２．NANDゲートのみで実現
３．更なる削減（CMOS回路）
2015/9/30
60
スイッチング理論と論理設計I
A
B
C
多数決論理回路(1)
f
2015/9/30
61
スイッチング理論と論理設計I
A
B
C
多数決論理回路(2)
#PMOS =
#NMOS =
f
2015/9/30
62
スイッチング理論と論理設計I
トランジスタ数の削減
１．論理式の簡単化
２．NANDゲートのみで実現
３．更なる削減（CMOS回路）
2015/9/30
63
スイッチング理論と論理設計I
論理式の簡単化
f  A BC  AB C  ABC  ABC
A
B
C
 ( A  A) BC  A( B  B)C  AB(C  C )
 BC  AC  AB
f
#PMOS =
#NMOS =
2015/9/30
64
スイッチング理論と論理設計I
トランジスタ数の削減
１．論理式の簡単化
２．NANDゲートのみで実現
３．更なる削減（CMOS回路）
2015/9/30
65
スイッチング理論と論理設計I
多数決論理回路(4)
A
B
C
f  BC  AC  AB
 BC  AC  AB
 BC  AC  AB
f
#PMOS =
#NMOS =
2015/9/30
66
スイッチング理論と論理設計I
トランジスタ数の削減
１．論理式の簡単化
２．NANDゲートのみで実現
３．CMOS回路を直に実現
2015/9/30
67
スイッチング理論と論理設計I
多数決論理回路のCMOS構成
＋５Ｖ
A
B
＋５Ｖ
C
f
A
B
#PMOS =
C
#NMOS =
2015/9/30
スイッチング理論と論理設計I
68
レポート
• 多数決論理関数とは何か？
• どのように、トランジスタ数を減らしていっ
たか？各方法の説明、トランジスタ数と以
下のもの
– 論理式の簡単化（ゲート回路図）
– NANDゲート（ゲート回路図、CMOS回路図）
– 更なる方法（CMOS回路図）
2015/9/30
69
スイッチング理論と論理設計I
論理式表現の高度のテクニック
2015/9/30
70
スイッチング理論と論理設計I
シャノン展開
• シャノン展開定理（Shannon’s expansion
theorem）
定理１
f ( x1 , x2 ,, xn )  x1 f (0, x2 ,, xn )  x1 f (1, x2 ,, xn )
2015/9/30
71
スイッチング理論と論理設計I
3.5 リード・マラー展開(1)
• 補題3.1
( x  y)  z  x  ( y  z)
x( y  z )  xy  xz
x y  y x
x x  0
x 1  x
2015/9/30
72
スイッチング理論と論理設計I
3.5 リード・マラー展開(2)
• 補題3.2
xy  0  x  y  x  y
意味：重なりがない場合は、右式のようにORの式を
EXORの式に直せる。
2015/9/30
73
スイッチング理論と論理設計I
3.5 リード・マラー展開(3)
• リード・マラー標準形
f ( x1 , x2 )  f (0,0)( x1 x2  x1  x2  1)  f (0,1)( x1 x2  x2 )
 f (1,0)( x1 x2  x1 )  f (1,1) x1 x2
2015/9/30
74
スイッチング理論と論理設計I
第２週目
ゲート論理回路の設計
2015/9/30
75
スイッチング理論と論理設計I
実習の概要
1.マルチプレクサの設計
・複合ゲートを用いた設計
・伝送ゲートを用いた設計
2.xlceによるゲートレベルの設計
・xlceの使用方法
・HA,FAの設計
・4bits adderの設計
2015/9/30
76
スイッチング理論と論理設計I
マルチプレクサとは
複数の入力線の中から、１つの入力線を選択する回路
切り替えスイッチ
D0
D1
D0
Y
D1
2015/9/30
77
スイッチング理論と論理設計I
マルチプレクサ（multiplexer）
D0
2-1 MUX
Y
D1
SEL Y
0 D0
1 D1
SEL
2015/9/30
78
スイッチング理論と論理設計I
2-1 MUXの設計(1)
_
Y=SEL・D0 + SEL・D1
D0
Y
D1
#NMOS=10
#PMOS=10
SEL
2015/9/30
79
スイッチング理論と論理設計I
2-1 MUXの設計(2-1)
AND-NORの複合ゲートを用いる
AND-NOR形論理式をCMOSで実現
2015/9/30
80
スイッチング理論と論理設計I
2-1 MUXの設計(2-2)
A
B
CD
0 0
0 1
1 1
1 0
0
0
1
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
1
0
1
1
0
1
_NMOS
f=AB+CD
PMOS
_ _ _ _ _ _ _ _
_ _
_ _
f=A・C+A・D+B・D+B・C = (A+B)・(C+D)
2015/9/30
81
スイッチング理論と論理設計I
2-1 MUXの設計(2-3)
AND-NORの複合ゲートを用いる
#NMOS=6
#PMOS=6
2015/9/30
82
スイッチング理論と論理設計I
2-1 MUXの設計(3-1)
伝送ゲートを用いる
0
NMOS,PMOSを同時にONで
いかなる値でも伝送できる。
10
1
2015/9/30
83
スイッチング理論と論理設計I
2-1 MUXの設計(3-2)
SEL=0 → Y=D0
SEL=1 → Y=D1
SEL=0でD0の伝送ゲートがON
SEL=1でD1の伝送ゲートがON
2015/9/30
84
スイッチング理論と論理設計I
4-1 MUXの設計(1-1)
D0
D1
D2
４-1 MUX
D3
Y
S1 S0
0 0
0 1
1 0
1 1
S0
S1
2015/9/30
Y
D0
D1
D2
D3
85
スイッチング理論と論理設計I
4-1 MUXの設計(1-2)
D0
D1
Y
D2
D3
S0
S1
2015/9/30
86
スイッチング理論と論理設計I
半加算器 HA(Half Adder)
1bitと1bitの加算器
A
S
HA
B
C
2015/9/30
A
0
0
1
1
B
0
1
0
1
C
0
0
0
1
S
0
1
1
0
87
スイッチング理論と論理設計I
全加算器 FA(Full Adder)
・下からの桁上がりが存在する
・多桁の加算のときに必要
Cin
A
S
FA
C out
B
2015/9/30
88
スイッチング理論と論理設計I
4bits adderの設計
（例）4ビットの加算
A3 A2 A 1 A 0
B 3 B2 B1 B 0
Cout S 3 S 2 S 1 S 0
2015/9/30
89
スイッチング理論と論理設計I
第2週目のレポート課題
• マルチプレクサとは？
• 2-1MUXの設計（真理値表、カルノー図
等）
– AND-OR2段回路（ゲート回路図）
– 複合ゲート（CMOS回路図）
– 伝送ゲート（CMOS回路図）
• 4-1MUXの設計（設計の説明、機能表）
– 複合ゲート（CMOS回路図）
– 伝送ゲート（CMOS回路図）
2015/9/30
90
スイッチング理論と論理設計I
第３週目
ALUの設計
2015/9/30
91
スイッチング理論と論理設計I
ALU（Arithmetic Logic Unit）とは
算術論理演算部
算術演算部：加算、減算、１増やす、１減らす
AU
論理演算部：AND、OR、XOR、NOT
LU
入力 A
ALU
出力 S
入力 B
制御信号 ctrl
2015/9/30
92
スイッチング理論と論理設計I
ALUの機能表
ctrl 2 ctrl 1 ctrl 0
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
機能
A+B
A-B
A -A ++
A and B
A or B
A xor B
not A
2015/9/30
算術演算
論理演算
93
スイッチング理論と論理設計I
ALU回路の内部構造
入力 A
AU
出力 S
LU
入力 B
ctrl 2
2015/9/30
94
スイッチング理論と論理設計I
LU（Logic Unit）の設計
入力 A
入力 B
４-1 MUX
2015/9/30
出力 S
95
スイッチング理論と論理設計I
AU（Arithmetic Unit）の設計１
入力 A
入力 B
加算
減算
４-1 MUX
出力 S
dec
inc
2015/9/30
96
スイッチング理論と論理設計I
AUの設計２
入力 A
加算器
出力 S
入力 B
減算器
2015/9/30
97
スイッチング理論と論理設計I
減算を加算に
Aー B
A ＋（‐B）
2015/9/30
減算の命令
加算器で実行
98
スイッチング理論と論理設計I
負の数の取り扱い
２の補数形式を採用
求め方：全ビットの反転に、１を足す
復習
１．３（００１１）⇒－３
２．５－３
３．２の補数で表現できる値の範囲
2015/9/30
99
スイッチング理論と論理設計I
AUの設計３
入力 A
加算器
（FA）
入力 B
AU
出力 S
付加回路
2015/9/30
100
スイッチング理論と論理設計I
付加回路の設計１
２の補数： Bの反転＋１
全加算器（FA）で最下位ビットのC_inは必要？
例：５－３
A=5 : 00000101
B=3 : 00000011
A : 00000101
B’: 11111100
+
1
A-B=
2015/9/30
101
スイッチング理論と論理設計I
付加回路の設計２
１
C_in
出力 S
加算器
（FA）
入力 A
入力 B
付加回路
C_out
Bの反転
2015/9/30
102
スイッチング理論と論理設計I
付加回路の真理値表
機能
A+B
A- B
A
-A-1
A ++
ctrl 1 ctrl 0
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
B
付加回路
C_in
0
1
0
1
0
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
1
1
-1はALL１
2015/9/30
103
スイッチング理論と論理設計I
第３週目のレポート課題
• ALUとは？
• 付加回路の設計（ゲート回路図、シミュレーション
結果）
• 1bit-AUの設計（ゲート回路図、シミュレーション
結果）
• 1bit-LUの設計（ゲート回路図、シミュレーション
結果）
• 1bit-ALUの設計（ゲート回路図、シミュレーション
結果）
• 4bits-ALUの設計（ゲート回路図、シミュレーショ
ン結果）
2015/9/30
104
スイッチング理論と論理設計I
テストパターン数
• 付加回路
：８パターン（全パター
ン）
• 1bit-AU
:最低８パターン（各演算×２
通り）
• 1bit-LU
:最低８パターン（各演算×２
通り）
• 1bit-ALU
:最低８パターン（各演
算×２通り）
• 4bits-ALU
:３２パターン（各演算×４通
り）
2015/9/30
105
スイッチング理論と論理設計I

Download Report