State Diagram and state table with solved problem on state reduction

The synchronous sequential circuits are generally represented by two models. They are Mealy model and Moore model, which we have already discussed in the posts “What is a sequential circuit?” These models have a finite number of states and are hence called finite state machine models.

Designing a sequential circuit involves the representation of sequential circuit models. It includes a state diagram, state table, reduced state table, reduced state diagram. Let us discuss them in detail.

State diagram

The state diagram is the pictorial representation of the behavior of sequential circuits. It clearly shows the transition of states from the present state to the next state and output for a corresponding input.

• In this diagram, each present state is represented inside a circle.
• The transition from the present state to the next state is represented by a directed line connecting the circles.
• If the directed line connects the circle itself, which indicates that there is no change in the state(the next state is the same as the present state).
• For mealy model, the directed line is labeled with binary numbers separated with ‘/’, as shown in the below diagram.
• The input value, which causes the transition to occur is labeled first ‘1/’. The output produced for the corresponding input is labeled second ‘/0’.

• For Moore circuit, the directed lines are labeled with only one binary number. It is nothing but the input value which causes the transition.
• The output value is indicated inside the circle below the present state. It is because, in Moore model, the output depends on the present state but not on the input.

State table

The information contained in the state diagram is transformed into a table called a state table or state synthesis table. Although the state diagram describes the behavior of the sequential circuit, in order to implement it in the circuit, it has to be transformed into the tabular form.

The below table shows the state table for Mealy state machine model. As you can see, it has the present state, next state and output. The present state is the state before the occurrence of the clock pulse.

After the application of the clock pulse, depending on the input(X = 0 or 1), the state changes. It is indicated in the ‘next state’ column. The output produced for each input is represented in the last column.

The table shown below is the state table for Moore state machine model. Since, in Moore state machine model, the output depends only on the present state, the last column has only output.

State reduction

While designing a sequential circuit, it is very important to remove the redundant states. The removal of redundant states will reduce the number of flip flops and logic gates, thereby reducing the cost and size of the sequential circuit.

When two states are said to be redundant?

The two states are said to be redundant if the output and the next state produced for each and every input are the same. In that case, one of the redundant states can be removed without altering the input-output relationship. This method is called the state elimination method.

Let us learn with examples here.

---

Example Problem #1

Determine the reduced state table for the given state table.

The given table contains the present state, next state and output produced for inputs X = 0 and 1. To find the reduced state table, the first step is to find the redundant/equivalent states from the given state table.

As explained above, any two states are said to be equivalent, if their next state and output are the same. In order to check that, compare each present state with the other.

First, consider the present state ‘a’, compare its next state and output with the other present states one by one. In this comparison, none of the present states is the same as the present state ‘a’.

Now, consider the next present state ‘b’ and compare it with other present states. While doing so, you can find the next state and the output of the present state ‘e’ is the same as that of ‘b’. They are marked as equivalent states as shown below.

Similarly, consider the other present states and compare them with other states for redundancy.

The next step is to replace the redundant states with the equivalent state. Here we have found, states b and e are redundant. Replace e by b and remove the state e.

Now, there are no equivalent states and so the reduced state table will become as follows.

---

Example Problem #2

Determine the reduced state diagram for the given state diagram.

To construct the reduced state diagram, first, build the state table for the given state diagram, find the equivalent states, remove the redundant state, draw the reduced state table and finally construct the state diagram.

First, the information in the state diagram is transferred into the state table as shown below.

Next, find the equivalent states. From the above table, you can observe that the next state and output of the present states ‘a’ and ‘d’ is found to be the same. It is shown in the below table.

Thus ‘a’ and ‘d’ are found as equivalent states. So, replace ‘d’ by ‘a’ and remove ‘d’. Now, the reduced state table will become as below.

The state diagram is constructed for the reduced state table as shown below.

FAQs