Longest Path in a Combinational Circuit

[jaus tail]

Homework Statement

Find the longest path in the circuit

Relevant Equations

Find out which paths won't be ever evaluated or make any difference, remove those paths, and then add individual delays

First for logic-1 at output: So I get that for Logic 1, the OR-2 Gate must have one input has logic-1.
Case1: Upper OR-Input is 1 of second OR Gate. So the longest path is Inv-1, Or-1, Or-2. Delay is 9ns.
Case2: For lower input to be 1, the 'And-2' output has to be 1, and for that Or-1 output has to be 1. So same as Case1. Delay = 9ns

For logic-0 at output. Both inputs for Or-2 have to be zero. For upper input of Or-2 to be zero, A=0, B =1. Delay is 5ns (B-path. 1 + 4) for this to reach Or-2
And for lower input of Or-2 to be zero, and 'And-2' output has to be zero. But this will be zero as Or-2 output is zero. So this will take 1 + 4 + 3 ns
Max time = 1 + 4 + 3 + 4 = 12 ns
Longest path:

However, the solution says that the longest path is Inv-1, Or-1, Or-2. But the last gate is an Or and not an And gate. Unless it gets both its inputs as 0,0 we can't be sure that output will remain at 0.
I agree that once the upper input to the Or-2 gate is 0, even the lower one will be 0 only as the upper input is coming to lower one via an 'And' gate.
But till then the lower input is floating. What if the output of this circuit was 1 earlier and the And'2 had 1 as output and now the output is becoming 0. In that case it will wait for the green path to execute before giving the correct output.

 

[berkeman]

Sorry, what does this mean? Are you given a specific input test bench to evaluate? If any pattern can be input, how would there be some inactive paths?

Find out which paths won't be ever evaluated or make any difference

 

[jaus tail]

We haven't been given any test bench. Inactive path would be like:

For Gate: OR-2, if the output of OR-1 is high, then the lower input for Gate OR-2 makes no difference. So we can say it's inactive. Like for calculation of delay purpose in case the output is logic-1.

 

[Tom.G]

The usually reliable way to evaluate such circuits manually is to construct a truth table. The sparse version would be four columns, one for each input, and one for the output. And since there are eight possible input combinations, there will be eight rows.

A complete truth table would also have a columns for each of the interior nodes (gate outputs).

Truth tables are handy because the human visual system and brain tend to process information in parallel, allowing more of an overview of the problem. It make things a lot easier.

Give it a try and let us know how it works out.

Cheers,
Tom

 

[jaus tail]

This is the truth table that I get:

From here we can deduce this modified truth table:

 

[willem2]

For Gate: OR-2, if the output of OR-1 is high, then the lower input for Gate OR-2 makes no difference. So we can say it's inactive. Like for calculation of delay purpose in case the output is logic-1.

And what about if OR-1 is low. If you could prove that the other input to AND-2 also has to be low, than the connection from OR1 to AND-2 is redundant, so it can't be part of the longest path.

 

[jaus tail]

And what about if OR-1 is low. If you could prove that the other input to AND-2 also has to be low, than the connection from OR1 to AND-2 is redundant, so it can't be part of the longest path.

True, but it is not given whether OR-1 is low or high. So maybe we'll have to take both cases.

 

[jaus tail]

What's bothering me is that what if there is an initial condition. Like initially the output is high and also output of And-2 is high. Now if A goes to 0, and B goes to 1, then the final output will have to wait for And-2 to become low. So we cannot remove And-2 from the longest path in this case.

 

[willem2]

True, but it is not given whether OR-1 is low or high. So maybe we'll have to take both cases.

You certainly need to consider both cases.
You already established that if OR-1 is high, the output is also high, and so AND-2 and everything in front of it that is not also used for the inputs of OR-1 is completely redundant. The other possibility is that OR-1 is low. If you could prove that one of the components or wires that you could eliminate when OR-1 was high is now also redundant, this component or wire would than be redundant in all cases, and it could be eliminated and it can't be part of the minimal path.
The first thing to look for is: what would the inputs have to be to make OR-1 low?

 

[jaus tail]

For OR-1 to be low, A would be low and B would be high. C would be X (don't care).

 

[willem2]

For OR-1 to be low, A would be low and B would be high. C would be X (don't care).

So what is the output of AND-2, and does if matter if you remove the connection from OR-1 to AND-2?

 

[jaus tail]

So what is the output of AND-2, and does if matter if you remove the connection from OR-1 to AND-2?

The output of And-2 depends on C as well, but it doesn't matter when final output is 1 because it's an OR-gate at the end. if output of Or-1 is high, then the output will always be high irrespective of and-2 gate output.

 

[willem2]

The output of And-2 depends on C as well, but it doesn't matter when final output is 1 because it's an OR-gate at the end. if output of Or-1 is high, then the output will always be high irrespective of and-2 gate output.

I can't really tell if you now have the answer, or even if you think you have the answer.
If OR-1 is low, B must be high, so the upper input to AND-1 is low, so the output of AND-1 is also low, so it does not depend on C, so the output of AND-2 does not depend on C as well. Note: all of this under the assumption that OR-1 is low.
You should now be able to prove that what ever OR-1 is, the upper input of AND-2 does not matter, so you can tie it to GND or VCC or anywhere, and so the connection can not be part of the critical path.

 

[jaus tail]

Yes. If OR-1 is high or low it doesn't matter what the output of And-2 is. But my confusion is suppose in transition state. Like if the output is going from high to low. Suppose Or-1 and And-2 outputs are high. And now if due to logic change in A input, Or-1 goes low, so it will take some time period (delay of combinational gate) for and-2 to be low. For that momentarily time the output of and-2 and final output will be one. So there will be some hazard for that small time.

 

[Tom.G]

For that momentarily time the output of and-2 and final output will be one. So there will be some hazard for that small time.

Yeah, that's why synchronous logic is so popular. It gives a clock-period for things to settle before the next state is entered. But you get the result faster if you can avoid the logic glitches.