Time (Propagation delay) taken for adding 3 n-bit binary numbers using Carry Propagate Adders (Ripple carry adders)

Question

While being introduced to carry save addition technique, I was told that the time taken for adding 3 n-bit binary numbers using ripple carry adders will be (2n+1)t_FA (Assuming we neglect the minor time difference between a full adder and a half adder), where t_FA is the delay for a full adder.

Excerpt from wikipedia:https://en.wikipedia.org/wiki/Carry-save_adder "If you were to add these 3 numbers using conventional methods, it would take you 2 carry-propagate adder delays to get to the answer. If you use the carry-save technique, you require one only 1 carry-propagate adder delay and 1 full-adder delay (which is much lower than a carry-propagate delay) and. Thus, CSA adders are typically very fast."

The reasoning was that it takes n(t_FA) time for adding 2 n-bit numbers using an n bit ripple carry adder and since the output can have at most n+1 bits, to add the 3rd number and the intermediate result requires (n+1) FAs and hence (n+1)t_FA and therefore total time of (2n+1)t_FA

Can someone show this through a circuit diagram?

Answer 1

Here's a diagram for 3 bits to show what many commenters are describing for the parallel execution of the addition of the 3rd input.

It's drawn such that the lsbs are on the left, and the calculation delay propagates left-to-right.

For n=3 bits, you can get the total sum of S[4:0] = A[2:0] + B[2:0] + C[2:0] after a delay of only 5. That's U1->U4->U5->U6->U7.

Perhaps the (2n+1) is for half-adders? Or some more structure, perhaps where the adders are reused, sequentially in time?

^{simulate this circuit – Schematic created using CircuitLab}

Answer 2

Let \$t_{FA}\$ be the maximal (dropped from here on) time from last input change to final output change for a full adder ((signal propagation) "delay time").
The delay time of an \$n\$-bit ripple carry adder (RCA) built from \$n\$ such adders will be limited \$t_{RCAn} \le nt_{FA}\$, result is an \$n+1\$ bit sum.
Adding another \$n\$-bit term using an \$n+1\$-bit ripple carry adder will take no more than \$(n+1)t_{FA}\$, for a total of \$(2n+1)t_{FA}\$.

As new observed, analysing a diagram of using FAs to add three terms gives a total of \$(n+2)t_{FA}\$.
The difference (in limit known - obviously not in observable characteristics) stems from (not) handling the \$n\$(+1)-bit adders as opaque blocks.

Things get more apparent adding more terms, say, 8:
Block analysis would have you believe there might be a big difference between a chain of 7 additions and an "adder tree" first adding 4 n-bit pairs, then 2 pairs of n+1-bit intermediate sums and finally 2 n+2-bit sums for an n+3 bit result:
7n+10 for the chain, 3n+3 for the tree.
At the FA level, the only difference is a few (7?) adders more in "the chain approach" versus a routing nightmare in "the tree approach".
(Addition of numerous terms is discussed ad nauseam in the context of binary multiplication.)