State Reduction and Good State Variable Assignments

State Reduction and Good State Variable Assignments

In digital circuit design, particularly for sequential circuits such as finite state machines (FSMs), state reduction and state variable assignments are crucial steps in optimizing the design. These processes help simplify the design, reduce the number of states needed, and improve the efficiency of the circuit in terms of both hardware resources and performance.

1. State Reduction

State reduction refers to the process of simplifying the state diagram of a finite state machine (FSM) by identifying and eliminating redundant or equivalent states. Redundant states are those that can be merged because they behave identically for all inputs and outputs. The goal of state reduction is to minimize the number of states in an FSM, which, in turn, reduces the complexity and resource requirements for the corresponding digital circuit.

Steps in State Reduction:

1. Construct the State Diagram:

   • First, draw the state diagram, identifying all states, transitions, and outputs for each state. In the case of a Mealy or Moore machine, determine the output associated with each state and transition.

2. Identify Equivalent States:

   • States are equivalent if, for all possible inputs, they transition to the same states and produce the same outputs.
   • To find equivalent states, create a state equivalence table (also known as a state table or reduced state table) where you compare every pair of states for their behavior. If two states behave identically under all inputs (i.e., produce the same output and transition to equivalent states), then they are equivalent and can be merged.

3. Merge Equivalent States:

   • After identifying equivalent states, merge them into a single state. This will reduce the number of states in the FSM, thus simplifying the design.

4. Draw the Reduced State Diagram:

   • After state reduction, draw the new state diagram with the reduced number of states. The transitions between the new merged states should reflect the same logic as before the reduction.

Example of State Reduction:

Consider a simple FSM with four states: S1, S2, S3, and S4. Assume that S2 and S4 are equivalent because they both transition to the same states and produce the same outputs for all inputs.

• Original States: S1, S2, S3, S4
• Reduced States: S1, (S2 = S4), S3

By merging S2 and S4 into a single state, we reduce the number of states and make the design simpler.

2. Good State Variable Assignments

Once state reduction has been applied, the next step is state variable assignment, which involves choosing how to represent the states of the FSM in terms of binary variables. The goal is to assign binary values to states in such a way that the FSM is easy to implement using digital circuits, and the logic for state transitions is as simple as possible.

A state variable is typically represented as a binary number, and the number of state variables depends on the number of states in the FSM. The number of binary variables needed is determined by the formula:

Where:

• $\lceil x \rceil$ is the ceiling function, which rounds up to the nearest integer.
• For example, if an FSM has 5 states, we would need $\lceil \log_2 5 \rceil = 3$ state variables (since $2^2 = 4$ and $2^3 = 8$, so 3 bits are needed to represent 5 states).

Criteria for Good State Variable Assignment:

• Minimize the number of state variables: The fewer state variables used, the fewer flip-flops are needed in the implementation, reducing the hardware resources.

• Simplify state transitions: A good state assignment should minimize the complexity of the transition logic between states. Ideally, the transitions between states should be as simple as possible to reduce the complexity of the combinational logic.

• Avoid unnecessary changes in multiple bits: Ideally, state assignments should be chosen such that only one state variable changes at a time during a transition, which makes the state machine easier to implement. This is often referred to as minimizing the Hamming distance between adjacent states (i.e., the number of bit changes between two states).

• Minimize "bounce": A good assignment reduces the chances that multiple state variables change simultaneously during a transition, which could lead to glitches or unnecessary complexity in the state transition logic.

Methods of State Variable Assignment:

1. Binary Assignment: The simplest method is to assign state variables in binary order (0, 1, 2, 3, etc.). This is often used when the number of states is relatively small, and the state transitions are simple.

2. Gray Code Assignment: Gray code is often used in situations where state transitions need to be smooth and minimize the number of bit changes between adjacent states. In Gray code, each consecutive state differs by only one bit, making the transitions simpler.

3. Using Symmetry: If the state diagram has symmetrical properties (e.g., the states are symmetric in terms of their inputs or outputs), try to assign the binary values in a way that reflects this symmetry, which can help simplify the state transition logic.

4. Adjacent States Assignment: Place adjacent states in binary assignments that minimize the number of bit changes, reducing the complexity of the logic that detects state transitions.

Example of State Variable Assignment:

Consider an FSM with the following states after reduction:

• States: S1, S2, S3
• Required State Variables: 2 (because $\lceil \log_2 3 \rceil = 2$)

We can assign the states as follows:

• S1 = 00
• S2 = 01
• S3 = 10

This simple binary assignment allows for efficient implementation with minimal state transitions.

However, if the state transitions require changes in multiple bits or result in a complex logic for detecting transitions, we may consider using Gray code or another optimized assignment to minimize the logic complexity.

3. Conclusion

• State Reduction is the process of simplifying a state machine by identifying and merging equivalent states, reducing the total number of states, which helps simplify the design and minimize the hardware resources required for implementation.

• Good State Variable Assignment involves choosing efficient binary representations for the states of an FSM. The goal is to minimize the number of state variables and make the transitions between states as simple as possible to reduce the complexity of the implementation.

Together, state reduction and good state variable assignment are crucial steps in optimizing the design of sequential circuits like FSMs, ensuring that the final implementation is both efficient and easy to build.