6.2.5 Equivalent States; Implementation

TL;DR

"Learn how to find and merge equivalent states in Finite State Machines (FSMs), resulting in hardware savings."

Transcript

Earlier we talked about about finding equivalent FSMs with fewer states. Now we'll develop an approach for finding such FSMs by looking for two states that that can be merged into a single state without changing the behavior of the FSM in any externally distinguishable manner. Two states are equivalent if they meet the following two criteria. First... Read More

Key Insights

• 🔠 Equivalent states in FSMs have identical outputs and transition to equivalent states for each input combination.
• 🥺 Merging equivalent states reduces the number of state bits required for implementation, leading to significant hardware savings.
• 💻 FSMs are widely used for modeling complex behaviors in various domains, including computer graphics and molecular interactions.
• ❓ Cellular automata can be used to model physical behaviors that arise from interactions between component molecules.
• 👻 Adopting the concept of allowing FSMs to modify their own transition tables can be a plausible model for evolution.

Questions & Answers

Q: What are the criteria for two states to be considered equivalent in an FSM?

Two states are considered equivalent if they have identical outputs and transition to equivalent states for each combination of input values.

Q: How is hardware savings achieved by merging equivalent states?

Merging equivalent states reduces the number of state bits required for implementation. This reduction in state bits translates to a smaller required ROM size, leading to significant hardware savings.

Q: Can merging equivalent states change the behavior of the FSM?

No, merging equivalent states does not change the externally distinguishable behavior of the FSM. The merged state behaves the same as the original states.

Q: What are some practical applications of FSMs?

FSMs are widely used for modeling and implementing various behaviors, such as maze following, swarming, flocking, and schooling. They are also used in computer graphics and cellular automata.

Summary & Key Takeaways

• Finding equivalent states in FSMs involves ensuring that they have identical outputs and transition to equivalent states for each input combination.

• By merging equivalent states, the number of state bits required for implementation can be reduced, resulting in hardware savings.

• The process of merging equivalent states can be repeated until no more equivalent states are found.