Debouncer circuit in VHDL - Time & Space Complexity

Time Complexity: Debouncer circuit

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a debouncer circuit to process input changes as the input signal changes more often.

How does the number of input changes affect the work the debouncer does?

Scenario Under Consideration

Analyze the time complexity of the following VHDL debouncer process.

process(clk)
  variable count : integer := 0;
  variable last_input : std_logic := '0';
  constant threshold : integer := 100000;
begin
  if rising_edge(clk) then
    if input_signal = last_input then
      if count < threshold then
        count := count + 1;
      else
        debounced_output <= input_signal;
      end if;
    else
      count := 0;
    end if;
    last_input := input_signal;
  end if;
end process;

This code waits for the input signal to stay stable for a set time before changing the output, filtering out quick changes.

Identify Repeating Operations

Look at what repeats as the clock ticks:

• Primary operation: Checking input stability and incrementing a counter each clock cycle.
• How many times: Up to the threshold count for each stable input period.

How Execution Grows With Input

As the input changes more often, the counter resets more frequently, so the debouncer does less counting per change.

Number of Stable Periods	Approx. Counting Operations
10 stable periods	10 x threshold
100 stable periods	100 x threshold
1000 stable periods	1000 x threshold

Pattern observation: The work grows linearly with the number of stable input periods times the threshold count.

Final Time Complexity

Time Complexity: O(n)

This means the time to debounce grows directly with the number of stable input changes.

Common Mistake

[X] Wrong: "The debouncer always takes the same time regardless of input changes."

[OK] Correct: The debouncer resets counting on input change, so more changes mean more resets and affect total processing time.

Interview Connect

Understanding how hardware processes signals over time helps you explain real-world timing and delays, a useful skill in many tech roles.

Self-Check

"What if we changed the threshold to a variable value depending on input speed? How would the time complexity change?"

Practice

1.

What is the main purpose of a debouncer circuit in VHDL?

easy

A. To remove noise and glitches from a button input signal

B. To increase the clock speed of the circuit

C. To convert analog signals to digital

D. To store multiple input values simultaneously

Solution

1. Step 1: Understand the problem of noisy inputs

   Mechanical buttons often produce multiple rapid on/off signals (noise) when pressed.

2. Step 2: Role of debouncer circuit

   A debouncer filters this noise to produce a clean, stable signal representing a single press.

3. Final Answer:

   To remove noise and glitches from a button input signal -> Option A

4. Quick Check:

   Debouncer cleans noisy input = A [OK]

Hint: Debouncer cleans noisy button signals to one stable output [OK]

Common Mistakes:

• Thinking debouncer speeds up the clock
• Confusing debouncer with analog-to-digital converter
• Assuming debouncer stores multiple inputs

2.

Which of the following is the correct VHDL syntax to declare a signal named counter as a 4-bit unsigned vector?

easy

A. signal counter : std_logic_vector(3 downto 0);

B. signal counter : std_logic_vector(0 to 3);

C. signal counter : unsigned(3 downto 0);

D. signal counter : unsigned(4 downto 0);

Solution

1. Step 1: Understand vector size and type

   A 4-bit vector has indices from 3 downto 0, and unsigned type is used for arithmetic.

2. Step 2: Check each option

   signal counter : unsigned(3 downto 0); correctly declares an unsigned 4-bit vector from 3 downto 0.

3. Final Answer:

   signal counter : unsigned(3 downto 0); -> Option C

4. Quick Check:

   Unsigned 4-bit vector = B [OK]

Hint: Unsigned vectors use (3 downto 0) for 4 bits [OK]

Common Mistakes:

• Using std_logic_vector instead of unsigned for counters
• Incorrect vector range (4 downto 0 is 5 bits)
• Using ascending range (0 to 3) instead of descending

3.

Given the following VHDL snippet for a debouncer process, what will be the value of debounced_out after 10 clock cycles if button_in remains stable at '1'?

process(clk)
begin
  if rising_edge(clk) then
    if button_in = last_state then
      if counter < 10 then
        counter <= counter + 1;
      else
        debounced_out <= button_in;
      end if;
    else
      counter <= 0;
    end if;
    last_state <= button_in;
  end if;
end process;

medium

A. '0'

B. '1'

C. Counter value

D. Undefined (signal not assigned)

Solution

1. Step 1: Analyze counter increment and stability

   Since button_in stays '1' and equals last_state, counter increments each clock from 0 to 10 over 10 cycles (while counter < 10).

2. Step 2: Check when debounced_out updates

   debounced_out <= button_in when counter >= 10. On the 10th cycle, counter reaches 10, so debounced_out is assigned '1'.

3. Final Answer:

   '1' -> Option B

4. Quick Check:

   After 10 cycles, debounced_out = '1' [OK]

Hint: Output updates only after stable input count reached [OK]

Common Mistakes:

• Assuming output changes immediately on input change
• Confusing counter value with output signal
• Ignoring last_state comparison logic

4.

Identify the error in this VHDL debouncer process snippet:

process(clk)
begin
  if rising_edge(clk) then
    if button_in = last_state then
      counter <= counter + 1;
    else
      counter <= 0;
    end if;
    if counter = 10 then
      debounced_out <= button_in;
    end if;
    last_state <= button_in;
  end if;
end process;

medium

A. button_in is not declared as a signal

B. last_state is updated before counter, causing timing issues

C. debounced_out is assigned outside the clock edge condition

D. Counter is incremented without checking maximum value, causing overflow

Solution

1. Step 1: Check counter increment logic

   Counter increments every clock when input stable but no max limit check, so it can overflow.

2. Step 2: Understand overflow impact

   Without limiting counter, debounced_out may never update correctly or cause unexpected behavior.

3. Final Answer:

   Counter is incremented without checking maximum value, causing overflow -> Option D

4. Quick Check:

   Missing counter max check = overflow risk [OK]

Hint: Always limit counter to max debounce count to avoid overflow [OK]

Common Mistakes:

• Ignoring counter overflow possibility
• Thinking last_state update order causes error
• Assuming debounced_out assignment outside clock edge

5.

You want to design a debouncer that requires the input to be stable for 20ms. Your clock runs at 50MHz. How many clock cycles should the counter count before updating the output?

hard

A. 1,000,000 cycles

B. 1,000 cycles

C. 20,000 cycles

D. 50,000 cycles

Solution

1. Step 1: Calculate clock period

   Clock frequency = 50MHz means period = 1 / 50,000,000 = 20ns per cycle.

2. Step 2: Calculate cycles for 20ms

   20ms = 20,000,000ns. Number of cycles = 20,000,000ns / 20ns = 1,000,000 cycles.

3. Step 3: Re-check calculation

   Wait, 20ms = 0.02 seconds. Clock frequency = 50,000,000 Hz. Cycles = 0.02 * 50,000,000 = 1,000,000 cycles.

4. Final Answer:

   1,000,000 cycles -> Option A

5. Quick Check:

   Stable time * clock freq = cycles [OK]

Hint: Multiply stable time by clock frequency for cycles [OK]

Common Mistakes:

• Confusing ms with us or ns units
• Dividing instead of multiplying time and frequency
• Choosing wrong option due to quick guess