Two 4 bit numbers are $A_{3}A_{2}A_{1}A{0}\ and\ B_{3}B_{2}B_{1}B{0}$ and their complements are also available.
Delay of each gate is one time unit.
Minimum time required for calculating $A\oplus B = A^{I}B+B^{I}A$ is
$A^{I}B$ and $B^{I}A$ are calculated parallel in one-time unit and their OR is calculated in one more time unit.
Total time = 2 units.
Propagation delay of Carry LookAhead adder can be analyzed through 3 levels.
Level 1:
All Carry Propagators and Carry Generators $G_{i},P_{i}$ are calculated in two time units
$\\G_{i} = A_{i}\cdot B_{i}\\ P_{i} = A_{i}\oplus B_{i}$
Level 2:
$\\C_{0} = 0\\ C_{1} = C_{0}P_{0}+G_{0}\\ C_{2} = C_{0}P_{0}P_{1}+G_{0}P_{1}+G_{1}\\ C_{3} = C_{0}P_{0}P_{1}P_{2}+G_{0}P_{1}P_{2}+G_{1}P_{2}+G_{2}\\ C_{4} = C_{0}P_{0}P_{1}P_{2}P_{3}+G_{0}P_{1}P_{2}P_{3}+G_{1}P_{2}P_{3}+G_{2}P_{3}+G_{3}\\$
Every $C_{i}$ takes 2 units of time(1 AND followed by 1 OR) and they can be computed parallelly.
Level 3:
$\\S_{0} = C_{0}\oplus P_{0}\\ S_{1} = C_{1}\oplus P_{1}\\ S_{2} = C_{2}\oplus P_{2}\\ S_{3} = C_{3}\oplus P_{3}$
Let’s take a generalized one $S_{i} = C_{i}\oplus P_{i}$
$S_{i} = C_{i}^{I}P_{i}+P_{i}^{I}C_{i}$
By the time we come to Level-3 we can compute the $P_{i}^{I}$ i.e while we are computing the things in Level-2
Now the things boil down to the question, can we compute $C_{i}^{I}$ in parallel with Level-2 operations.
Let’s take the $C_{3}$ and work on that
$C_{3}^{I} = (C_{0}^{I}+P_{0}^{I}+P_{1}^{I}+P_{2}^{I})(G_{0}^{I}+P_{1}^{I}+P_{2}^{I})(G_{1}^{I}+P_{2}^{I})G_{2}^{I}$
$\\G_{i}^{I} = (A_{i}B_{i})^{I}\\ P_{i}^{I} = A_{i}\odot B_{i} = A_{i}B_{i}+A_{i}^{I}B_{i}^{I}$.
Therefore $G_{i}^{I}\ and\ P_{i}^{I}$ can be computed parallely with Level-1 operations.
So we can compute $C_{i}^{I}$ with 1 OR followed by 1 AND, parallely with Level-2 operations.
Now $S_{i}$ can be computed in 2 time units having $C_{i}^{I}\ ,C_{i},\ P_{i}^{I}\ ,C_{i}$ in hand after completing with Level-2 operations.
Therefore total time = Level-1 + Level-2 + Level-3
= 2+2+2 = 6 units
Now let’s look at a specific case of each gate having FAN-IN = 2
Level-1 operations has no effect, they can be computed in 2 units.
Now here each $C_{i}$ doesn't have equal time units to compute.
$\\C_{3}\ time = log_{2}4(AND\ time)+log_{2}4(OR\ time) = 2+2 = 4\ units\\ C_{4}\ time = log_{2}5(AND\ time)+log_{2}5(OR\ time) = 3+3 = 6\ units$
Coming to Level-3
Same way $C_{i}^{I}\ and\ P_{i}^{I}$ are computed(as the approach mentioned above)
Therefore $S_{i}$ takes 2 time units.
And $S_{i}$ can be computed only when $C_{i}$ is available.
So $S_{3}$ computation takes (2+4+2) time units from begining and and also $C_{4}$ computation takes (2+6) time units from begining.
PS: We need not to wait for the $C_{4}$ to get complete for calculating $S_{3}$.
Then total time = 8 units
