キャリールックアヘッド加算器：リップルキャリーより高速

キャリールックアヘッド加算器は、生成・伝播信号でキャリー生成を再構成します。4 ビット CLA を導出し、実設計で階層化が必要な理由を説明します。

Denny

2026年5月7日読了まで約8分

Chalkboard feature illustration for “キャリールックアヘッド加算器：リップルキャリーより高速”

要約： キャリールックアヘッドは、直列の漸化式 $C_{i+1}=G_i+P_iC_i$ を、ビットごと・グループごとの 生成／伝播 信号で書き換えます。小さな平坦 CLA は被演算子から複数のキャリーを直接表せます。階層型と並列プレフィックス型は、追加セル、ファンアウト、配線を代償に、キャリー深さを線形から対数的へ近づけます。

4 ビットのリップルキャリー加算器は単純です。四つの全加算器を連鎖し、各 $C_{out}$ を次の $C_{in}$ へ接続します。最悪のキャリー依存は語長とともに伸びますが、タイミングを満たせるかは技術、クロック目標、セル、周辺データパスに依存します。幅だけで設計を「不適格」とは言えません。

CLA は、被演算子から直接得られる中間信号からキャリー式を導くことで、この直列依存に取り組みます。

リップルキャリーが遅くなる理由

全加算器の式を思い出してください。

$S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

$S_i$ と $C_{i+1}$ はともに $C_i$ に依存します。したがって依存鎖は $C_0 \to C_1 \to C_2 \to \dots \to C_n$ です。一段のキャリーに $t_c$ かかるなら、最悪の加算時間はおよそ次です。

$T_{ripple} \approx n \cdot t_c + t_{sum}$

一次の依存は語長に対し線形です。絶対ナノ秒には実装の指定が必要なので、ゲート遅延数はトポロジ比較にのみ使います。これが伝搬遅延の制約です。

生成と伝播

キャリー式をもう一度見ます。

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

最初の項 $A_iB_i$ は両被演算子ビットが 1 のとき真で、 $C_i$ に関係なくキャリーを生みます。

$G_i = A_i \cdot B_i$

これが生成信号です。二番目の項は、一方だけが 1 なら到着したキャリーを通すことを表します。

$P_i = A_i \oplus B_i$

これが伝播信号です。よって式は次へ縮約されます。

$C_{i+1} = G_i + P_i \cdot C_i$

これは、既知の AND ゲートと OR ゲートによる漸化式であり、平坦化できます。

キャリー漸化式を平坦化する

既知の $C_0$ から漸化式を代入します。

$C_1 = G_0 + P_0 C_0$ $C_2 = G_1 + P_1G_0 + P_1P_0C_0$ $C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$ $C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$

各 $C_{i+1}$ は、0〜 $i$ 段の $G$ 、 $P$ 、 $C_0$ による積和形です。論理的には、直前の全加算器の物理遷移完了ではなくこれらの信号だけに依存します。ただし物理的には、広い積項と配線にも有限のゲート、バッファ、配線が必要です。

4 ビットの例

$C_0=0$ として $A=1011_2$ （11）と $B=0110_2$ （6）を加えます。ビットは下位から書きます。

ビット $i$	$A_i$	$B_i$	$P_i=A_i\oplus B_i$	$G_i=A_iB_i$	$C_i$	$S_i=P_i\oplus C_i$
0	1	0	1	0	0	1
1	1	1	0	1	0	0
2	0	1	1	0	1	0
3	1	0	1	0	1	0

キャリー式から $C_1=0$ 、 $C_2=1$ 、 $C_3=1$ 、 $C_4=1$ です。 $C_4S_3S_2S_1S_0$ は $10001_2=17$ になります。算術結果はリップルキャリーと同じで、変わるのはキャリーネットワークのトポロジだけです。

グループ生成と伝播

$i$ から $j$ のビット群に対して、グループ伝播と生成を定義します。

$P_{j:i}=P_jP_{j-1}\cdots P_i$ $G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$ $C_{j+1}=G_{j:i}+P_{j:i}C_i$

隣接二群は同じ演算で結合できます。

(G_H,P_H)\circ(G_L,P_L) = (G_H+P_HG_L,\;P_HP_L)

この結合性が、直列鎖ではなくペア、さらにペアのペアをツリーにする階層 CLA と並列プレフィックス加算器の鍵です。

4 ビット CLA の構成

ブール水準の平坦 4 ビット CLA には三つの機能があります。

生成／伝播層。 $n$ 個の AND が $G_i=A_iB_i$ を、 $n$ 個の XOR が $P_i=A_i\oplus B_i$ を一遅延で並列生成します。
キャリーネットワーク。 AND-OR 論理が展開式から $C_1$ 〜 $C_4$ を計算します。無制限ファンインなら二論理段に見えますが、実ライブラリは広い項を分解するため、幅とともに深さと負荷が増えます。
和の層。 $n$ 個の XOR が $S_i=P_i\oplus C_i$ を一遅延で生成します。

四ビットでは全加算器の連鎖よりキャリー経路を短縮できます。しかし平坦な式を無限に伸ばすのは実用的でないため、大きな CLA はグループを導入します。

4 ビット CLA のブロック図

A0,B0 ─┬── XOR ── P0 ──┐                           ┌── XOR ── S0
       └── AND ── G0 ──┤                           │
                       │   ┌─── carry network ───┐ │
A1,B1 ─┬── XOR ── P1 ──┤   │                     │ ├── XOR ── S1
       └── AND ── G1 ──┤   │   computes          │ │
                       ├──>│   C1, C2, C3, C4    │─┤
A2,B2 ─┬── XOR ── P2 ──┤   │   from expanded     │ ├── XOR ── S2
       └── AND ── G2 ──┤   │                     │ │
                       │   │   carry expressions  │ │
                       │   └─────────────────────┘ │
A3,B3 ─┬── XOR ── P3 ──┤                           ├── XOR ── S3
       └── AND ── G3 ──┘                           │
                                                   └────────── C4
C0 ──────────────────────>┘

ファンイン、配線、隠れたコスト

$C_4$ の最長平坦式は $C_0$ を含めると五入力積項です。 $C_{16}$ では 17 入力になります。標準セルのファンインには限界があり、長い配線と大きな負荷は遅延を加えます。ブール式が浅く見えても、文字どおり平坦な CLA はきれいにスケールしません。

通常の解決策は 階層化 です。しばしば四ビット単位でグループ $G$ と $P$ を作り、別段で群を結合します。16 ビットなら四つの 4 ビット群と第二ルックアヘッド段を使えます。並列プレフィックス加算器は、この結合演算をツリー全体へ適用します。

構造	キャリー依存	代表的な強み	代表的なコスト
リップルキャリー	線形	小面積、単純な配線	最悪キャリー経路が長い
ブロック・ルックアヘッド	階層的	速度／面積の中程度の妥協	広い局所論理と群配線
キャリーセレクト	両キャリー場合を事前計算	決定経路が短い	和ハードウェアの重複
並列プレフィックス	ツリー状	低い論理深さ	多いプレフィックスセル、配線、高ファンアウト

実際の遅延、面積、エネルギーは、マッピングと物理実装後に測定する必要があります。抽象的なゲート段数で有利なトポロジが、混雑、バッファ、負荷を含めると負けることもあります。

CLA を超えて：並列プレフィックス加算器

キャリールックアヘッドの考え方は一般化できます。漸化式 $C_{i+1}=G_i+P_iC_i$ は独自の演算子の下で結合的です。隣接位置を組にし、さらに組の組をツリーで作れます。これが 並列プレフィックス ファミリです。

Kogge–Stone： プレフィックス深さが小さく論理ファンアウトが抑えられますが、密な配線と多くのノードが必要です。
Brent–Kung： プレフィックスノードと配線が少ない一方、深さは大きくなります。
Han-Carlson、Ladner-Fischer、Sklansky： ファンアウト、配線複雑度、深さに異なるトレードオフがあります。

量産加算器はプレフィックスを混ぜたり、スパース化したり、選択した群の周囲にキャリーセレクトを置くこともあります。選択は、特定のタイミング、面積、電力、配線予算に対して行われます。プロセッサのクロック周波数だけから加算器トポロジを知ることはできません。

DigiSim で CLA を実装する

4 ビット CLA は基本部品から作れます。生成用の四つの AND ゲート、伝播用の四つの XOR ゲート、上のキャリー式、和用の四つの最終 XOR を用います。高水準の加算器と 8 ビット加算器は振る舞いを提供する便利部品であり、文書が明記しない限り内部構造を推測してはいけません。

トポロジを比べるには、全加算器四つをリップルキャリーとしてつなぎ、別に 4 ビット CLA を作ります。まず全被演算子組み合わせで機能同値を検証します。次にシミュレータがゲート遅延をモデル化していれば、入力変化後の最後の安定時刻を比べます。理想ゲートなら依存論理段数を数えてください。理想波形からシリコンタイミングは予測できません。

よくある落とし穴

$P_i$ が OR でなく XOR であることを忘れる。 $P_i=A_i+B_i$ と $P_i=A_i\oplus B_i$ は、 $A_i=B_i=1$ が $G_i$ で覆われるため、いずれも正しいキャリーを作れます。しかし XOR を選べば同じ線を $S_i=P_i\oplus C_i$ へ使えます。OR 定義ではこの再利用ができず、和用 XOR が別に必要です。
ファンインの拡大を過小評価する。 平坦な 16 ビット展開は $C_0$ を含めて 17 リテラル項を持ちます。実用的な広幅設計では論理を分解またはグループ化します。
CLA が常に速いと考える。 狭い幅ではリップル実装が面積で勝ち、十分にタイミングを満たす場合があります。アーキテクチャ非依存の交差幅はありません。
和とキャリーのクリティカルパスを混同する。 キャリーネットワークの深さが支配的でも、最後の和 XOR がさらに一ゲート遅延を加えます。

次は何を学ぶか

ALU の仕組み：ゲートから作る算術論理装置を続け、別の算術最適化として Booth 乗算器の解説を読んでください。

実際に二つの加算構造を比べるには、キャリー付き全加算器テンプレートを開き、四つを連鎖してリップルキャリー加算器にします。ロジックアナライザでビットごとのキャリー伝播を観察し、次にこの記事の式から同等の 4 ビット CLA を作って両方の回路を測定してください。この差こそが高速 ALU の存在理由です。