2
\$\begingroup\$

I came across the following problem:

A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit-ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is ______.

How does the ripple adder work? I can guess two approaches / interpretations of the internal workings of "standard" ripple adder as explained below:

Interpretation or approach 1: First Half Adders of each full adders compute immediately without requiring to wait for carry from previous full adder becomes available

  • Delay for first full adder:

    • For sum: 4.8 μs
    • For carry: 4.8 μs

    As can be seen in below diagram:

    enter image description here

  • The carry of first full adder adder becomes input carry Cin for 2nd full adder. This carry is input for 2nd half adder of the 2nd full adder. Hence 1st half adder of full adder does not need to wait for anything.

  • This is the case with 1st half adder of all full adders. They all can generate their respective output at the end of time t=2.4μs.
  • 2nd Half adders of each full adders needs to wait till carry from previous full adder become available.
  • Hence total delay = 4.8 + 2.4 + 2.4 + 2.4 = 12 μs

Interpretation or approach 2: Full adders (even 1st Half adder in the full adder) remains deactivated until carry from previous Full adder becomes available

  • In this case the delay will be simply 4 * 4.8 = 19.2 μs

Question

  • My question is "how does a standard ripple carry adder behave?" Does each full adder remains deactivated until carry from previous full adder becomes available or only 2nd half adders of each full adder needs to wait until carry from previous full adder becomes available?
  • Wikipedia gives following animation which suggests approach 2: enter image description here
\$\endgroup\$
  • \$\begingroup\$ Good question, anir. Your first approach works. The basic idea is that the carry out of each full adder's carry is fed into the 2nd HA of the following adder, which is a good thing and improves the final result. The 1st HA of each adder does, in fact, operate in parallel. If you need a detailed explanation, I can write it. But I think you already have the idea. \$\endgroup\$ – jonk Jul 17 at 23:07
2
\$\begingroup\$

My doubt is how standard ripple adder behaves?

The standard gate delay behaves like 2 and that is correct. Adders do not deactivate. This logic is called asynchronous and the output of the gates do not change until the signal 'upstream' changes. This means that if A or B changes, then Cout will be the last to change. This also means a propagation delay while chaining gates, and the propagation delay gets larger when chaining.

enter image description here
https://allaboutfpga.com/vhdl-code-for-full-adder/

(In the picture above the delays are difficult to see for this simulated full adder because the gate delays are so small, many adders could be chained before the gate delay could be noticed.)

In modern digital logic there are other ways to overcome the gate delay.
First off most gates have a small delay in the nano-second range.
Secondly, by adding more gates, the propagation delay can be reduced. The Carry Look Ahead adder does this:

enter image description here
Source: https://www.geeksforgeeks.org/digital-logic-carry-look-ahead-adder/

The last thing that is worth mentioning is clocks and memory (in the form of flip flops). Usually the logic is stored in memory by a clock, the logic is designed in such a way that the values of the logic are finished changing before a clock edge (when values are stored). This enables better stability and certainty in the logic operations in a microprocessor or FPGA.

\$\endgroup\$
  • \$\begingroup\$ Not able to get what exactly you mean to say. (not core electronics / electrical student). Do you mean to say the outcome is as in approach 2, but not because full adder remains deactivated till carry from earlier full adder becomes available, but due to gate delays? \$\endgroup\$ – anir Jul 18 at 7:18
2
\$\begingroup\$

In the following diagram, I've re-drawn the full-adder stages to show more clearly why your 1st approach is correct and replicated your analysis of the timing:

schematic

simulate this circuit – Schematic created using CircuitLab

In the above diagram, you can see that both the sum and the carry-out of each stage (bit position) has exactly the same relative delay. So nothing new here and the first bit position adder does, in fact, have \$4.8\:\mu\text{s}\$ delay for both sum and carry out. However, the 1st half-adder of the second bit position is operating in parallel to the 1st half-adder of the first bit position (as shown) and therefore the 2nd (carry-in) half-adder of the second bit position only adds \$2.4\:\mu\text{s}\$ in generating its sum and carry outputs. Etc.

In the above diagram, \$X\$ is the propagation delay of the AND/OR gate. So \$X=1.2\:\mu\text{s}\$. As you can see, the 4th sum and the final carry-out of the 4-bit ripple-adder is \$10\:X\$ (or stable at \$12\:\mu\text{s}\$.) Just as you calculated.

\$\endgroup\$
  • \$\begingroup\$ Am bit confused. Does laptop2D's answer suggest 2nd approach is correct? Am bit struggling to make full sense of his answer (not core electronics student) . Just to note again, I want to know how "standard" ripple adder behaves. \$\endgroup\$ – anir Jul 18 at 6:33
  • \$\begingroup\$ @anir What I wrote about is a standard ripple-adder. I didn't know that you didn't know what one was, though now I think you don't because you weren't able to recognize the schematic I drew out. What I did was to draw it differently. This doesn't mean it's actually different. It's just drawn out in a different way to help you see the timing better. It's still the exact same thing. I've updated the diagram. \$\endgroup\$ – jonk Jul 18 at 9:48
  • \$\begingroup\$ @anir A half-adder is an XOR and an AND gate (the question explicitly makes it clear that's what is desired in this case.) Two half-adders and an OR gate makes up a full-adder with 3-in and 2-out. Look at your own diagram and you can see how one pair of wires feed an XOR/AND pair and another pair of wires feed a different XOR/AND pair and how the OR gate connects the partial carries from each. Then look at my diagram and you will see the same full-adder grouping repeated four times. \$\endgroup\$ – jonk Jul 18 at 10:02
  • \$\begingroup\$ I did not say I am confused about working of your diagram. In fact the diagram which I was learning was somewhat similar to yours. I am confused because I feel laptop2D is suggesting approach 2 is the "standard" one in his answer. You missed this point which I stated clearly in earlier comment. \$\endgroup\$ – anir Jul 18 at 12:48
  • \$\begingroup\$ @anir No, I didn't miss your question about laptop3d. I chose not to discuss my thoughts about his post. I'll leave that to you. The diagram you and I are discussing is the standard ripple carry adder. Beyond that, it is up to you. \$\endgroup\$ – jonk Jul 18 at 12:50
0
\$\begingroup\$

Each logic gate is continuously calculating the output value. If you assume that your a[3:0] and b[3:0] input arrive simultaneously, then the all the outputs can/will change after maybe 4.8µs. However, the calculation for each bit will not be complete until the final inputs are present (and the inputs have had time to propagate to the ouputs).

Inputs arriving at t=0 is a common assumption, and in a stand-alone question like this, makes the most sense. Your first method is correct for sum[3:0], but see if you need to account for the final carry out.

While the Wikipedia example of a[0] and b[0] arriving first, and then a[1] and b[1] arriving at the full adder at the same time as c[0] is needed can happen, it "normally" wouldn't. Two ways that the Wikipedia representation can make sense are:

  • Bus a[3:0] and bus b[3:0] are both outputs of ripple carry adders, and bit 0 will be ready before bit 3
  • When the inputs turn green, the value is "locked in" for the output. The input could change any time until it turns green without impacting the time for the final output to be valid. This would help teach concepts in Static Timing Analysis (STA).
\$\endgroup\$

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.