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?
But the solution is shown as below, how can it be the critical path(orange line)?
\$\begingroup\$
\$\endgroup\$
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
8
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}$$
answered Nov 30, 2016 at 19:33
-
\$\begingroup\$ I was referring to the slides here: web.mit.edu/6.111/www/f2005/handouts/L12.pdf \$\endgroup\$ Commented Nov 30, 2016 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\$ Commented Nov 30, 2016 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\$ Commented Nov 30, 2016 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\$ Commented Nov 30, 2016 at 19:55
-
1\$\begingroup\$ No, because if any P bit is not set in a 4-bit stage, then the carry input will NOT propagate to the output! That's the very definition of what a P bit means. The carry output of that stage will depend only on its own A and B inputs, but not the carry input. \$\endgroup\$ Commented Nov 30, 2016 at 20:10