1. No category

2014.12.2
論理回路論解答例 (9)
次の演習を行え．
1. 演習 5-4 を行え．
別のオーバーフローの検出法として，以下のような方法がある．n ビットの加算とし，最上
位桁を (n-1) 桁とする．また，最上位桁への桁上がり入力を cn−1 ，最上位桁からの桁上がり
出力を cn とする．そうすると，
ovf = cn−1 ⊕ cn
となる．ここで，⊕ は排他的論理和である．
その証明：
(cn ,cn−1 ) の値の組合せごとに検討する．2 数を A, B とし，和を S とする．
(a) (0,0) の場合：cn = 0 ということは，an−1 + bn−1 + cn−1 が 1 以下であるが cn−1 = 0 で
あるから，an−1 ,bn−1 はともに 0 であるか，一方が 1 であるかのいずれかである．これ
は正＋正，正＋負，負＋正の場合である．さらに，正＋正の場合は，sn−1 は 0 となる．
よって，オーバーフローは発生しない．
(b) (0,1) の場合：cn = 0 ということは，an−1 +bn−1 +cn−1 が 1 以下である．さらに cn−1 = 1
であるから，an−1 ,bn−1 はともに 0 でなければならない．そして，sn−1 は 1 となる．こ
れは正＋正で S が負を意味する．よってオーバーフローが発生する．
(c) (1,0) の場合：cn = 1 ということは，an−1 + bn−1 + cn−1 が 10 以上であるが cn−1 = 0
であるから，an−1 ,bn−1 はともに 1 でなければならない．これは負＋負の場合である．
しかし，Sn−1 は 0 であるから，S が正になる．よって，オーバーフローが発生する．
(d) (1,1) の場合：cn = 1 ということは，an−1 + bn−1 + cn−1 が 10 以上であるが cn−1 = 1
であるから，an−1 ,bn−1 はともに 1 であるか，一方が 1 であるかのいずれかである．こ
れは正＋負，負＋正，負＋負の場合である．さらに，負＋負の場合は，sn−1 は 1 とな
る．よって，オーバーフローは発生しない．
以上から，cn−1 ⊕ cn はオーバーフローの論理値を表している．
これを，表で書くと以下のようになる．
（ovf と cn−1 ⊕ cn が一致）
表 オーバーフロー検出
cn−1 sn1 ovf cn
cn−1 ⊕ cn
an−1
bn−1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
0
0
1
1
1
1
0
1
0
1
1
0
1
1
1
0
1
c
cin
a
b
s=a b cin
cout=a・b+(a+b)・cin
FA
(a)全加算器
a
b
FA’
s=a b
g=a・b
p=a+b
c
(b)変形した全加算器
図 1: 全加算器
2. 演習 5-5 を行え．
リップルキャリー方式の加算は，桁上げ信号が下位ビットから上位ビットに向かって逐次的に
伝播するので，時間がかかる．そこで，下位ビットからの桁上げを先読みして，最上位ビット
に桁上げがあるかないかを判定する方式が考えられる．そのひとつに桁上げ先見 (carry look
ahead) 方式がある．
全加算器の桁上げ出力の論理式は，
cout = a · b + a · cin + b · cin
で与えられた．F Ai への a, b 入力と桁上げ入力を添え字 i をつけて表すと上式は次のように
なる．
ci+1 = ai · bi + ai · ci + bi · ci
となる．F A0 と F A1 について具体的に書くと，
c1 = a0 · b0 + a0 · c0 + b0 · c0
(1)
c2 = a1 · b1 + a1 · c1 + b1 · c1
(2)
となる．式（1）を式（2）に代入して，
c2
= a1 · b1 + a1 (a0 · b0 + a0 · c0 + b0 · c0 ) + b1 (a0 · b0 + a0 · c0 + b0 · c0 )
= a1 · b1 + a1 · a0 · b0 + a1 · a0 · c0 +
a1 · b0 · c0 + b1 · a0 · b0 + b1 · a0 · c0 + b1 · b0 · c0
(3)
を得る．式（3）を見ると，c2 は a0 , b0 , a1 , b1 , c0 で表されることがわかる．同様にして c3 , ...c31
を作るとそれぞれが ai , bi , c0 で表されることがわかる．
このように構成すると，ci を表す式は積和形で記述できるので，and ゲートと or ゲートの 2
段で回路が実現できることになり高速動作が期待できる．しかしながら，積項の数は i のべ
き乗で増えていくので実現が難しい1 ．
そこで，妥協点を探る．ゲート数がそこそこに抑えられて，そこそこ高速に動作する構成，
いわゆるエンジニアリング・ソリューション，を考える．まず，gi = ai · bi , pi = ai + bi と置
く．すると，ci+1 = ai · bi + ai · ci + bi · ci は，ci+1 = gi + pi · ci と書ける．ここで，gi と pi
の意味を考えてみよう．gi が１だと ci+1 が 1 となる．これはキャリーが生成 (generate) さ
れることを意味する．また，pi が 1 だと ci が 1 のとき ci+1 が１になる．つまり，pi は ci を
i+1 − 1 となる．なぜなら，積項の数は，nc = 3, nc = 1 + 2nc
1
i を ci の積項の数とすると，nci = 2
i
i−1
なる漸化式で記述できるからである．nci − nci−1 = bi と置くと，この漸化式は，bi = 2bi−1 , b2 = 4 となる．したがっ
て，bi = 2i となるから，nci = nci−1 + 2i = nci−2 + 2i−1 + 2i = ... = 2i + 2i−1 + ... + 2 + 1 = 2i+1 − 1 となる．
1 実際，nc
2
c1
c2
c3
c0
c4
G0
P0
CLA4
g0 p0 g1 p1 g2 p2 g3 p3
図 2: 桁上げ先見器
c1
c2
c3
c4
G0
P0
s0
c0
s1 s2
s3 c0 c1 c2
c3 G0 P0
CLA4
s0
g0 p0
FA’
s1
g1 p1
FA’
c0
c1
a0 b0
s2
s3
g2 p2
FA’
c0
CADR4
FA’
c3
c2
a3 b3
a2 b2
a1 b1
g3 p3
(a) ４ビット桁上げ先見加算器(詳細記述）
a0
b0
a1
b1
a2
b2
a3
b3
(b) ４ビット桁上げ先見加算器(包括図）
図 3: 4 ビット桁上げ先見加算器
ci+1 に伝播 (propagate) させることを意味する．次に，この式を利用して，4 ビットの加算
器を考える．キャリー出力は次のように書ける．
g0 + p0 · c0
c1
=
(4)
c2
= g1 + p1 · c1 = g1 + p1 · g0 + p1 · p0 · c0
(5)
c3
= g2 + p2 · c2 = g2 + p2 · g1 + p2 · p1 · g0 + p2 · p1 · p0 · c0
(6)
c4
= g3 + p3 · c3 = g3 + p3 · g2 + p3 · p2 · g1 + p3 · p2 · p1 · g0 + p3 · p2 · p1 · p0 · c0 (7)
4 ビット加算器では c4 がキャリー出力となる．これを図示してみる．まず，全加算器を図 1(b)
のように書き換える．そして，上の式 c1 ∼ c4 を論理回路で記述したものを図 2 のように書く．
これを CLA4 と表す．
（G0 ，P0 の意味はこの後すぐに述べる．
）式の形からわかるように，図
の箱の中は 2 段のゲート回路で記述できる．これらを結びつければ，図 3 のような 4 ビットの
桁上げ先見型加算器が得られる．ここで注意すべきことは，c1 ∼ c4 は ai , bi , c0 , (i = 0, 1, 2, 3)
から決まるので，リップルキャリー型のように長い伝播遅延を要しないことである．この加
算器を CADR4 と書く．
つぎに，c4 の式を次のように書き換える．まず，
P0
= p3 · p2 · p1 · p0
G0
= g3 + p3 · g2 + p3 · p2 · g1 + p3 · p2 · p1 · g0
とおく．P0 は c0 のキャリーの伝播を意味し，G0 は 4 ビット加算器のキャリー生成を意味す
る．図 2 と図 3 の P0 と G0 は，これを表している．さて，この 4 ビット加算器を 4 つ接続
する．それぞれの 4 ビット加算器のキャリー出力を大文字の Ci と書く．すると，前と同じよ
うに
C1
= G0 + P0 · c0
3
C2
=
G1 + P1 · C1
C3
=
G2 + P2 · C2
C4
=
G3 + P3 · C3
を得る．これを展開して，
C1
= G0 + P0 · c0
C2
= G1 + P1 · G0 + P1 · P0 · c0
C3
= G2 + P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · c0
C4
= G3 + P3 · G2 + P3 · P2 · G1 + P3 · P2 · P1 · G0 + P3 · P2 · P1 · P0 · c0
を得る．この式は，大文字小文字の違いを除けば式（4）∼ （7）と同じである．すなわち，
このキャリー計算に，図 2 の回路が使えることがわかる．そして，16 ビット加算器が構成で
きることがわかる．その構成図を図 4 に示す．以下同様の構成をすれば，16 ビット加算器を
4 つと，桁上げ先見器 (CLA4) を 1 つ使って 64 ビットの加算器が構成できる．また，32 ビッ
ト加算器は，16 ビット加算器を 2 つと桁上げ先見器 1 つを使って構成できる．この場合は，
C2 出力を最上位ビットからの桁上げ信号として使う．
c2
c1
G0
c4
c3
c0
P0
CLA4
s0 – s3
4
G0 P0
CADR4
4
G1 P1
CADR4
4
a0 – a3
s4 – s7
4
b0 – b3
4
a4 – a7
s8 – s11
4
G2 P2
CADR4
4
b4 – b7
4
a8 – a11
s12 – s15
G3 P3
4
CADR4
4
b8 – b11
4
4
a12 – a15 b12 – b15
注 CADR4のc0 – c3出力は省略した．
図 4: 16 ビット桁上げ先見加算器
このように構成すると，c0 入力からキャリー出力（CLA4 の c4 出力）までに何段のゲート
を通るだろうか？全加算器の pi ，gi 出力は，ci に依存しないので，それは桁上げ先見器の
ゲート通過段数で決まる．CLA4 は 2 段のゲートで構成されるから，16 ビット加算器では，
CLA4 を 2 個分，すなわち 4 段のゲートを通過する．64 ビット加算器では 6 段のゲートを通
過する．一方で，リップルキャリー型加算器は，全加算器 1 つあたり 2 段のゲートを通過す
るから，n ビット加算器では，2n 段のゲートを通過する．このことから，桁上げ先見型加算
器の高速性がわかる．
4