1ビットの論理から複数ビットの加算へ
半加算器、全加算器、4ビットRCAを順に構成し、各ビットのキャリーが 低位から高位へ伝搬する仕組みと、その遅延を観察する。
1ビット加算を Carry と Sum の2出力として読む。
10進数で「9+1=10」になると一桁上がるように、2進数では 「1+1=10（二進数）」 で桁が上がる。
この「上の桁に1を持ち越す」ことを 桁上がり（キャリー / Carry） と呼ぶ。
右端の0が現在の桁の Sum、左端の1が次の桁へ渡す Carry になる。
2進数の足し算も、右（LSB）から順に1桁ずつ計算して、桁上がりを左隣の桁に伝えていく。
この例では bit0 で生じた Carry が bit1、bit2、bit3 へ順に伝わる。この直列の伝搬経路が
リップルキャリー（Ripple Carry） と呼ばれる。
1ビット + 1ビット を計算する最小の回路
半加算器の内部構造（XOR + AND）
| A | B | S（和） | C（桁上がり） |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
なぜ「半」加算器なのか。 2つのビットを足せるが、前の桁からの 桁上がり入力（Cin）を受け取れない。 複数桁の計算では「前の桁から来たキャリーも一緒に足す必要がある」—— それが次の「全加算器」である。
A、B、前段の Cin を加算し、S と次段の Cout を出力する。
全加算器は 半加算器を2つ と OR ゲート1つ で構成できる。
全加算器の内部構造（HA×2 + OR）
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
全加算器4段を Carry の直列経路で接続する。
全加算器（FA）× 4
各ビット（bit0〜bit3）を担当
C1 → C2 → C3 の順に
Carry が低位から高位へ伝わる
各入力は0〜15
C4を含む5ビット結果は0〜31
bit0からbit3まで、Carry が確定する順序を追跡する。
Carry のクリティカルパスと高速化手法を比較する。
最悪の場合、bit0で発生したCarryが全段を通過し、bit31のSumまたは最終Coutが確定するまで待つ必要がある。 したがって段数Nに対してCarry経路の遅延は線形に増える。これは回路の最大動作周波数を制限する クリティカルパス になる。
Carry-Lookaheadは各ビットのGenerate（G）とPropagate（P）からCarryをまとめて求める。 Kogge–StoneやBrent–Kungなどの並列プレフィックス加算器は、この計算を木構造にして論理段数を減らす。 実際の高性能ALUでは、面積・配線・消費電力とのバランスに応じて複数方式を組み合わせる。
| 種類 | 遅延 | 回路規模 | 主な用途 |
|---|---|---|---|
| 半加算器 (HA) | 最小 | 2ゲート | 1ビット加算 |
| 全加算器 (FA) | 小 | 典型構成で5ゲート | RCA の基本単位 |
| リップルキャリー (RCA) | O(N) | FA × N | 小規模・低面積重視 |
| CLA / Prefix | 階層化でO(log N) | 大 | 高性能ALU |