PWM generator in VHDL - Time & Space Complexity

Time Complexity: PWM generator

O(1)

Understanding Time Complexity

We want to understand how the time needed to run a PWM generator changes as the input size changes.

Specifically, we ask: how does the number of operations grow when the PWM period or resolution changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

process(clk)
  variable counter : integer range 0 to PERIOD := 0;
begin
  if rising_edge(clk) then
    if counter < PERIOD then
      counter := counter + 1;
    else
      counter := 0;
    end if;
    pwm_out <= '1' when counter < duty_cycle else '0';
  end if;
end process;

This code creates a PWM signal by counting clock cycles up to a set period and comparing the count to the duty cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counter increments once every clock cycle until it reaches the period.
• How many times: It repeats exactly once per clock cycle, resetting after reaching the period value.

How Execution Grows With Input

As the period value increases, the counter counts more steps before resetting, but each clock cycle still does only one increment operation.

Input Size (Period)	Approx. Operations per Cycle
10	1 increment + 1 compare
100	1 increment + 1 compare
1000	1 increment + 1 compare

Pattern observation: The number of operations per clock cycle stays the same regardless of period size.

Final Time Complexity

Time Complexity: O(1)

This means the time to process each clock cycle does not grow with the period size; it stays constant.

Common Mistake

[X] Wrong: "The time to generate PWM grows as the period gets bigger because the counter counts more."

[OK] Correct: The counter increments once per clock cycle, so each cycle's work is the same no matter the period length.

Interview Connect

Understanding how hardware counters work and their time behavior helps you explain efficient designs clearly and confidently.

Self-Check

"What if we changed the PWM generator to use a nested loop to count multiple periods before resetting? How would the time complexity change?"

Practice

1. What is the main purpose of a PWM generator in VHDL?

easy

A. To create a signal that switches on and off quickly to control power

B. To store data in memory

C. To perform arithmetic calculations

D. To generate random numbers

Solution

1. Step 1: Understand PWM function

   PWM (Pulse Width Modulation) generates a signal that switches on and off rapidly.

2. Step 2: Identify purpose in power control

   This switching controls the power delivered to devices by changing the duty cycle.

3. Final Answer:

   To create a signal that switches on and off quickly to control power -> Option A

4. Quick Check:

   PWM controls power by switching signal [OK]

Hint: PWM controls power by fast on/off switching [OK]

Common Mistakes:

• Confusing PWM with memory storage
• Thinking PWM does arithmetic
• Assuming PWM generates random signals

2. Which VHDL statement correctly compares a counter to a duty cycle to generate a PWM output?

easy

A. pwm_out := '1' if counter > duty_cycle else '0';

B. pwm_out = '1' when counter = duty_cycle else '0';

C. pwm_out <= '1' when counter < duty_cycle else '0';

D. pwm_out <= '1' if counter = duty_cycle else '0';

Solution

1. Step 1: Identify correct VHDL assignment syntax

   In VHDL, signal assignment uses '<=' and conditional assignment uses 'when ... else'.

2. Step 2: Match correct comparison and syntax

   pwm_out <= '1' when counter < duty_cycle else '0'; uses '<=' and 'when ... else' with correct comparison 'counter < duty_cycle'.

3. Final Answer:

   pwm_out <= '1' when counter < duty_cycle else '0'; -> Option C

4. Quick Check:

   VHDL signal conditional assignment = pwm_out <= '1' when counter < duty_cycle else '0'; [OK]

Hint: Use '<=' with 'when ... else' for conditional signal assignment [OK]

Common Mistakes:

• Using ':=' instead of '<=' for signals
• Using 'if' instead of 'when' in signal assignment
• Using '=' for assignment instead of comparison

3. Given this VHDL snippet for PWM output:

process(clk)
begin
  if rising_edge(clk) then
    if counter < duty_cycle then
      pwm_out <= '1';
    else
      pwm_out <= '0';
    end if;
    if counter = max_count then
      counter <= 0;
    else
      counter <= counter + 1;
    end if;
  end if;
end process;

What is the value of pwm_out when counter is 3 and duty_cycle is 5?

medium

A. Undefined

B. '1'

C. '0'

D. Error

Solution

1. Step 1: Compare counter and duty_cycle values

   Counter is 3, duty_cycle is 5, so 3 < 5 is true.

2. Step 2: Determine pwm_out value based on condition

   Since counter < duty_cycle, pwm_out is assigned '1'.

3. Final Answer:

   '1' -> Option B

4. Quick Check:

   3 < 5 means pwm_out = '1' [OK]

Hint: If counter < duty_cycle, pwm_out is '1' [OK]

Common Mistakes:

• Confusing '<' with '>' in condition
• Assuming pwm_out is '0' when counter < duty_cycle
• Ignoring the process clock edge condition

4. Identify the error in this VHDL PWM process:

process(clk)
begin
  if clk'event and clk = '1' then
    if counter <= duty_cycle then
      pwm_out <= '1';
    else
      pwm_out <= '0';
    end if;
    if counter = max_count then
      counter <= 0;
    else
      counter <= counter + 1;
    end if;
  end if;
end process;

medium

A. Using 'clk'event and clk = '1' instead of rising_edge(clk)

B. Using '<=' in 'if counter <= duty_cycle' instead of '<'

C. Missing reset condition for counter

D. No error, code is correct

Solution

1. Step 1: Check clock edge detection method

   Using 'clk'event and clk = '1' is legal but less safe than rising_edge(clk).

2. Step 2: Identify best practice for clock edge

   rising_edge(clk) is preferred for clarity and synthesis compatibility.

3. Final Answer:

   Using 'clk'event and clk = '1' instead of rising_edge(clk) -> Option A

4. Quick Check:

   Use rising_edge(clk) for clock detection [OK]

Hint: Use rising_edge(clk) for clock detection [OK]

Common Mistakes:

• Using 'clk'event and clk = '1' which is outdated
• Confusing '<=' with '<' in duty cycle comparison
• Ignoring reset logic necessity

5. You want to design a PWM generator in VHDL that supports variable frequency and duty cycle. Which approach correctly allows changing frequency and duty cycle dynamically?

hard

A. Use asynchronous signals to change frequency and duty cycle without counters

B. Use a fixed counter for frequency and hard-coded duty cycle value

C. Use a single counter and fix duty cycle at compile time

D. Use two counters: one for period (frequency) and one for duty cycle comparison, both updated dynamically

Solution

1. Step 1: Understand dynamic frequency and duty cycle needs

   Changing frequency means changing the PWM period, so a period counter is needed.

2. Step 2: Use counters for period and duty cycle comparison

   One counter tracks the period length, another compares to duty cycle to set output.

3. Step 3: Allow dynamic updates

   Both counters and duty cycle values must be variable to change PWM parameters on the fly.

4. Final Answer:

   Use two counters: one for period (frequency) and one for duty cycle comparison, both updated dynamically -> Option D

5. Quick Check:

   Two counters enable dynamic frequency and duty cycle [OK]

Hint: Use separate counters for period and duty cycle [OK]

Common Mistakes:

• Fixing duty cycle or frequency at compile time
• Using asynchronous signals causing glitches
• Trying to change frequency without a period counter