# Longest Path in a Combinational Circuit

• Engineering
• jaus tail
In summary: AND-2 is... ...low as well. And since the final gate is an OR-gate, the output must be low.In summary, the longest path for logic-0 at the output of the circuit is Inv-1, Or-1, Or-2 with a delay of 12ns. This is because if OR-1 is low, the output of AND-2 must also be low, making the lower input of OR-2 redundant and resulting in a delay of 12ns. However, if OR-1 is high, the output of the circuit will always be high, regardless of the output of AND-2
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.

#### Attachments

• 1562494822204.png
27.2 KB · Views: 475
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.

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:

Tom.G and sysprog
jaus tail said:
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
willem2 said:
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.

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.

jaus tail said:
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).

jaus tail said:
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?

willem2 said:
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.

jaus tail said:
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.

jaus tail said:
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.

jaus tail

## 1. What is the longest path in a combinational circuit?

The longest path in a combinational circuit refers to the path that takes the most number of logic gates to reach from the input to the output. It is also known as the critical path and is important to consider in order to ensure proper timing and functionality of the circuit.

## 2. How is the longest path determined in a combinational circuit?

The longest path in a combinational circuit is determined by analyzing the logic gates and their connections in the circuit. The path with the most number of gates is considered the longest path. This can be done manually by tracing the path or through software tools such as logic simulators.

## 3. Why is the longest path important in a combinational circuit?

The longest path is important in a combinational circuit because it affects the overall timing and performance of the circuit. If the longest path is not properly optimized, it can lead to delays and errors in the output of the circuit. Therefore, it is essential to consider the longest path in the design and optimization of a combinational circuit.

## 4. How can the longest path be reduced in a combinational circuit?

The longest path can be reduced in a combinational circuit by simplifying the logic gates and their connections, using faster logic gates, or by rearranging the circuit layout. Additionally, using advanced design techniques such as pipelining and parallel processing can also help reduce the longest path and improve the overall performance of the circuit.

## 5. What are the consequences of having a long longest path in a combinational circuit?

A long longest path in a combinational circuit can lead to slower circuit operation, increased power consumption, and potential errors in the output. It can also make it more challenging to meet timing requirements and can limit the overall performance of the circuit. Therefore, it is important to carefully consider and optimize the longest path in the design of a combinational circuit.

Replies
1
Views
1K
Replies
1
Views
1K
Replies
10
Views
4K
Replies
20
Views
2K
Replies
14
Views
2K
Replies
7
Views
2K
Replies
10
Views
3K
Replies
4
Views
1K
Replies
7
Views
1K
Replies
14
Views
3K