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

二の補数の加算 top view −, + overflow O underflow side view 2n O +, + −, − +, − 2n O 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 部分和 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

半加算器，全加算器 桁上げ 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)

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

桁上げ先見器 (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:0 + p1:0 c-1

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

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

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

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

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

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

今日のまとめ

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

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