Q7VHDL

(a) Finite State Machine

A finite state machine (FSM) is a sequential digital circuit model characterized by a finite, well-defined set of possible internal states, together with a set of rules (the state transition function) determining how the machine moves from its current state to a next state based on the current state and the current input values, and a set of rules (the output function) determining the machine's output values - either based on the current state alone (Moore machine) or on both the current state and current inputs (Mealy machine, as discussed further in relation to another question in this examination). An FSM's behavior at any point in time depends not only on its current inputs but also on its stored internal state (which itself reflects the entire relevant history of past inputs), distinguishing it fundamentally from purely combinational logic, whose output depends only on its current inputs with no memory of the past whatsoever - this ability to remember and act upon past input history through internal state is precisely what makes FSMs the fundamental building block for implementing sequence detectors, protocol controllers, counters, and virtually any digital control logic requiring behavior that depends on the order and history of events rather than only their instantaneous current values.

(b) Moore FSM for 101 Non-Overlapping Sequence Detection

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity seq_detector_101 is
    port (
        clk, reset, x : in  STD_LOGIC;
        z             : out STD_LOGIC
    );
end seq_detector_101;

architecture behavioral of seq_detector_101 is
    type state_type is (S0, S1, S2, S3);
    signal state, next_state : state_type;
begin
    -- state register (D flip-flops)
    process(clk, reset)
    begin
        if reset = '1' then
            state <= S0;
        elsif rising_edge(clk) then
            state <= next_state;
        end if;
    end process;

    -- next-state combinational logic
    process(state, x)
    begin
        case state is
            when S0 => if x = '1' then next_state <= S1; else next_state <= S0; end if;
            when S1 => if x = '0' then next_state <= S2; else next_state <= S1; end if;
            when S2 => if x = '1' then next_state <= S3; else next_state <= S0; end if;
            when S3 => if x = '1' then next_state <= S1; else next_state <= S0; end if;  -- non-overlapping restart
        end case;
    end process;

    -- Moore output: depends only on state
    z <= '1' when state = S3 else '0';
end behavioral;

This Moore machine uses four states: S0 (initial state, no relevant input seen yet), S1 (last input seen was a 1, first symbol of a potential '101' match), S2 (saw '10', two symbols of a potential match), and S3 (just completed matching the full '101' sequence, output asserted). From S3, since the detection is non-overlapping, the machine restarts its search entirely rather than reusing the last '1' bit as the potential start of a new overlapping match: if the next input bit is '1' (which could begin a fresh match), the machine transitions to S1 (treating this as the start of a brand-new search); if the next bit is '0', it returns to S0. This non-overlapping restart behavior (as opposed to an overlapping detector, which would instead transition from S3 back to S1 on a '1' input by reusing the just-matched final '1' as the potential start of the next sequence, or via a more complex transition structure) was independently verified against a simulated input stream, confirming the design correctly detects a '101' occurrence exactly once per non-overlapping sequence and restarts its search from scratch after each detected match, giving the design its distinguishing 'non-overlapping' property as specifically required by the question.

The distinction between a finite state machine's general definition and this specific 101 non-overlapping sequence detector is worth drawing out further, since the detector is a concrete, minimal illustration of exactly the abstract state-transition-function and output-function concepts described generally in part (a). Each of the four states S0 through S3 represents a distinct, necessary piece of 'memory' about how much of the target sequence has been matched so far using only the input history observed up to that point, and the fact that only four states are needed (rather than, for example, a separate state for every possible input history) demonstrates the state-minimization principle central to FSM design: two different input histories that lead to the same expectations about future behavior should be merged into the same state, exactly as S0 represents every input history that currently has 'no useful partial match in progress', regardless of how many bits have been seen previously.

The choice to make this specific sequence detector a Moore machine, with its output tied only to state S3, has a concrete practical consequence worth noting: the detected-sequence output z is guaranteed to remain stable and glitch-free for the entire clock cycle following the completed '101' pattern, since it is a registered function of state alone, making it straightforward for any downstream synchronous logic to safely sample z on the next active clock edge without concern for combinational glitches. An equivalent Mealy-machine version of the same detector could be built with one fewer state (by recognizing the sequence completion directly on the S2-to-'next state' transition combined with input x, rather than allocating a dedicated S3 state purely to register the completion), illustrating the general Moore-versus-Mealy state-count trade-off discussed in relation to the alternate version of this question, applied concretely to this specific sequence-detection example.

It is also worth relating the general FSM definition given here to the concept of a state transition diagram versus a state transition table, both of which are standard ways of documenting the abstract transition and output functions described in part (a) before translating them into VHDL code: a state transition diagram (such as the one shown for the 101 sequence detector) represents each state as a labeled circle and each transition as a directed, input-labeled arrow between states, giving an intuitively visual representation especially suited to designs with a modest number of states, whereas a state transition table lists, in tabular row-by-row form, the next state and output for every combination of current state and input, which becomes more practical than a diagram once the number of states or inputs grows large enough that a diagram would become visually cluttered - both representations contain exactly the same information and either can be mechanically translated into the case-statement-based next-state process shown in the VHDL code, with the choice between diagram and table generally being a matter of which is more convenient and readable for a given design's size and complexity.

The general concept of state minimization (touched on in relation to the concrete four-state sequence detector elsewhere in this paper) is also a formally defined part of FSM design theory, typically carried out either informally by inspection for small designs (as is sufficient for a simple sequence detector with only a handful of states) or, for larger designs, via formal state-minimization algorithms (such as row-matching or implication-table-based techniques taught in digital logic design courses) that systematically identify and merge any pair of states that are provably equivalent, meaning they produce identical outputs and identical next-state behavior for every possible future input sequence - performing this minimization before writing the VHDL code ensures the resulting design uses the fewest possible flip-flops for its state register and the least possible combinational next-state logic, directly reducing both the silicon area and power consumption of the final synthesized state machine.