加算器の原理 ─ リップルキャリーからキャリー先読み・接頭加算器まで

加算が遅延を決める理由

ALUの中で加算は最も頻繁に使われる演算であり、減算・アドレス計算・比較もすべて加算器に帰着します。そして加算は単なる桁ごとの足し算ではありません。ある桁の結果は、下位から繰り上がってくる**桁上げ（キャリー）**に依存します。この桁上げをいかに速く全桁へ届けるかが、加算器の遅延を支配します。

1ビットの全加算器（full adder）は、入力 a、b と下位からの桁上げ入力 c に対し、和 s と上位への桁上げ出力 c_out を次のように作ります。

s     = a XOR b XOR c
c_out = (a AND b) OR (c AND (a XOR b))

この c_out が次の桁の c になります。問題は、上位桁の和を確定するには下位の桁上げが確定していなければならない、という直列の依存にあります。加算器の設計史は、この桁上げ伝搬の鎖をいかに短く切るかの工夫の歴史です。

リップルキャリー加算器：O(n)の素直な実装

全加算器をn個並べ、各段の c_out を次段の c に素直に繋いだものが**リップルキャリー加算器（RCA）**です。回路は最小（全加算器n個のみ）で配線も規則的ですが、最下位の桁上げが最上位まで「波（ripple）」のように伝わって初めて結果が確定します。

遅延の臨界パス（RCA, nビット）
  最下位の c0 → c1 → c2 → … → c_n
  桁上げ1段の遅延を t_carry とすると
  全体の遅延 ≒ n × t_carry  → O(n)

つまりビット幅に比例して遅くなります。64ビットなら最悪64段ぶんの桁上げを直列に待つことになり、これはプロセッサのパイプライン1ステージに収めるには遅すぎます。面積は最小だが遅延が線形、という一方の極がRCAです。

generate と propagate：桁上げを式に分解する

桁上げを速く求める鍵は、各桁を桁上げ入力に依存しない量へ分解することです。i番目の桁について次の2つを定義します。

generate  g_i = a_i AND b_i        … その桁自身が桁上げを生む
propagate p_i = a_i XOR b_i        … 下位の桁上げをそのまま上へ通す

すると桁上げ出力は、桁上げ入力 c_i を使って次のように書けます。

c_(i+1) = g_i OR (p_i AND c_i)

g_i と p_i は a_i、b_i だけから決まり、桁上げを待たずに全桁ぶん一斉に計算できます。残るのは、この漸化式を展開して各桁の c_i を桁上げ入力 c_0 から直接求めることです。

キャリー先読み加算器（CLA）：漸化式を展開する

c_(i+1) = g_i OR (p_i AND c_i) を c_0 まで再帰的に展開すると、各桁の桁上げが論理積・論理和の浅い式になります。

c1 = g0 OR (p0·c0)
c2 = g1 OR (p1·g0) OR (p1·p0·c0)
c3 = g2 OR (p2·g1) OR (p2·p1·g0) OR (p2·p1·p0·c0)

各 c_i が c_0 と g/p だけの2段論理（AND-OR）で書けるため、原理上は段数一定で全桁上げを並列に求められます。これがキャリー先読み加算器（CLA）です。ただし式の項数は桁が上がるほど増え、上位桁の論理積ゲートは入力数（ファンイン）が大きくなります。実ゲートのファンインは有限なので、現実には4ビット程度のブロックにまとめ、ブロック間をさらに先読みする階層CLAにします。完全並列の理想と、ファンイン制約の現実の折り合いがCLA設計の勘所です。

キャリースキップ／キャリーセレクト：中庸の最適化

CLAほど凝らずにRCAを部分的に速くする手もあります。

キャリースキップは、ブロック内の全桁が p_i=1（桁上げ素通し）なら、そのブロックの桁上げ伝搬を丸ごと飛ばして上位へ直結します。ブロック幅を適切に選ぶと遅延はおよそ O(√n) に下がり、追加回路はブロックごとのAND1個程度と軽量です。

キャリーセレクトは、各ブロックを桁上げ入力0用と1用の2本のRCAで先に両方計算しておき、下位から本当の桁上げが届いた瞬間にマルチプレクサで正解を選びます。計算を投機的に二重化して待ち時間を隠す発想で、面積はおよそ2倍ですが遅延を大きく削れます。

接頭加算器：桁上げ計算を結合演算にたたむ

CLAの並列性を体系化したのが接頭（prefix）加算器です。鍵は、隣り合う桁の (g,p) を1つにまとめる結合演算子（ここでは ∘ と書きます）を定義することです。

(g_hi, p_hi) ∘ (g_lo, p_lo)
  = ( g_hi OR (p_hi AND g_lo),  p_hi AND p_lo )

この演算子は結合律を満たします。よって0桁目からi桁目までの (g,p) をまとめた値（プレフィックス）は、足し算の総和を木でまとめるのと同じ要領で計算順序を自由に組み替えられます。i桁目までまとめた g がそのまま桁上げ c_(i+1) になるため、すべての桁上げを求める問題は「結合演算子のプレフィックス計算」に帰着します。結合律のおかげで木の深さ、すなわち遅延を O(log n) にできます。

Kogge-Stone と Brent-Kung：トレードオフの両端

同じ O(log n) でも、結合演算子のノードをどう配置するかで段数・素子数・配線量が変わります。代表的な2つが両極を示します。

Kogge-Stoneは段数を理論最小の log2(n) にし、各ノードのファンアウトを1に抑えるため遅延が安定して速い反面、中間のプレフィックスを多数複製するので演算ノードと配線が多く、面積と配線混雑が大きくなります。Brent-Kungは上りと下りの2本の木で結果を集約・分配し、ノード数を約2nまで削りますが、段数が約2倍になり遅延では劣ります。Sklansky や Han-Carlson はこの両端の中間で、段数・ファンアウト・配線を別の配分で取った設計です。

まとめ

• 加算の遅延を支配するのは桁上げ伝搬であり、全加算器を直列に繋ぐRCAは O(n) 遅延だが面積最小。
• 各桁を generate（g=a·b）と propagate（p=a XOR b）に分解すると、桁上げを桁上げ入力に依存させず並列に求められる。
• CLAは漸化式を展開して桁上げを2段論理で導くが、ファンイン制約から実装は階層化される。
• キャリースキップ／セレクトは RCA を中庸に高速化し、おおむね O(√n) を狙う実用的な折衷案。
• 接頭加算器は g/p の結合律を使い桁上げ計算を木にたたんで O(log n) を達成、Kogge-Stone（速いが配線密）と Brent-Kung（軽量だが段数倍）が遅延・面積・配線トレードオフの両端を示す。