9. 演算回路 五島 正裕.

Presentation on theme: "9. 演算回路 五島 正裕."— Presentation transcript:

1 9. 演算回路 五島 正裕

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

3 補数表現

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

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

6 十進数 九の補数（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 から引く

7 二進数 一の補数（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 足す

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

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

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

11 二の補数の加算 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 オーバフロー

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

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

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

15 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

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

17 加減算器

18 二進数の加算 1 1 +) +) 1 +) +) 1 1 1 1 桁上げ carry 部分和 partial sum 1 1 1 1 1 1
1 1 +) +) 1 +) +) 1 1 1 1 桁上げ carry 部分和 partial 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

19 半加算器，全加算器 桁上げ carry 部分和 partial sum x y cout s 1 cin x y cout s 1
1 cin x y cout s 1 半加算器 (half adder) 全加算器 (full adder)

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

21 桁上げ伝搬加算器 (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

22 桁上げ先見加算器 (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

23 桁上げ先見器 (carry lookahead generator)
ci = xiyi + yci-1 + ci−1 xi = 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

24 桁上げ先見器 (carry lookahead generator)
ci = xiyi + (xi ^ yi ) ci−1 = gi pi ci−1 gi：（下位からのキャリーに関わらず） キャリーが生成 (generate) pi：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate) c0 = g0 + p0c-1 c1 = g1 + p1c0 = g1 + p1(g0 + p0c-1) = g1 + p1g0 + p1p0c-1 = g1: p1:0 c-1

25 2-bit 桁上げ先見器 (carry lookahead generator)
c0 = g0 + p0c-1 c1 = g1 + p1c0 = g1 + p1(g0 + p0c-1) = g1 + p1g0 + p1p0c-1 = g1:0 + p1:0 c-1 g1:0 = g1 + p1g0 p1:0 = p1p0 c-1 c1 g1:0 p1:0 g1 p1 g0 p0 x1 y1 x1 y1 x0 y0 x0 y0

26 2-bit 桁上げ先見器のツリー接続 c3 = g3:0 + p3:0 c−1 g3:0 = g3:2 + p3:2g1:0 p3:0 = p3:2p1:0 g3:2 = g3 + p3g2 p3:2 = p3p2 g1:0 = g1 + p1g0 p1:0 = p1p0 c-1 c3 g3:0 p3:0 g3:2 p3:2 g1:0 p1:0 g3 p3 g2 p2 g1 p1 g0 p0 x3 y3 x3 y3 x2 y2 x2 y2 x1 y1 x1 y1 x0 y0 x0 y0

27 4-bit 桁上げ先見器 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

28 4-bit 桁上げ先見器 g3 p3 g2 p2 g1 p1 g0 p0 c-1 P G c3 c2 c1 c0

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

30 加算器による減算 入力の一方（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

31 シフタ

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

33 算術シフト演算 n 進数，k 桁のシフト： n k 倍（左），1/n k 倍（右） 2進数，k 桁のシフト：
粒度が小さいので，使いやすい （小さい整数）倍：算術シフト ＆ 加算 3x = 2x + x 5x = 4x + x 7x = 8x - x

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

35 今日のまとめ

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

37 今後の予定 12/24 工学部・工学系・情報理工学系は月曜の授業 1/ 7 メモリ 1/14 試験 1/28（水）（補講日）
1/ 7 メモリ 1/14 試験 1/28（水）（補講日） 10:40～11:40（この時間） （13：10～ D論審査＠本郷）

38