Moore machine implementation in VHDL - Time & Space Complexity

Time Complexity: Moore machine implementation

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a Moore machine in VHDL changes as the input size grows.

Specifically, we ask: how does the number of steps the machine takes grow with the input length?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity MooreMachine is
  Port ( clk : in STD_LOGIC;
         reset : in STD_LOGIC;
         input_signal : in STD_LOGIC_VECTOR(3 downto 0);
         output_signal : out STD_LOGIC);
end MooreMachine;

architecture Behavioral of MooreMachine is
  type state_type is (S0, S1, S2);
  signal current_state, next_state : state_type;
begin
  process(clk, reset)
  begin
    if reset = '1' then
      current_state <= S0;
    elsif rising_edge(clk) then
      current_state <= next_state;
    end if;
  end process;

  process(current_state, input_signal)
  begin
    case current_state is
      when S0 =>
        if input_signal = "0001" then
          next_state <= S1;
        else
          next_state <= S0;
        end if;
      when S1 =>
        if input_signal = "0010" then
          next_state <= S2;
        else
          next_state <= S1;
        end if;
      when others =>
        next_state <= S0;
    end case;
  end process;

  output_signal <= '1' when current_state = S2 else '0';
end Behavioral;

This code models a Moore machine with three states that changes state on each clock cycle based on the input signal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The state update on each clock cycle (rising edge).
• How many times: Once per clock cycle, repeating for each input in the sequence.

How Execution Grows With Input

Each input symbol causes one state transition on the next clock cycle.

Input Size (n)	Approx. Operations
10	10 state transitions
100	100 state transitions
1000	1000 state transitions

Pattern observation: The number of operations grows directly with the number of input symbols.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows linearly with the number of inputs.

Common Mistake

[X] Wrong: "The Moore machine processes all inputs instantly in one step."

[OK] Correct: Each input causes a state change on a clock cycle, so processing takes time proportional to input length.

Interview Connect

Understanding how hardware state machines scale with input size helps you reason about timing and performance in digital design.

Self-Check

"What if the Moore machine had nested loops inside the state transitions? How would the time complexity change?"

Practice

1. What is a key characteristic of a Moore machine in VHDL?

easy

A. Output depends only on the current state

B. Output depends on current state and input

C. Output changes asynchronously with input

D. Output depends only on input signals

Solution

1. Step 1: Understand Moore machine output behavior

   Moore machine outputs depend solely on the current state, not on inputs directly.

2. Step 2: Compare options with Moore machine definition

   Only 'Output depends only on the current state' matches Moore machine behavior.

3. Final Answer:

   Output depends only on the current state -> Option A

4. Quick Check:

   Moore output = current state only [OK]

Hint: Remember: Moore output ignores inputs directly [OK]

Common Mistakes:

• Confusing Moore with Mealy machine output
• Thinking output changes immediately with input
• Assuming output depends on input signals

2. Which VHDL process is typically used to update the current state in a Moore machine?

easy

A. Process sensitive only to output signals

B. Combinational process with sensitivity to inputs

C. Clocked process triggered on rising edge of clock

D. Asynchronous reset process without clock

Solution

1. Step 1: Identify state update mechanism in Moore machine

   The current state updates synchronously on clock edges, typically rising edge.

2. Step 2: Match process type to state update

   Only a clocked process triggered on rising clock edge updates state correctly.

3. Final Answer:

   Clocked process triggered on rising edge of clock -> Option C

4. Quick Check:

   State update = clocked process [OK]

Hint: State changes on clock edge, not input change [OK]

Common Mistakes:

• Using combinational process for state update
• Ignoring clock in state transition
• Confusing output process with state update

3. Given this VHDL snippet for a Moore machine output process:

process(current_state)
begin
  case current_state is
    when S0 => output_signal <= '0';
    when S1 => output_signal <= '1';
    when others => output_signal <= '0';
  end case;
end process;

What is the output when current_state = S1?

medium

A. '0'

B. '1'

C. 'Z' (high impedance)

D. No output assigned

Solution

1. Step 1: Analyze the case statement for current_state = S1

   When current_state is S1, output_signal is assigned '1'.

2. Step 2: Confirm output assignment

   The process explicitly sets output_signal to '1' for S1 state.

3. Final Answer:

   '1' -> Option B

4. Quick Check:

   State S1 output = '1' [OK]

Hint: Check case for current state to find output [OK]

Common Mistakes:

• Assuming output is '0' for all states
• Confusing 'others' case with S1
• Missing output assignment in process

4. Identify the error in this Moore machine state transition process:

process(clk)
begin
  if clk = '1' then
    current_state <= next_state;
  end if;
end process;

medium

A. Missing edge detection on clock signal

B. Incorrect use of non-blocking assignment

C. No reset signal included

D. Process sensitivity list is empty

Solution

1. Step 1: Check clock condition in process

   The process checks if clk = '1' but does not detect clock edge (rising_edge(clk)).

2. Step 2: Understand importance of edge detection

   Without edge detection, state updates continuously when clk is high, causing incorrect behavior.

3. Final Answer:

   Missing edge detection on clock signal -> Option A

4. Quick Check:

   Use rising_edge(clk) for proper clock sync [OK]

Hint: Use rising_edge(clk) for clocked processes [OK]

Common Mistakes:

• Using clk = '1' instead of rising_edge(clk)
• Ignoring reset signal importance
• Leaving sensitivity list empty

5. You want to design a Moore machine in VHDL that outputs '1' only after the input sequence '101' is detected. Which approach correctly implements the output logic?

hard

A. Output assigned asynchronously outside any process

B. Output assigned directly from input signals combinationally

C. Output assigned in next state logic process based on inputs

D. Output assigned in state process based only on current state

Solution

1. Step 1: Recall Moore machine output rule

   Moore machine output depends only on current state, not inputs directly.

2. Step 2: Determine correct output assignment

   Output must be assigned in a process sensitive to current state, not inputs or next state logic.

3. Final Answer:

   Output assigned in state process based only on current state -> Option D

4. Quick Check:

   Moore output = function of current state only [OK]

Hint: Assign output only from current state process [OK]

Common Mistakes:

• Assigning output from inputs directly
• Using next state logic for output
• Assigning output asynchronously