加算器の高速化

琉球大学　情報工学科　和田　知久

加算の復習と高速化

教科書のP２１９〜P２２８の「桁上げの先見」のあたりの内容を解説しますが、まず例を用いて説明します。

• 以下の16ビットの数の加算をやりましょう　（クイズ５−１）
  下位の4ビット分だけ記入しています。上位の計算は自分でやってください

• このような加算を高速にやれるようにするには、どうすればよいか？
• 何が計算のスピードを決めるネックか？

−＞　キャリー（桁上げ）が下位の桁から上位の桁へ伝播するのに時間がかかることがネックである。

• 同じ計算を4ビットずつに分けて、4人の人間が計算するとしたらどうなるか？

1. まずAさんが計算をする。計算の最後にC1の値がわかる。
2. BさんはXがわかるまで、計算を始められない。

• ということで、結果的に、以下のようになり4人の人間で仕事を早く終わらせることができない。

• さて？　どうすれば計算時間を短くすることができるか？？？？
• 4人の人間の休み時間をいかにして、減らせばよいか？

キャリーのC1, C2, C3を先に計算すればよい。そうすれば以下のようにできる。

C1、C2、C3発生回路の検討

• C1、C2、C3発生回路はみな同じ下記の4ビットの加算の計算となる。

↓

↓記号化

• 今やりたいのは4ビットの入力(a3, a2, a1, a0)と(b3, b2, b1, b0)からC1=c3を直接求める回路。
• C1=c4が’１’になるのはどういう時か？

1. a3=1 and b3=1 の時（他の入力に関係ない）
2. a3=1 and b3=0 もしくは　a3=0 and b3=1 の時でかつ、その下位からのキャリーc2=1の時

• ここで新しい概念を導入する（シンプルであるが）

1. 各桁で、ai=1 & bi=1 であれば、キャリー ci　が発生する。
   したがって、発生=generateで　gi = ai and bi なる信号を計算する。
2. 各桁で、ai=1 and bi=0 もしくは ai=0 and bi=1 であれば、その下の桁からのキャリーが伝播する。
   したがって、伝播=propageteで pi = ai exor bi なる信号を計算する。
   教科書では　or を’＋’記号でしめし、pi = ai + bi と示している。これは、exor と or は異なるが、問題ないのでそうしている。

• これをもちいれば、

c4 = g3 + p3･c3
c3 = g2 + p2･c2
c2 = g1 + p1･c1
c1 = g0 + p0･cin

• これを書き直すと、

c4 = g3 + p3･(g2 + p2･(g1 + p1･(g0 + p0･c0)))
c4 = g3 + p3･g2 + p3･p2･g1 + p3･p2･p1･g0 + p3･p2･p1･p0･cin

• この意味はｃ４＝C1キャリーが発生する条件は

1. 3桁目g3=1で発生、3桁目で発生する、もしくは
2. 2桁目g2=1で発生し、3桁目でp3=1でそれが伝播する、もしくは
3. 1桁目g1=1で発生し、2桁目､3桁目ともp2=p3=1でそれが伝播する、もしくは
4. 0桁目g0=1で発生し、1桁目､2桁目､3桁目ともp1=p2=p3=1でそれが伝播する、もしくは
5. cin=1で最下位でキャリーが入力され、p0=p1=p2=p3=1ですべての桁を伝播する場合である。

• 教科書ではこれを図４．２２でがんばって説明している。あなたに、作者の意図が伝わるか？

ここでクイズ５−２）をやる！

• クイズ５−１）をやって、cinがp0,p1,p2,p3,g0,g1,g2,g3と計算されて、C1が発生する。

細かくややこしいので、4ビットを固まりとして、キャリー発生＝Generateと、キャリー伝播＝Propagateを考える。

• すなわち、以上の表を以下のように修正する

C1 = G0 + P0･cin
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

P0 = p3･p2･p1･p0
P1 = p7･p6･p5･p4
P2 = p11･p10･p9･p8
P3 = p15･p14･p13･p12

G0 = g3 + p3･g2 + p3･p2･g1 + p3･p2･p1･g0
G1 = g7 + p7･g6 + p7･p6･g5 + p7･p6･p5･g4
G2 = g11 + p11･g10 + p11･p10･g9 + p11･p10･p9･g8
G3 = g15 + p15･g14 + p15･p14･g13 + p15･p14･p13･g12

クイズ６　：学籍番号､名前、日付を書いて提出のこと。

１）　以下の16ビットの数の加算をやりましょう

２）　以下の表を、以下の順で埋めよ

1. generate
2. propagate
3. 先見キャリー
4. その他のキャリーとサム

３）　以下の表を埋めよ

宿題６　：学籍番号､名前、日付を書いて提出のこと。

１） propagateの計算時に exor ではなく、or　をもちいても良い

この理由を説明せよ。

２）上記問題で、exor を用いる場合と　or を用いる場合で、速度と回路面積でどのような違いがあるか述べよ！

３）図４．２４に示される２つの回路BOX（小と大）をゲートを用いて設計せよ。回路を簡単化する必要はない。ANDゲートとORゲートを用いて作成するのが簡単！

以上