Hello! In our last lesson, we explored the "what" and "why" behind Mealy and Moore state machines, focusing on their different architectures and timing behaviors. You now know that a Moore machine's output depends only on its state, while a Mealy machine's output depends on both its state and its current inputs.
Today, we'll shift from theory to practice and tackle the "how". This lesson is all about translating a sequential problem description into a state diagram. This is arguably the most creative and critical step in designing a Finite State Machine (FSM), as this diagram serves as the visual blueprint for your entire circuit. We will focus on a classic digital design problem: a sequence detector.
By the end of this lesson, you will be able to take a simple sequential problem and create a complete state diagram to represent its behavior.
1. The Anatomy of a State Diagram
Before we start designing, let's establish the "grammar" of state diagrams. A state diagram is a directed graph with a few key components.
Designing sequential circuits using state diagrams
This section from Digilent's "Structural Design of Sequential Circuits" clearly breaks down the components of a state diagram.
Read the section titled "Designing sequential circuits using state diagrams". Focus on how states, transitions, and conditions are represented: States are shown as circles. Transitions are shown as directed arrows between states. Input Conditions are labels on the arrows that specify what input causes that transition. Outputs are shown either inside the state circle (Moore) or on the transition arrow (Mealy).
A crucial rule for any valid state diagram is that for any given state, every possible input combination must lead to exactly one, unambiguous next state. This is sometimes broken down into two rules:
- Collectively Exhaustive: All possible input combinations from a state must be accounted for. You can't have an input for which the behavior is undefined.
- Mutually Exclusive: A specific input combination can only lead to one next state. There should be no ambiguity.
2. The Design Process: A Step-by-Step Approach
Creating a state diagram involves thinking like the machine. You need to ask yourself, "What information must I remember at this moment to make a correct decision later?" Each unique answer to this question becomes a state.
The general process is:
- Identify the States: Determine the distinct conditions or phases of operation. A good starting point is to have a "reset" or "idle" state. Then, add states that represent the progress made towards a goal.
- Draw the Transitions: For each state you've defined, consider every possible input. Draw an arrow to the appropriate next state based on that input.
- Assign Outputs: Based on whether you are designing a Moore or Mealy machine, place the output values in the states or on the transitions.
- Verify: Check that your diagram is exhaustive and mutually exclusive for all states.
Let's see this in action with a classic example.
3. Example: Detecting the Sequence 0111 (Moore FSM)
Our goal is to design a circuit that takes a single-bit input stream and asserts its output to 1 whenever it detects the exact sequence 0111. For this first attempt, we'll design a Moore machine.
The key is to create a state for each partial sequence we've successfully detected.
- State A (Idle): We haven't seen any part of the sequence yet.
- State B: We've just seen a
0. - State C: We've seen
01. - State D: We've seen
011. - State E: We've seen the complete
0111sequence. This is our "success" state where the output will be1.
Now, let's watch a video that walks through the process of connecting these states based on the input.
0111 Sequence Detector-Using Mealy and Moore FSM
This video from Easy Electronics provides a clear, step-by-step construction of a Moore state diagram for our 0111 sequence detector.
Watch the segment on the Moore type FSM. As you watch, focus on the logic for each transition: When does the FSM progress to the next state? (e.g., in State B, receiving a 1 moves you to State C). When does the FSM have to reset? (e.g., in State D, receiving a 0 breaks the sequence, so where should it go?). When does the FSM stay in the same state? (e.g., in State B, receiving another 0 still means the last relevant bit was a 0).
After following that process, you end up with a complete state diagram. The image below shows a cleanly drawn version of the Moore FSM you just studied.
4. Revisiting the Problem: The Mealy Approach
As we discussed in the last lesson, Mealy machines can often accomplish the same task with fewer states. Let's see how that applies to our 0111 detector.
Since a Mealy machine's output depends on the input and state, we can generate the 1 output on the final transition itself. We don't need a separate state just for the output.
- State A (Idle): We've seen nothing.
- State B: We've seen a
0. - State C: We've seen
01. - State D: We've seen
011.
From State D, if we receive a 1, we have detected 0111. The machine will output a 1 during this transition and then decide where to go next.
Now, let's continue with the same video to see how this is constructed.
0111 Sequence Detector-Using Mealy and Moore FSM
This part of the video builds the Mealy version of the same detector.
Now, watch the construction of the Mealy type sequence detector. Pay close attention to: How the output 1 is generated on the transition from the state where 011 is detected to the state where the sequence starts over. Why this allows the FSM to have only four states instead of the five required for the Moore machine.
5. A Second Example: Detecting "Three or More Consecutive 1s"
To solidify your skills, let's look at a slightly different problem: designing an FSM to detect three or more consecutive 1s. This example introduces the idea of an "overlapping" sequence, where the end of one detected sequence can be the start of another.
This video from Neso Academy provides an excellent walk-through of this new problem.
First, watch the problem description to understand the goal and the concept of overlapping sequences. Next, see how the states are systematically defined based on how many consecutive '1's have been detected. Finally, watch the full state diagram construction. Notice how receiving a 1 in the final state keeps the machine in that state, continuing to output 1 as long as the input is 1.
This example reinforces the core thinking process: define your states based on what you need to remember, and then for each state, methodically handle every possible input.
Conclusion
In this lesson, you moved from knowing what an FSM is to creating the blueprint for one. The state diagram is a powerful tool that bridges the gap between a human-readable problem description and a machine-implementable logic circuit.
Key Takeaways:
- A state diagram represents states (circles), transitions (arrows), and the input conditions that cause them.
- A valid diagram must be exhaustive (handles all inputs) and mutually exclusive (no ambiguity).
- The design process involves identifying the unique pieces of information the machine needs to remember and defining a state for each.
- For each state, you must trace the path for every possible input, either progressing, resetting, or staying in the same state.
- The choice of Mealy vs. Moore affects how outputs are assigned and can change the number of states required.
In our next lesson, we will take the state diagrams we've created today and learn how to translate them into a state transition table. This tabular format is the next logical step toward writing the final Verilog code for your FSM.