Carry lookahead adder - How is this possible?

[coolmoniker]

Homework Statement

I have a book which says that the gate delay for generating C_i is 2 log_r(n) + 1, where r is the fan-in for each gate and n is the number of bits.

This implies that with a fan-in of 2 and 4 bits, the delay for a generating C₅ as shown below should be 5 gate delays. How is this possible?

Homework Equations

For an n-bit carry lookahead adder, it is well known that the carry out can be determined by examining the 'carry propagate' and 'carry generate' for each of the inputs. This allows the carry out to be expressed solely in terms of the input bits and carry-in.

As an example, the carry-out for a four bit adder is given by:

C₅ = G₄ + P₄G₃ + P₄P₃G₂ + P₄P₃P₂G₁ + P₄P₃P₂P₁C

Where
C is the carry in,
Carry propagate P_i = A_i + B_i,
Carry generate G_i = A_iB_i

The Attempt at a Solution

Initially:
We have the inputs
C,
A₁,
B₁,
A₂,
B₂,
A₃,
B₃,
A₄,
B₄

After one gate delay:
The carry-propagate and carry generate for each bit can be determined. So we have
C,
G₁,
P₁,
G₂,
P₂,
G₃,
P₃, G₄, P₄

After two gate delays:
We can use 'and' to start the carry propagates and carry generates together. So we have

P₄G₃,
P₄P₃,
P₂G₁,
P₂P₁

After three gate delays:
Now we can use 'or', and also continue 'anding' together the propogates
So
G₄ + P₄G₃,
P₄P₃G₂,
P₄P₃P₂G₁,
P₄P₃P₂P₁


After four gate delays:

G₄ + P₄G₃ + P₄P₃G₂,
P₄P₃P₂G₁,
P₄P₃P₂P₁C


After five gate delays:
G₄ + P₄G₃ + P₄P₃G₂ + P₄P₃P₂G₁,
P₄P₃P₂P₁C

This is too slow. There is still more work to be done as we need another 'OR' to put the two remaining terms together.

How is it possible to determine the carry out in only five gate delays?

 

[berkeman]

I only skimmed the question, but why are you constrained to 2-input AND logic?

 

[coolmoniker]

I only skimmed the question, but why are you constrained to 2-input AND logic?

That's the difficulty...The book states that C_i can be found in 2 log_r(n) + 1 delays, where r is the number of inputs for each gate. So for 2 inputs and 4 bits, that's 5 delays.

Apparently it's possible, but I can't do it in less than six. There must be some trick or logic identity to exploit.