論理回路

プログラミング論 I
2008年7月11日
論理回路(and,or,not)を作成．
回路を組み合わせ半/全加算器．
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/
H-1
おまけ：getchar() 1/4
• getchar() とは？
• キーボードから1文字読み込み，その文字
CODEを取得する関数．
• 入力されるのを待つので，人間がキーを叩
くまでプログラムは停止する．
– 正しくは“キーボードから”でなく，“標準入力
から”読み込む．
– “標準入力”は，通常はキーボードだが，パイ
プやリダイレクトにより変えることができる．
H-2
#include <stdio.h>
void main(){
int i;
printf("Hello,World!! ");
printf("(No.0)\n");
getchar() 2/4
printf("Please hit Enter key.");
i = getchar();
printf("Hello,World!! ");
printf("(No.1)\n");
}
ここで
一端停止
する
実行結果
Hello,World!! (No.0)
Please hit Enter key.[人間がEnterを押す]
Hello,World!! (No.1)
H-3
getchar() 3/4
• Windows+VisualStudioでありがちな状況．
– プログラムを実行し，
途中でprintf()などにより文字が出力され，
プログラムが無事終了し
Windowが自動的に閉じてしまう．
– 結果，途中で出力した文字が消えてしまい，
実行(出力)結果を人間が確認できない．
– このような場合は，最後にgetchar()を入れ
る．そうすれば，人間がEnterを押すまでプロ
グラムが止まってくれる．
H-4
getchar() 4/4
#include <stdio.h> キーボードからの入力を待ち，
入力されたキーの文字コード
void main(){
をiに代入．
int i;
do {
i = getchar();
printf("You typed [%c].\n\n", i);
} while ( i != '.' );
}
入力された文字を表示．
%cはchar型(文字型)を
表示する．
H-5
論理回路(and,or,not)
の作成．
回路を組み合わせ
半/全加算器を作成
H-6
BTW... 演算子とは?
• 算数の足し算 + とは？
3 + 4 = 7
3 と 4 の演算結果が，7である．
3 と 4 を入力すると，7が出力される．
H-7
ブール論理
(Boolean logic)
• 0と1(真と偽)を論理体系．
• それを扱う代数が，ブール代数．
– 論理否定(not),論理和(or)，論理積
(and)の3演算より構成される．
– 登場する値は“真”と“偽”のみ．
• 0と1と考えてもよい．これはdigitalである．
– 基本は，四則演算(+-*/)より単純
• ただし，多くの場合は大量に登場する
H-8
論理値
• “真”と“偽”の二値
– 通常，真を1，偽を0と表現する．
– つまり，“整数の足し算”よりも単純で簡単？
H-9
演算
• 基本的な演算
– not(論理否定),or(論理和),
and(論理積)
• 応用的な演算
– 基本的な演算を組み合わせることにより表現
可能だが，よく使われる演算．
– xor(排他的論理和),nor(否定論理和),
nand(否定論理積)など
• 例えば,P nand Q = not( P and Q )
H-10
論理否定 (not)
• 論理値を反転する演算．
– 表記は￢P や not P や P など.
単項演算子．
Pが真のとき，￢Pは偽.
￢真 = 偽
P
￢1 = 0
偽
Pが偽のとき，￢Pは真.
0
￢偽 = 真
真
￢0 = 1
1
注意：0と1以外の値は存在しない．
￢P
真
1
偽
0
H-11
論理和 (or)
• どれが一つでも真なら，演算結果は真.
– 表記は，P∨Q や P or Q
– 多項演算子
– 日本語の“または”に
近い(が少し異なる)．
– P+Q+R
=(P+Q)+R=P+(Q+R)
や P+Q など．
P
Q
P∨Q
0
0
0
0
1
1
1
0
1
1
1
1
これは，足し算に近い？ H-12
論理積 (and)
• 全てが真のとき限り，演算結果は真.
– 表記は，P∧Q や P and Q
– 多項演算子
– 日本語の“かつ”に
近い．
– P・Q・R
=(P・Q)・R=P・(Q・R)
や P・Q など．
P
Q
P∨Q
0
0
0
0
1
0
1
0
0
1
1
1
これは，まさにかけ算 H-13
排他的論理和 (xor)
• 論理和に近いが，1xor1=0
– 表記は，P xor Q や P  Q など．
– exclusive or
– PとQが異なれば 1
PとQが同じななら 0
– P Q R
=(P  Q)  R
=P  (Q  R)
P
Q
P∨Q
0
0
0
0
1
1
1
0
1
1
1
0
論理和に近いが排他的？ H-14
否定論理和 (nor)
• P nor Qは, not(P or Q)
• 本講義では扱わない
P
Q
P∨Q
0
0
1
0
1
0
1
0
0
1
1
0
H-15
否定論理積 (nand)
• P nand Qは, not(P and Q)
– nandを組み合わせれば，
not,and,orなど
P
全てを表現できる．
• 本講義では扱わない
Q
P∨Q
0
0
1
0
1
1
1
0
1
1
1
0
H-16
“or” と日本語“または”
• 「国語90点以上」または「算数90点以上」
の人は授業料免除です．
– 両方満たした人も含む．“or”と同じ．
– 「少なくとも1個が成り立てば」の意味．
• コーヒーまたは紅茶がつきます．
– 両方つくことはない．これは“xor”と同じ．
• 電車代またはガソリン代を請求します．
– 両方請求することはない．“xor”と同じ．
H-17
Bool代数
• ￢(￢P)=P
2回反転すると，元に戻る．
• ドモルガンの法則
￢(P∧Q) = (￢P)∨(￢Q)
￢(P∨Q) = (￢P)∧(￢Q)
H-18
Bool代数
• P  Qは，(Pに対して，  Qが施されたと考える)
– Qが0ならP． Qが1なら￢P．
つまり， 0は値を保持， 1は値を反転．
– P  Q  R  S  Tは
1が登場するたびに反転するので，
1が偶数個の場合→計算結果は 0
1が奇数個の場合→計算結果は 1
H-19
論理回路
• 0 と 1 の情報の演算を処理する回路．
– 計算機, CPUは基本的にこれら回路の組み合
わせ．これらを組み合わせると計算ができる．
– ディジタル(電子)回路などと呼ばれる
H-20
論理回路
not
and
or
xor
H-21
論理回路
x
z
x
y
not
z
or
入力
x
出力
z
入力
x
入力
y
出力
z
0
1
0
0
0
1
0
0
1
1
1
0
1
1
1
1
左から0を入れると，
右から1が出てくる回路．
H-22
論理回路
x
y
z
x
y
z
xor
and
入力
x
入力
y
出力
z
入力
x
入力
y
出力
z
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
H-23
論理回路の例
• 下の回路に(左から) 1 と 0 を入力すると，
(右から) 1 が出力される．
1
1
or
0
1
1
1
1
0
0
and
0
0 not
and
1
1
H-24
加算器
• not,or,andを組み合わせると“加算処
理装置”を作ることができる．
• 2進数の加算器を考える．
– 例えば，
10進数:
5 +
1 =
6
2進数: 101 + 001 = 110
H-25
半加算器 (half adder)
• 1桁の2進数 A と B を入力し，
その和を出力する回路考える．
– ただし，下の桁からの繰り上がりは考えない．
• 1桁の2進数は，真偽値(0か1)が1個．
• つまり，2個の真偽値を入力すると，
2個の真偽値が出力される回路．
– 注意：桁が繰り上がる事があるので，
1桁同士の加算結果は，2桁になることがある．
H-26
半加算器 (half adder)




0
0
1
1
と
と
と
と
0
1
0
1
の加算→ 0
の加算→ 1
の加算→ 1
の加算→10
入力
A
入力
B
出力
C
出力
S
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
(上桁
(上桁
(上桁
(上桁
0,
0,
0,
1,
下桁
下桁
下桁
下桁
0)
1)
1)
0)
上の桁の出力結果をC，
下の桁の出力結果をS
とるす．
上の桁は繰り上がり
(Carry Out)と呼ばれる．
H-27
半加算器 (上の桁)
入A 入B 出C
0
0
1
• A と B の両方が 1 のときのみ， 1
C が 1 となる．
A
B
and
0
1
0
1
0
0
0
1
C
H-28
半加算器 (下の桁)
入A 入B
0
0
1
• (A と B の少なくとも片方が 1 ) 1
かつ (“A と B の両方が 1”でない)
が成り立つとき，S が 1 と考える．
A
0
1
1
0
or
and
B
0
1
0
1
出S
and
S
not
H-29
半加算器
• 2入力の加算器が完成
A
or
入A 入B 出C 出S
0
0
1
1
and
0
1
0
1
0
0
0
1
0
1
1
0
S
not
B
and
C
H-30
全加算器 (full adder)
• 1桁の加算器を桁数分組み合わせれば，
n桁の2進数同士の加算器が作成可能．
• ただし，一番下の桁以外は，
下の桁からの繰り上がりを
1 Carry
考慮するする必要がある．
繰り上がりも考慮し，
結局この3個を
足す必要がある．
1
+) 0
1
0
0
1
1
1
0
H-31
全加算器 (full adder)
• 1桁の2進数3個 A と B と c を入力し，
その和を出力する回路考える．
出力は，繰り上がりとその桁の２個．
入力
A
入力
B
入力
C0
出力
C1
出力
S
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
H-32
全加算器 (full adder)
A
or
and
S
not
B
and
C
先ほど作成した上の回路を，
“Half Adder”という一つの回路と定義する．
Half
Adder
S
C
“Half Adder”は, 2入力2出力の回路．
内部構成は忘れて良い.
原理が分からなくても使えればよい．
入出力の関係さえ理解していればよい．
Black Boxという．
H-33
全加算器 (full adder)
A
B
Half S
Adder
C
Half S
Adder
C
S
C
or
C
H-34
4桁2進数同士の加算回路
• 4桁2進数 A3A2A1A0 と B3B2B1B0 を
入力し，その加算結果，
S4S3S2S1S0を出力する回路を考える．
• ただし，A3A2A1A0 は
A3*8 + A2*4 + A1*2 + A0
H-35
4桁2進数同士の加算回路
• 先ほど作成した下の回路を，“Full
Adder”という一つの回路と定義する．
A
B
C
Half S
Adder
C
Half S
Adder
C
or
S
A Full
B Adder
C
C
S
C
入力のA,B,Cは
省略する．
入れ替えても
結果は同一
H-36
4桁2進数同士の加算回路
A0B0
A1B1
A2B2
A3B3
FA
FA
FA
HA
C
C
C
C
S
S
S
S
S0
S1
S2
S3
S4
H-37
C言語で回路を模倣
• not回路
– 1入力1出力の関数で模倣できる．
入力値を反転した物を返す．
char not(char a){
if( a == 1 ){
return 0;
} else {
return 1;
}
}
H-38
C言語で回路を模倣
• or回路
– 2入力1出力の関数で模倣できる．
2個の入力の論理和演算結果を返す．
char or(char a, char b){
if( a == 1 || b == 1 ){
return 1;
} else {
return 0;
}
}
H-39
C言語で回路を模倣
• and回路
– 2入力1出力の関数で模倣できる．
2個の入力の論理積演算結果を返す．
char and(char a, char b){
if( a == 1 && b == 1 ){
return 1;
} else {
return 0;
}
}
H-40
A
or
B
and
C
char lc00(char a, char b, char, c){
return and(or(a,b),c);
}
H-41
A
B
or
and
Y
X
not
and
S
Z
char ha_s(char a, char b){
char x, y, z;
x = or(a,b);
y = and(a,b);
z = not(y);
return and(x,z);
}
H-42
A
B
or
and
Y
X
not
and
S
Z
char ha_s(char a, char b){
return
and(
or(a,b), not(and(a,b))
);
}
1文で書くと．
H-43
A
B
and
C
char ha_c(char a, char b){
return and(a,b);
}
H-44
A
B
Half S
Adder
C
X
Ci
Half S
Adder
C
or
S
Z
Co
Y
char fa_s(char a, char b, char ci){
char x;
x = ha_s(a,b);
return ha_s(x,c);
}
H-45
A
B
Half S
Adder
C
X
Ci
Half S
Adder
C
or
S
Z
Co
Y
char fa_c(char a, char b, char ci){
char x, y, z;
x = ha_s(a,b);
y = ha_c(a,b);
z = ha_c(x,c);
return or(z,y);
}
H-46
4桁2進数同士の加算回路
A0B0
A1B1
A2B2
A3B3
FA
FA
FA
HA
C X
C
Y
C
Z
C
S
S
S
S
S0
S1
S2
S3
S4
H-47
void adder( char a3, char a2, char a1, char a0,
char b3, char b2, char b1, char b0){
char s4, s3, s2, s1, s0;
char x, y, z;
s0 = ha_s(a0,b0);
x = ha_c(a0,b0);
4桁2進数同士の
加算回路
s1 = fa_s( a1, b1, x);
y = fa_c( a1, b1, x);
s2 = fa_s( a2, b2, y);
z = fa_c( a2, b2, y);
注意：
本関数は，
演算結果を返すのではなく
演算結果を表示する．
s3 = fa_s( a3, b3, z);
s4 = fa_c( a3, b3, z);
printf("%d%d%d%d + ", a3, a2, a1, a0);
printf("%d%d%d%d = ", b3, b2, b1, b0);
printf("%d%d%d%d%d\n", s4, s3, s2, s1, s0);
}
H-48
練習 0
#include <stdio.h>
void f0(){
printf("f0 S!\n");
printf("f0 E!\n");
}
実行結果は
どのようになるか？
void main(){
printf("main S!\n");
f0();
printf("main E!\n");
}
H-49
解答 0
main S!
f0 S!
f0 E!
main E!
H-50
#include <stdio.h>
void f0(){
printf("f0
printf("f0
}
void f1(){
printf("f1
f0();
printf("f1
}
練習 1
S!\n");
E!\n");
実行結果は
どのようになるか？
S!\n");
E!\n");
void main(){
printf("main S!\n");
f1();
printf("main E!\n");
}
H-51
解答 1
main S!
f1 S!
f0 S!
f0 E!
f1 E!
main E!
H-52
#include <stdio.h>
void f0(){
printf("f0
printf("f0
}
void f1(){
printf("f1
f0();
printf("f1
}
void f2(){
printf("f2
f0();
f1();
printf("f2
}
練習 2
S!\n");
E!\n");
実行結果は
どのようになるか？
S!\n");
E!\n");
S!\n");
E!\n");
void main(){
printf("main S!\n");
f2();
printf("main E!\n");
}
H-53
解答 2
main S!
f2 S!
f0 S!
f0 E!
f1 S!
f0 S!
f0 E!
f1 E!
f2 E!
main E!
H-54
練習 3
• 下記の回路に左から0と1を入力すると，
右から0と1のどちらが出力されるか？
0
not
or
or
1
S
and
H-55
解答 3
0
0
or
1
1 not
1
0
0
1
0
1
and
0
0
or
0
S
H-56

Download Report