The Carry-Select Adder
The carry-lookahead adder of the last article removes the carry chain by computing every carry from the inputs. The carry-select adder in this article does something quite different: it does not try to compute the carry any faster. It removes the waiting instead. A chess player does not sit idle while the opponent thinks; they work out their reply to each likely move in advance, and when the move comes they play the reply they already had. The carry-select adder prepares both answers and picks one when the carry arrives.
The idea
Take bits [7:4] of a 16-bit adder. This block needs $C_4$ before it can produce its sum and carry-out. In a ripple-carry adder it waits for $C_4$ to ripple through bits [3:0], which is most of the delay.
Instead, give the block two ripple-carry adders and run both from time zero. One assumes $C_4 = 0$ and one assumes $C_4 = 1$. While they work, bits [3:0] compute the real $C_4$ in the normal way. When $C_4$ arrives, a 2-to-1 mux picks the result that assumed the right value. The only delay added on top of the precomputed results is the mux, one gate delay.
This is speculation in hardware: extra area to compute both outcomes, and one mux delay to choose. Downstream blocks never wait for their carry-in, because both answers are already sitting there.
A 16-bit carry-select adder
Four 4-bit groups (Figure 1).
Group [3:0] is a plain 4-bit ripple-carry adder with $C_{in} = 0$. It produces $S[3:0]$ and $C_4$.
Group [7:4] has two 4-bit ripple-carry adders, one with $C_{in} = 0$ and one with $C_{in} = 1$, each producing a candidate $S[7:4]$ and a candidate $C_8$. Five muxes, four for the sum bits and one for the carry, select between the candidates using $C_4$.
Groups [11:8] and [15:12] are the same, selected by $C_8$ and $C_{12}$, each of which is itself a mux output from the previous group.
Timing
Take a 4-bit ripple-carry adder as 10 gate delays and a mux as 1.
At time 0, every ripple-carry block starts. Group [3:0] computes its real result; the other three groups compute both their candidates.
At time 10, group [3:0] is done and $C_4$ is known. At the same moment, all the candidate results in the other groups are done too, since they had the same 10 delays to work in.
At time 11, $C_4$ has passed through the muxes of group [7:4]: $S[7:4]$ is valid and $C_8$ is known.
At time 12, $C_8$ has selected group [11:8]. At time 13, $C_{12}$ has selected group [15:12].
Thirteen gate delays for 16 bits, against 34 for ripple-carry and about 8 for a hierarchical CLA. The carry-select adder sits between them, and it is built from nothing but ripple-carry blocks and muxes, which makes it easy to lay out and easy to verify.
| Path | Delay |
|---|---|
| Group [3:0] complete, $C_4$ ready | 10 |
| Candidates in the other groups complete | 10, in parallel |
| $S[7:4]$ and $C_8$ through mux 1 | 11 |
| $S[11:8]$ and $C_{12}$ through mux 2 | 12 |
| $S[15:12]$ and $C_{out}$ through mux 3 | 13 |
| 16-bit ripple-carry, for reference | 34 |
| 16-bit hierarchical CLA, for reference | about 8 |
Area
Each speculative group has two ripple-carry adders instead of one, plus its muxes. For the 16-bit adder above that is seven 4-bit adders and fifteen muxes where the ripple-carry adder had four adders, so roughly 1.6 to 1.8 times the area for a 2.6 times speed-up. Whether that is a good deal depends on the design. What the carry-select adder has in its favour is that its logic stays uniform as it scales, unlike the CLA, whose lookahead terms grow with width.
Power goes up too, and by more than the area alone suggests, because the discarded candidate still switched its nodes. In a battery-powered design that wasted switching is a real cost.
Group size and the square-root delay
With group size $k$ and width $N$, the critical path is the first group’s ripple time plus one mux per remaining group:
$$t = t_{RCA}(k) + \left(\frac{N}{k} - 1\right) t_{MUX}$$
For $k = 4$, $N = 16$: $10 + 3 = 13$, as above. Make $k$ smaller and the first term shrinks while the second grows; make it larger and the reverse. The minimum is where the two are balanced, and solving for that gives $k$ proportional to $\sqrt{N}$, with total delay also proportional to $\sqrt{N}$. This is why the carry-select adder is sometimes called a square-root adder.
Better still is to use unequal groups. Later groups have more muxes to pass through before their result is final, so they can afford to be wider, since a wider group takes longer to compute its candidates and that extra time is available anyway. Sizes such as 4, 5, 6, 7, 7 for a 32-bit adder balance the contributions and come close to optimal.
The carry-skip adder
A close relative is worth mentioning here. Within a group of $k$ bits, the carry either ripples through every stage or, if every bit propagates, it passes straight through. The carry-skip adder detects the second case:
$$\text{SKIP} = P_{k-1} P_{k-2} \cdots P_0$$
and uses a mux to route the carry-in directly to the carry-out when SKIP is 1, bypassing the ripple:
$$C_{out} = \text{SKIP} \cdot C_{in} + \overline{\text{SKIP}} \cdot C_{ripple}$$
The worst case is one group’s ripple plus a mux per skipped group, which again gives square-root delay with the right group sizes. It needs only one ripple-carry adder per group, so it is cheaper than carry-select, at the cost of timing that is a little harder to reason about.
Select-style logic turns up inside almost every fast adder in some form, often at the boundaries between lookahead groups, because muxes are fast and regular in silicon. And the same “compute both, keep one” idea appears further up the architecture: a processor that executes both sides of a branch and discards one is doing the same thing at a larger scale.
One practical note for FPGA users. Do not write a carry-select adder in Verilog for an FPGA. The dedicated carry chain in the fabric is faster than any structure you can build from LUTs and muxes, and A + B will use it. Carry-select is an ASIC technique.
Practice Exercise
A 24-bit carry-select adder uses equal 4-bit groups, a 4-bit ripple-carry adder is 10 gate delays, and a mux is 1. How many groups are there and how many are speculative? What is the worst-case delay? How does it compare with a 24-bit ripple-carry adder?
Solution
Six groups. The first is a single ripple-carry adder; the other five are speculative with two adders each.
Delay: $10 + 5 \times 1 = 15$ gate delays.
A 24-bit ripple-carry adder is $2 \times 24 + 2 = 50$ gate delays, so the carry-select version is about 3.3 times faster, for roughly 1.7 times the area.
You now have three adders: ripple-carry, carry-lookahead and carry-select, with delay growing as $N$, $\log N$ and $\sqrt{N}$. The next article puts them side by side, adds the prefix adders that real processors use, and looks at the difference between FPGA and ASIC that changes which one is actually fastest.