carry_lookahead.txt

Start with the classical carry equation:

c[i+1] = f(x[i], y[i], c[i])

Let f_i(c) = f(x[i], y[i], c), so that f_i is the partial application of f to x[i] and y[i].

Now c[i+1] = f_i(c[i]) = f_i(f_(i-1)(c[i-1]) = f_i(f_(i-1)(...(c[0]))) = F_i(c[0])

where F_i is defined as f_i composed with F_(i-1) for i > 0 and F_0 = f_0.

Then F_0, F_1, ... is just the scan of the sequence f_0, f_1, ... with respect to the function composition operator.

Since function composition is associative, this scan can be computed in logarithmic depth, assuming we can
represent the relevant functions and their composition operator efficiently.

Fortunately, both the input carry and the output carry are a single bit, and there are only 2^(2^1) = 4
possible functions of that type: for each of the 2 possible inputs, we have to choose one of 2 outputs.
If h is such a function, we can use the mux representation:

    h(x) = when(x, h(1), h(0)) = (x & h(1)) | (~x & h(0))

Thus if we specify the bits h(1) and h(0), we will have specified h completely and uniquely.

Now suppose we have two such functions, h and k, and we want to compute the representation of their composition h(k(x)):

    h(k(x)) = when(k(x), h(1), h(0)) = when(when(x, k(1), k(0)), h(1), h(0))

If we plug in x = 1, we get when(k(1), h(1), h(0)). For x = 0, we get when(k(0), h(1), h(0)). So we can define
the function composition operator in this representation as follows:

    (h(1), h(0)) . (k(1), k(0)) = (when(k(1), h(1), h(0)), when(k(0), h(1), h(0)))

Going back to our original use-case of computing carry chains, it turns out that only 3 of the 4 possible functions
can turn up. These are conventionally called kill (the constant 0 function), generate (the constant 1 function)
and propagate (the identity function). The missing 4th function is logical not, which you might call anti-propagate.

The conventional representation of the function used for look-ahead adders is the propagate-generate representation:

    f_i(c) = g | (p & c)

There are 4 choices for (p, g) but unlike our mux representation it is redundant: if g = 1 then any value of p
yields the same function. However, this yields a simpler, more efficient composition operator:

    (p1, g1) . (p2, g2) = (p1 & p2, g1 | (p1 & g2))

But the thing I want to get across is that the existence of the log-depth carry-lookahead circuit does not depend on this
extra level of constant-factor optimization. You could have used the generic approach outlined above, which works for any
bit-to-bit function, and indeed can be generalized to arbitrary multi-bit functions (beware the combinatorial explosion).