ディジタル回路：桁上げ先見加算器・プリフィックス加算器

順次桁上げ加算器については、割愛。

桁上げ先見加算器

加算器の設計。順次桁上げ加算器みたいに桁上げをいちいち計算して渡して、とやっていると時間がかかるので、先に計算をする。大まかな流れとしては、

・加算器全体をブロック分け

・ブロックごとに、ブロックの外に桁上げが伝播するか判定

・それを用いて計算

4ビットで考える

一ブロックは基本的に4ビット、なのでとりあえず4ビットだけを考えてみる。

登場する信号は生成信号(G)、伝播信号(P)の2つ。これは桁ごとに計算される。以下では加算を行う2つの信号の i 桁目を A_i と B_i とする。

・生成信号 G_i：その桁で桁上げが生成されるかの信号。A_i = B_i = 1の場合は桁上げが生成されるので、G_i = A_i * B_i で計算される。

・伝播信号 P_i：その桁に下の桁からの桁上げが伝播してきたとき、桁上げを生成するかの信号。A_i か B_i の片方が1であれば桁上げを伝播するので、P_i = A_i ⊕ B_i で計算される。

この2つを用いると、特定の桁の繰り上がりビット C_i について、以下の漸化式が成り立つ。

C_i = G_i + P_i * C_i-1

つまり、その桁で桁上げを生成するか、前の桁の桁上げを伝播するか、というわけ。この漸化式を順番に計算しているのが、桁上げ伝播加算器。漸化式を解く回数分の時間がかかる。ということで、この漸化式を展開してしまう。4ビットなので、i = 0~3。例としてC_3を示す。

C_3 = G_3 + P_3 * ( G_2 + P_2 * ( G_1 + P_1 * ( G_0 + P_0 * C_-1 ) ) )

さらなる展開式はめんどくさいので書かないけど、この式を展開してしまえば4つの項の論理和であろうことは分かる。つまり、「各桁のGとPだけを用いて論理演算した結果」の論理和を取るという2段でC_3が計算できることが分かる。

桁上げ伝播加算器におけるC_3の計算手順は、C_0の計算→C_1の計算→C_2の計算→C_3の計算 であり、4段。今回4ビットだから4段で済んでるけど、もし32ビットなら32段で困る。しかしここまでの計算方法を用いれば、何ビットの計算であったとしても、GとPの計算→GとPを用いた論理演算→その論理和の計算、の3段で済む。

桁上げさえわかれば、あとはその桁上げC_iとP_iを用いてS_i = P_i ⊕ C_i でその桁の出力は計算できる。当たり前だけど、ここは全加算器の計算と同じ。なんかここの説明を省いてるのが多くてわかりにくかった。

なぜブロック分けするか？

GとPの計算→GとPを用いた論理演算→その論理和の計算、で良かったんだけど、最後の論理和の計算は例えば4ビットの例では4個の入力の論理和だった。これをたとえば32ビットでやろうとすると、32個の入力から論理和を計算する羽目になる。しかし、実際の論理ゲートの入力は4個が限界である(ファンイン数)。ということで、4ビットずつにブロック分けして考えていく。

32ビットに応用する

ということで4ビットずつにブロック分けして32ビットの計算を考える。この時に先ほどまでに加えて考えないといけないのは、ブロック間の生成と伝播。ということで、各ブロックにおける生成と伝播を計算する式を考える。実は、今までの考え方を拡張すればよい。つまり、ブロックが桁上げを生成するか伝播するかというわけ。

ブロックの桁上げ生成

3桁目から0桁目のブロックの生成信号をG_3:0とする。ブロックが桁上げを生成するのは、「ブロックの最上位桁が桁上げを生成する」または「ブロックの最上位桁が桁上げを伝播し、かつその前の桁が桁上げを生成する」場合。これを順々に考えて式にすると、

G_3:0 = G_3 + P_3 * ( G_2 + P_2 * ( G_1 + P_1 * G_0 ) )

である。上で出てきた漸化式の展開式とほとんど同じ。

ブロックの桁上げ伝播

3桁目から0桁目のブロックの伝播信号をP_3:0とする。ブロックが桁上げを伝播するのは、ブロック内のすべての桁が桁上げを伝播するとき。よって、これを式にすると、

P_3:0 = P_3 * P_2 * P_1 * P_0

である。

あわせる

ということで、このブロックの桁上げ出力 C_i は、そのブロックへの桁上げ出力 C_i-1 を用いて、

C_i = G_3:0 + P_3:0 * C_i-1

で計算できる。第一項はブロック内生成、第二項はブロックに届いた桁上げを頑張って伝播したとき。あとは4ビットで考えたブロック内の計算さえすれば結果が出る。

計算速度

ということでお待ちかねの計算速度。桁上げ先見加算器がやる計算は以下。

・各桁のGとPの計算

・各ブロックのGとPの計算

ここまでは全ブロック同時。

・ブロックの桁上げを順次計算　

これは最後のブロックまで届くまでなので、Nビットをkビットずつに分けている場合、(N/k - 1)回行われる。

・最後のブロックの出力計算

これは1桁1桁が全加算器の計算時間と同じ。S_i = P_i ⊕ C_i で計算するよって言ったやつ。

順に時間をt_pg、t_pg_block、t_AND_OR、t_FAとすれば、

t_CLA = t_pg + t_pg_block + (N/k - 1)t_AND_OR + kt_FA

となる。

ゲート数

計算式を見ればわかるが。。。

t_pg：各桁のGとPの計算にはゲート1個

t_pg_block：各ブロックのGとPの計算にはゲート6個

t_AND_OR：各ブロック間の桁上げ伝播にはANDとOR一個ずつのゲート2個

t_FA：全加算器の計算にはゲート3個

の時間がかかる。

プリフィックス加算器

やりたいことは、全ての桁の桁上げ入力を先に全部計算してしまい、それを用いて計算結果を出すこと。i桁目の2つの数をA_i、B_iとして、i桁目への桁上げをC_i-1とすれば、出力S_iは

S_i = ( A_i ⊕ B_i ) ⊕ C_i-1

で求められる。こうなれば次はC_i-1をどう出すか。

ここで -1 桁目の生成信号Gと伝播信号Pを考えてみる。 -1桁目の桁上げ出力はC_inであり、G-1 = C_in、P-1 = 0となる。

次に、0桁目と-1桁目を合わせたブロックのG_0:-1とP_0:-1を用いてC_0を考える。P-1 = 0なので、P_0:-1 = P_0 * P-1 = 0であることから、C_0 = G_0:-1 + P_0:-1 * C-1 = G_0:-1 となる。

さらに、1桁目から-1桁目をブロックとしたときも同様に考えてみると、C_1 = G_1:-1となることがわかる。順々に計算すれば、C_i-1 = G_i-1:0であることがわかる。これを用いてS_iの式を書き換えれば、

S_i = (A_i ⊕ B_i ) ⊕ G_i-1:-1

となる。このブロックごとの生成信号G_i-1:-1をプリフィックスと呼び、これをどのように計算するかを考える。

プリフィックスの高速計算

連続した2ブロックから合成したブロックのG、P計算

ここで、G_i:jとP_i:jを上位部分と下位部分に分けて、その2つのPとGから計算する方法を考える。i > k > jとし。G_i:k、P_i:kを上位部分、G_k-1:j、P_k-1:jを下位部分とすると、

G_i:j = G_i:k + P_i:k * G_k-1:j

P_i:j = P_i:k * P_k-1:j

となる。一個目の式は、「上位で桁上げを生成する or (下位で桁上げを生成する and 上位で桁上げを伝播する)」と、ブロック内で桁上げの生成ができることを示している。二個目の式は、「上位が桁上げを伝播する and 下位も桁上げを伝播する」と、ブロック内で桁上げの伝播ができることを示している。

どう使うか

プレフィックス加算器の計算をやっと示す。プレフィックス加算器は、

・全ての桁でGとPを計算する

・隣り合う2個ずつをブロック分けしたブロックのGとPを計算する

つまり、G_0:-1、G_2:1、G_4:3、・・・といった具合に計算を行う。

・隣り合う2ブロックずつを合わせたブロックのGとPを計算する

つまり、G_2:-1をG_0:-1、G_2:1から、G_6:3をG_6:5とG_4:3から・・といった具合に計算を行う。

・並行して、他のブロックのGとPを計算する

つまり、G_1:-1をG_1:1 = G_1とG_0:-1から計算するとか。

という流れになる。ここで、G_i:i = G_i、P_i:i = P_i と考えている。

計算時間

計算回数を考えてみる。PとGは同時に計算されるので、Gのみで書く。例えば8ビットであれば、

・G_7、G_6、・・・、G_0の計算

・G_6:5、G_4:3、G_2:1、G_0:-1の計算

・G_6:3、G_2:-1の計算（裏でG_5:3やG_1:-1を計算）

・G_6:-1の計算（裏でG_5:-1、G_4:-1、G_3:-1を計算）

括弧内の計算は、そこまでに求められたGから計算できるようになっていることがわかる。つまり、最高位ビットの計算に用いる桁上げであるG_6:-1を計算し終わるのと同時に、全ビットの桁上げの計算が完了するということになっている。

今回は8ビットであり、8ビットの加算に用いるプレフィックスの計算は、各桁のPとGを求めてから3回の計算で終了している。考えれば、1→2→4→8で3回、つまり、log_2(8)回の計算だったということになる。Nビットなら、log_2(N)回の計算で済むことが容易にわかる。

よって、プレフィックス加算器の計算時間は、プレフィックスを計算する回路1段の遅延時間t_pg_prefixを用いて、

t_PA = t_pg + log_2(N) * t_pg_prefix + t_XOR

で求められる。第三項のt_XORがあるのは、求められた桁上げから最後に結果を出力するにはXORゲートを通す必要があるため。

ゲート数

こっちも計算式を見ればわかる。

t_pg_prefix：AND・ORのゲート2個

t_pgは前と同じくゲート1個、t_XORはその名の通りゲート1個。

まとめ

計算したいビット数Nが計算時間の式には必ず登場するが、そのオーダーをどう下げるかで計算時間が大きく異なる。桁上げ先見加算器では(N/k - 1)、プリフィックス加算器ではlog_2(N)まで落とした。あとはそれぞれの計算に何個ゲートを使っているかを考えれば計算時間がわかるね～。