Why isn't the circuit a combinatorial one?

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Circuit
In summary, the conversation discusses the concept of combinatorial circuits and how they are defined as circuits with unique outputs based on their inputs. The circuit in figure 8.3 is not a combinatorial circuit because it has a feedback loop, which allows for multiple possible outputs for the same inputs. This means that the circuit does not have a unique output and cannot be represented by a single expression. The conversation also clarifies the concept of feedback loops and how they contribute to the lack of uniqueness in the circuit's output.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

I read the following about parity functions:

View attachment 6679

Since I haven't heard of combinatorial circuits before, I have searched for them.

I have found the following: http://http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-combcirc.pdf
I haven't understood how we deduce that the circuit in figure 8.3 ( page 3 from the link- 120 from the book) is not a combinatorial circuit.
Do we have to find the expression that represents it? If so, how do we do so? (Thinking)
 

Attachments

  • parity.PNG
    parity.PNG
    13.8 KB · Views: 66
Physics news on Phys.org
  • #2
Hey evinda! (Smile)

It says in the book:
A combinatorial circuit is a circuit whose output is uniquely defined by its inputs.
and:
If x1 = 1 and x2 = 0 then y can be 0 or 1.
So the output is not uniquely defined by its inputs.
And that's why the circuit in figure 8.3 is not a combinatorial circuit. (Thinking)
 
  • #3
I like Serena said:
Hey evinda! (Smile)

It says in the book:
A combinatorial circuit is a circuit whose output is uniquely defined by its inputs.
and:
If x1 = 1 and x2 = 0 then y can be 0 or 1.
So the output is not uniquely defined by its inputs.

But, why is it like that? Since at the circuit there aren't said any inputs, we can go anywhere with input either 0 or 1 ?(Thinking)
 
  • #4
evinda said:
But, why is it like that? Since at the circuit there aren't said any inputs, we can go anywhere with input either 0 or 1 ?(Thinking)

I don't understand your question.

The problem is really that there is a (so called feedback) loop in the circuit.
If we verify what happens when x1 = 1, x2 = 0, and y=0, it turns out that all logic gates can work as intended, and that the result is 'true'.
But the same thing applies if we verify what happens with x1 = 1, x2 = 0, and y=1.
Without feedback loops this is not possible, and the output is always unique.
 
  • #5
I like Serena said:
I don't understand your question.

The problem is really that there is a (so called feedback) loop in the circuit.
If we verify what happens when x1 = 1, x2 = 0, and y=0, it turns out that all logic gates can work as intended, and that the result is 'true'.

So if we have $x_1=1$ and $x_2=0$ do we have to take the first possible way for $x_2$, then we have the expression $x_1$ AND $x_2$ and get $1 \wedge 0=0$ and then we get $y=0$ ? Or how do we find the value of $y$ ?
Or do we have to take into consideration all the paths for $x_2$ ? I am a bit confused right now. (Worried)
 
  • #6
evinda said:
So if we have $x_1=1$ and $x_2=0$ do we have to take the first possible way for $x_2$, then we have the expression $x_1$ AND $x_2$ and get $1 \wedge 0=0$ and then we get $y=0$ ? Or how do we find the value of $y$ ?
Or do we have to take into consideration all the paths for $x_2$ ? I am a bit confused right now. (Worried)

Let's start at the left with the first AND gate.
Here we are confronted with the feedback loop, while we do not know yet what $y$ is.
Let's keep $y$ unknown for now.
Then we get:
$$(x_1 \land y) = (1 \land y) = y$$
Now we apply the OR gate, yielding:
$$(x_2 \lor y) = (0 \lor y) = y$$
As we can see, whatever $y$ is, that's also what we get back at the end.
So any value of $y$ will do.
That is, there is no unique value of $y$ for the given inputs.
 
  • #7
I like Serena said:
Let's start at the left with the first AND gate.
Here we are confronted with the feedback loop, while we do not know yet what $y$ is.
Let's keep $y$ unknown for now.
Then we get:
$$(x_1 \land y) = (1 \land y) = y$$
Now we apply the OR gate, yielding:
$$(x_2 \lor y) = (0 \lor y) = y$$
As we can see, whatever $y$ is, that's also what we get back at the end.
So any value of $y$ will do.
That is, there is no unique value of $y$ for the given inputs.

So does this mean that if we get from $x_i$ to some gate that represents one specific operation $\star$ , will we then apply the operation $x_i \star y$, where $y$ is the unknown result? (Thinking)
 
  • #8
evinda said:
So does this mean that if we get from $x_i$ to some gate that represents one specific operation $\star$ , will we then apply the operation $x_i \star y$, where $y$ is the unknown result? (Thinking)

Yes - but only if there is a feedback loop from the unknown result to that gate.
 
  • #9
I like Serena said:
Yes - but only if there is a feedback loop from the unknown result to that gate.

What do you mean with feedback loop?
 
  • #10
evinda said:
What do you mean with feedback loop?

A wire that connects the output of a gate to the input of an earlier gate.
In other words, an output feeds back into an input that was part of getting that output.
 
  • #11
I like Serena said:
Let's start at the left with the first AND gate.
Here we are confronted with the feedback loop, while we do not know yet what $y$ is.
Let's keep $y$ unknown for now.
Then we get:
$$(x_1 \land y) = (1 \land y) = y$$
Now we apply the OR gate, yielding:
$$(x_2 \lor y) = (0 \lor y) = y$$
As we can see, whatever $y$ is, that's also what we get back at the end.
So any value of $y$ will do.
That is, there is no unique value of $y$ for the given inputs.

I am confused right now. (Sweating)

I thought that we do the following.

At the beginning we apply the operation $x_1$ AND $x_2$, the result will be equal to , say , $x_3$, then we apply the operation $x_2$ OR $x_3$, and get some result $y$, and then we continue the same procedure with $x_2$ getting the value $y$.

Have I understood it wrong? And as I understood we have an infinite loop, right? (Thinking)
 
Last edited:
  • #12
evinda said:
I am confused right now. (Sweating)

I thought that we do the following.

At the beginning we apply the operation $x_1$ AND $x_2$, the result will be equal to , say , $x_3$, then we apply the operation $x_2$ OR $x_3$, and get some result $y$, and then we continue the same procedure with $x_2$ getting the value $y$.

Have I understood it wrong? And as I understood we have an infinite loop, right? (Thinking)

$x_3$ is supposed to be an input and not a result, isn't it? (Wondering)

And no, we don't necessarily apply AND to $x_1$ and $x_2$. It depends on how the graph is defined.
As it is, doesn't the first AND gate have $x_1$ and the unknown output $y$ as its inputs?

And yes, we have an infinite loop - the feedback loop.
 
  • #13
I like Serena said:
$x_3$ is supposed to be an input and not a result, isn't it? (Wondering)

Why? I thought that $x_1$ and $x_2$ are the only inputs... (Thinking)

I like Serena said:
And no, we don't necessarily apply AND to $x_1$ and $x_2$. It depends on how the graph is defined.
As it is, doesn't the first AND gate have $x_1$ and the unknown output $y$ as its inputs?

But then why is $x_2$ connected to the AND-gate? (Thinking)
 
  • #14
evinda said:
Why? I thought that $x_1$ and $x_2$ are the only inputs... (Thinking)

We could. It's just that in our context $x_i$ is used to denote inputs and $y_i$ for outputs. Perhaps we can use, say, $z_i$ for intermediate results?

evinda said:
But then why is $x_2$ connected to the AND-gate? (Thinking)

Isn't $x_2$ connected to another gate?
Or are we talking about different circuits?
Which circuit are you talking about?
 
  • #15
I like Serena said:
We could. It's just that in our context $x_i$ is used to denote inputs and $y_i$ for outputs. Perhaps we can use, say, $z_i$ for intermediate results?

A ok.

I like Serena said:
Isn't $x_2$ connected to another gate?
Or are we talking about different circuits?
Which circuit are you talking about?

I was talking about this circuit:View attachment 6859

and I meant the red marked path that connects $x_2$ to the AND-gate:View attachment 6860If $x_1=1$ and $x_2=0$, I thought that the following is done:View attachment 6861

Am I wrong? (Thinking)
 

Attachments

  • graph.PNG
    graph.PNG
    1.7 KB · Views: 51
  • red.PNG
    red.PNG
    1.9 KB · Views: 50
  • grt.PNG
    grt.PNG
    5.1 KB · Views: 47
  • #16
I'm afraid that the wire from $x_2$ crosses the other wire and is not connected to it.
It's different for the other intersection of wires on the right side. There is black knot there to indicate that those wires are connected.
So $x_2$ is connected to the second gate and is not connected to the first gate. (Thinking)
 
  • #17
I like Serena said:
I'm afraid that the wire from $x_2$ crosses the other wire and is not connected to it.
It's different for the other intersection of wires on the right side. There is black knot there to indicate that those wires are connected.
So $x_2$ is connected to the second gate and is not connected to the first gate. (Thinking)

Ah I think I understand. So after each loop, the result is $y$ and so it is not unique, right? (Thinking)
 
  • #18
evinda said:
Ah I think I understand. So after each loop, the result is $y$ and so it is not unique, right? (Thinking)

$y$ is indeed not unique, but it doesn't change with each loop.
If we assign $y$ the value of $0$, the circuit is consistent.
So $y=0$ is a valid output.
However, the same holds true for $y=1$.
And that's why $y$ is not unique. (Thinking)
 
  • #19
I like Serena said:
$y$ is indeed not unique, but it doesn't change with each loop.
If we assign $y$ the value of $0$, the circuit is consistent.
So $y=0$ is a valid output.
However, the same holds true for $y=1$.
And that's why $y$ is not unique. (Thinking)

I understand. And we can repeat the loop as many times as we want, right? (Thinking)
 
  • #20
evinda said:
I understand. And we can repeat the loop as many times as we want, right? (Thinking)

Yep!
To be fair, since the loop doesn't change the first or the second time, it's unlikely to change in a later repetition. (Smirk)
 
  • #21
I like Serena said:
Yep!
To be fair, since the loop doesn't change the first or the second time, it's unlikely to change in a later repetition. (Smirk)

Yes, I see... Thanks a lot! (Smirk)
 

Related to Why isn't the circuit a combinatorial one?

1. Why do some circuits use sequential logic instead of combinatorial logic?

Some circuits use sequential logic because it allows for memory and feedback, which is necessary for complex operations and decision making. Combinatorial logic is limited to only input-output relationships.

2. What is the main difference between combinatorial and sequential logic?

The main difference between combinatorial and sequential logic is that combinatorial logic only considers the current inputs to determine the output, while sequential logic also takes into account the previous inputs and outputs.

3. Can combinatorial circuits be converted to sequential circuits?

Yes, combinatorial circuits can be converted to sequential circuits by adding memory elements such as flip-flops. However, this may result in a more complex and slower circuit.

4. When is it more appropriate to use a combinatorial circuit?

Combinatorial circuits are more appropriate for simple and straightforward operations that do not require memory or feedback. They are also faster and more efficient compared to sequential circuits.

5. What are the limitations of using only combinatorial logic in a circuit?

The main limitation of using only combinatorial logic is that it cannot handle complex operations or decision making that require memory and feedback. It also does not have the ability to "remember" previous inputs and outputs, which can be necessary in many applications.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
4K
  • Introductory Physics Homework Help
Replies
4
Views
421
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Introductory Physics Homework Help
Replies
8
Views
316
  • Math Proof Training and Practice
Replies
5
Views
1K
  • Introductory Physics Homework Help
Replies
5
Views
1K
Replies
2
Views
651
  • Beyond the Standard Models
Replies
2
Views
792
  • Quantum Physics
Replies
1
Views
676
Back
Top