2008年7月11日 論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器． プログラミング論 I 2008年7月11日 論理回路(and,or,not)を作成． 回路を組み合わせ半/全加算器． http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/

おまけ：getchar() 1/4 getchar() とは？ キーボードから1文字読み込み，その文字CODEを取得する関数． 入力されるのを待つので，人間がキーを叩くまでプログラムは停止する． 正しくは“キーボードから”でなく，“標準入力から”読み込む． “標準入力”は，通常はキーボードだが，パイプやリダイレクトにより変えることができる．

getchar() 2/4 #include <stdio.h> void main(){ int i; printf("Hello,World!! "); printf("(No.0)\n"); printf("Please hit Enter key."); i = getchar(); printf("(No.1)\n"); } getchar() 2/4 ここで 一端停止 する 実行結果 Hello,World!! (No.0) Please hit Enter key.[人間がEnterを押す] Hello,World!! (No.1)

getchar() 3/4 Windows+VisualStudioでありがちな状況． プログラムを実行し， 途中でprintf()などにより文字が出力され， プログラムが無事終了し Windowが自動的に閉じてしまう． 結果，途中で出力した文字が消えてしまい， 実行(出力)結果を人間が確認できない． このような場合は，最後にgetchar()を入れる．そうすれば，人間がEnterを押すまでプログラムが止まってくれる．

getchar() 4/4 #include <stdio.h> void main(){ int i; do { キーボードからの入力を待ち， 入力されたキーの文字コードをiに代入． #include <stdio.h> void main(){ int i; do { i = getchar(); printf("You typed [%c].\n\n", i); } while ( i != '.' ); } 入力された文字を表示． %cはchar型(文字型)を 表示する．

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

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

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

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

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

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

論理和 (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 これは，足し算に近い？

論理積 (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 これは，まさにかけ算

排他的論理和 (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 論理和に近いが排他的？

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

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

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

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

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

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

論理回路 not or and xor

論理回路 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

論理回路 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

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

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

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

半加算器 (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

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

半加算器 (下の桁) 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

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

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

全加算器 (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

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

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

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

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

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

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; }

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; }

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; }

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

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); }

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文で書くと．

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

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,c); }

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,c); return or(z,y); }

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

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

練習 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"); }

解答 0 main S! f0 S! f0 E! main E!

練習 1 実行結果は どのようになるか？ #include <stdio.h> void f0(){ printf("f0 S!\n"); printf("f0 E!\n"); } void f1(){ printf("f1 S!\n"); f0(); printf("f1 E!\n"); 実行結果は どのようになるか？ void main(){ printf("main S!\n"); f1(); printf("main E!\n"); }

解答 1 main S! f1 S! f0 S! f0 E! f1 E! main E!

練習 2 実行結果は どのようになるか？ #include <stdio.h> void f0(){ printf("f0 S!\n"); printf("f0 E!\n"); } void f1(){ printf("f1 S!\n"); f0(); printf("f1 E!\n"); void f2(){ printf("f2 S!\n"); f1(); printf("f2 E!\n"); 実行結果は どのようになるか？ void main(){ printf("main S!\n"); f2(); printf("main E!\n"); }

解答 2 main S! f2 S! f0 S! f0 E! f1 S! f1 E! f2 E! main E!

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

解答 3 1 1 not or 1 or S and 1 1