9. 演算回路 五島 正裕.

Slides:



Advertisements
Similar presentations
2009/11/10 10 進数と r 進数を相互に変換できる コンピュータのための数を表現できる 2進数の補数を扱える コンピュータにおける負の数の表現を説明で きる コンピュータでの演算方法を説明できる 文字や記号の表現方法を示せる 第7回 今日の目標 § 2.2 数の表現と文字コード.
Advertisements

平成 27 年 10 月 21 日. 【応用課題 2-1 】 次のビット列は、ある 10 進数を 8 ビット固定小数点表示で表した時の ものです。ただし、小数点の位置は 3 ビット目と 4 ビット目の間としてお り、負数は2の補数で表しています。このとき、元の 10 進数を求めてく ださい。
7章 情報の表現と基礎理論. 数の表現(書き方) 「数」と「数の書き方」をわけて考える 「数の書き方」と,「数そのものの性質」は別のもの 例:13 は素数・・・”13”という書き方とは無関係 ここでは書き方(表現方法)について考える 567.
第7章 計算の機構.
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
10進数 Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 例: 3271 = (3×103) + (2×102) + (7×101) + (1×100) 8進数 Digits: 0, 1, 2, 3, 4, 5, 6, 7 例: 3271 = (3×83) + (2×82)
全加算回路 A, Bはそれぞれ0または1をとるとする。 下位桁からの繰り上がりをC1とする。(0または1)
第5回 ディジタル回路内の数値表現 瀬戸 ディジタル回路内部で,数を表現する方法(2進数)を学ぶ 10進数⇔2進数⇔16進数の変換ができる
計算機システムⅡ 命令セットアーキテクチャ
計算機基礎Ⅱ,Ⅲ (指導書 pp. 76~94) 改訂:佐竹 純二 (作成:岡本 吉央).
補数 n:桁数、b:基数 bの補数 bn-x 253(10進数)の10の補数は、 =747
2016年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
基本情報技術概論(第3回) 埼玉大学 理工学研究科 堀山 貴史
8. 順序回路の簡単化,機能的な順序回路 五島 正裕.
5. 機能的な組み合わせ回路 五島 正裕.
香川大学工学部 富永浩之 情報数学1 第3-2章 情報量と二進法での四則演算 香川大学工学部 富永浩之
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
ICトレーナーの構成 7セグメントLED ブレッドボード XOR OR AND NAND 電源端子 スイッチ端子 LED端子 データLED
第6回 よく使われる組合せ回路 瀬戸 重要な組合せ回路を理解し、設計できるようにする 7セグディスプレイ用デコーダ 加算回路・減算回路
アルゴリズムとチューリングマシン 「もの」(商品)としてのコンピュータ 「こと」(思想)としてのコンピュータ アルゴリズム
高速剰余算アルゴリズムとそのハードウェア実装についての研究
第5回 今日の目標 §1.6 論理演算と論理回路 ブール代数の形式が使える 命題と論理関数の関係を示せる
岩村雅一 知能情報工学演習I 第8回(C言語第2回) 岩村雅一
プログラミング演習Ⅱ 課題4第3週 画像処理 (1) ビット演算子.
第4回 コンピューティングの要素と構成 平成22年5月10日(月)
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
ICトレーナーの構成 7セグメントLED ブレッドボード XOR OR AND NAND 電源端子 スイッチ端子 LED端子 データLED
第3章 演算装置.
ディジタル回路の設計と CADによるシステム設計
計算機構成 第2回 ALUと組み合わせ回路の記述
ICトレーナーの構成 7セグメントLED ブレッドボード XOR OR AND NAND 電源端子 スイッチ端子 LED端子 データLED
Ibaraki Univ. Dept of Electrical & Electronic Eng.
9. 演算回路 五島 正裕.
コンピュータアーキテクチャ 第 7 回.
コンピュータアーキテクチャ 第 7 回.
0. ディジタル回路 五島 正裕.
ディジタル回路 0. ディジタル回路 五島 正裕.
7. 機能的な組み合わせ回路 五島 正裕.
ディジタル回路 7. 機能的な組み合わせ回路 五島 正裕.
プログラミング演習I 2004年5月19日(第5回) 理学部数学科・木村巌.
ディジタル回路 五島 正裕.
ディジタル回路 9. 演算回路 五島 正裕.
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
論理回路 第12回
  第3章 論理回路  コンピュータでは,データを2進数の0と1で表現している.この2つの値,すなわち,2値で扱われるデータを論理データという.論理データの計算・判断・記憶は論理回路により実現される.  コンピュータのハードウェアは,基本的に論理回路で作られている。              論理積回路.
データの表現 2進数 0と1を使う。 基数(基準になる数)が2. 101(2) かっこで2進数と示すことがある。
コンピュータアーキテクチャ 第 2 回.
コンピュータアーキテクチャ 第 4 回.
2017年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
コンピュータアーキテクチャ 第 3 回.
基本情報技術概論(第13回) 埼玉大学 理工学研究科 堀山 貴史
メカトロニクス 12/15 デジタル回路 メカトロニクス 12/15.
コンピュータアーキテクチャ 第 4 回.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
コンピュータアーキテクチャ 第 3 回.
情報処理Ⅱ 2005年10月28日(金).
プログラムの開発手順 1.プログラム設計(仕様の決定) 2.コーディング(ソースファイルの作成) 3.アセンブル(オブジェクトファイル
ディジタル回路 8. 機能的な順序回路 五島 正裕.
ca-9. 数の扱い (コンピュータアーキテクチャとプロセッサ)
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
岩村雅一 知能情報工学演習I 第8回(C言語第2回) 岩村雅一
2014年度 プログラミングⅠ ~ 内部構造と動作の仕組み(1) ~.
香川大学創造工学部 富永浩之 情報数学1 第3-2章 情報量と二進法での四則演算 香川大学創造工学部 富永浩之
論理回路(and,or,not)を作成. 回路を組み合わせ半/全加算器.
2008年7月11日 論理回路(and,or,not)を作成. 回路を組み合わせ半/全加算器.
JavaScript    プログラミング入門 2-3 式と演算子 2006/10/12 神津 健太.
香川大学創造工学部 富永浩之 情報数学1 第3-3章 多進法での四則演算 香川大学創造工学部 富永浩之
2009年8月18日,新潟大学 「情報」と「ものづくり」 の実践教育3 下保敏和,佐藤亮一.
Presentation transcript:

9. 演算回路 五島 正裕

今日の内容 演算回路 二の補数 加算器 シフト演算器

補数表現

負の数の表現 表現される値 補数 (complement) 表現: 「上半分」を負数に充てる k 進数 k の補数 k-1 の補数 元の値

補数表現 k 進数 n 桁 k の補数 - x : kn から x を引いた値 k-1 の補数 - x : kn-1 から x を引いた値

十進数 九の補数(1桁): 9 から引く 十の補数(1桁): 10 から引く 符号なし 1 2 3 4 5 6 7 8 9 符号付き −4 1 2 3 4 5 6 7 8 9 符号付き −4 −3 −2 −1 −0 九の補数(1桁): 9 から引く 符号なし 1 2 3 4 5 6 7 8 9 符号付き −5 −4 −3 −2 −1 十の補数(1桁): 10 から引く

二進数 一の補数(3桁) 23-1 = 111 から引く ⇒ 各桁反転 二の補数(3桁) 補数表現 000 001 010 011 100 101 110 111 表現される値 1 2 3 −3 −2 −1 −0 一の補数(3桁) 23-1 = 111 から引く ⇒ 各桁反転 補数表現 000 001 010 011 100 101 110 111 表現される値 1 2 3 −4 −3 −2 −1 二の補数(3桁) 23 = 1000 から引く ⇒ 各桁反転し,1 足す

補数表現 表現される値 表現される値 +11 +11 +10 +10 +01 +01 00 00 (100) 01 10 元の値 01 10 O O 11 元の値 -01 -01 -10 一の補数 二の補数

二進数の補数表現 符号ビット (sign bit) 最上位桁(ビット)が符号を表す(0 が正,1 が負) 一の補数 と 二の補数 一の補数: ビット反転で得られる 計算が困難 二の補数 ビット反転後,+1 計算が容易

二の補数の加算 二の補数の加減算 基本的には,特に何も気にしなくてよい 符号ビットからの桁上げは無視 オーバフロー (overflow) 結果が表現できる範囲にない 符号ビットがおかしなことになる 0 (+) + 0 (+) → 1 (-) 1 (-) + 1 (-) → 0 (+)

二の補数の加算 1 1 1 1 1 1 … −1 +) 1 1 1 … −1 1 1 1 … −2 符号ビットからの桁上げ 1 1 1 1 1 1 1 1 … +3 1 1 … +3 1 … −4 1 … −4 +) 1 … +1 +) 1 1 … +3 +) 1 1 1 … −1 +) 1 … −4 1 … −4 1 1 … −2 1 1 1 … +3 1 … +0 オーバフロー

符号なし加算 z = x + y overflow 2n +1 y 2n 2n O 2n x

二の補数の加算 −, + O top view 2n O overflow +, + −, − +, − 2n 2n 2n−1 O underflow −2n−1 −2n side view

二の補数の加算 O O 符号なし加算結果を 二の補数とみなす 符号なし加算 overflow 2n +1− 1 2n − 1 2n− 1

n -bit 二の補数の和 符号ありの値 2n +1− 1 2n + 2n −1− 1 2n − 1 1...1 1 0...0 1 1...1 1 0...0 1 1...1 2n −1− 1 0...0 符号なしの値 O 1 1 1...1 − 2n −1 1 0...0 1 1...1 1 1 0...0

二の補数の加算 overflow underflow 符号なし加算結果を 二の補数とみなす 符号あり加算

加減算器

二進数の加算 1 1 +) +) 1 +) +) 1 1 1 1 桁上げ carry 和 sum 1 1 1 1 1 1 1 ← 桁上げ 1 1 1 +) +) 1 +) +) 1 1 1 1 桁上げ carry 和 sum 1 1 1 1 1 1 1 ← 桁上げ 1 1 1 1 1 1 +) 1 +) 1 1 +) 1 +) 1 1 1 1 1 1 1

半加算器,全加算器 桁上げ carry 和 sum x y cout s 1 cin x y cout s 1 1 cin x y cout s 1 半加算器 (half adder) 全加算器 (full adder)

全加算器 cout = xy + ycin + cin x s = x ^ y ^ cin xy cin 00 01 11 10 1 xy 1 xy cin 00 01 11 10 1 cout = xy + ycin + cin x s = x ^ y ^ cin x y x cout y s cin cin

桁上げ伝搬加算器 (ripple carry adder) n 個の全加算器の cin と cout を順に接続 桁上げ (carry) が下位から伝播 伝搬遅延時間:O(n) xn-1 yn-1 x1 y1 x0 y0 c-1 = 0 FA FA FA x y x y x y cn-1 cout cin cout cin cout cin s cn-2 c1 s c0 s sn-1 s1 s0

桁上げ先見加算器 (carry-lookahead adder) 桁上げを先読み 伝搬遅延時間: O(log n) xn-1 yn-1 x1 y1 x0 y0 c-1 = 0 carry lookahead generator x y x y x y cin cin cin s cn-2 s c0 s sn-1 s1 s0

桁上げ先見器 (carry lookahead generator) ci = xy + yci-1 + ci-1 x = xiyi + (xi + yi ) ci-1 = gi + pi ci-1 gi:(下位からのキャリーに関わらず)キャリーが生成 (generate) pi:(下位からのキャリーが 1 のとき)キャリーが伝播 (propagate) 1 ? 1 1 1 1 1 1 1 ? ? 1 ? 1 ? +) 1 ? +) 1 ? +) ? +) 1 ? ? ? ? ? ? ? gi = 1 pi = 1

桁上げ先見器 (carry lookahead generator) ci = xiyi + (xi ^ yi ) ci-1 = gi + pi ci-1 gi:(下位からのキャリーに関わらず)キャリーが生成 (generate) pi:(下位からのキャリーが 1 のとき)キャリーが伝播 (propagate) c3 = g3 + p3c2 = g3 + p3 (g2 + p2c1) = g3 + p3 (g2 + p2(g1 + p1c0)) = g3 + p3 (g2 + p2(g1 + p1(g0 + p0c−1))) = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c-1 c2 = g2 + p2g1 + p2p1g0 + p2p1p0c-1 c1 = g1 + p1g0 + p1p0c-1 c0 = g0 + p0c-1

桁上げ先見器 (carry lookahead generator) p3 g2 p2 g1 p1 g0 p0 c-1 P G c3 c2 c1 c0

桁上げ先見器のツリー接続 c15 g15 p15 c0 g0 p0 c-1 c-1 c-1 c-1 GP GP GP GP c-1 c-1

加算器による減算 入力の一方(y)を二の補数に: y の各ビットを反転 c−1 を 1 に xn-1 yn-1 x1 y1 x0 y0 sub c-1 FA FA FA x y x y x y cn-1 cout cin cout cin cout cin s cn-2 c1 s c0 s sn-1 s1 s0

シフタ

シフト演算 シフト演算 左/右 算術/論理 論理シフト演算 (logical shift): 左シフト(1桁): 10100 ⇒ 01000 右シフト(1桁): 10100 ⇒ 01010 算術シフト演算 (arithmetic shift):符号ビットを保存 左シフト(1桁): 10100 ⇒ 11000 右シフト(1桁): 10100 ⇒ 11010 (ローテート) 左シフト(1桁): 10100 ⇒ 01001

算術シフト演算 n 進数,k 桁のシフト: n k 倍(左),1/n k 倍(右) 2進数,k 桁のシフト: 粒度が小さいので,使いやすい (小さい整数)倍:算術シフト & 加算 3x = 2x + x 5x = 4x + x 7x = 8x - x

バレル・シフタ 8b バレル・ローテータ x7 x6 x5 x4 x3 x2 x1 x0 shamt0 shamt1 shamt2 z7

今日のまとめ

今日のまとめ 演算回路 加減算器 シフト演算器

今後の予定 1/25(最後) メモリ 試験問題について 3/ 10(月)13:00~14:30 試験