論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器．

Presentation on theme: "論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器．"— Presentation transcript:

1 論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器．
プログラミング論 論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器．

2 配列のメモリ格納方法 int x[4][3]; は， 「長さ3の配列」が4個 であり， 「長さ4の配列」が3個 ではない？
計算機のメモリ上には，以下の順で格納されている． ｘ[0][0] ｘ[0][1] ｘ[0][2] ｘ[1][0] ｘ[1][1] ｘ[1][2] ｘ[2][0] ｘ[2][1] これは重要ではない.無理して理解する必要はない.

3 練習 A int x[100]のx[0]～x[99]には値が格納されている.
この100個をint y[100]のy[0]～y[99]にコピーするプログラムは? ヒント: y[0] = x[0]; y[1] = x[1]; : をfor文を使って作り上げれば良い.

4 C言語と関数 関数を作成し,関数呼び出すことにより これが,手続き型言語C言語の神髄(?) 積極的に関数を作成し,関数に慣れましょう.
同一/類似の処理を再度書かなくて良い 関数を組み合わせることにより,より複雑な処理を簡易に記述可能 これが,手続き型言語C言語の神髄(?) 積極的に関数を作成し,関数に慣れましょう.

5 だめな例 int main(){ void hoge(){ printf("hello\n"); } printf("abc\n");

6 論理回路(and,or,not) の作成． 回路を組み合わせ 半/全加算器を作成

7 BTW... 演算子とは? 算数の足し算 + とは？ 3 + 4 = 7 3 と 4 の演算結果が，7である．
3 と 4 を入力すると，7が出力される．

8 ブール論理 (Boolean logic) 0と1(真と偽)を論理体系． それを扱う代数が，ブール代数．
論理否定(not),論理和(or)，論理積(and)の3演算より構成される． 登場する値は“真”と“偽”のみ． 0と1と考えてもよい．これはdigitalである． 基本は，四則演算(+-*/)より単純 ただし，多くの場合は大量に登場する

9 論理値 “真”と“偽”の二値 通常，真を1，偽を0と表現する． つまり，“整数の足し算”よりも単純で簡単？

10 演算 基本的な演算 not(論理否定),or(論理和), and(論理積) 応用的な演算
基本的な演算を組み合わせることにより表現可能だが，よく使われる演算． xor(排他的論理和),nor(否定論理和), nand(否定論理積)など 例えば,P nand Q = not( P and Q )

11 論理否定 (not) 論理値を反転する演算． ￢P 真 1 偽 表記は ￢P や not P や P など. 単項演算子．
￢真 = 偽 ￢1 = 0 Pが偽のとき，￢Pは真. ￢偽 = 真 ￢0 = 1 P ￢P 偽 真 1 真 1 偽 注意：0と1以外の値は存在しない．

12 論理和 (or) どれが一つでも真なら，演算結果は真. 表記は，P∨Q や P or Q や P+Q など． 多項演算子
日本語の“または”に 近い(が少し異なる)． P+Q+R =(P+Q)+R=P+(Q+R) P Q P∨Q 1 1 1 1 1 1 1 これは，足し算に近い？

13 論理積 (and) 全てが真のとき限り，演算結果は真. 表記は，P∧Q や P and Q や P・Q など． 多項演算子
日本語の“かつ”に 近い． P・Q・R =(P・Q)・R=P・(Q・R) P Q P∨Q 1 1 1 1 1 これは，まさにかけ算

14 排他的論理和 (xor) 論理和に近いが，1xor1=0 表記は，P xor Q や P Q など． exclusive or
P Q R =(P Q) R =P (Q R) P Q P∨Q 1 1 1 1 1 1 論理和に近いが排他的？

15 否定論理和 (nor) P nor Qは, not(P or Q) 本講義では扱わない P Q P∨Q 1 1 1 1 1

16 否定論理積 (nand) P nand Qは, not(P and Q) 本講義では扱わない nandを組み合わせれば，
not,and,orなど 全てを表現できる． 本講義では扱わない P Q P∨Q 1 1 1 1 1 1 1

17 “or” と 日本語“または” 「国語90点以上」または「算数90点以上」の人は授業料免除です． コーヒーまたは紅茶がつきます．
「少なくとも1個が成り立てば」の意味． コーヒーまたは紅茶がつきます． 両方つくことはない．これは“xor”と同じ． 電車代またはガソリン代を請求します． 両方請求することはない．“xor”と同じ．

18 Bool代数 ￢(￢P)=P ドモルガンの法則 2回反転すると，元に戻る． ￢(P∧Q) = (￢P)∨(￢Q)

19 Bool代数 P Qは，(Pに対して， Qが施されたと考える) Qが0ならP． Qが1なら￢P． つまり， 0は値を保持， 1は値を反転．
つまり， 0は値を保持， 1は値を反転． P Q R S Tは 1が登場するたびに反転するので， 1が偶数個の場合→計算結果は 0 1が奇数個の場合→計算結果は 1

20 論理回路 0 と 1 の情報の演算を処理する回路． 計算機, CPUは基本的にこれら回路の組み合わせ．これらを組み合わせると計算ができる．
ディジタル(電子)回路などと呼ばれる

21 論理回路 not or and xor

22 論理回路 1 1 1 1 1 1 1 1 1 x x z z y not or 入力 x 出力 z 入力 x 入力 y 出力 z
1 1 1 1 1 1 左から0を入れると， 右から1が出てくる回路． 1 1 1

23 論理回路 1 1 1 1 1 1 1 1 1 1 1 x x z z y y xor and 入力 x 入力 y 出力 z 入力 x 入力
1 1 1 1 1 1 1 1 1 1 1

24 論理回路の例 下の回路に(左から) 1 と 0 を入力すると， (右から) 1 が出力される． 1 or and not and 1 1 1
and 1 1 1 not and 1

25 加算器 not,or,andを組み合わせると“加算処理装置”を作ることができる． 2進数の加算器を考える． 例えば，
10進数: = 6 2進数: = 110

26 半加算器 (half adder) 1桁の2進数 A と B を入力し， その和を出力する回路考える．
ただし，下の桁からの繰り上がりは考えない． 1桁の2進数は，真偽値(0か1)が1個． つまり，2個の真偽値を入力すると， 2個の真偽値が出力される回路． 注意：桁が繰り上がる事があるので　， 1桁同士の加算結果は，2桁になることがある．

27 半加算器 (half adder) 1 1 1 1 1 1 1 0 と 0 の加算→ 0 (上桁 0, 下桁 0)
0 と 1 の加算→ 1 (上桁 0, 下桁 1) 1 と 0 の加算→ 1 (上桁 0, 下桁 1) 1 と 1 の加算→10 (上桁 1, 下桁 0) 入力 A 入力 B 出力 C 出力 S 上の桁の出力結果をC， 下の桁の出力結果をS とるす． 上の桁は繰り上がり (Carry Out)と呼ばれる． 1 1 1 1 1 1 1

28 半加算器 (上の桁) 入A 入B 出C 1 1 A と B の両方が 1 のときのみ， C が 1 となる． 1 1 1 A C and B

29 半加算器 (下の桁) 1 1 1 1 (A と B の少なくとも片方が 1 ) かつ (“A と B の両方が 1”でない)
出S 1 1 1 1 (A と B の少なくとも片方が 1 ) かつ (“A と B の両方が 1”でない) が成り立つとき，S が 1 と考える． 1 1 A or and S not and B

30 半加算器 入A 入B 出C 出S 1 1 1 1 2入力の加算器が完成 1 1 1 A or and S not and C B

31 全加算器 (full adder) 1 1 0 1 +) 0 0 1 1 1 0 1桁の加算器を桁数分組み合わせれば，
n桁の2進数同士の加算器が作成可能． ただし，一番下の桁以外は， 下の桁からの繰り上がりを 考慮するする必要がある． 1 Carry +) 繰り上がりも考慮し， 結局この3個を 足す必要がある．

32 全加算器 (full adder) 1桁の2進数3個 A と B と c を入力し， その和を出力する回路考える．
出力は，繰り上がり と その桁 の２個． 入力 A 入力 B 入力 C0 出力 C1 出力 S 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

33 全加算器 (full adder) A or S and not C and B S Half Adder C 先ほど作成した上の回路を，
内部構成は忘れて良い. 原理が分からなくても使えればよい． 入出力の関係さえ理解していればよい． Black Boxという． S Half Adder C

34 全加算器 (full adder) Half Adder S C Half Adder S C A S B C or C

35 4桁2進数同士の加算回路 4桁2進数 A3A2A1A0 と B3B2B1B0 を入力し，その加算結果，
S4S3S2S1S0を出力する回路を考える． ただし，A3A2A1A0 は A3*8 + A2*4 + A1*2 + A0

36 4桁2進数同士の加算回路 先ほど作成した下の回路を，“Full Adder”という一つの回路と定義する． Half Adder S C
B or C C 入力のA,B,Cは 省略する． 入れ替えても 結果は同一 Full Adder S C A B

37 4桁2進数同士の加算回路 A0 B0 A1 B1 A2 B2 A3 B3 S0 S1 S2 S3 S4 C FA S C FA S C FA
HA S0 S1 S2 S3 S4

38 C言語で回路を模倣 not回路 char not(char a){ if( a == 1 ){ return 0; } else {
1入力1出力の関数で模倣できる． 入力値を反転した物を返す． char not(char a){ if( a == 1 ){ return 0; } else { return 1; }

39 C言語で回路を模倣 or回路 char or(char a, char b){ if( a == 1 || b == 1 ){
2入力1出力の関数で模倣できる． 2個の入力の論理和演算結果を返す． char or(char a, char b){ if( a == 1 || b == 1 ){ return 1; } else { return 0; }

40 C言語で回路を模倣 and回路 char and(char a, char b){ if( a == 1 && b == 1 ){
2入力1出力の関数で模倣できる． 2個の入力の論理積演算結果を返す． char and(char a, char b){ if( a == 1 && b == 1 ){ return 1; } else { return 0; }

41 A or B and C char lc00(char a, char b, char, c){ 　　return and(or(a,b),c); }

42 char ha_s(char a, char b){ char x, y, z; x = or(a,b); y = and(a,b);
not Z and B 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); }

43 char ha_s(char a, char b){ return and( or(a,b), not(and(a,b)) ); }
X and S Y not Z and B char ha_s(char a, char b){ return and( or(a,b), not(and(a,b)) ); } 1文で書くと．

44 char ha_c(char a, char b){ return and(a,b); }

45 char fa_s(char a, char b, char ci){ char x; x = ha_s(a,b);
Half Adder S C X Half Adder S C A S B Z Ci or Co Y char fa_s(char a, char b, char ci){ char x; x = ha_s(a,b); return ha_s(x,ci); }

46 char fa_c(char a, char b, char ci){ char x, y, z; x = ha_s(a,b);
Half Adder S C X Half Adder S C A S B Z Ci or 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,ci); return or(z,y); }

47 4桁2進数同士の加算回路 A0 B0 A1 B1 A2 B2 A3 B3 Z Y X S0 S1 S2 S3 S4 C FA S C FA
HA X S0 S1 S2 S3 S4

48 4桁2進数同士の 加算回路 注意： 本関数は， 演算結果を返すのではなく 演算結果を表示する．
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); 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); } 4桁2進数同士の 加算回路 注意： 本関数は， 演算結果を返すのではなく 演算結果を表示する．

49 練習 B 下記の回路に左から0と1を入力すると， 右から0と1のどちらが出力されるか？ not or or S and 1