演算回路

ディジタル回路
9. 演算回路
五島 正裕
ディジタル回路
今日の内容
 演算回路
 二の補数
 加算器
 シフト演算器
ディジタル回路
補数表現
ディジタル回路
負の数の表現
表現される値
 補数 (complement) 表現:
 「上半分」を負数に充てる
 k 進数
 k
の補数
 k-1 の補数
O
元の値
ディジタル回路
補数表現
 k 進数 n 桁
の補数
k

-x:k
n
から x を引いた値
 k-1 の補数

- x : k -1 から x を引いた値
n
ディジタル回路
十進数
符号なし
0
1
2
3
4
5
6
7
8
9
符号付き
0
1
2
3
4
−4
−3
−2
−1
−0
九の補数(1桁): 9 から引く
符号なし
0
1
2
3
4
5
6
7
8
9
符号付き
0
1
2
3
4
−5
−4
−3
−2
−1
十の補数(1桁): 10 から引く
ディジタル回路
二進数
補数表現
000
001
010
011
100
101
110
111
表現される値
0
1
2
3
−3
−2
−1
−0
一の補数(3桁)
23-1 = 111 から引く ⇒ 各桁反転
補数表現
000
001
010
011
100
101
110
111
表現される値
0
1
2
3
−4
−3
−2
−1
二の補数(3桁)
23 = 1000 から引く ⇒ 各桁反転し,1 足す
ディジタル回路
補数表現
表現される値
表現される値
+11
+11
+10
+10
+01
+01
00
O
00
01
元の値
10
11
-01
O
(100)
01
10
元の値
-01
-10
一の補数
11
二の補数
ディジタル回路
二進数の補数表現
 符号ビット (sign bit)
 最上位桁(ビット)が符号を表す(0 が正,1 が負)
 一の補数 と 二の補数
 一の補数:

ビット反転で得られる

計算が困難
 二の補数

ビット反転後,+1

計算が容易
ディジタル回路
二の補数の加算
 二の補数の加減算
 基本的には,特に何も気にしなくてよい
 符号ビットからの桁上げは無視
 オーバフロー (overflow)
 結果が表現できる範囲にない

符号ビットがおかしなことになる
– 0 (+) + 0 (+) → 1 (-)
– 1 (-) + 1 (-) → 0 (+)
ディジタル回路
二の補数の加算
111
1 1 1 … −1
1 1 1 … −1
+)
1 1 1 0 … −2
符号ビットからの桁上
げ
+)
1
11
11
0 1 1 … +3
0 1 1 … +3
0 0 1 … +1
1 0 0 … −4
+)
0 1 1 … +3
1
1 0 0 … −4
+)
1 1 0 … −2
オーバフロー
1 1 1 … −1
1 0 1 1 … +3
1 0 0 … −4
+)
1 0 0 … −4
1 0 0 0 … +0
ディジタル回路
符号なし加算
z=x+y
2
2
overflow
n +1
n
2
n
y
O
2
n
x
ディジタル回路
二の補数の加算
top view
2
n
−, +
O
overflow
−, −
+, +
+, −
2
n
O
2
2
underflow
n
n−1
O
−2
n−1
−2
n
side view
ディジタル回路
二の補数の加算
2
overflow
n +1
−1
n
2 −1
n
2 −1
O
O
n
2 −1
符号なし加算
符号なし加算結果を
二の補数とみなす
ディジタル回路
n -bit 二の補数の和
符号ありの値
n +1
−1
2
n −1
n
−1
2 +2
n
−1
2
0 1...1 1 0 0...0 1 0 1...1
2
n −1
−1
符号なしの値
0 0...0
O
1 1 1...1
n −1
−2
1 0...0
1 1...1
1 1 0...0
ディジタル回路
二の補数の加算
overflow
underflow
符号あり加算
符号なし加算結果を
二の補数とみなす
ディジタル回路
加減算器
ディジタル回路
二進数の加算
0
+)
0
0
+)
1
1
0
+)
1
0
1
+)
1
1
10
桁上げ
carry
1 1
1
0 1
+)
0 1
1 0
1 1
0 1
+)
1 1
1 0 0
1 1
1 1
+)
0 1
1 0 0
部分和
partial sum
1 1
+)
1 1
1 1 0
← 桁上げ
ディジタル回路
半加算器,全加算器
桁上げ
carry
部分和
partial sum
x
y cout s
cin x
y cout s
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
0
0
1
1
1
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
半加算器 (half adder)
全加算器 (full adder)
ディジタル回路
全加算器
xy
cin
00
01
0
1
11
xy
10
cin
1
1
1
00
0
1
01
11
1
1
1
10
1
1
s = x ^ y ^ cin
cout = xy + ycin + cin x
x
y
x
cout
cin
y
cin
s
ディジタル回路
桁上げ伝搬加算器 (ripple carry adder)
 桁上げ伝搬加算器 (ripple carry adder)
 n 個の全加算器の cin と cout を順に接続
 桁上げ (carry) が下位から伝播
 伝搬遅延時間:O(n)
xn-1 yn-1
x1 y1
FA
cn-1
x0 y0
FA
cout
x
y
s
sn-1
cin
cn-2
c1
c-1 = 0
FA
cout
x
y
s
s1
cin
c0
cout
x
y
s
s0
cin
ディジタル回路
桁上げ先見加算器 (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
s
sn-1
cin
x
cn-2
y
s
s1
cin
x
c0
y
s
s0
cin
ディジタル回路
桁上げ先見器 (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 ?
? ?
gi = 1
1 1
0 ?
+)
1 ?
0 ?
1 1
1 ?
+)
0 ?
0 ?
pi = 1
1 ?
+)
1 ?
? ?
ディジタル回路
桁上げ先見器 (carry lookahead generator)
ci = xiyi + (xi ^ yi ) ci−1
= gi + pi
ci−1
gi:(下位からのキャリーに関わらず)
pi:(下位からのキャリーが 1 のとき)
c0 = g0 + p0c-1
c1 = g1 + p1c0
= g1 + p1(g0 + p0c-1)
= g1 + p1g0 + p1p0c-1
= g1:0 + p1:0 c-1
キャリーが生成 (generate)
キャリーが伝播 (propagate)
ディジタル回路
2-bit 桁上げ先見器 (carry lookahead generator)
c-1
c1
g1:0
c0 = g0 + p0c-1
p1:0
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
g1
p1
x1 y1 x1 y1
g0
p0
x0 y0 x0 y0
ディジタル回路
2-bit 桁上げ先見器のツリー接続
c-1
c3
g3:0
p3:0
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
p3:2
g3:2
g3
p3
g2
p2
x3 y3 x3 y 3 x2 y2 x2 y2
p1:0
g1:0
g1
p1
g0
p0
x1 y1 x1 y1 x0 y0 x0 y0
ディジタル回路
4-bit 桁上げ先見器
ci = xiyi + (xi ^ yi ) ci−1
= gi + pi
ci−1
gi:(下位からのキャリーに関わらず)
pi:(下位からのキャリーが 1 のとき)
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
キャリーが生成 (generate)
キャリーが伝播 (propagate)
ディジタル回路
4-bit 桁上げ先見器
g3
p3
g2
p2
g1
p1
g0 p0 c-1
P
G
c3
c2
c1
c0
ディジタル回路
4-bit 桁上げ先見器のツリー接続
c0 g0 p0
c15 g15 p15
GP
c-1
GP
c-1
GP
c-1
GP
c-1
c-1
GP
c-1
ディジタル回路
加算器による減算
 入力の一方(y)を二の補数に:
 y の各ビットを反転
 c−1 を 1 に
xn-1 yn-1
x1 y1
x0 y0
sub
c-1
FA
cn-1
FA
cout
x
y
s
sn-1
cin
cn-2
c1
FA
cout
x
y
s
s1
cin
c0
cout
x
y
s
s0
cin
ディジタル回路
シフタ
ディジタル回路
シフト演算
 シフト演算
 左/右
 算術/論理
 論理シフト演算 (logical shift):
 左シフト(1桁): 10100 ⇒ 01000
 右シフト(1桁): 10100 ⇒ 01010
 算術シフト演算 (arithmetic shift):符号ビットを保存
 左シフト(1桁): 10100 ⇒ 11000
 右シフト(1桁): 10100 ⇒ 11010
 (ローテート)
 左シフト(1桁): 10100 ⇒ 01001
 右シフト(1桁): 10100 ⇒ 01010
ディジタル回路
算術シフト演算
 n 進数,k 桁のシフト:
 n k 倍(左),1/n k 倍(右)
 2進数,k 桁のシフト:
 2 k 倍(左),1/2 k 倍(右)
 粒度が小さいので,使いやすい
 (小さい整数)倍:算術シフト & 加算

3x = 2x + x

5x = 4x + x

7x = 8x - x
ディジタル回路
バレル・シフタ
x7
x6
x5
x4
x3
x2
x1
x0
shamt0
shamt1
shamt2
z7
z6
z5
z4
z3
z2
8b バレル・ローテータ
z1
z0
ディジタル回路
今日のまとめ
ディジタル回路
今日のまとめ
 演算回路
 加減算器
 シフト演算器
ディジタル回路
今後の予定
 12/24
 工学部・工学系・情報理工学系は月曜の授業
 1/ 7
 メモリ
 1/14
 試験
 1/28(水)(補講日)
 10:40~11:40(この時間)

(13:10~ D論審査@本郷)
ディジタル回路