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