# Objective 2.8 — Finite State Machines (Documentation: ChatGPT was used in helping generate this objective's reading.) | LO# | Description | |----------|----------| | 2.8 | I can model Moore and Mealy Finite State Machines (FSMs) using tools such as state transition diagrams, transition tables, and combinational and sequential logic circuits. | By the end of this reading you should be able to: 1. Distinguish **combinational** from **sequential** logic. 2. Distinguish a **Moore** machine from a **Mealy** machine. 3. Read and draw a **state transition diagram** and convert it to a **transition table**. 4. Work the **seven-step design process** through to logic equations and flip-flops. --- ## 1. Introduction to Finite State Machines (FSMs) ### 1.1 What is a Finite State Machine? A **Finite State Machine (FSM)** is a computational model used to represent and control the execution flow of a system that can exist in a **finite number of states**. At any given time, an FSM is in one particular state. Based on the input it receives and the current state, it determines the next state and may produce an output. This behavior makes FSMs ideal for modeling systems where outcomes depend on both past and present events. FSMs are defined by the following components: - **States** – A finite set of distinct configurations that represent the system’s condition at any given moment. - **Inputs** – A set of signals or conditions that affect the state transitions. - **Transitions** – A set of rules that define how the FSM moves from one state to another based on inputs. - **Outputs** – Signals or values that the FSM generates based on the current state and/or inputs. - **Initial State** – The state where the FSM starts operating. FSMs are widely used in various fields of engineering and computer science because they provide a structured and predictable way to model complex systems. They are especially useful in **control systems**, **digital circuits**, **communication protocols**, **robotics**, and **software development**. --- ### 1.2 Why Use FSMs? FSMs are used because they offer: **Predictability** – FSMs follow a clear and deterministic pattern of state transitions based on inputs. **Simplicity** – Complex problems are broken down into manageable states and transitions. **Reusability** – FSM models can be reused and adapted across different applications. **Debuggability** – FSMs offer clear, structured models that simplify troubleshooting. **Automation** – FSMs enable the automation of complex sequences and decision-making processes. --- ### 1.3 FSM Examples in Engineering FSMs are used extensively in both hardware and software applications: 1. **Digital Circuits** - Used in control logic for microprocessors, memory controllers, and communication interfaces. - Example: An FSM controlling an elevator's floor selection system. 2. **Networking and Protocols** - FSMs define the state-based behavior of communication protocols (e.g., TCP/IP handshake). - Example: A protocol state machine for handling data transmission and reception. 3. **Embedded Systems** - Used to control devices like washing machines, traffic lights, and vending machines. - Example: An FSM managing the washing cycles of a washing machine. 4. **Software Development** - Used in artificial intelligence for decision-making models. - Example: Game AI where different NPC (Non-Player Character) states determine behavior. 5. **Automotive Systems** - Used for managing state-dependent functions like anti-lock braking systems (ABS) and automatic transmission. - Example: FSM controlling gear shifts based on speed and load. --- :::{admonition} Key Concept :class: key-concept **Moore** output depends only on the state and is written inside the bubble. **Mealy** output depends on state *and* input and is written on the arrow. Project 2's machine carries one of each — a state telemetry voltage (Moore) and a fire command (Mealy). ::: ### 1.4 Moore vs. Mealy Machines FSMs are classified into two types based on how they generate outputs: #### **Moore Machine** - The output depends **only on the current state**. - State transitions are determined by inputs, but outputs are defined solely by the state. - Moore machines typically have **more states** but **simpler transition logic**. - Outputs are generated after a state transition has occurred, which may introduce a delay. ![](./ECE215_B2_Obj08_Reading_media/Image2.png) **Advantages of Moore Machines:** - Simpler to design and understand. - Outputs are more stable since they depend only on the state. **Disadvantages:** - More states may be required to implement the same functionality compared to Mealy machines. **Example:** Traffic lights are typically modeled as Moore machines where the light state determines the output (red, green, yellow). --- #### **Mealy Machine** - The output depends on **both the current state and the input**. - State transitions and outputs can change simultaneously when the input changes. - Mealy machines can have **fewer states** than Moore machines for the same task but require **more complex transition logic**. - Outputs can change more quickly in response to inputs since they are not tied to state alone. ![](./ECE215_B2_Obj08_Reading_media/Image3.png) **Advantages of Mealy Machines:** - Fewer states are required for complex behavior. - Can respond faster to inputs since the output is computed directly from the input and state. **Disadvantages:** - More complex to design and test. - Outputs can be less stable since they depend on real-time inputs. **Example:** A vending machine is often modeled as a Mealy machine because the output (dispensing an item) depends on both the state (amount of money entered) and the input (coin type). --- ### 1.5 FSM Implementation in Hardware FSMs are commonly implemented in digital hardware using: - **Flip-Flops** – To store the current state. - **Combinational Logic** – To compute the next state and outputs based on current state and inputs. Modern FSM designs are often implemented using **Field Programmable Gate Arrays (FPGAs)** and **hardware description languages** like **VHDL** and **Verilog**. #### **Basic FSM Structure in Hardware:** 1. **Inputs** – Binary signals that control the state transitions. 2. **Next State Logic** – Determines the next state based on the present state and inputs using combinational logic. 3. **Flip-Flops** – Hold the current state and update it on each clock cycle. 4. **Output Logic** – Generates the output signals based on the state and inputs (Mealy) or state alone (Moore). FSM Hardware Block Diagram: ``` +-------------+ +--------------+ Inputs →| Next State |→ Next State → | Flip-Flops | | Logic | | (State Memory)| +-------------+ +--------------+ | | ↓ ↓ +-------------+ +--------------+ | Output Logic |→ Outputs → | Output Signals| +-------------+ +--------------+ ``` **Example:** A traffic light FSM in hardware would: - Use a D flip-flop to store the current state. - Combinational logic to determine the next state and outputs. - Outputs would control the traffic lights based on the current state. --- ### 1.6 FSM Implementation in Software FSMs are also widely used in software design for state-based control and behavior modeling. - A state can be represented using **constants** or **enumerations**. - A state transition table can be implemented using **arrays** or **switch-case** statements. - Transitions can be triggered by user input, timeouts, or external events. **Example:** A video game AI might use an FSM to control the behavior of a character. Transitions would be based on game events like proximity to an enemy or health level. - **State 1** – Idle → low health - **State 2** – Patrol → high health and close to an enemy - **State 3** – Attack → high health and under attack or close to an enemy - **State 4** – Flee → low health and under attack or close to an enemy --- ### 1.7 Advantages and Limitations of FSMs **Advantages:** ✔️ Simple to design and understand. ✔️ Predictable behavior. ✔️ Efficient in hardware and software implementations. ✔️ Good for sequential control problems. **Limitations:** ✖️ Limited scalability – FSMs become difficult to manage when the number of states becomes large. ✖️ Not well suited for complex, parallel operations. ✖️ State explosion – As the complexity increases, the number of states can grow exponentially. --- ### 1.8 Summary Finite State Machines provide a structured approach to modeling complex state-based behavior. Moore and Mealy machines each offer unique advantages depending on the application. FSMs are central to digital design, embedded systems, and software development due to their simplicity and predictability. When properly designed, FSMs can lead to efficient, reliable, and scalable systems. --- ## 2. State Transition Diagrams FSMs are often modeled using **state transition diagrams**, which provide a graphical representation of states and transitions. ### Components of a State Transition Diagram: 1. **States** – Represented as circles, showing all possible configurations of the system. 2. **Transitions** – Represented as arrows connecting states, indicating how the system moves from one state to another. 3. **Events/Inputs** – Labels on the arrows that describe the condition that causes the transition. 4. **Outputs** – The values produced based on the state (Moore) or state and inputs (Mealy). ### Moore Machine Example: A Moore FSM that recognizes the binary sequence `10` would have states: - S0 → Start state - S1 → After seeing `1` - S2 → After seeing `10` Transition Example: - Start in S0 - If input = `1`, transition to S1 - If next input = `0`, transition to S2 and generate an output ![](./ECE215_B2_Obj08_Reading_media/Image4.png) ### Mealy Machine Example: In a Mealy FSM, the output can change based on the input while in a given state. This can reduce the number of required states but increases the complexity of the transition logic. --- :::{admonition} Key Concept :class: key-concept $n$ states need $\lceil \log_2 n \rceil$ bits, and **each bit needs its own flip-flop**. If you use 2 bits for 3 states, you must decide what the unused fourth code does — a machine that glitches into an undefined state with no transition out will stay there forever. ::: ## 3. FSM Design Process ### Step 1: Define/Encode the States - Assign a binary value to each state. - Example: 3 states require 2 bits ($2² = 4$ states). - S0 = 00, S1 = 01, S2 = 10 This is exactly the shape of **Project 2's** machine — its three states SEARCH, DETECT and LOCK are encoded 00, 01 and 10, and the leftover 11 is guarded so a corrupted state falls back to SEARCH rather than locking up. ### Step 2: Define/Encode the Inputs - Inputs are typically binary (0 or 1), but multi-bit inputs are possible. - Example: An input `X` could represent `0` or `1`, or more complex values. ### Step 3: Define/Encode the Outputs - In a Moore machine, output depends on state only. - In a Mealy machine, output depends on state and input. ### Step 4: Create a State Transition Diagram - Draw the states as circles. - Connect them with arrows showing the transitions based on input. ### Step 5: Create a State Transition Table A state transition table maps the present state and input to the next state and output. In the example below there are three states encoded in two bits, $Q_1$ and $Q_0$, and one input, $X$. All possible combinations of the state bits and the input are listed: 2 state bits + 1 input bit gives $2^3 = 8$ rows, and the last two — the unused code `11` — must be defined like any other. The third column shows the next state (represented by the $^+$) for each present state and input combination, while the fourth column shows the output, $Z$. | Present State, $Q_1 Q_0$ | Input, $X$ | Next State, $Q_1^+ Q_0^+$ | Output, $Z$ | |:-------------:|:-----:|:----------:|:------:| | 00 | 0 | 00 | 0 | | 00 | 1 | 01 | 0 | | 01 | 0 | 10 | 1 | | 01 | 1 | 00 | 0 | | 10 | 0 | 00 | 0 | | 10 | 1 | 00 | 0 | | 11 | 0 | 00 | 0 | | 11 | 1 | 00 | 0 | Sending the unused code `11` back to `00` is what keeps a machine that glitches into it from staying there forever. ### Step 6: Express Logic Equations Use Boolean algebra to express the next state and output logic. From the state transition table above, we use the Sum of Products (SOP) form to find $Q_1^+$, $Q_0^+$, and $Z$ — one product term for each row where that column is a 1: - Next state equation: $$Q_1^+ = \overline{Q_1} Q_0 \overline{X}$$ $$Q_0^+ = \overline{Q_1} \overline{Q_0} X$$ - Output equation: $$Z = \overline{Q_1} Q_0 \overline{X}$$ Here the output expression happens to look like $Q_1^+$, but an output and a next-state bit are different things: read each one off its own column. And because $Z$ depends on the input $X$ as well as on the state, this example is a **Mealy** machine. ### Step 7: Implement with Flip-Flops and Logic Gates Use flip-flops to store the state and combinational logic to calculate the next state and outputs: - Flip-flop holds the current state. - Combinational logic calculates the next state and output. --- ## 4. Example FSM Designs The following examples will be worked out in class. ### Example 1: Sequence Recognizer **Design Goal:** Recognize the sequence `11` - States: S0 (nothing yet) → S1 (one 1) → S2 (two 1s in a row) - Inputs: Binary input $X$ - Outputs: Output `1` whenever the last two inputs were `11`, so a third 1 keeps the output asserted (overlapping detection) ### Example 2: 2-Bit Counter **Design Goal:** Count from 0 to 3 and wrap around - States: 00, 01, 10, 11 - Inputs: Increment signal (1 = increment, 0 = hold) - Outputs: Current state (Moore machine) | Present State | Input | Next State | Output | |---------------|-------|------------|--------| | 00 | 0 | 00 | 00 | | 00 | 1 | 01 | 00 | | 01 | 0 | 01 | 01 | | 01 | 1 | 10 | 01 | | 10 | 0 | 10 | 10 | | 10 | 1 | 11 | 10 | | 11 | 0 | 11 | 11 | | 11 | 1 | 00 | 11 | ### Example 3: Vending Machine **Design Goal:** Dispense product after receiving 20¢ - States represent the total inserted so far: 0¢, 5¢, 10¢, 15¢ — four states in two bits (00, 01, 10, 11); a total that reaches 20¢ dispenses and returns to 0¢ - Inputs: N = nickel, D = dime, Q = quarter - Outputs: Dispense product and return change Three of the rows (the full table is worked in class): | Present State | Input | Next State | Output | |---------------|-------|------------|--------| | 00 | N | 01 | 0 | | 01 | D | 11 | 0 | | 11 | N | 00 | 1 (Dispense) | ### Example 4: Traffic Light Control **Design Goal:** Control traffic light based on sensor inputs - States: - S0 = NS green, EW red - S1 = NS yellow, EW red - S2 = NS red, EW green - S3 = NS red, EW yellow - Inputs: Sensor data - Outputs: Light configuration | Present State | Input | Next State | Output | |---------------|-------|------------|--------| | S0 | 00 | S0 | NS green, EW red | | S0 | 01 | S1 | NS yellow, EW red | | S1 | - | S2 | NS red, EW green | | S2 | 10 | S2 | NS red, EW green | --- ## 5. Summary Finite State Machines (FSMs) provide a structured and systematic way to design and analyze state-based systems. They are widely used in both hardware and software applications due to their ability to represent complex sequences of operations in a clear and predictable manner. FSMs consist of a finite number of states, and the system transitions between these states based on inputs and defined transition rules. FSMs are classified into two main types: **Moore machines** and **Mealy machines**. Moore machines generate outputs based only on the current state, making them more stable and easier to test. Mealy machines generate outputs based on both the current state and the inputs, allowing them to respond more quickly to changes but adding complexity to the design. The design process for FSMs includes defining the states, encoding inputs and outputs, creating state transition diagrams and tables, deriving logic equations, and implementing the system using flip-flops and combinational logic. Modern FSMs are frequently implemented using **FPGAs** and programmed with hardware description languages like **VHDL** and **Verilog**. FSMs offer significant advantages, such as predictability, simplicity, and reusability, but they can become challenging to manage when the number of states grows too large. Despite this, FSMs remain one of the most effective methods for modeling and controlling state-dependent behavior in modern engineering and computer science. ::::{admonition} Type-along :class: type-along Design a Moore FSM that counts $0 \to 1 \to 2 \to 0$ circularly, with a direction input $B$: $B = 1$ counts up, $B = 0$ counts down. 1. Encode the states. How many bits and flip-flops? 2. How many rows does the full transition table have? 3. Write the SOP equations for $Q_1^+$ and $Q_0^+$. 4. What happens if the machine powers up in the unused fourth state code? :::{admonition} Solution :class: dropdown **1.** Three states need 2 bits and 2 flip-flops. Encode S0 = 00, S1 = 01, S2 = 10; 11 is unused. **2.** 2 state bits + 1 input bit = 3 bits, so **8 rows** — including the two for the unused code, which you must still fill in. **3.** Up ($B=1$): $00\to01$, $01\to10$, $10\to00$. Down ($B=0$): $00\to10$, $01\to00$, $10\to01$. $Q_1^+ = \overline{Q_1}Q_0 B + \overline{Q_1}\,\overline{Q_0}\,\overline{B}$ and $Q_0^+ = \overline{Q_1}\,\overline{Q_0}B + Q_1\overline{Q_0}\,\overline{B}$. **4.** With no transition defined out of 11, the machine **locks up there permanently**. The fix is to define $11 \to 00$ explicitly. This is why unused state codes matter in real systems. ::: :::: ## Wrap-Up Sequential logic depends on **history**, and the state is the memory. A **Moore** machine's output depends only on the state; a **Mealy** machine's depends on state and input. The seven-step process — encode states, inputs, and outputs; diagram; table; logic equations; flip-flops — turns a behavioral description into hardware, and the next-state logic is just the combinational logic of Objective 2.7 wrapped around memory. This objective is the whole of **Project 2** — which requires the diagram and table, with the circuit step in software. Deriving the next-state and FIRE equations is optional but encouraged: if you do, check them with **Test All Rows** in the FSM Explorer's **Student Logic** card.