加減算

(1)

「論理回路」ノート (2013年度, c 関西学院大学石浦菜岐佐)

http://ist.ksc.kwansei.ac.jp/∼ishiura/lc/

10 _{算術演算回路}

♣ 桁上げ

伝播

^加算器

♣

加減算

^器

♣ 桁上げ

先見

^加算器

♣

オーバーフロー

^検出

10.1 桁上げ伝播加算回路

• 2 進数の加算

(

0

⁾ ⁽

0

⁾ ⁽

0

⁾ ⁽

1

⁾ ^{· · ·}^桁上がり⁽

carry

⁾

0 1 0 1 · · ·(510)

+) 1 0 0 1 · · ·(910)

1 1 1 0

^{· · ·}⁽

14

¹⁰⁾

練習 10.1 符号なし2進数0110と0111の和を筆算により求めよ.

• 桁上げ伝播加算器(carry

propagation

^adder,

ripple

carry adder)

半加算器(HA:

half

^{adder) 1}^{個と全加算器}^(FA:

full

^adder)ⁿ⁻¹ ^{個を直列に接続}

(c4) (c3) (c2) (c1) a3 a2 a1 a0

+) b3 b2 b1 b0

s3 s2 s1 s0

FA s co a b ci

HA s co

a b a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

0101 + 1001の例

(0) (0) (0) (1)

0 1 0 1

+) 1 0 0 1

1 1 1 0

0 1 0 1

0 1

1 0

FA s co a b ci

HA s co

a b a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

0 1 1 0 0 0 1 1

(2)

全加算器をn個を直列に接続してc0 に

0

を入力するという構成もある (c0 に 1を入力すると,s=

a + b + 1

^{が計算される)}

FAs co a b ci

FAs co a b ci a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

c₀=0

• 半加算器の真理値表とゲートによる設計例

a b co s

0 0

0 1

1 0

0 1

1 1

1 0

co=

ab

s=

a ⊕ b

a b

co s

• 全加算器の真理値表とゲートによる設計例

a b ci co s

0 0 0

0 0

0 0 1

0 1

0 1 0

0 1

0 1 1

1 0

1 0 0

0 1

1 0 1

1 0

1 1 0

1 0

1 1 1

1 1

c^o=

ab + bc

_i

+ c

_i

a

s=

a ⊕ b ⊕ c

_i

a b ci

co s

10.2 加減算器

• 減算器(

subtractor

⁾

加算と同様の原理で実現可能

sumとcarryの代わりに,

difference

^(差)^と

borrow

^(桁借り)^を用いる

0 0 1 0

^{· · ·} ^(borrow)

0 1 0 1 · · · (510)

−) 0 0 1 0 · · · (210)

0 0 1 1

^{· · ·} ⁽

3

¹⁰⁾

(3)

a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

d₃ d₂ d₁ d₀

B₄

B₃ B₂ B₁

FS d Bo a b Bi

HS d Bo a b

(d3, d2, d1, d0)が減算結果

Bi はi桁目からi+ 1 桁目に伝わる桁借り HSは半減算器(half subtractor)

F Sは全減算器(full subtractor)

しかし,「

補数

^を

加算

する」方法がより一般的

⇒ 加算器と減算器を一体化した

加減算

^{器を構成する}

• 加減算器(adder-subtractor) – 制御入力xを持ち,







x= 0のとき

加算

x= 1のとき

減算

– 符号付きの2進数を扱い,

2 の補数

^{表現を用いる}

【復習】2の補数表現とは: −xの表現にxの

2 の補数を用いる

^表現体系

【復習】2の補数とは:

0/1 を反転

^して

1 を足す

【復習】2の補数表現体系での減算:

2 の補数

^の加算(最上位からの桁上りは無視) 例) 0101

(5)

−0011 (3)

= 0101 (5)

+

1101

(−3)

=

0010

(2) 例) 0101

(5)

−0111 (7)

= 0101 (5)

+

1001

(−7)

=

1110

(−2) 練習 10.2 次の2の補数の加減算に関する式の空欄を埋めよ.

1. 0101−0010 = 0101 + = 2. 0010−0110 = 0010 + =

bababababababababababababababababababababab

なぜ2の補数はそのまま加算できるのか

2の補数表現体系は, 10進数で考えてみると,次のような表現体系 2 → 0002

1 → 0001 0 → 0000

−1 → 9999

−2 → 9998

すると, 加算は次のように行える(ただし, 5桁目以上は無視する) 5 + (−2) = 5 + 9998 = 0003

5 + (−7) = 5 + 9993 = 9998 (=−2)

(4)

– 回路構成

FA s co

a b ci FA

s co

a b ci FA

s co

a b ci FA

s co a b ci

a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

x x= 0のとき(加算)

bi⊕0 =

b

_i なので(b3, b2, b1, b0)はそのまま全加算器のb 入力に入る桁上げの初期値c0 はx=

0

⇒下記の回路(加算回路)と等価になる

FAs co

a b ci coFAs

a b ci coFAs a b ci a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

c₀=0 x= 1のとき(減算)

bi⊕1 =

b

_i なので(b3, b2, b1, b0)を

反転

^{したものが全加算器の}^b ^{入力に入る}

桁上げの初期値c0 はx=

1

^⇒

1 を足した

^{ことになる}

⇒下記の回路と等価(減算回路)になる

FA s co

a b ci FA

s co

a b ci FA

s co

a b ci FA

s co a b ci

a₃ a₂ a₁ a₀

b₃ b₂ b₁ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

c₀=1

(5)

10.3 桁上げ先見加算器

桁上げ伝播加算器の問題点

計算時間(組合せ回路の最大遅延時間,つまり

段数

⁾が桁数に比例して大きくなる

(nビットのときO(

n

))

桁上げ先見加算器(carry

look-ahead

adder: CLA) 桁上げ信号を組合せ回路で高速に計算する

FA s co a b ci

FA s co a b ci a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀

s₃ s₂ s₁ s₀

c₄

c₃ c₂ c₁

c₀

a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀ c₀

s₃ s₂ s₁ s₀

c₄ c₃ c₂ c₁

⇓

a₃ b₃ a₂ b₂ a₁ b₁

s₃ s₂ s₁ s₀

a₀ b₀ c₀ a₀ b₀

c₄ c₃ c₂ c₁

c₀ a₁ b₁

a₃ b₃ a₂ b₂

look-ahead carry generator

桁上げ信号の計算

各桁i= 0,1,· · ·, n−1に対し,gi とpi を次のように定義する







gi=

a

_i

b

_i

pi =

a

_i

+ b

_i

例)n= 4 (4ビット加算器)の場合には g0=a0b0, p0=a0+b0

(6)

g2=a2b2, p2=a2+b2

g3=a3b3, p3=a3+b3

直観的意味【重要】

gi …「i 桁目が桁上げを

生成 (generate)

^する」

pi …「i桁目への桁上げ信号がi+ 1 桁目に

伝播 (propagate)

^する」

ci+1 をgi,pi,およびci で表す ci+1=

g

_i ⁺

p

_i

c

_i

この漸化式を展開する c0=c0

c1=

g

0

+ p

0

c

0

c2=

g

1

+ p

1

c

1 =g1+p1g0+p1p0c0

c3=

g

2

+ p

2

c

2 =g2+p2g1+p2p1g0+p2p1p0c0

c4=

g

3

+ p

3

c

3 =g3+p3g2+p3p2g1+p3p2p1g0+p3p2p1p0c0

桁上げ生成回路

a₃ b₃ a₂ b₂ a₁ b₁ a₀ b₀ c₀

c₄ c₃ c₂ c₁

p₃

g₃ g₂ p₂ g₁ p₁ g₀ p₀

☆ ファンイン制限を考慮した場合, この方法で得られる桁上げ生成回路の段数はO(

log n

)だが,ゲート数がO(

n

³ )になってしまい,ビット数が多い場合非現実的. 実際には,n= 4程度の桁上げ生成回路をtree 状に接続して全体の桁上げ生成回路を構成する(ゲート数はO(

n

)).

(7)

10.4 オーバーフロー検出

オーバーフロー(

overflow

⁾

演算結果が表現可能な範囲外になってしまうこと

【復習】nビットの2の補数表現で表現可能な範囲

4 ビットの場合,最大数は

0111

₂⁼

7

₁₀^,^最小数は

1000

₂⁼

−8

₁₀

7 0111 6 0110 5 0101 4 0100 3 0011 2 0010 1 0001 0 0000

−1 1111

−2 1110

−3 1101

−4 1100

−5 1011

−6 1010

−7 1001

−8 1000

nビットの場合,最大数は

2

ⁿ⁻¹

− 1

^, ^最小数は

− 2

ⁿ⁻¹

例 (加算) 0101

(5)

+ 0010 (2)

= 0111 (7)

OK

0101 (5)

+ 0100 (4)

=

1001

(−7)

overflow

0011 (3)

+ 1011 (−5)

= 1110 (−2)

OK

1011 (−5)

+ 1010 (−6)

=

0101

(

5

⁾

overflow

練習 10.3 次の2の補数表現の加算のうち,オーバーフローが発生するものはどれか.

1. 0110 + 0110 2. 0110 + 0001 3. 0110 + 1111 4. 1100 + 1111 5. 1001 + 1100

(8)

加算でオーバーフローが起こる条件

☆ 符号に注目

a b a+b overflow

+ + +

×

+ + −

○

+ − +

×

+ − −

×

− + +

×

− + −

×

− − +

○

− − −

×

最上位

^{ビットが符号ビット}⁽

0

^のとき^+,

1

^のとき⁻⁾

a,b,および加算結果sの最上位ビットをそれぞれ

a

_n−1 ,

b

_n−1 ,

s

_n−1 とするオーバーフローの発生を表す関数fv の真理値表

an−1 bn−1 sn−1 fv

0 0 0 0

0 0 1

1

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0

1

1 1 1 0

論理式で表すと

fv=

a

_n−1

b

_n−1

s

_n−1

+ a

_n−1

b

_n−1

s

_n−1

⊕を用いて次のように表すこともできる

fv =

( a

_n−1

⊕ b

_n−1

)( a

_n−1

⊕ s

_n−1

)

(aⁿ−1と bⁿ−1が

等しく

^,^aⁿ⁻¹ ^と^sⁿ⁻¹ ^が

等しくない

^{ときオーバーフロー)}

☆ A⊕B= 1 ⇔ A とB は

等しくない

A⊕B= 1 ⇔ A とB は

等しい

(9)

練習問題の解答例

練習10.1

0 1 1 0

0 1 1 0 · · ·(6)

+) 0 1 1 1 · · ·(7)

1 1 0 1 · · ·(13)

練習10.2 1. 0101

(5)

−0010 (2)

= 0101 (5)

+ 1110 (−2)

= 0011 (3)

1 1 0 0

0 1 0 1 · · ·(5)

+) 1 1 1 0 · · ·(−2)

1

/ 0 0 1 1 · · ·(3)

2. 0010 (2)

−0110 (6)

= 0010 (2)

+ 1010 (−6)

= 1100 (−4)

0 0 1 0

0 0 1 0 · · ·(2)

+) 1 0 1 0 · · ·(−6)

1 1 0 0 · · ·(−4)

練習10.3 計算結果が−8∼7の範囲に入っていなければオーバーフロー 1. 0110 + 0110 = (6) + (6) = (12)→ オーバーフロー

2. 0110 + 0001 = (6) + (1) = (7) 3. 0110 + 1111 = (6) + (−1) = (5) 4. 1100 + 1111 = (−4) + (−1) = (−5)

5. 1001 + 1100 = (−7) + (−4) = (−11)→ オーバーフロー