Pulse generator in Verilog - Time & Space Complexity

Time Complexity: Pulse generator

O(n)

Understanding Time Complexity

We want to understand how the time needed to generate pulses changes as we change the input size.

Specifically, how does the pulse generator's work grow when the input count or width changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module pulse_generator(
  input wire clk,
  input wire rst,
  output reg pulse
);
  reg [3:0] counter = 0;

  always @(posedge clk or posedge rst) begin
    if (rst) counter <= 0;
    else if (counter == 9) begin
      pulse <= 1;
      counter <= 0;
    end else begin
      pulse <= 0;
      counter <= counter + 1;
    end
  end
endmodule

This code creates a pulse every 10 clock cycles by counting from 0 to 9.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counter increments on every clock cycle.
• How many times: It repeats once per clock cycle continuously.

How Execution Grows With Input

Each clock cycle triggers one increment operation regardless of the counter size.

Input Size (n)	Approx. Operations
10	10 increments
100	100 increments
1000	1000 increments

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

Final Time Complexity

Time Complexity: O(n)

This means the work grows directly in proportion to the number of clock cycles or input size.

Common Mistake

[X] Wrong: "The pulse generator does all counting steps at once, so it runs in constant time."

[OK] Correct: The counter updates once per clock cycle, so the total time depends on how many cycles pass, not just one step.

Interview Connect

Understanding how hardware counters scale with input size helps you explain timing and performance in digital designs clearly and confidently.

Self-Check

"What if we changed the counter width to count to 1000 instead of 10? How would the time complexity change?"

Practice

1. What is the main purpose of a pulse generator in Verilog?

easy

A. To convert analog signals to digital

B. To store large amounts of data

C. To perform arithmetic calculations

D. To create short on/off signals in digital circuits

Solution

1. Step 1: Understand the function of a pulse generator

   A pulse generator creates short bursts of signals that switch between high and low states.

2. Step 2: Compare options with the definition

   Only To create short on/off signals in digital circuits describes creating short on/off signals, which matches the pulse generator's role.

3. Final Answer:

   To create short on/off signals in digital circuits -> Option D

4. Quick Check:

   Pulse generator = short on/off signals [OK]

Hint: Pulse generator makes quick on/off signals [OK]

Common Mistakes:

• Confusing pulse generator with memory storage
• Thinking it performs calculations
• Mixing it up with analog to digital converters

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

easy

A. reg counter[3:0];

B. wire [4:0] counter;

C. reg [3:0] counter;

D. integer counter = 4;

Solution

1. Step 1: Recall Verilog register declaration syntax

   Registers use 'reg' keyword and bit width is declared as [high:low].

2. Step 2: Check each option

   reg [3:0] counter; correctly declares a 4-bit register from bit 3 down to 0. wire [4:0] counter; uses 'wire' which is not for registers. reg counter[3:0]; uses incorrect array syntax. integer counter = 4; declares an integer, not a 4-bit register.

3. Final Answer:

   reg [3:0] counter; -> Option C

4. Quick Check:

   4-bit reg = reg [3:0] name; [OK]

Hint: Use reg [3:0] for 4-bit registers [OK]

Common Mistakes:

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

3. Given this Verilog code snippet for a pulse generator:

reg [3:0] count = 0;
reg pulse = 0;
always @(posedge clk or posedge reset) begin
  if (reset) begin
    count <= 0;
    pulse <= 0;
  end else if (count == 4) begin
    pulse <= 1;
    count <= 0;
  end else begin
    pulse <= 0;
    count <= count + 1;
  end
end

What will be the value of pulse after 5 clock cycles without reset?

medium

A. 0

B. 1

C. Undefined

D. It causes a syntax error

Solution

1. Step 1: Trace the counter and pulse values over clock cycles

   Count starts at 0. Each clock cycle increments count by 1 until it reaches 4. At count == 4, pulse is set to 1 and count resets to 0.

2. Step 2: Determine pulse value at 5th clock

   At 5th clock, count was 4, so pulse becomes 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Pulse high at count 4 = 1 [OK]

Hint: Pulse goes high when count hits 4 [OK]

Common Mistakes:

• Assuming pulse stays high after count resets
• Confusing reset behavior
• Ignoring the else conditions

4. Identify the error in this pulse generator code snippet:

reg [3:0] count;
reg pulse;
always @(posedge clk) begin
  if (reset) begin
    count = 0;
    pulse = 0;
  end else if (count == 4) begin
    pulse = 1;
    count = 0;
  end else begin
    pulse = 0;
    count = count + 1;
  end
end

medium

A. Using blocking assignments (=) inside always @(posedge clk)

B. Missing sensitivity to reset signal

C. Incorrect bit width for count register

D. pulse should be declared as wire, not reg

Solution

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

   Inside always @(posedge clk), non-blocking assignments (<=) should be used to avoid race conditions.

2. Step 2: Identify the error

   The code uses blocking assignments (=) which is incorrect for sequential logic.

3. Final Answer:

   Using blocking assignments (=) inside always @(posedge clk) -> Option A

4. Quick Check:

   Sequential logic uses <=, not = [OK]

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

Common Mistakes:

• Using = instead of <= in sequential blocks
• Not including reset in sensitivity list
• Declaring pulse as wire instead of reg

5. You want to design a pulse generator that produces a high pulse for exactly 3 clock cycles every 10 clock cycles. Which approach correctly implements this behavior?

hard

A. Use a 4-bit counter that resets at 10, set pulse high when count < 3

B. Use a 3-bit counter that resets at 3, pulse high when count == 10

C. Use a 4-bit counter that resets at 3, pulse high when count > 10

D. Use a 10-bit counter that resets at 3, pulse high when count == 3

Solution

1. Step 1: Understand the timing requirements

   The pulse should be high for 3 cycles and repeat every 10 cycles, so count cycles from 0 to 9.

2. Step 2: Choose counter and pulse logic

   A 4-bit counter can count up to 15, enough for 10 cycles. Setting pulse high when count is less than 3 gives a 3-cycle pulse.

3. Final Answer:

   Use a 4-bit counter that resets at 10, set pulse high when count < 3 -> Option A

4. Quick Check:

   Pulse high 3 cycles every 10 cycles = Use a 4-bit counter that resets at 10, set pulse high when count < 3 [OK]

Hint: Pulse high when count < pulse width, reset at total cycles [OK]

Common Mistakes:

• Using wrong counter size
• Setting pulse high at wrong count values
• Confusing reset and pulse conditions