I am a bit stuck with the concept of carry-lookahead adder so I'd like to compare it with another concept I'm more familiar with: the ripple-carry adder. I'm trying to make some basic math comparison between the two ones.
Assuming every gate can accept at most 2 (two) inputs and has a delay of '1', and that, at least for the moment, we're adding two 4-bit numbers.
Let's start with the ripple-carry adder. I've built it putting four full-adder in column. Every carry-out is computed as
$$c_i^{(\text{out})} = a_i \cdot b_i + \left[ a_i + b_i \right] \cdot c_i^{(\text{in})} \qquad \text{where} \; \cdot \equiv \text{AND},\, + \equiv \text{OR}$$
Since
$$\left[ a_i + b_i \right]$$
is computed in parallel for every full-adder, the cost for computing the k-th carry-out is
$$1 + 2k$$
right?
Now say we want to compute carry's at first, then the sum -- bit by bit. Using the formula above, (and omitting the superscript) we write that
$$c_{i+1} = g_i + p_i c_i$$
Hence, we can write recursively the fourth term as a function of the first one, i.e.
$$c_1 = g_0 + p_0 c_0 \\ c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0 \\ \vdots \\ c_4 = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 + p_3 p_2 p_1 p_0 c_0$$
Of course it is the last term that costs more. How much? I'd say
$$\lceil \log_2{4} \rceil + \lceil \log_2{4} \rceil $$
where the first term is needed for computing every AND operations, while the second one for computing every OR operation.
Hence for an overview ...
$$1 + \lceil \log_2{k} \rceil + 2$$
where the first term is the gate delay needed for computing every propagator/generator term, the second term is the one needed for computing every carry_in, then the last term is the gate delay of a single full-adder.
That is, the comparison of "time" between a ripple-carry adder and a carry-lookahead's one is the comparison of the following two functions
$$1 + 2k$$ $$3 + \lceil \log_2{k} \rceil$$
I know that carry-lookahead can be improved more, and I've done that by myself...though I'd like you give me some feedback about the stuff above for now.
!(abcd)
with two NAND's in parallel then a OR gate!(ab) + !(cd)
, resulting in a 2 port delay. Where am I wrong? \$\endgroup\$a + b + c + d + e + f
can be implemented simply with a 6 input OR, with delay 1? I mean: I should not care about the number of inputs of the gates but instead about the number of gates I have to pass through before the output become stable, right? \$\endgroup\$