加算器の高速化

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


加算の復習と高速化

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

           
       
キャリー                                  
サム                                  

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


      Dさん担当   Cさん担当   Bさん担当   Aさん担当
           
       
キャリー   C4       C3         C2         C1    
サム                                  
  1. まずAさんが計算をする。計算の最後にC1の値がわかる。
  2. BさんはXがわかるまで、計算を始められない。
                                   
  時間
Aさんの仕事 *計算中* 休み 休み 休み  
Bさんの仕事 休み *計算中* 休み 休み  
Cさんの仕事 休み 休み *計算中* 休み  
Dさんの仕事 休み 休み 休み *計算中*  

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

                                   
  時間
Aさんの仕事 *計算中*                          
Bさんの仕事     *計算中*                      
Cさんの仕事         *計算中*                  
Dさんの仕事             *計算中*              

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

           
       
キャリー                                  
サム                                  

       
   
―――
キャリー     C1=0 Cin
サム      

↓記号化

        a3 a2 a1 a0
    b3 b2 b1 b0
―――
キャリー     C1=c4 c3 c2 c1 Cin
サム       s3 s2 s1 s0
  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

  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ですべての桁を伝播する場合である。

ここでクイズ5−2)をやる!


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

           
       
generate g15 g14 g13 g12 g11 g10 g9 g8 g7 g6 g5 g4 g3 g2 g1 g0
propagate p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0
先見キャリー C4 C3 C2 C1
キャリー                         cin
サム                                
           
       
generate g15 g14 g13 g12 g11 g10 g9 g8 g7 g6 g5 g4 g3 g2 g1 g0
propagate p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0
Generate G3 G2 G1 G0
Propagate P3 P2 P1 P0
先見キャリー C4 C3 C2 C1
キャリー                         cin
サム                                

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


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

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

           
       
キャリー                                  
サム                                  

2) 以下の表を、以下の順で埋めよ

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

3) 以下の表を埋めよ

           
       
generate                                
propagate                                
Generate        
Propagate        
先見キャリー        
キャリー                        
サム                                

 


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

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

この理由を説明せよ。

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

3)図4.24に示される2つの回路BOX(小と大)をゲートを用いて設計せよ。回路を簡単化する必要はない。ANDゲートとORゲートを用いて作成するのが簡単!

以上