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

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?

• I tried to draw it and I got two ripple carry adders in a parallel fashion with sum output of each full adder of the first ripple carry adder going into each full adder of the second ripple carry adder (and the second ripple carry adder has an extra full adder with the carry out of the last FA in the first ripple carry adder going into it) and the delay seems to be considerably less. So, I want to know the correct logic for addition of 3 n-bit binary numbers using 2 Ripple carry adders and the resulting delay.
– new
Commented Dec 4, 2020 at 17:10
• Why can't we use it in this parallel fashion? How are they cascaded?
– new
Commented Dec 4, 2020 at 17:11
• I'll remove that comment. Please do add your diagram to the question and then perhaps we could see how the delay adds up in that circuit.
– AJN
Commented Dec 4, 2020 at 17:11
• They're cascaded by the propogation of the carry from one to the next. In that sense, even though the other inputs are available in parallel, the dependence on the carries means that the computation is a very long series chain of combinatorial elements. Which is a big words way of saying "slow". Put your drawing in your question. Commented Dec 4, 2020 at 17:14
• Yes but how does another factor of n appear?
– new
Commented Dec 4, 2020 at 17:17

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

• "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." -en.wikipedia.org/wiki/….
– new
Commented Dec 4, 2020 at 17:52
• What's the logic circuit where the delay is actually 2 carry-propagate adder delays ?
– new
Commented Dec 4, 2020 at 17:52

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.)