第2章計算の理論とオートマトン

第2章論理回路とオートマトン
2章の内容
1. １０進数から２進数へ
2. 論理代数
3. 論理回路
1. 組み合せ論理回路（演算回路の設計）
2. 順序論理回路（カウンターの設計）
4. 論理素子の高速化・高密度化
5. 計算機の一般化・抽象化
•
•
オートマトン
機械を越えて ‐セル・オートマトン‐
§1 １０進数から２進数へ
歯車計算機から論理回路へ
• 歯車計算機
– 歯車の角度が０～９に対応
入力データ
演算装置（歯車）
出力データ
（10進数）
10進数のまま計算
（10進数）
• 論理回路
– 電気を使った演算の高速化
入力データ
演算装置（論理回路）
出力データ
（10進数）
2進数として計算
（10進数）
10進数
⇒2進数
2進数
⇒10進数
10進数⇔2進数
２進数
２で割った
商と余り
２で割った
商と余り
１０進数⇒２進数
（i）２で割った余りを下の桁の値に
（ii）商がゼロでなければ更に２で割る
（iii）以上を繰り返す
２進数⇒１０進数
（111）2=（100）2+（010）2 +（001）2
=1×22+1×2+1=7
10進数の計算⇔2進数の計算
• ２進数を使った計算の例
（3）10
+ （5）10
（8）１0
（0011）2
+ （0101）2
（1000）2
§2 論理代数
論理演算
命題
–
–
真・偽の判定可能な主張
例：「人間は、動物である。」（真）
「横浜は、日本の首都である。」（偽）
論理演算
ある命題A、Bに対する論理演算
• A ：論理否定（Aでない）
• A+B：論理和（AまたはB）
• A・B：論理積（AかつB）
論理代数（1）
論理代数（ブール代数）
命題の具体的中身にこだわらず（①）真偽だけに注目（②）
①特定の命題の代わりに論理変数（変数化された命題）を扱う（代
数）
②真偽が同じ命題は等価の命題とみなし等式で結ぶ
例：論理和の真偽の等式
0+0=0, 0+1=1, 1+0=1, 1+1=1
論理積の真偽の等式
0・0=0, 0・1=0, 1・0=0, 1・1=1
A
B
A・B
0
0
0
0
1
0
1
0
0
1
1
1
A
B
A+B
0
0
0
0
1
1
1
0
1
1
1
1
真理値表
論理代数（2）
論理代数（ブール代数）の意義
例：論理変数A, Bに対して
A B  A  B （ドモルガンの公式）
が成り立つ
そこで、論理代数を用いれば、
–
–
命題１：「田中さんは、出身が横浜で年齢が18歳以上の
人ではない。」
命題２：「田中さんは、出身が横浜以外か、18歳未満の
いずれかに当てはまる。」
が等価な命題（同じ真偽）であると具体的な意味の
吟味なしに分かってしまう
論理代数（4）
論理代数の基本公式
論理変数A、B、Cに対して以下の真偽の等式が成り立つ
1. 同一則：A+A=A, A・A=A
2. 吸収則：A+1=1, A+0=A, A・0=0, A・1=A
3. 否定則：A+ A =1, A・ A =0
4. 交換則：A+B=B+A, A・B=B・A
5. 結合則：（A+B）+C=A+（B+C）, （A・B）・C=A・（B・C）
6. 分配則：A・（B+C）=A・B+A・C, A+B・C=（A+B）・（A+C）
7. ドモルガンの定理： A B  A  B, A B  A  B
–計算でよく使うものを挙げたもの
–真理値表で確かめられるので憶える程のものでない
論理関数（1）
•
•
•
•
論理代数は、数学を使って論理学を明快に
しようとして、ブールによってつくられたもの
である
そもそも、コンピュータのためにつくられたも
のではない
では、なぜ？どのように？コンピュータに役
立つのか？
論理関数の真理値表が与えられたとき、そ
れを論理演算で表現する一般的な方法を
与えるからである
論理関数（2）
論理関数
– 論理変数と論理演算で書かれた式
– 例： F(A,B)  A B  A  B
論理関数（3）
論理関数の展開式
F(A,B, C,)  A F(1,B, C,)  A  F(0,B, C,)
1を代入された関
数はAを伴う
0を代入された関数
はAの否定を伴う
A
A・F(1,A,B,…)
A・F(0,A,B,…)
A・F(1,A,B,…) +A・F(0,A,B,…)
0
0
F(0,A,B,…)
F(0,A,B,…)
1
F(1,A,B,…)
0
F(1,A,B,…)
論理関数（4）
F(A,B, C,)  A F(1,B, C,)  A  F(0,B, C,)
を繰り返し使うと、以下の展開式が簡単に証明できる
F(A)  A F(1) A  F(0)
F(A,B)  (A B)  F(1,1) (A B) F(1,0)
 (A  B)  F(0,1) (A  B)  F(0,0)
F(A,B, C)  (A B C)  F(1,1,1) (A B C)  F(1,1,0)
 (A B  C)  F(1,0,1) (A B  C)  F(1,0,0)
 (A  B C)  F(0,1,1) (A  B C)  F(0,1,0)
 (A  B  C)  F(0,0,1) (A  B  C)  F(0,0,0)
論理関数（5）
すべての項が必要なわけではない
論理関数Fが0になる項は0になる（論理積の
吸収則によって）ので省くことができる（論理
和の吸収則によって）
(A B C)  0  0, (A B C) 1  A B C
(A B C)  0  0, (A B C) 1  A B C
(A B  C)  0  0, (A B  C) 1  A B  C
(A B  C)  0  0, (A B  C) 1  A B  C
etc
論理関数（6）
論理関数の真理値表が与えられたときそれを
論理演算で表現する一般的な方法
1. F=1となる論理変数の１組に注目
2. 論理変数の真偽から変数の否定の有り無しを決
める
0 ⇒ A, 1⇒ A
3. 論理積を取り一つの項とする
4. F=1に対応したすべての項の論理和をつくる
§3 論理回路
３つの論理素子（1）
動作表
(a)ＡＮＤ回路（論理積と同じ働き）
+5V
A
A
B
Y
0V
0V
0V
0V
5V
0V
5V
0V
0V
5V
5V
5V
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
Y
抽象化
B
0V
記号
A
B
Y
３つの論理素子（2）
動作表
(b)OR回路（論理和と同じ働き）
+5V
A
A
B
Y
0V
0V
0V
0V
5V
5V
5V
0V
5V
5V
5V
5V
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
Y
抽象化
B
0V
記号
A
B
Y
３つの論理素子（3）
(c)NOT回路（論理否定と同じ働き）
+5V
A
Y
動作表
A
Y
0V
5V
5V
0V
抽象化
0V
記号
A
Y
A
Y
0
1
1
0
論理関数から論理回路へ
論理関数と論理回路との対応例
S(X, Y)  X  Y X Y  X Y （排他的論理和）
X
真理値表
動作表
NOT
0
Y X
0 1
0
1
1
1
XY Y
X Y
X  Y X Y
0
1
0
0
1
1
0
0
1
0
0
0
1
1
1
1
0
0
0
0
0
AND
X
OR
Y
S（X,Y）
NOT
AND
入力X,Yに対する出
力Sと考えれば関数S
（X,Y）である
半加算器（1）
半加算器（Half Adder）
２進数１桁の和
0+0=0, 0+1=1, 1+0=1, 1+1=10
動作表
入力
回路図
出力
X
Y
C
S
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
X
C
H.A.
Y
S
半加算器（2）
半加算器（Half Adder）
C(X, Y)  X Y
論理関数
X
Y
C
半加算器（3）
排他的論理和
半加算器（Half Adder）
論理関数 S(X, Y)  X  Y X Y  X Y
NOT
AND
X
OR
Y
S
NOT
記号
X
Y
AND
S
排他的OR回路
半加算器（4）
半加算器（Half Adder）
回路図
AND
X
C
Y
排他的OR
S
X
C
H.A.
Y
S
全加算器（1）
全加算器（Full Adder）
２進数１桁の和の計算
下の桁からの繰り上がりC’も和に入れる
動作表
入力
出力
X
Y
C’
C
S
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
1
1
0
1
0
1
1
0
1
1
1
1
1
回路図
X
C
Y
C’
F.A.
S
全加算器（2）
全加算器（Full Adder）
論理関数
S(X, Y, C)  X  Y C  X Y  C  X  Y  C X Y C
 
 X Y   C
回路図
C1
X
Y
C’
H.A.
X Y
H.A.
C2
S
全加算器（3）
全加算器（Full Adder）
論理関数
C(X, Y)  X Y C  X  Y C X Y  C X Y C
 
 X Y  X Y   C
回路図
C1
X
Y
C’
H.A.
C
S1
H.A.
C2
S
全加算器（4）
全加算器（Full Adder）
回路図
X
Y
C
H.A.
H.A.
C’
S
X
C
Y
C’
F.A.
S
２進数加算器（1）
2進数加算器の構成
（ X3 X2 X1 X0 ）2
+）（ Y3 Y2 Y1 Y0 ）2
（ S3 S2 S1 S0 ）2
FA4 FA3 FA2 FA1
X3 Y3
X2 Y2
C’2
C’3
F.A.4
F.A.3
C2
C4
桁あふれ
S3
X1 Y1
C’1
F.A.2
C1
S2
C’3=0
X0 Y0
F.A.1
C0
S1
S0
２進数加算器（2）
F.A.の動作表
計算例
（ 0101 ）2+（0111）2= （1100）2
0 0
1
1
F.A.
1
1
1
1
F.A.
1
0
Y
C’
C
S
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
1
1
0
1
0
1
1
0
1
1
1
1
1
0
1
F.A.
F.A.
1
1
1
1
0
0
1
X
0
論理回路のまとめ
• リレーは何個ぐらい必要か？
– 半加算器
AND回路3個+OR回路1個+ＮＯＴ回路2個
＝リレー10個
– 全加算器
半加算器2個+OR回路１個
=リレー22個
– 64ビット２進数加算器
全加算器６４個
= リレー22個×64=1408個
１０進数で1.8×1019 (=264）まで計算可能
加算から減算・乗算・割算へ（1）
• 減算
– 補数表現（ビットによる負の数の表示）
十進数
補数表現
ビット反転
十進数
補数表現（ビット反転+1)
-8
1000
7
0111
1000
-7
1001
6
0110
1001
-6
1010
5
0101
1010
-5
1011
4
0100
1011
-4
1100
3
0011
1100
-3
1101
2
0010
1101
-2
1110
1
0001
1110
-1
1111
0
0000
加算から減算・乗算・割算へ（2）
• 減算
– 減算=負の数の和
（例）5-2 =5+(-2)
-2の補数
表現
0101 （510）
+)
1110 （-210）
10011 （310）
桁あふれ
は気にし
ない
加算から減算・乗算・割算へ（3）
• 乗算：加算の繰り返し
• 割算：減算の繰り返し
×)
0101 （510）
0011
0011 （310）
0101 ) 1111
0101
+) 0101
1111 （1510）
101
0101
0101
0

Download Report