1
\$\begingroup\$

enter image description hereWhile 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?

\$\endgroup\$
12
  • \$\begingroup\$ 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. \$\endgroup\$ – new Dec 4 '20 at 17:10
  • \$\begingroup\$ Why can't we use it in this parallel fashion? How are they cascaded? \$\endgroup\$ – new Dec 4 '20 at 17:11
  • \$\begingroup\$ 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. \$\endgroup\$ – AJN Dec 4 '20 at 17:11
  • \$\begingroup\$ 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. \$\endgroup\$ – Chris Stratton Dec 4 '20 at 17:14
  • \$\begingroup\$ Yes but how does another factor of n appear? \$\endgroup\$ – new Dec 4 '20 at 17:17
0
\$\begingroup\$

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?

schematic

simulate this circuit – Schematic created using CircuitLab

\$\endgroup\$
2
  • \$\begingroup\$ "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/…. \$\endgroup\$ – new Dec 4 '20 at 17:52
  • \$\begingroup\$ What's the logic circuit where the delay is actually 2 carry-propagate adder delays ? \$\endgroup\$ – new Dec 4 '20 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.