Document

論理回路
第5回代表的な組み合わせ論理回路
http://www.info.kindai.ac.jp/LC
38号館4階N-411 内線5459
[email protected]
組み合わせ回路
 定義2.4
(組み合わせ回路)
– ある時刻の出力信号が、現在の入力信号だ
けで決まる回路
 定義3.2
(順序回路)
– ある時刻の出力信号が、現在の入力信号だ
けでなく、過去の入力信号の影響も受ける
回路 (回路内にバッファ・メモリがある)
選択器 (multiplexor)

2n本の入力から1本を選択し出力する回路
• 2n+n 入力1出力
D = (D0,D1,…,D2n -1), n ビット制御信号S
–出力: Q
–入力:

例: 2ビット選択器
制御信号S
入力
S =0
←2ビット
D0
D1
D2
D3
S =1
S =2
S =3
出力
Q
S
0
1
2
3
S1 S0
0 0
0 1
1 0
1 1
Q
D0
D1
D2
D3
選択器
• D = (D0,D1,…,D2n –1) : 入力
• S : n ビット制御信号
• Q : 出力
MulPle (D,S ) {
switch (S ) {
case 0 : Q =D0 ; break;
case 1 : Q =D1 ; break;
case 2n-1: Q =D2n -1; break;
}
}
1ビット選択器

2本の入力{D0,D1}から1本を選択
– 1ビット信号S で制御
S
入力
D0
D1
制御信号S
S =0
S =1
出力
Q
𝑄 = 𝑆 ⋅ 𝐷0 + 𝑆 ⋅ 𝐷1
Di
D0 =0
D0 =1
D1 =0
D1 =1
0
1
Q
D0
D1
S
Q
0
1
0
1
0
1
1ビット選択器の設計
𝑄 = 𝑆 ⋅ 𝐷0 + 𝑆 ⋅ 𝐷1
入力
D0
D1
制御信号S
S =0
S =1
制御信号
S
MulPle
入力
出力 D
0
Q
D1
出力
Q
2ビット選択器

22=4本の入力 D0,D1,D2,D3 から1本を選択
– 2ビット信号 S =(S1,S0) で制御
入力
D0
D1
D2
D3
制御信号S
S =0
S =1
S =2
S =3
出力
Q
S
0
1
2
3
S1 S0
0 0
0 1
1 0
1 1
Q
D0
D1
D2
D3
2ビット選択器
S 1 S0
0 0
0 1
1 0
1 1
Q
D0
D1
D2
D3
Di
D0=0
D0=1
D1=0
D1=1
D2=0
D2=1
D3=0
D3=1
S1 S0
0 0
0 1
1 0
1 1
Q
0
1
0
1
0
1
0
1
Q  S1 S0 D0  S1S0 D1  S1 S0 D2  S1S0 D3
2ビット選択器の設計
Q  S1 S0 D0  S1S0 D1  S1 S0 D2  S1S0 D3
制御信号
S1 S0
MulPle2
入力
D0
D1
D2
D3
制御信号S
S =0
S =1
S =2
S =3
入力
D0
出力
Q D1
D2
D3
出力
Q
1ビット選択器
gate6.v
分配器(demultiplexor)

信号を2n本のうち1本に出力する回路
• n +1入力2n出力
–入力:
D, n ビット制御信号S
–出力: Q = (Q0,Q1,…,Q2n -1)

入力
D
例: 2ビット分配器
制御信号S
出力
S =0
Q0
S =1
Q1
S =2
Q2
S =3
Q3
S S 1 S 0 Q 0 Q1 Q2 Q3
0 0 0 D 0 0 0
1 0 1 0 D 0 0
2 1 0 0 0 D 0
3 1 1 0 0 0 D
分配器
• D : 入力
• S : n ビット制御信号
• Q = (Q0,Q1,…,Q2n –1) : 出力
DeMulPle (D,S ) {
switch (S ) {
case 0 : Q0 =D ; break;
case 1 : Q1 =D ; break;
case 2n-1: Q2n -1 =D ; break;
}
}
1ビット分配器

信号を2本のうち1本に出力
– 1ビット信号S で制御
制御信号S
入力
D
S =0
S =1
𝑄0 = 𝑆 ⋅ 𝐷
𝑄1 = 𝑆 ⋅ 𝐷
出力
Q0
Q1
D
0
1
0
1
S
0
1
Q0
0
1
0
0
Q1
0
0
0
1
1ビット分配器の設計
𝑄0 = 𝑆 ⋅ 𝐷
𝑄1 = 𝑆 ⋅ 𝐷
制御信号S
入力
D
S =0
S =1
制御信号
S
DeMulPle
出力
Q0 入力
D
Q1
出力
Q0
Q1
問題 : 2ビット分配器の設計

2ビット分配器を設計せよ
制御信号
S1
S0
DeMulPle2
出力
Q0
入力
D
Q1
Q2
Q3
比較器 (comparator)

入力の大小を比較する
• 2入力3出力
ZX : X の方が大きい
–入力 : X,Y
ZY : Y の方が大きい
–出力 : ZX,ZY,Zeq Zeq: X とY が同じ
Comp (X,Y ) {
if (X >Y ) ZX = true;
else if (Y >X ) ZY = true;
else Zeq = true;
}
1ビット比較器の論理関数
X
0
0
1
1
Y
0
1
0
1
ZX
0
0
1
0
ZY
0
1
0
0
Zeq
1
0
0
1
𝑍𝑋 = 𝑋 ⋅ 𝑌
𝑍𝑌 = 𝑋 ⋅ 𝑌
𝑍𝑒𝑞 = 𝑋 ⋅ 𝑌 + 𝑋 ⋅ 𝑌
1ビット比較器の設計
Z X  X Y
ZY  X  Y
Z eq  X  Y  X  Y  ( X  Y )  ( X  Y )  Z X  ZY
Comp
X
Y
Comp
ZX X
ZX
Zeq
Zeq
ZY Y
ZY
2ビット比較器の真理値表
•
2ビット×2入力3出力
16通りの
組み合わせ
–入力
: X =(X1,X0),Y =(Y1,Y0)
–出力 : ZX,ZY,Zeq
X1 X0
0 0
0 1
Y1 Y0
0 0
ZX
0
ZY Zeq
0
1
0 1
0
1
0
1 0
0
1
0
1 1
0
1
0 0
1
0 1
X1 X0
Y1 Y0
0 0
ZX
1
ZY Zeq
0
0
0 1
1
0
0
1 0
0
0
1
0
1 1
0
1
0
0
0
0 0
1
0
0
0
0
1
0 1
1
0
0
1 0
0
1
0
1 0
1
0
0
1 1
0
1
0
1 1
0
0
1
1 0
1 1
2ビット比較器の論理関数
Y1 Y0
0 0
0 1
1 1
1 0
0 1
=
>
<
=
<
<
<
<
1 1
>
>
=
>
1 0
>
>
<
=
X 1 X0
0 0
Z X  X1Y1  X 0 Y1Y0  X1 X 0 Y0
ZY  X 1Y1  X 1 X 0Y0  X 0Y1Y0
•
> : X >Y
• = : X =Y
• < : X <Y
Z eq  X 1 X 0 Y1Y0  X 1 X 0 Y1Y0  X 1 X 0Y1Y0  X 1 X 0Y1Y0
2ビット比較器の設計
Comp2
X1
ZX
X0
Zeq
Y1
Y0
ZY
多ビット比較器の場合

比較器のビット数と出力の組み合わせ数
1.
2.
3.
4.
5.
1ビット : 21×21 = 4通り
2ビット : 22×22 = 16通り
3ビット : 23×23 = 64通り
4ビット : 24×24 = 256通り
5ビット : 25×25 = 1024通り
ビット数が増えるにつれ膨大な組み合わせが必要
高ビット比較器の設計はとても無理！
複雑な回路の設計・製作

複雑な回路
– 設計が難しい
– 製作コストが高価
複雑な回路をより簡単な回路(設計済み)の
組み合わせで作る
• 設計が簡単になる
• 回路の量産化で製作コスト削減
回路のモジュール化

回路全体を1つのゲートとみなす
例 : 比較器
Comp
X
ZX
Zeq
Y
X
モジュール化
Y
ZY
ZX
Comp Zeq
ZY

1ビット比較器モジュールを用いた
2ビット比較器
X =(X1,X0), Y =(Y1,Y0) の大小比較
•
•
•
X >Y : X1>Y1 または (X1=Y1 かつ X0>Y0)
X <Y : X1<Y1 または (X1=Y1 かつ X0<Y0)
X =Y : X1=Y1 かつ X0=Y0
ZX 1,ZY 1,Zeq1 : X1,Y1の比較結果
– ZX 0,ZY 0,Zeq0 : X0,Y0の比較結果
–
Z X  Z X 1  Z eq1  Z X 0
Z Y  Z Y 1  Z eq1  Z Y 0
Z eq  Z eq1  Z eq 0
2ビット比較器の設計
Z X  Z X 1  Z eq1  Z X 0
Z Y  Z Y 1  Z eq1  Z Y 0
Z eq  Z eq1  Z eq 0
Comp2
X1
X
X0
Y
ZX
Comp
Zeq
ZY
1ビット比較器
モジュール
ZX 1
Zeq1
ZX
ZY 1
Zeq
Y1
Y0
ZX
X
Y
Comp
Zeq
ZY
ZX 0
Zeq0
ZY 0
ZY
1ビット選択器モジュールを用いた
2ビット選択器

1ビット選択器: D = (D0,D1), S
Q  S  D0  S  D1

2ビット選択器: D = (D00,D01 ,D10 ,D11), S = (S1,S0)
Q  S1 S0 D00  S1S0 D01  S1 S0 D10  S1S0 D11
 S1  (S0 D00  S0 D01)  S1  (S0 D10  S0 D11)
Q0  S 0 D00  S 0 D01
Q1  S 0 D10  S 0 D11
Q  S1  Q0  S1  Q1
1ビット選択器
問題 : 2ビット選択器の設計

1ビット選択器モジュール3個を用いて
2ビット選択器を設計せよ
S0
S1
D00
D0
D01
MulPle2
S
MulPle
Q
D1
D0
D1
D10
D0
D11
D1
S
MulPle
Q
S
MulPle
Q
Q
問題 : 4ビット比較器の設計

2ビット比較器モジュール2個を用いて
4ビット比較器を設計せよ
Comp4
X3
X2
X1
X0
Y3
Y2
Y1
Y0
X1
X0
Y1
Y0
ZX
Comp2
Zeq
ZX
ZY
Zeq
X1
X0
Y1
Y0
ZX
Comp2
Zeq
ZY
ZY
符号化器(encoder)
復号化器(decoder)


符号化 : 情報を数値コードに変える
復号化 : 数値コードを情報に戻す
例
: 情報をメモリに格納
情報 : データ
– コード : データのアドレス
–
データ
8
アドレス
符号化器
データ
3
4
アドレス
復号化器
2
メモリ
アドレスデータ
0
1
2
3
4
5
6
7
1
8
3
5
8
アドレス符号化器(address encoder)
– 入力: 2n本の1ビット信号 D =(D2n-1,…D0)

ただし、1本のみ 1,残りの2n-1本は 0 が入力される
– 出力: n ビット信号 Q =(Dn-1,…D0)
アドレスエンコーダ
D7
D6
D5
D4
D3
D2
D1
D0
Q2
Q1
Q0
D
Q
D
Q
00000001 000 00010000 100
00000010 001 00100000 101
00000100 010 01000000 110
00001000 011 10000000 111
表に無い入力はドントケア
アドレス復号化器(address decoder)
– 入力: n ビット信号 D =(Dn-1,…,D0)
– 出力: 2n本の1ビット信号 Q =(Q2n-1,…Q0)

D1
D0
アドレスデコーダ
D2
ただし、1本のみ 1,残りの2n-1本は 0 が出力される
Q7
Q6
Q5
Q4
Q3
Q2
Q1
Q0
D
000
001
010
011
Q
00000001
00000010
00000100
00001000
D
100
101
110
111
Q
00010000
00100000
01000000
10000000
アドレスエンコーダ
D
Q
D
Q
00000001 000 00010000 100 Q  D  D  D  D
2
7
6
5
4
00000010 001 00100000 101 Q  D  D  D  D
1
7
6
3
2
00000100 010 01000000 110 Q  D  D  D  D
0
7
5
3
1
00001000 011 10000000 111
D7 D6 D5 D4 D3 D2 D1 D0
Q2
Q1
Q0
アドレスデコーダ
D
000
001
010
011
Q
00000001
00000010
00000100
00001000
D
100
101
110
111
Q
00010000
00100000
01000000
10000000
D2
D1
D0
Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0
Q7  D2  D1  D0
Q6  D2  D1  D0
Q5  D2  D1  D0
Q4  D2  D1  D0
Q3  D2  D1  D0
Q2  D2  D1  D0
Q1  D2  D1  D0
Q0  D2  D1  D0
優先順位付符号化器(priority encoder)
– 入力: 2n本の1ビット信号D =(D2n-1,…D0)
– 出力: n ビット信号Q =(Qn-1,…,Q0) :
通常の符号化器は入力に1は1個のみ
入力に複数の1がある場合
•
通常の符号化器 : ドントケア
•
優先順位付符号化器 : 上位ビットを優先
入力に1が1つも無い場合
通常の符号化器 : ドントケア
• 優先順位付符号化器 : ドントケア
•
2ビット優先順位付符号化器の真理値表
D3D2D1D0 P Q
D3D2D1D0 P
0 0 0 0
1 0 0 0
3
0 0 0 1
0
0
1 0 0 1
3
0 0 1 0
1
1
1 0 1 0
3
0 0 1 1
1
1 0 1 1
3
0 1 0 0
2
2
1 1 0 0
3
0 1 0 1
2
1 1 0 1
3
0 1 1 0
2
1 1 1 0
3
0 1 1 1
2
1 1 1 1
3
P :優先順位付符号化器 Q : 符号化器
Q
3
-
加算器(adder)

2入力の和を計算
– 入力 : 1桁の算術変数 X, Y
– 出力 : S X +Y の1桁め
COUT X +Y の上位桁への繰り上がり
例 : X = 7, Y = 8 (10進数)
•
S=5
• COUT= 1
1ビット半加算器(half adder)
– 入力 : 1ビット変数 X, Y
– 出力 : S X +Y の1ビットめ
COUT X +Y の上位ビットへの繰り上がり
XY
00
01
10
11
CO
0
0
0
1
S
0
1
1
0
S  X Y  X Y  X  Y
CO  X  Y
1ビット半加算器の設計
S  X Y  X Y  X  Y
CO  X  Y
HA
HA
X
CO X
CO
Y
S Y
S
1ビット全加算器(full adder)
– 入力 : 1ビット変数 X, Y
CIN 下位ビットからの繰り上がり
– 出力 : S X +Y の1ビットめ
COUT X +Y の上位ビットへの繰り上がり
X Y
0 0
0 1
CI
0
1
0
1
CO
0
0
0
1
S
0
1
1
0
X Y
1 0
1 1
CI
0
1
0
1
CO
0
1
1
1
S
1
0
0
1
1ビット全加算器の論理関数
S
XY
00
01
11
10
0
0
1
0
1
1
1
0
1
0
CI
S  X YCI  X Y CI  X Y CI  XYCI  X  Y  CI
CO
XY
00
01
11
10
0
0
0
1
0
1
0
1
1
1
CI
CO  XY  XCI  YCI
1ビット全加算器の設計
S  X YCI  XY CI  X Y CI  XYCI  X  Y  CI
CO  XY  XCI  YC I
FA
FA
X
CO
X
Y
Y
CI
S C
I
CO
S
半加算モジュールを用いた全加算器

半加算器 S HA ( X , Y )  X  Y
COHA ( X , Y )  XY
FA
 全加算器 S
( X , Y , CI )  X  Y  CI
HA
 S ( X , Y )  CI
HA
HA
 S ( S ( X , Y ), CI )
FA
CO ( X , Y , CI )  XY  XCI  YC I
 XY  ( X  Y )CI
 XY  ( X  Y  XY )CI
 XY  XYC I  ( X  Y )CI
 XY  ( X  Y )CI
HA
HA
 CO ( X , Y )  S ( X , Y )CI
 COHA ( X , Y )  COHA ( S HA ( X , Y ), CI )
問題 : 全加算器の設計
半加算器モジュール2個を用いて
全加算器を設計せよ
S FA ( X , Y , CI )  S HA ( S HA ( X , Y ), CI )
COFA ( X , Y , CI )  COHA ( X , Y )  COHA ( S HA ( X , Y ), CI )

FA
X
Y
X
HA
Y
CO
CO
S
X
HA
CI
Y
CO
S
S
2ビット加算器
– 入力 : 2ビット変数 X =(X1,X0), Y =(Y1,Y0)
CIN 下位ビットからの繰り上がり
– 出力 : S =(S1,S0), X +Y の1,2ビットめ
COUT X +Y の上位ビットへの繰り上がり
FA2
X1
CO
X
CO
FA
Y
X0
Y1
Y0
CI
CI
S
CO
X
Y FA
S
CI
S1
S0
問題 : 4ビット全加算器の設計

4ビット全加算器を設計せよ
X3
X2
X1
X0
Y3
Y2
Y1
Y0
CI
FA4
X
Y
CI
X
Y
CI
X
Y
CI
X
Y
CI
FA
FA
FA
FA
CO
S
CO
CO
S4
S
CO
S3
S
S2
CO
S1
S
多数決器
– 入力 : n 変数 X1,X2,…, Xn
1 (入力のうち1が半分以上)
– 出力 : Z =
0 (入力のうち1が半分未満)

例 3変数多数決器
X1 X2 X3
Z
X1 X2 X3
Z
0 0 0
0
1 0 0
0
0 0 1
0
1 0 1
1
0 1 0
0
1 1 0
1
0 1 1
1
1 1 1
1
多数決器の論理関数
X1 X2
00
01
11
10
00
0
0
1
0
01
0
1
1
1
11
1
1
1
1
10
0
1
1
1
X3 X4
Z  X1 X 2  X 2 X 3  X 3 X 4
 X 4 X1  X1 X 3  X 2 X 4
多数決回路
Z  X1 X 2  X 2 X 3  X 3 X 4  X 4 X1  X1 X 3  X 2 X 4
Major4
X1
X2
Z
X3
X4
例題 : 重み付き多数決器
各人が持つ票の重みが違う多数決
 例題2.26

– A 4票,B 3票,C 2票,D 1票を持つ (賛成5票で可決)
WeightedMajor
AB
00 01 11 10
CD
A
00 0 3 7 4
B
01 1 4 8 5
M
11 3 6 10 7 C
10 2 5 9 6 D
問題 : Tkgate 課題


gate7.v のシミュレート結果からスコープ図
および真理値表を作成せよ
ただし、入力は以下の値を入力すること
– X : 学籍番号の下1桁
(下1桁が 0 の場合は a (10) を入力)
– Y : 0～f (16進数)
– SIGN : 0,1
なお、遅延は無視してよい
学籍番号
下1桁
0～f
(16進数)
0, 1
gate7.v
全加算器
モジュール
X
学籍番号下1桁
Y 0
SIGN
Co
S3
S2
S1
S0
1
2
3
4
5
6
7
8
9
a
b
c
X
学籍番号下1桁
Y 0
SIGN
Co
S3
S2
S1
S0
1
2
3
4
5
6
7
8
9
a
b
c
X
学籍番号
下1桁
Y
SIGN
0
S
X
Y
学籍番号
下1桁
8
1
9
2
a
3
b
4
0
c
5
d
6
e
7
f
SIGN
0
S
X
学籍番号
下1桁
Y
SIGN
0
S
X
Y
学籍番号
下1桁
8
1
9
2
a
3
b
4
1
c
5
d
6
e
7
f
SIGN
1
S
中間試験





試験日 : 6月9日(木)
試験時間 : 60分
試験範囲 : 第1～7回
配点 : 30点満点
持ち込み : 可
– ただし外部とのネットワーク接続は不可
– TkGateは使用しない
演習問題 : 選択器の設計

1ビット選択器を設計せよ
Q= 𝑆 ⋅ 𝐷0 + 𝑆 ⋅ 𝐷1
制御信号 S
Di
D0 = 0
D0 = 1
D1 = 0
D1 = 1
S
0
1
Q
0
1
0
1
MulPle
入力
D0
D1
出力
Q0
演習問題 : 分配器の設計

1ビット分配器を設計せよ
Q0= 𝑆 ⋅ 𝐷
Q1= 𝑆 ⋅ 𝐷
制御信号 S
入力
D
D S Q0
0
0
0
1
1
0
0
1
1
0
DeMulPle
Q1
0
0
0
1
出力
Q0
Q1
演習問題 : 符号化器の設計

2ビット符号化器を設計せよ D3D2D1D0 Q1 Q0
0 0 0 1
0 0
Q0= D1+D3
0 0 1 0
0 1
Q1= D2+D3
0 1 0 0
1 0
1 0 0 0
入力
D0
D1
D2
D3
1 1
Encode
D0は使用されない
出力
Q0
Q1
演習問題 : 半加算器の設計

1ビット半加算器を
設計せよ
S = X Y  X Y  X  Y
CO = X  Y
HA
XY
00
CO
0
S
0
01
10
11
0
0
1
1
1
0
HA
X
CO X
CO
Y
S
S
Y
演習問題 : 全加算器の設計
1ビット全加算器を
設計せよ
S = X  Y  CI
CO = X  Y  X  C I  Y  C I

X Y CI CO
000 0
S
0
X Y CI CO
100 0
S
1
001
010
011
1
1
0
101
110
111
0
0
1
0
0
1
1
1
1
FullAdder
X
CO
Y
CI
S
演習問題 : 2ビット全加算器の設計

1ビット全加算器モジュール2個を用いて
2ビット全加算器を設計せよ
FA2
X1
X0
X
Y
CI
FA
CO
S
S1
Y1
Y0
CI
CO
X
Y
CI
FA
CO
S
S0

Download Report