ディジタル回路 9. 演算回路 五島 正裕
ディジタル回路 今日の内容 演算回路 加算器 半加算器・全加算器 リプル・キャリー・アダー キャリー・ルックアヘッド・アダー シフト演算器
ディジタル回路 1-bit 加算器
二進数の加算 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 ディジタル回路 半加算器，全加算器 桁上げ carry 部分和 partial sum x y cout s 1 cin x y cout s 1 半加算器 (half adder) 全加算器 (full adder)
全加算器 cout = x y + y cin + cin x s = x ^ y ^ cin x y cin 00 01 11 10 1 ディジタル回路 全加算器 x y cin 00 01 11 10 1 x y cin 00 01 11 10 1 cout = x y + y cin + cin x s = x ^ y ^ cin x y x cout y s cin cin
ディジタル回路 n-bit 加算器
桁上げ伝搬加算器 (ripple carry adder) ディジタル回路 桁上げ伝搬加算器 (ripple carry adder) 桁上げ伝搬加算器 (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
加算器による減算 xn-1 yn-1 x1 y1 x0 y0 sub c-1 FA FA FA x y x y x y cn-1 cout ディジタル回路 加算器による減算 減算なら (sub = 1)，減数（y）を二の補数に： y の各ビットを反転 1 (= sub) と XOR y に 1 を加える c−1 を 1 (= sub) に 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
桁上げ先見加算器 (carry lookahead adder) ディジタル回路 桁上げ先見加算器 (carry lookahead adder) 桁上げ先見加算器 (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
ディジタル回路 g と p ci = xi yi + y ci-1 + ci−1 xi = xi yi + (xi + yi) ci−1 ≡ gi + pi ci−1 gi ≡ xi yi ：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi ≡ xi + yi ：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate)
ディジタル回路 g と p （十進数の場合） ci = xi yi + y ci-1 + ci−1 xi = xi yi + (xi + yi) ci−1 ≡ gi + pi ci−1 gi ≡ xi yi ：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi ≡ xi + yi ：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate) 1 ? 1 ? 1 1 1 1 5 ? 9 ? 1 ? 6 ? +) 5 ? +) 9 ? +) 8 ? +) 3 ? ? ? ? ? ? ? gi = 1 ： xi と yi は足して 10 以上 pi = 1 ： xi と yi は足して 9
ディジタル回路 g と p ci = xi yi + y ci-1 + ci−1 xi = xi yi + (xi + yi) ci−1 ≡ gi + pi ci−1 gi ≡ xi yi ：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi ≡ xi + yi ：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate) 1 ? 1 1 1 1 1 1 1 ? 1 ? ? 1 ? +) 1 ? +) 1 ? +) 1 ? +) ? ? ? ? ? ? ? gi = 1 gi = pi = 1 pi = 1
ディジタル回路 g と p ci = xi yi + y ci-1 + ci−1 xi = xi yi + (xi ^ yi) ci−1 ≡ gi + pi ci−1 gi ≡ xi yi ：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi ≡ xi ^ yi ：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate) 1 ? 1 1 1 1 1 ? ? 1 ? +) 1 ? +) 1 ? +) ? ? ? ? ? gi = 1 ： xi と yi は足して 2 以上 pi = 1 ： xi と yi は足して 1
ディジタル回路 漸化式 ―― g1:0 と p1:0 ci = gi + pi ci−1 gi ≡ xi yi pi ≡ xi ^ yi c0 = g0 + p0 c−1 c1 = g1 + p1c0 = g1 + p1(g0 + p0 c−1) = g1 + p1g0 + p1 p0 c−1 ≡ g1:0 + p1:0 c−1 g1:0 ≡ g1 + p1 g0 p1:0 ≡ p1 p0 x1 y1 x1 y1 x0 y0 x0 y0 g1 p1 g0 p0 g1:0 p1:0 c1 c-1
g1:0 / p1:0 は，四進数 1桁 の g / p 1 +) 1 2 +) 3 1 9 +) 7 二進数 四進数 十六進数 ディジタル回路 g1:0 / p1:0 は，四進数 1桁 の g / p 1 +) 1 2 +) 3 1 9 +) 7 二進数 四進数 十六進数
g1:0 / p1:0 は，四進数 1桁 の g / p c1 = g1:0 + p1:0 c-1 ディジタル回路 g1:0 / p1:0 は，四進数 1桁 の g / p c1 = g1:0 + p1:0 c-1 g1:0 ≡ g1 + p1g0 p1:0 ≡ p1 p0 gi ≡ xi yi pi ≡ xi ^ yi 1 になるのは，x1:0 と y1:0 が： g1:0 ： 足して 4 以上 p1:0 ： 足して 3 y1:0 1 2 3 x1:0 00 01 10 11 p1:0 g1:0 (p1g0) (g1)
ディジタル回路 g1:0 / p1:0 は，四進数 1桁 の g / p 1 ? ? 1 1 ? 1 1 1 1 1 1 1 ? ? 1 ? ? 1 ? +) 1 ? ? +) 1 1 ? +) 1 1 ? +) 1 ? ? ? ? ? ? ? ? 1 ? 1 ? 1 ? 1 1 1 1 2 ? 2 ? 1 ? ? 1 ? +) 2 ? +) 3 ? +) 3 ? +) 3 ? +) 2 ? ? ? ? ? ? ? ? ? g1 = 1 p1g0 = 1 g1:0 = 1 : 足して 4 以上 p1:0 = 1 : 足して 3
ディジタル回路 2-bit 桁上げ先見器のツリー接続 g1:0 = g1 + p1 g0 p1:0 = p1 p0 g3:2 = g3 + p3 g2 p3:2 = p3 p2 g3:0 = g3:2 + p3:2 g1:0 p3:0 = p3:2 p1:0 c3 = g3:0 + p3:0 c−1 x3 y3 x3 y3 x2 y2 x2 y2 x1 y1 x1 y1 x0 y0 x0 y0 g3 p3 g2 p2 g1 p1 g0 p0 g3:2 p3:2 g1:0 p1:0 g3:0 p3:0 c3 c-1
2-bit 桁上げ先見器のツリー接続 ディジタル回路 p0 p1 c1 c0 p1:0 g1:0 p1 p1 p0 p0 g1 g0 g0 x7/y7 x6/y6 x5/y5 x4/y4 x3/y3 x2/y2 x1/y1 x0/y0 cin p0 p1 c1 c0 g/p7 g/p6 g/p5 g/p4 g/p3 g/p2 g/p1 g/p0 g/p7:6 g/p5:4 g/p3:2 g/p1:0 g/p7:4 g/p3:0 g/p7:0 c7 c3 c−1 c5 c1 c6 c4 c2 c0 p1:0 g1:0 p1 p1 p0 p0 g1 cout s7 s6 s5 s4 s3 s2 s1 s0 g0 g0 c-1 c-1 : si = xi ^ yi ^ c−1 = pi ^ c−1
2-bit 桁上げ先見器のツリー接続 ディジタル回路 p0 p1 c1 c0 p1:0 g1:0 p1 p1 p0 p0 g1 g0 g0 cin g/p7:4 g/p3:0 cout c7 p1:0 g1:0 p1 p1 p0 p0 g1 g0 g0 c-1 c-1
ディジタル回路 4-bit 桁上げ先見器 ci ≡ gi + pi ci−1 gi ≡ xi yi ：（下位からのキャリーに関わらず）キャリーが生成 (generate) pi ≡ xi ^ yi ：（下位からのキャリーが 1 のとき） キャリーが伝播 (propagate) c3 = g3 + p3 c2 = g3 + p3 (g2 + p2c1) = g3 + p3 (g2 + p2 (g1 + p1c0)) = g3 + p3 (g2 + p2 (g1 + p1(g0 + p0 c−1))) = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 c−1 c2 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 c−1 c1 = g1 + p1 g0 + p1 p0 c−1 c0 = g0 + p0 c−1
4-bit 桁上げ先見器 ディジタル回路 p0 p1 p2 p3 c3 c2 c1 c0 p3 p3 p3 p3 p2 p2 p2 g2
4-bit 桁上げ先見器のツリー接続 ディジタル回路 g/p31 g/p30 g/p29 g/p28 g/p27 g/p26 g/p25 c31 c30 c29 c28 c27 c26 c25 c24 c23 c22 c21 c20 c19 c18 c17 c16 g/p31:28 c27 g/p27:24 c23 g/p23:20 c19 g/p19:16 c31 c15 g/p63L48 c47 g/p47:32 c31 g/p31:16 g/p15:0 c63 c−1
ディジタル回路 シフタ
シフト演算 シフト演算の種類： {論理，算術，ローテート} × {左，右} 論理シフト (logical shift)： ディジタル回路 シフト演算 シフト演算の種類： {論理，算術，ローテート} × {左，右} 論理シフト (logical shift)： 左 1桁： 10100 ⇒ 01000 右 1桁： 10100 ⇒ 01010 算術シフト (arithmetic shift)： 符号ビットを保存 左 1桁： 10100 ⇒ 11000 (-12 ⇒ -8，オーバフロー) 右 1桁： 10100 ⇒ 11010 (-12 ⇒ -6) ローテート (rotate)： 左 1桁： 10100 ⇒ 01001
算術シフト演算 n 進数，k 桁のシフト： n k 倍（左），n -k 倍（右） 二進数，k 桁のシフト： ディジタル回路 算術シフト演算 n 進数，k 桁のシフト： n k 倍（左），n -k 倍（右） 二進数，k 桁のシフト： 2 k 倍（左），2 -k 倍（右） 粒度が小さいので，使いやすい （小さい整数）倍： 算術シフト ＆ 加算 3x = 2x + x 5x = 4x + x 7x = 8x - x
論理/算術 左シフト演算 オーバフローする場合： 論理シフト演算： 10100 ⇒ 01000 ディジタル回路 論理/算術 左シフト演算 オーバフローする場合： 論理シフト演算： 10100 ⇒ 01000 算術シフト演算： 10100 ⇒ 11000 (-12 ⇒ -8，オーバフロー) オーバフローしない場合： 論理シフト演算： 11010 ⇒ 10100 算術シフト演算： 11010 ⇒ 10100 (-6 ⇒ -12) フラグの更新以外，論理と算術は区別する必要がない
バレル・シフタ（ローテータ） 8b バレル・ローテータ x7 x6 x5 x4 x3 x2 x1 x0 shamt0 shamt1 ディジタル回路 バレル・シフタ（ローテータ） x7 x6 x5 x4 x3 x2 x1 x0 shamt0 shamt1 shamt2 z7 z6 z5 z4 z3 z2 z1 z0 8b バレル・ローテータ
ディジタル回路 まとめ
まとめ 二の補数 正負の区別なく扱える 「符号付き加算器」「符号なし加算器」はない 加算器によって減算できる 「減算器」はない ディジタル回路 まとめ 二の補数 正負の区別なく扱える 「符号付き加算器」「符号なし加算器」はない 加算器によって減算できる 「減算器」はない
まとめ 多ビット加算器 リプル・キャリー・アダー： O(n) キャリー・ルックアヘッド・アダー： O(log n) シフト演算器 ディジタル回路 まとめ 多ビット加算器 リプル・キャリー・アダー： O(n) キャリー・ルックアヘッド・アダー： O(log n) シフト演算器 O(log n)