Debouncer circuit design in Verilog - Time & Space Complexity

Time Complexity: Debouncer circuit design

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 size or clock cycles increase.

How does the number of operations grow when the input signal changes over time?

Scenario Under Consideration

Analyze the time complexity of the following Verilog debouncer code snippet.

module debouncer(
  input clk,
  input noisy,
  output reg clean
);
  reg [15:0] count = 0;
  reg state = 0;

  always @(posedge clk) begin
    if (noisy == state) count <= 0;
    else if (count == 16'hFFFF) state <= noisy;
    else count <= count + 1;
    clean <= state;
  end
endmodule
    

This code waits for the input signal to be stable for a certain number of clock cycles before changing the output.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The always block runs every clock cycle, checking and updating counters and state.
• How many times: It executes once per clock cycle, repeating continuously as the clock runs.

How Execution Grows With Input

The circuit checks the input signal every clock cycle and counts how long it stays stable before updating the output.

Input Size (clock cycles)	Approx. Operations
10	10 checks and updates
100	100 checks and updates
1000	1000 checks and updates

Pattern observation: The number of operations grows directly with the number of clock cycles, increasing steadily.

Final Time Complexity

Time Complexity: O(n)

This means the work done grows linearly with the number of clock cycles the circuit runs.

Common Mistake

[X] Wrong: "The debouncer only runs when the input changes, so it does less work."

[OK] Correct: The always block runs every clock cycle regardless of input changes, so it always performs its checks and updates.

Interview Connect

Understanding how hardware modules like debouncers scale with input time helps you reason about efficient circuit design and timing behavior in real projects.

Self-Check

"What if we changed the counter size to 8 bits instead of 16 bits? How would the time complexity change?"

Practice

1.

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

easy

A. To convert analog signals to digital

B. To increase the clock speed of the circuit

C. To generate random signals for testing

D. To clean noisy button signals and produce a stable output

Solution

1. Step 1: Understand the problem of noisy signals

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

2. Step 2: Role of debouncer

   A debouncer waits for the input to be stable for some time before changing the output, thus cleaning the noise.

3. Final Answer:

   To clean noisy button signals and produce a stable output -> Option D

4. Quick Check:

   Debouncer = Clean noisy signals [OK]

Hint: Debouncer = stable output from noisy input [OK]

Common Mistakes:

• Thinking debouncer speeds up the clock
• Confusing debouncer with analog to digital converter
• Assuming debouncer generates signals

2.

Which of the following is the correct way to declare a 16-bit counter register in Verilog?

?

easy

A. wire [16:0] counter;

B. reg [15:0] counter;

C. reg counter[15:0];

D. integer counter[16];

Solution

1. Step 1: Understand Verilog register declaration

   Registers use 'reg' keyword and bit width is declared as [MSB:LSB].

2. Step 2: Check each option

   reg [15:0] counter; correctly declares a 16-bit register from bit 15 down to 0.

3. Final Answer:

   reg [15:0] counter; -> Option B

4. Quick Check:

   16-bit reg = reg [15:0] name; [OK]

Hint: Use reg [15:0] for 16-bit registers [OK]

Common Mistakes:

• Using wire instead of reg for counters
• Incorrect bit range syntax
• Declaring arrays instead of bit vectors

3.

Given this Verilog snippet for a debouncer counter:

always @(posedge clk) begin
  if (button == last_button) begin
    if (counter < 3) counter <= counter + 1;
  end else counter <= 0;
  last_button <= button;
end

What is the value of counter after 5 clock cycles if button stays stable at 1?

medium

A. 5

B. 0

C. 3

D. 1

Solution

1. Step 1: Analyze counter increment condition

   Counter increments only if button equals last_button and counter is less than 3.

2. Step 2: Trace counter over 5 cycles

   Initially counter=0. It increments each cycle until it reaches 3, then stops incrementing.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Counter maxes at 3 despite 5 cycles [OK]

Hint: Counter stops incrementing at max value 3 [OK]

Common Mistakes:

• Assuming counter increments beyond 3
• Ignoring last_button update
• Resetting counter incorrectly

4.

Identify the error in this debouncer code snippet:

reg [3:0] counter;
reg last_button;
always @(posedge clk) begin
  if (button == last_button) begin
    counter = counter + 1;
  end else begin
    counter = 0;
  end
  last_button = button;
end

medium

A. Using blocking assignments (=) inside always block for sequential logic

B. Missing sensitivity list for asynchronous reset

C. Counter width too small for debounce time

D. No initial value for last_button

Solution

1. Step 1: Check assignment types in sequential always block

   Sequential logic should use non-blocking assignments (<=) to avoid race conditions.

2. Step 2: Identify the error

   The code uses blocking assignments (=) inside a clocked always block, which is incorrect.

3. Final Answer:

   Using blocking assignments (=) inside always block for sequential logic -> Option A

4. Quick Check:

   Use <= for sequential logic assignments [OK]

Hint: Use <= in clocked always blocks [OK]

Common Mistakes:

• Using = instead of <=
• Ignoring sensitivity list importance
• Assuming initial values fix assignment errors

5.

You want to design a debouncer that waits for 10ms of stable input before changing output. The clock frequency is 1MHz. How many bits should the counter have at minimum?

hard

A. 14 bits

B. 10 bits

C. 20 bits

D. 8 bits

Solution

1. Step 1: Calculate required count for 10ms at 1MHz clock

   10ms = 0.01 seconds. Clock period = 1us (1/1MHz). Number of counts = 0.01 / 0.000001 = 10,000 counts.

2. Step 2: Find minimum bits to count 10,000

   2^13 = 8192 (too small), 2^14 = 16384 (enough). So minimum 14 bits needed.

3. Final Answer:

   14 bits -> Option A

4. Quick Check:

   10,000 < 2^14 = 16384 [OK]

Hint: Count = time * clock freq; bits = ceil(log2(count)) [OK]

Common Mistakes:

• Using clock frequency as count directly
• Choosing too few bits to cover count
• Confusing ms and us units