Drawing State Diagrams

state-machines

So I'm going through my textbook and I'm stuck on this problem:

Design a circuit that has two inputs, \$clk\$ and \$X\$, and produces one output \$O\$.
- \$X\$ may change every clock cycle, and the change happens at the falling edge.
- The circuit samples the input at every rising edge of the clock.
- If the input is \$1\$, consider as read a \$1\$, else read a \$0\$. \$O\$ is \$1\$ (for one clock cycle, from positive edge to positive edge) if the last three bits read are \$110\$, with \$0\$ as the most recent bit.

Draw the state diagram. Close to an arc, show \$X=1\$ or \$X=0\$ to indicate whether the change of state happens when \$X=1\$ or when \$X=0\$.

How would one approach this problem?

Best Answer

First design the state machine without worrying about the clk. You have to remember something about what happened with the last 3 inputs, so at worst you are going to need 8(=2^3) states (but you can do substantially better than that.)

Once you have the state diagram, you need to choose an n-bit representation for each state. You will store this in an n bit register.

Then you write down the truth table for the transition function. There will be n+1 inputs (the n-bit state, and the 1 bit for X.) There will be n output bits (representing next state.)

Then you figure out how to implement a circuit that performs the truth table.

Finally, you need to implement the output function. This will be a circuit that is true when you are in the state where the last three bits are 110, and false otherwise.

In your final circuit you will have an n-bit clocked register, and a bunch of combinational logic.

Related Solutions

Next-State Tables

You start with the basic form:

Inputs  |  Outputs
------------------
        |

Then you figure out what your inputs and your outputs are. In this case, your inputs are just the current state, and the output is the next state you're going to switch to:

Q2 Q1 Q0 | Q2' Q1' Q0'
----------------------
         |

Now just start filling it in. To get started, when the current state is 0, according to your spec the next state is 4:

Q2 Q1 Q0 | Q2' Q1' Q0'
----------------------
0   0  0 |  1   0   0
0   0  1 |  
0   1  0 |  
0   1  1 | 
...

You just need to fill in the rest of the outputs according to the sequence you want to count over.

Electronic – Curious state transitions in state machine RTL simulation

I went ahead and made a testbench to see the behavior of the circuit. Please right click the image to see it more clearly.

enter image description here

From my simulation, there is nothing unexpected or strange about the waveform. The state gets correctly initialized by the reset. When TxSync is high the state toggles once every clock cycle. When TxSync is deasserted the state holds a constant value.

I also used a lint checker and there are no major problems with the RTL. I must conclude that the circuit is simulating exactly as specified in the RTL. If you were expecting something different, you should make that more clear, and I will tell you how to change the model.

Some notes on the simulation:

The currentState register latches the value of nextState at the rising edge of TxByteClk
The nextState logic is updated after an infinitesimally small unit of time after the rising edge of TxByteClk (or TxSync), since this is a 0 delay model
The currentState and nextState may appear to change simultaneously, but currentState is updated first

Pitfall: If your testbench updates the TxSync input exactly at the rising clock edge, You will just have a glitch in nextState. Your simulator may remove this glitch, making it look like nextState never entered State_WRITETOLANE1, when in fact it did, just for a very brief moment. This would make it look like currentState latched a value that nextState never had.

Remedy: Don't update the inputs exactly at the rising clock edge. Add some small delay so that the simulation can be more clearly understood. In my case, I updated the input at the falling clock edge. But the update time is arbitrary if you are doing a 0 delay simulation.

Best Answer

Related Solutions

Next-State Tables

Electronic – Curious state transitions in state machine RTL simulation

Related Topic