  We consider the problem of constructing fast and small binary adder circuits.
Among widely-used adders, the Kogge-Stone adder is often considered the
fastest, because it computes the carry bits for two $n$-bit numbers (where $n$
is a power of two) with a depth of $2\log_2 n$ logic gates, size $4 n\log_2 n$,
and all fan-outs bounded by two. Fan-outs of more than two are avoided, because
they lead to the insertion of repeaters for repowering the signal and
additional depth in the physical implementation. However, the depth bound of
the Kogge-Stone adder is off by a factor of two from the lower bound of $\log_2
n$. This bound is achieved asymptotically in two separate constructions by
Brent and Krapchenko. Brent's construction gives neither a bound on the fan-out
nor the size, while Krapchenko's adder has linear size, but can have up to
linear fan-out. With a fan-out bound of two, neither construction achieves a
depth of less than $2 \log_2 n$. In a further approach, Brent and Kung proposed
an adder with linear size and fan-out two, but twice the depth of the
Kogge-Stone adder. These results are 33-43 years old and no substantial
theoretical improvement for has been made since then.
  In this paper we integrate the individual advantages of all previous adder
circuits into a new family of full adders, the first to improve on the depth
bound of $2\log_2 n$ while maintaining a fan-out bound of two. Our adders
achieve an asymptotically optimum logic gate depth of $\log_2 n + o(\log_2 n)$
and linear size $\mathcal {O}(n)$.
