How to Setup the following Finite State Machine

Question

The question goes as follows:

Design a finite state machine (FSM) with two inputs (x and y) with an output z, which is asserted every time x and y change state to opposing values at the same time. A sample output looks as follows:

$$x : 000111010100$$ $$y : 011011011010$$ $$x : 000100000110$$

I am stuck on how to set up my input and what the states should be. If I assign: $$A[00], B[01], C[11], D[10]$$ and my inputs are two values w1 w2 to be the next state then I get a table which looks like this, and it is unclear how to derive a minimal cost sum of product logic expression for the next state and output signals...:

Addition:

Once I do a karnaugh map, and create a circuit, I get the following result:

The issue here is that the circuit is not taking any information regarding the previous state ... so I know the answer is wrong. How do I fix this?

Answer 1

The issue here is that the circuit is not taking any information regarding the previous state ... so I know the answer is wrong. How do I fix this?

I really enjoyed your summary. It right on target. Your solution doesn't take any prior information into account and that is a problem.

Of course, the obvious answer to this is to take prior information into account. And this isn't hard to do.

Other than that, you used a process to get where you did and that's a good thing.

Things that you did right are:

1. Recognizing that you need to capture four possible states with two DFFs.
2. Laying out a state-transition table, correctly.
3. Recognizing that part of the problem is detecting when a state transition implies that both \$x\$ and \$y\$ have changed and denoting that case in your table.

Perhaps a thing you didn't do right is:

4. Realizing that \$z\$ doesn't just respond to only (3) above, but also requires that \$x\$ is different from \$y\$, before and after.

So, of the four state transitions of interest due to (3) above, only two of them cause \$z\$ to become 1.

Let's take your example (I think you made a mistake by listing \$x\$ twice) and expand it:

$$\begin{array}{c|c} \text{Input/Variable} & \text{Sequence} \\\hline {\begin{smallmatrix}\begin{array}{l} x\\ y\\\\ z^{'}\\\\ z \end{array}\end{smallmatrix}} & {\begin{smallmatrix}\begin{array}{c:c:c:c:c:c:c:c:c:c:c:c} 0&0&0&1&1&1&0&1&0&1&0&0\\ 0&1&1&0&1&1&0&1&1&0&1&0\\\\ 0&0&0&1&0&0&1&1&0&1&1&0\\\\ 0&0&0&1&0&0&0&0&0&1&1&0 \end{array}\end{smallmatrix}} \end{array}$$

In the above, \$z^{'}\$ follows your state transition table indicators of '1'. But the output follows \$z\$, instead. Note that these two are not the same.

You need one more piece of information: "Were both inputs different?" This can either be the inputs, directly, or the captured values of the inputs in the DFFs after the clock. (It doesn't matter as the worst case propagation delays are likely similar, either way.) This address the "change state to opposing values at the same time" part of the problem. And perhaps because of the "at the same time part of that, you should examine the DFF outputs and not the \$x\$ and \$y\$ inputs.

To detect changes in \$x\$ and \$y\$, all you have to do is use an XOR that compares the input with the \$Q\$ output, for each DFF. To detect a difference between \$x\$ and \$y\$ at the same time you need one more XOR that compares the \$Q\$ outputs of \$x\$ and \$y\$. So that's three XORs total. The outputs need to be ANDed together to create the \$D\$ input to the \$z\$ DFF.