Vending machine FSM example in VHDL - Time & Space Complexity

Time Complexity: Vending machine FSM example

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a vending machine FSM to process inputs changes as the number of inputs grows.

Specifically, how does the machine's operation time grow when handling more input coins or selections?

Scenario Under Consideration

Analyze the time complexity of the following VHDL FSM code snippet.

process(clk)
begin
  if rising_edge(clk) then
    case state is
      when IDLE =>
        if coin_inserted = '1' then
          state <= CHECK_AMOUNT;
        end if;
      when CHECK_AMOUNT =>
        if amount >= price then
          state <= DISPENSE;
        else
          state <= IDLE;
        end if;
      when DISPENSE =>
        dispense_item <= '1';
        state <= IDLE;
      when others =>
        state <= IDLE;
    end case;
  end if;
end process;

This code models a vending machine's states reacting to coin input and dispensing items.

Identify Repeating Operations

The FSM runs inside a clocked process, repeating every clock cycle.

• Primary operation: The state machine checks and updates its state each clock cycle.
• How many times: Once per clock cycle, indefinitely as inputs arrive.

How Execution Grows With Input

The FSM processes one input per clock cycle, so the total steps grow directly with the number of inputs.

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

Pattern observation: The number of operations grows linearly with the number of inputs.

Final Time Complexity

Time Complexity: O(n)

This means the time to process inputs grows in direct proportion to how many inputs the machine receives.

Common Mistake

[X] Wrong: "The FSM processes all inputs instantly, so time does not grow with input size."

[OK] Correct: The FSM updates once per clock cycle, so each input takes time to process sequentially, not all at once.

Interview Connect

Understanding how FSMs handle inputs over time helps you explain hardware behavior clearly and shows you can reason about system performance.

Self-Check

"What if the FSM had nested loops inside states to check multiple items per input? How would the time complexity change?"

Practice

1. What is the main purpose of a vending machine FSM in VHDL?

easy

A. To perform complex mathematical calculations

B. To control the sequence of accepting coins and dispensing items

C. To store large amounts of data permanently

D. To display graphics on a screen

Solution

1. Step 1: Understand FSM role in vending machine

   The FSM (Finite State Machine) controls the order of operations like accepting coins and dispensing items.

2. Step 2: Compare options to FSM purpose

   Only To control the sequence of accepting coins and dispensing items describes controlling the sequence of actions, which matches FSM's role.

3. Final Answer:

   To control the sequence of accepting coins and dispensing items -> Option B

4. Quick Check:

   FSM controls sequence = To control the sequence of accepting coins and dispensing items [OK]

Hint: FSM controls steps in process flow, not data storage or math [OK]

Common Mistakes:

• Confusing FSM with memory storage
• Thinking FSM does math or graphics
• Ignoring the sequence control aspect

2. Which VHDL statement correctly declares a state type for a vending machine FSM?

easy

A. signal state : integer := 0;

B. variable state : std_logic_vector(1 downto 0);

C. type state_type is (IDLE, COIN_INSERTED, DISPENSE);

D. constant state : boolean := true;

Solution

1. Step 1: Identify correct state type declaration

   States in FSM are usually declared as an enumerated type listing all states.

2. Step 2: Check options for enumerated type

   type state_type is (IDLE, COIN_INSERTED, DISPENSE); declares a type with named states, which is correct for FSM states.

3. Final Answer:

   type state_type is (IDLE, COIN_INSERTED, DISPENSE); -> Option C

4. Quick Check:

   State type enum = type state_type is (IDLE, COIN_INSERTED, DISPENSE); [OK]

Hint: FSM states use enumerated types, not integers or booleans [OK]

Common Mistakes:

• Using integer or boolean instead of enumerated type
• Confusing signal and type declarations
• Using variable instead of type for states

3. Given this VHDL snippet inside a vending machine FSM process:

case state is
  when IDLE =>
    if coin = '1' then
      next_state <= COIN_INSERTED;
    else
      next_state <= IDLE;
    end if;
  when COIN_INSERTED =>
    next_state <= DISPENSE;
  when DISPENSE =>
    next_state <= IDLE;
end case;

What will be the next state if current state is IDLE and coin = '0'?

medium

A. COIN_INSERTED

B. Undefined

C. DISPENSE

D. IDLE

Solution

1. Step 1: Analyze the IDLE state condition

   If coin = '1', next_state is COIN_INSERTED; else next_state remains IDLE.

2. Step 2: Apply coin = '0' condition

   Since coin = '0', the else branch applies, so next_state stays IDLE.

3. Final Answer:

   IDLE -> Option D

4. Quick Check:

   coin '0' in IDLE = next_state IDLE [OK]

Hint: Check coin input condition in IDLE state carefully [OK]

Common Mistakes:

• Assuming coin '0' moves to COIN_INSERTED
• Confusing next_state with current state
• Ignoring else branch in if statement

4. Identify the error in this VHDL FSM process snippet for a vending machine:

process(clk)
begin
  if rising_edge(clk) then
    case state is
      when IDLE =>
        if coin = '1' then
          state <= COIN_INSERTED;
        end if;
      when COIN_INSERTED =>
        state <= DISPENSE;
      when DISPENSE =>
        state <= IDLE;
    end case;
  end if;
end process;

medium

A. No reset condition for state initialization

B. State variable should be a signal, not variable

C. No default case in case statement

D. Missing else branch in IDLE state causes latch

Solution

1. Step 1: Check for reset condition in FSM process

   FSM processes usually include a reset to initialize the state at start.

2. Step 2: Identify missing reset

   This code lacks any reset signal or condition to set initial state, which is an error.

3. Final Answer:

   No reset condition for state initialization -> Option A

4. Quick Check:

   Missing reset = No reset condition for state initialization [OK]

Hint: Always include reset to set initial FSM state [OK]

Common Mistakes:

• Thinking else branch missing causes latch in synchronous process
• Confusing signal and variable usage
• Ignoring importance of reset in FSM

5. You want to extend a vending machine FSM to accept two coin types: 5 cents and 10 cents. The FSM should dispense an item when total inserted coins reach 15 cents or more. Which approach correctly updates the FSM to handle this?

hard

A. Add a coin_value input and a coin_total signal; update coin_total on each coin and transition to DISPENSE when coin_total >= 15

B. Use two separate FSMs for 5 and 10 cent coins and combine outputs

C. Ignore coin values and dispense after 3 coins inserted

D. Add a timer to dispense item after fixed time regardless of coins

Solution

1. Step 1: Understand requirement to track coin values

   We must track total coin value inserted, not just count coins.

2. Step 2: Choose approach to accumulate coin values

   Add a coin_value input and a coin_total signal; update coin_total on each coin and transition to DISPENSE when coin_total >= 15 uses a coin_value input and coin_total signal to sum coins and trigger dispense when total >= 15, which fits requirement.

3. Final Answer:

   Add a coin_value input and a coin_total signal; update coin_total on each coin and transition to DISPENSE when coin_total >= 15 -> Option A

4. Quick Check:

   Track coin values and total = Add coin_value and coin_total, dispense at 15+ [OK]

Hint: Sum coin values, dispense when total reaches target [OK]

Common Mistakes:

• Using separate FSMs instead of one with coin total
• Counting coins instead of summing values
• Dispensing by time, not coin total