# Drawing State Diagrams

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?

## 1 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.