基本情報技術概論 (第３回) 演算と論理回路埼玉大学理工学研究科堀山貴史 1 前回の復習  数値の表現方法  文字の表現方法  ASC I I コード  J I S コード、シフト JIS、EUC、Unicode  演算  四則演算 (＋, －, ×, ÷) １０１００＋０１１０１０１０ 10進法での筆算と同じようにできる  ２進数では、０, １を操作すれば実現できる  2 論理演算 3 論理演算  ２進数の四則演算（＋, －, ×, ÷）は、０, １を操作すれば実現できる  与えられた０, １（入力）から、計算結果の０, １（出力）を得る仕組みを作ろう！例） NOT ：入力の否定（０，１を反転させる）入力Ａ出力ｆＡｆ０１１０（真理値表） 4 論理演算ＮＯＴ（否定）ＡＮＤ（論理積）ＯＲ（論理和）ＸＯＲ（排他的論理和）回路記号ＡＡＢＡＢＡＢｆ真理値表Ａ０１ｆ１０Ｂ０１０１ｆｆＡ００１１Ｂ０１０１ｆｆＡ００１１Ｂ０１０１ｆｆＡ００１１０００１０１１１０１１０論理式ｆ = Ａｆ =￢Ａｆ = Ａ・Ｂｆ = Ａ∧Ｂｆ = Ａ＋Ｂｆ = Ａ∨Ｂｆ = Ａ＋Ｂ 5 論理演算：ＮＡＮＤ論理演算ＮＯＴ（否定）ＡＮＤ（論理積）ＮＡＮＤ回路記号ＡＡＢＡＢｆ真理値表Ａ０１ｆ１０Ｂ０１０１ｆｆＡ００１１Ｂ０１０１ｆｆＡ００１１０００１１１１０論理式ｆ = Ａｆ =￢Ａｆ = Ａ・Ｂｆ = Ａ∧Ｂｆ = Ａ・Ｂｆ = Ａ∧Ｂ 6 論理演算：ＮＯＲ論理演算ＮＯＴ（否定）ＯＲ（論理和）ＮＯＲ回路記号ＡＡＢＡＢｆ真理値表Ａ０１ｆ１０Ｂ０１０１ｆｆＡ００１１Ｂ０１０１ｆｆＡ００１１０１１１１０００論理式ｆ = Ａｆ =￢Ａｆ = Ａ＋Ｂｆ = Ａ∨Ｂｆ = Ａ＋Ｂｆ = Ａ∨Ｂ 7 練習：  ビット演算各ビットごとに、指示された論理演算を行う 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 AND 0 0 0 0 1 1 1 1 AND 0 0 0 0 1 1 1 1 AND 0 0 0 0 1 1 1 1 マスク演算（この部分は演算結果が必ず０になる） 8 練習：ビット演算 1 1 0 0 1 1 0 0 OR 0 0 0 0 1 1 1 1 OR 0 0 1 1 0 0 1 1 OR 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 マスク演算（この部分は演算結果が必ず１になる） 9 練習：ビット演算 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 XOR 0 0 0 0 1 1 1 1 XOR 0 0 1 1 0 0 1 1 XOR 0 0 0 0 1 1 1 1 ビット反転（この部分はビットが反転する）０クリア（同じものの XOR は、全ビット０になる） 10 論理回路  ２進数の四則演算（＋, －, ×, ÷）は、０, １を操作すれば実現できる  論理素子 (NOT, AND, OR, …)  ０, １の入力から、０, １の出力を得る仕組み  論理回路  論理素子を用いて、論理演算を実現する  組合せ回路と順序回路に分類できる 11 組合せ回路 ________________  現在の入力のみから出力が決められる回路 ________________ 例）半加算器 (half adder) … 入力Ａ, Ｂを加算し、その桁の和 (Sum) Ｓと桁上げ (Carry) Ｃを出力１０１＋１１０入力出力ＡＢＣＳ００１１０００１０１０１０１１０ＡＢＣＳ 12 例) 全加算器  (full adder) 入力されたＡ, Ｂ, Ｃ in を加算し、その桁の和Ｓと桁上げＣout を出力入力出力ＡＢＣin Ｃout Ｓ００００１１１１００１１００１１０１０１０１０１１１０１＋１１０００００１０１１１０１１０１００１ＡＣout ＢＣin Ｓ 13 例）加算器１１１１０１０１＋１１１１０１００Ｃ3 Ｓ3 Ｃ2 Ｓ2 Ｃ1 Ｓ1 Ｃ0 Ｓ0 全加算器全加算器全加算器半加算器Ａ3 Ｂ3 Ａ2 Ｂ2 Ａ1 Ｂ1 Ａ0 Ｂ0 14 論理回路と論理式  次の論理回路と論理式は等価？ X C Y S Z  S = X + Y + Z C = X・Y + Y・Z + Z・X 真理値表で確かめるＸ００００１１１１Ｙ００１１００１１Ｚ０１０１０１０１Ｃ０００１０１１１Ｓ０１１０１００１Ｘ００００１１１１Ｙ００１１００１１Ｚ０１０１０１０１Ｃ０００１０１１１Ｓ０１１０１００１ 15 カルノー図参考：  論理回路の設計に利用するＸ００００１１１１真理値表カルノー図 XY Z Ｙ００１１００１１Ｚ０１０１０１０１Ｃ０００１０１１１Ｓ０１１０１００１論理回路 X C Y Z 論理式 00 01 11 10 0 0 0 1 0 1 0 1 1 1 C = X・Y + Y・Z + Z・X 16 順序回路 ________________    記憶を保持することができる記憶（内部状態）と現在の入力から出力が決められる回路 ________________ 論理素子がループしている部分がある例）フリップフロップ（S R フリップフロップなど）カウンタ 17 例） S R フリップフロップＳＲＱｎＱｎ入力内部状態出力ＳＲＱn-1 Ｑｎ０００００１０１内部状態保持０１０１０１００リセット１０１００１１１セット１１１１０１－－禁止入力 18 例） S R フリップフロップＳＲ１０１００１０１ＱｎＱｎ入力内部状態出力ＳＲＱn-1 Ｑｎ０００００１０１内部状態保持０１０１０１００リセット１０１００１１１セット１１１１０１－－禁止入力 19 20 練習問題：  組合せ回路 (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)) 21 22 練習：  ビット演算各ビットごとに、指示された論理演算を行う 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 AND 0 0 0 0 1 1 1 1 AND 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 AND 0 0 0 0 1 1 1 1 マスク演算（この部分は演算結果が必ず０になる） 23 練習：ビット演算 1 1 0 0 1 1 0 0 OR 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 OR 1 1 0 0 1 1 1 1 OR 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 マスク演算（この部分は演算結果が必ず１になる） 24 練習：ビット演算 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 XOR 0 0 0 0 1 1 1 1 XOR 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 XOR 0 0 0 0 1 1 1 1 ビット反転（この部分はビットが反転する）０クリア（同じものの XOR は、全ビット０になる） 25 26 27 この教材のご利用について     この文面は、TOKYO TECH OCW の利用条件を参考にしましたこの教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。非商業利用に限定  この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。著作権の帰属  この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。同一条件での頒布・再頒布  この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件28 この教材のご利用について  配布場所  http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/  この powerpoint ファイルの著作者  堀山貴史 2007-2009 [email protected]  改変等を加えられた場合は、お名前等を追加してください図の著作者  p. 4, 8, 9, 10, 18, 19, 23, 24, 25  クリップアート : Microsoft Office Online / クリップアート  その他  堀山貴史  29