What starts as a simple task can quickly spiral into something far more complex—whether it’s home repairs, birthday parties, or, unfortunately, Finite State Machines (FSMs). In Hardware Description Language (HDL), it’s easy to keep adding states—“wait” states, nested states, and so on. While these states are meant to simplify logic and improve maintainability, they often end up doing the opposite! Let’s discuss Finite State Machines and how to simplify their usage in your designs.
What Is a State Machine?
A state machine is a computational model used to design systems that operate in a series of distinct modes, or “states,” and move between them based on defined events or conditions. Each state represents a specific configuration or mode in which the system behaves in a certain way. The transitions between states are determined by rules that respond to external inputs or conditions. This design approach is valuable for controlling predictable behaviors. State machines are widely used in applications where systems need structured responses to inputs. Examples of using state machines include controlling devices, managing workflows, or automating processes with defined operational modes.
Example of a State Machine
A simple example of a state machine would be your front door. When you approach the door, it may be locked or unlocked. Think of these as two different states of the door. If you supply the correct key, the door lock will change state from ‘locked’ to ‘unlocked’ and you can open the door. Providing an incorrect key will not change the lock’s state, which in turn does not allow you to open the door. Using the correct key will allow you to change the state of the door lock and open the door. This is an example of how a state machine can be used to produce a result or output.
What Is a Finite State Machine?
A finite state machine is a computational model that consists of a finite number of states, transitions between those states, and actions, which occur based on inputs. An FSM can be in only one state at a time, and it changes states in response to external inputs and its current state according to pre-defined transition rules. It’s used to model systems with a limited, well-defined number of conditions or states.
Types of Finite State Machines
Mealy Machines
A Mealy machine is a type of state machine whose output depends on both the current state and the input. This allows for faster responses to changes in input. The output in a Mealy machine is produced during state transitions. It can vary for the same state based on different inputs. In our door lock example, imagine we added an LED which blinked when the lock was supplied with an incorrect key and while in the LOCKED state. The output, in this case, the blinking LED, depends on whether the correct or incorrect key is used as the input and the state of the FSM. This design makes Mealy machines suitable for applications needing immediate reactions. They are often used in control systems and digital circuits where outputs change dynamically with inputs.
Moore Machines
A Moore machine is a type of finite state machine (FSM). Its output depends only on the current state, not the input. This is the key difference from a Mealy machine, where both state and input determine the output. In a Moore machine, the output remains constant while in a given state. It only changes when the state transitions. For example, in a traffic light system, the Red state produces the output “Stop.” The Green state produces the output “Go.” The Yellow state produces the output “Caution,” regardless of external input. This makes Moore machines more predictable but slower to respond. They are commonly used in systems requiring stable outputs tied to specific states, such as counters or control systems.
Using Finite State Machines
Keeping the example of the door lock in mind, you may be thinking about a single FSM to implement it. And that’s what most people think. In the future, though, this FSM may be a barely maintainable massive block of code as new features and new states are added. A better approach would be to notice in the example that the state of the door does not depend on the key, only the state of the lock.
This example would benefit from two FSMs. One FSM revolves around the state of the door and whether it can open or close. The other is entirely focused on the lock and whether it can be locked or unlocked. These FSMs do interact with each other but are independent. This allows for future rework and addition of new features with ease, while each FSM remains a simple concept and implementation.
How to Simplify Finite State Machines
But this blog post is not about locks and doors, it is instead about simplifying the operation of FSMs. This approach of keeping an FSM to a simple idea can help separate what would otherwise be a monolithic and complex FSM into independent and simple FSMs.
State Diagram Analysis
Reference the state diagram above: a typical FSM will have states which loop; a single loop is as simple as it gets. If the FSM state diagram shows multiple loops, as in smaller loops embedded into the larger loop, investigate whether the smaller loops’ control signals are highly localized to that small loop. If so, you may have a candidate for a separate FSM.
Functional Flow Analysis
Another way to inspect an FSM is to see that at its core, an FSM enacts a functional flow correlating inputs and outputs. Identifying whether there are multiple functional flows being described can aid in separating the FSM into simpler forms. This could look like the states are describing the functions and conditions of a bus while also managing those of a process or module. In which case, ensuring that the bus functions have their own FSM, separate from other processes and module functions, eliminates odd, amalgamated states and improves understanding of the overall purpose of the FSM. Additionally, separate FSMs do not tie each other up unless intended. While one FSM is busy performing its functions, the others can be busy with different tasks.
The effort to simplify and split FSMs early in the design process is always worth doing, if nothing else than for ease of comprehension and maintainability.
FSM Optimization Techniques
Beyond splitting large FSMs into smaller, more manageable machines, there are additional optimization techniques that can further simplify your design. State reduction is one such technique, which involves minimizing the number of states without sacrificing functionality. By identifying redundant or equivalent states, you can reduce the complexity of the FSM while maintaining its original behavior. Another powerful approach is encapsulation, where related states are grouped together into higher-level abstractions. This modularizes the FSM, making it easier to manage, understand, and extend. Encapsulation allows you to handle related functionality within a smaller scope. This reduces the overall cognitive load and making future updates more straightforward. Together, these techniques help streamline FSM design, making systems more efficient and maintainable.
Edge Cases and Error Handling in Finite State Machines
Handling edge cases and error states is crucial in FSM design, yet it’s often overlooked. Finite State Machines should account for unexpected inputs or faults to ensure robust operation. Best practices include defining explicit error states that the FSM can transition to when it encounters invalid inputs or conditions. These error states can trigger recovery actions, such as resetting the FSM to a safe state or alerting other system components to handle the fault. Additionally, incorporating guard conditions—checks that prevent illegal transitions—can help manage edge cases before they lead to errors. By designing error-handling mechanisms early in the process, you can ensure your FSM remains resilient in real-world scenarios, improving its reliability and maintainability.
Hardware Considerations
When designing Finite State Machines (FSMs), it is essential to consider their implications on hardware implementation. This is true especially in terms of resource consumption and timing. The complexity of states directly affects the resource usage in Field Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuits (ASICs). It influences the number of registers, memory blocks, and logic gates required. A more complex FSM can lead to increased resource consumption, which may impact overall system cost and efficiency. Additionally, timing considerations play a critical role as particularly complex FSM states can affect timing paths and performance. Poorly designed FSMs can introduce timing violations or increase propagation delays, potentially degrading the system’s performance. Therefore, optimizing FSM design with these hardware considerations in mind is vital for ensuring a reliable and efficient implementation in real-world applications.
Finite State Machines Testing and Debugging
Testing and debugging are critical aspects of Finite State Machine (FSM) design, ensuring that the system functions as intended before deployment. To effectively test FSMs, employing state coverage metrics can be invaluable. These metrics help determine which states and transitions have been exercised during testing, providing insights into areas that may require further validation. Additionally, utilizing simulation techniques allows designers to model the FSM behavior under various conditions, making it easier to identify potential issues before hardware implementation. Tools like ModelSim or other simulation environments can facilitate this process, enabling thorough testing of both expected and edge-case scenarios. By incorporating these strategies into the design workflow, developers can enhance the reliability of their FSMs and reduce the risk of encountering unforeseen issues in real-world applications.
Wait States
HOLD ON, WAIT!
A Wait State is a state which exists solely to consume a clock cycle. We recommend you use just one wait state for the FSM with two registered signals. One for the number of clock cycles to consume, and another for the state to go to afterwards.
Conclusion
Do we really want to live in a world where large, monolithic FSMs are the norm? We already do… but let’s change that. Complexity can easily creep in, turning a once simple system into a convoluted mess. However, by keeping FSMs focused on a single function and splitting them, when necessary, you can maintain clarity, simplicity, and scalability in your designs. Whether you’re handling doors and locks or designing complex hardware systems, breaking down monolithic FSMs into smaller, independent ones will improve maintainability, facilitate future updates, and make your systems easier to understand and manage. Taking the time to streamline your FSMs now will save you from headaches later.
LEARN MORE
Watch our on-demand video on RFSoCs and Safe State Machines.
Read about Cross Triggering in our blog.
Take a Class: Designing with VHDL
