I am trying to understand the worst case path in the 16bit carry bypass adder. Isn't the critical path through all the adders in the design?

enter image description here

But the solution is shown as below, how can it be the critical path(orange line)?

enter image description here


Where did these diagrams come from? If the white trapezoids are meant to be ordinary 2:1 multiplexers, then this is not a correct implementation of a carry-bypass adder. The carry input to each 4-bit stage needs to be the logical OR of the mux output and the carry output of the previous stage.

The actual longest path through the whole design is from the inputs of the first stage (on the left) to the sum output of the 16th stage (on the right), following most of the orange path, but not through the final mux.

The logic after each stage should look like this:

$$C_{o,stage} = C_{i,n}\cdot P_{n}\cdot P_{n+1}\cdot P_{n+2}\cdot P_{n+3} + C_{o,n+3}$$

  • \$\begingroup\$ I was referring to the slides here: web.mit.edu/6.111/www/f2005/handouts/L12.pdf \$\endgroup\$ – Sai Gautham Nov 30 '16 at 19:36
  • \$\begingroup\$ I see. The "Key Idea" on slide 11 is simply wrong. It completely ignores the possibility that a carry will be generated inside the 4-bit stage even if all of the P bits are set! This makes the "Message" on slide 13 particularly ironic... \$\endgroup\$ – Dave Tweed Nov 30 '16 at 19:39
  • \$\begingroup\$ I still don't understand the orange path concept here. Considering that all adders in every stage waits on the carry from the previous stage, isn't that the worst case scenario? \$\endgroup\$ – Sai Gautham Nov 30 '16 at 19:45
  • \$\begingroup\$ Note that the critical path has been corrected in the current version of the handout (page 18), but the "Key Idea" error remains (page 16). I'm trying to figure out who to contact at MIT about this. \$\endgroup\$ – Dave Tweed Nov 30 '16 at 19:55
  • \$\begingroup\$ No, the middle stages can be bypassed, because their P bits are generated long before the carry output of the first stage is available. If the P bits in an intermediate stage are not all set, then the carry output of the first stage does not matter, and the carry output of that intermediate stage is guaranteed to be faster than the one from the first stage, because of the delay introduced by the muxes. \$\endgroup\$ – Dave Tweed Nov 30 '16 at 19:57

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.