基本情報技術概論（第３回） 埼玉大学 理工学研究科 堀山 貴史

Presentation on theme: "基本情報技術概論（第３回） 埼玉大学 理工学研究科 堀山 貴史"— Presentation transcript:

1 基本情報技術概論（第３回） 埼玉大学 理工学研究科 堀山 貴史
2008/5/8 基本情報技術概論 (第３回) 演算 と 論理回路 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

2 前回の復習 数値の表現方法 文字の表現方法 ASC I I コード J I S コード、シフト JIS、EUC、Unicode 演算
四則演算 (＋, －, ×, ÷) 10進法での筆算と同じようにできる ２進数では、０, １ を操作すれば実現できる １ 　 ０１００ ＋ ０１１０ １ ０ １ ０

3 論理演算

4 論理演算 ２進数の四則演算 （＋, －, ×, ÷） は、 ０, １ を操作すれば実現できる 与えられた ０, １ （入力） から、
　　０, １ を操作すれば実現できる 与えられた ０, １ （入力） から、 　　計算結果の ０, １ （出力） を得る仕組みを作ろう！ 例） NOT ： 入力の否定 （０，１ を反転させる） 入力 出力 Ａ ｆ ０ １ １ ０ Ａ ｆ （真理値表）

5 論理演算 回路記号 真理値表 論理式 ＮＯＴ （否定） ＡＮＤ （論理積） ＯＲ （論理和） ＸＯＲ （排他的 ｆ = Ａ ｆ = ￢ Ａ
Ａ　 ｆ ０　 １ １　 ０ ｆ = Ａ ｆ = ￢ Ａ Ａ ｆ ｆ = Ａ ・ Ｂ ｆ = Ａ ∧ Ｂ Ａ Ｂ　 ｆ ０ ０　 ０ ０ １　 ０ １ ０　 ０ １ １　 １ Ａ Ｂ ｆ ＡＮＤ （論理積） Ａ Ｂ　 ｆ ０ ０　 ０ ０ １　 １ １ ０　 １ １ １　 １ ｆ = Ａ ＋ Ｂ ｆ = Ａ ∨ Ｂ Ａ Ｂ ｆ ＯＲ （論理和） Ａ Ｂ ｆ Ａ Ｂ　 ｆ ０ ０　 ０ ０ １　 １ １ ０　 １ １ １　 ０ ｆ = Ａ ＋ Ｂ ＸＯＲ （排他的 論理和）

6 論理演算： ＮＡＮＤ 論理演算 回路記号 真理値表 論理式 ＮＯＴ （否定） ＡＮＤ （論理積） ＮＡＮＤ ｆ = Ａ ｆ = ￢ Ａ Ａ
論理演算： ＮＡＮＤ 論理演算 回路記号 真理値表 論理式 ＮＯＴ （否定） Ａ　 ｆ ０　 １ １　 ０ ｆ = Ａ ｆ = ￢ Ａ Ａ ｆ Ａ Ｂ　 ｆ ０ ０　 ０ ０ １　 ０ １ ０　 ０ １ １　 １ ＡＮＤ （論理積） Ａ Ｂ ｆ ｆ = Ａ ・ Ｂ ｆ = Ａ ∧ Ｂ Ａ Ｂ　 ｆ ０ ０　 １ ０ １　 １ １ ０　 １ １ １　 ０ ｆ = Ａ ・ Ｂ ｆ = Ａ ∧ Ｂ Ａ ＮＡＮＤ ｆ Ｂ

7 論理演算： ＮＯＲ 論理演算 回路記号 真理値表 論理式 ＮＯＴ （否定） ＯＲ （論理和） ＮＯＲ ｆ = Ａ ｆ = ￢ Ａ Ａ ｆ
論理演算： ＮＯＲ 論理演算 回路記号 真理値表 論理式 ＮＯＴ （否定） Ａ　 ｆ ０　 １ １　 ０ ｆ = Ａ ｆ = ￢ Ａ Ａ ｆ Ａ Ｂ　 ｆ ０ ０　 ０ ０ １　 １ １ ０　 １ １ １　 １ ＯＲ （論理和） ｆ = Ａ ＋ Ｂ ｆ = Ａ ∨ Ｂ Ａ Ｂ ｆ Ａ Ｂ　 ｆ ０ ０　 １ ０ １　 ０ １ ０　 ０ １ １　 ０ ｆ = Ａ ＋ Ｂ ｆ = Ａ ∨ Ｂ Ａ Ｂ ｆ ＮＯＲ

8 各ビットごとに、指示された論理演算を行う
練習：　ビット演算 各ビットごとに、指示された論理演算を行う 1 1 1 1 1 1 1 1 AND AND 1 1 1 1 1 1 1 1 AND 1 1 1 1 マスク演算 （この部分は演算結果が必ず ０ になる）

9 マスク演算 （この部分は演算結果が必ず １ になる）
練習：　ビット演算 1 1 1 1 1 1 1 1 OR OR 1 1 1 1 1 1 1 1 OR 1 1 1 1 マスク演算 （この部分は演算結果が必ず １ になる）

10 ビット反転 （この部分はビットが反転する）
練習：　ビット演算 1 1 1 1 1 1 1 1 XOR XOR 1 1 1 1 1 1 1 1 XOR 1 1 1 1 ビット反転 （この部分はビットが反転する） ０クリア （同じものの XOR は、全ビット ０ になる）

11 論理回路 ２進数の四則演算 （＋, －, ×, ÷） は、 ０, １ を操作すれば実現できる 論理素子 (NOT, AND, OR, …)
　　０, １ を操作すれば実現できる 論理素子 (NOT, AND, OR, …) ０, １ の入力 から、０, １ の出力 を得る仕組み 論理回路 論理素子を用いて、論理演算を実現する 組合せ回路と順序回路に分類できる

12 組合せ回路 現在の入力のみから出力が決められる回路 例） 半加算器 (half adder) … 入力 Ａ, Ｂ を 加算 し、
________________ ________________ 現在の入力のみから出力が決められる回路 例） 半加算器 (half adder) … 入力 Ａ, Ｂ を 加算 し、 その桁の和 (Sum) Ｓ と 桁上げ (Carry) Ｃ を 出力 　 １ 　 ０ １ ＋ １ １ 　 　 ０ 入力 出力 Ａ Ｂ　　Ｃ Ｓ ０ ０　　０ ０ ０ １　　０ １ １ ０　　０ １ １ １　　１ ０ Ｂ Ｓ Ａ Ｃ

13 例) 全加算器 (full adder) 入力された Ａ, Ｂ, Ｃ in を 加算し、 その桁の和 Ｓ と 桁上げ Ｃout を 出力
１ １ 　 ０ １ ＋ １ １ 　 ０ ０ 入力された Ａ, Ｂ, Ｃ in を 加算し、 その桁の和 Ｓ と 桁上げ Ｃout を 出力 Ａ Ｂ Ｃin ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ 入力 出力 　 Ｓ ０ ０ ０ １ １ ０ １ １ Ｃout Ｂ Ａ Ｃin Ｃout Ｓ

14 例） 加算器 ０ １ ０ １ ＋ １ １ １ １ ０ １ ０ ０ 全加算器 Ａ3 Ｂ3 Ｓ3 Ｃ3 全加算器 Ａ2 Ｂ2 Ｓ2 Ｃ2
例） 加算器 １ １ １ １ 　 ０ １ ０ １ ＋ １ １ １ １ 　 ０ １ ０ ０ 全加算器 Ａ3 Ｂ3 Ｓ3 Ｃ3 全加算器 Ａ2 Ｂ2 Ｓ2 Ｃ2 全加算器 Ａ1 Ｂ1 Ｓ1 Ｃ1 半加算器 Ａ0 Ｂ0 Ｓ0 Ｃ0

15 論理回路 と 論理式 次の論理回路と論理式は等価？ 真理値表で確かめる S = X + Y + Z
C S = X + Y + Z Y C = X ・ Y + Y ・ Z + Z ・ X S Z Ｘ Ｙ Ｚ ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ Ｃ Ｓ ０ ０ ０ １ １ ０ １ １ Ｘ Ｙ Ｚ ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ Ｃ Ｓ ０ ０ ０ １ １ ０ １ １

16 論理回路の設計に利用する 論理回路 真理値表 論理式 カルノー図 XY 00 01 11 10 Z 1 1 1 1 1 参考： カルノー図
参考：　カルノー図 論理回路の設計に利用する Ｘ Ｙ Ｚ ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ Ｃ Ｓ ０ ０ ０ １ １ ０ １ １ 論理回路 X C Y 真理値表 Z 論理式 カルノー図 XY 00 01 11 10 Z C = X ・ Y + Y ・ Z + Z ・ X 1 1 1 1 1

17 順序回路 記憶を保持することができる 記憶 （内部状態） と 現在の入力から 出力が決められる回路 論理素子がループしている部分がある
________________ 記憶を保持することができる 記憶 （内部状態） と 現在の入力から 出力が決められる回路 論理素子がループしている部分がある 例） フリップフロップ （S R フリップ フロップなど） カウンタ ________________

18 例） S R フリップ フロップ 内部状態 入力 出力 Ｓ Ｒ Ｑn-1 ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０
０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ Ｑｎ ０ １ － Ｓ Ｑ　ｎ 内部状態保持 リセット Ｑ　ｎ Ｒ セット 禁止入力

19 例） S R フリップ フロップ 内部状態 入力 出力 Ｓ Ｒ Ｑn-1 ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０
基本情報技術概論（第３回） 2008/5/8 例） S R フリップ フロップ 内部状態 入力 出力 Ｓ Ｒ Ｑn-1 ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １ ０ １ １ １ Ｑｎ ０ １ － ０ １ ０ ０ １ １ Ｓ Ｑ　ｎ 内部状態保持 リセット Ｑ　ｎ Ｒ ０ ０ １ セット １ ０ 禁止入力

20

21 X OR Y を、NAND だけを使って表した論理式はどれか
練習問題：　組合せ回路 (H17年度 秋) X OR Y を、NAND だけを使って表した論理式はどれか ア． ((X NAND Y) NAND X) NAND Y イ． (X NAND X) NAND (Y NAND Y) ウ． (X NAND Y) NAND (X NAND Y) エ． X NAND (Y NAND (X NAND Y))

22

23 各ビットごとに、指示された論理演算を行う
練習：　ビット演算 各ビットごとに、指示された論理演算を行う 1 1 1 1 1 1 1 1 AND AND 1 1 1 1 1 1 1 1 1 1 1 1 AND 1 1 1 1 マスク演算 （この部分は演算結果が必ず ０ になる）

24 マスク演算 （この部分は演算結果が必ず １ になる）
練習：　ビット演算 1 1 1 1 1 1 1 1 OR OR 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 OR 1 1 1 1 マスク演算 （この部分は演算結果が必ず １ になる）

25 ビット反転 （この部分はビットが反転する）
練習：　ビット演算 1 1 1 1 1 1 1 1 XOR XOR 1 1 1 1 1 1 1 1 1 1 1 1 XOR 1 1 1 1 ビット反転 （この部分はビットが反転する） ０クリア （同じものの XOR は、全ビット ０ になる）

26

27

28 この文面は、TOKYO TECH OCW の利用 条件を参考にしました
この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

29 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/
この powerpoint ファイルの著作者 堀山 貴史　 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4, 8, 9, 10, 18, 19, 23, 24, 25 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史