Modulo-N counter in VHDL - Time & Space Complexity

Time Complexity: Modulo-N counter

O(N)

Understanding Time Complexity

We want to understand how the time it takes for a modulo-N counter to update changes as N grows.

Specifically, how does the number of steps to count up to N affect the execution time?

Scenario Under Consideration

Analyze the time complexity of the following VHDL code snippet.

process(clk)
  begin
    if rising_edge(clk) then
      if count = N-1 then
        count <= 0;
      else
        count <= count + 1;
      end if;
    end if;
  end process;

This code increments a counter on each clock cycle and resets it to zero after reaching N-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Incrementing the counter by 1 each clock cycle.
• How many times: Up to N times before resetting.

How Execution Grows With Input

Each count step takes one clock cycle, so the total steps grow directly with N.

Input Size (N)	Approx. Operations (clock cycles)
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The number of steps grows linearly as N increases.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete a full count grows directly in proportion to N.

Common Mistake

[X] Wrong: "The counter updates instantly regardless of N."

[OK] Correct: Each increment happens one step at a time per clock cycle, so larger N means more steps.

Interview Connect

Understanding how counters scale helps you reason about timing and performance in hardware design.

Self-Check

"What if we changed the counter to increment by 2 each clock cycle? How would the time complexity change?"

Practice

1. What does a Modulo-N counter do in VHDL?

easy

A. Counts from 0 up to N-1 and then restarts at 0

B. Counts from N down to 0 and stops

C. Counts only even numbers up to N

D. Counts from 1 to N without restarting

Solution

1. Step 1: Understand the counting range

   A Modulo-N counter counts starting at 0 and goes up to N-1.

2. Step 2: Recognize the restart behavior

   After reaching N-1, it restarts counting from 0 again.

3. Final Answer:

   Counts from 0 up to N-1 and then restarts at 0 -> Option A

4. Quick Check:

   Modulo-N counter = Counts 0 to N-1 then resets [OK]

Hint: Remember: Modulo means count resets after N-1 [OK]

Common Mistakes:

• Thinking it counts down instead of up
• Assuming it counts from 1 instead of 0
• Believing it stops after reaching N-1

2. Which of the following is the correct VHDL syntax to declare a signal for a 4-bit Modulo-16 counter?

easy

A. signal count : std_logic_vector(15 downto 0);

B. signal count : integer range 1 to 16;

C. signal count : integer range 0 to 15;

D. signal count : std_logic_vector(4 downto 0);

Solution

1. Step 1: Identify the correct data type and range

   For a Modulo-16 counter, integer range 0 to 15 covers all counts from 0 to 15.

2. Step 2: Check signal declaration syntax

   "signal count : integer range 0 to 15;" is valid VHDL syntax for this purpose.

3. Final Answer:

   signal count : integer range 0 to 15; -> Option C

4. Quick Check:

   Integer 0 to 15 fits 4-bit Modulo-16 counter [OK]

Hint: Use integer range 0 to N-1 for Modulo-N counters [OK]

Common Mistakes:

• Using std_logic_vector with wrong bit width
• Setting range from 1 to N instead of 0 to N-1
• Confusing bit width with integer range

3. Given the following VHDL process for a Modulo-4 counter, what is the value of count after 5 rising clock edges (assuming reset is inactive)?

process(clk, reset)
begin
  if reset = '1' then
    count <= 0;
  elsif rising_edge(clk) then
    if count = 3 then
      count <= 0;
    else
      count <= count + 1;
    end if;
  end if;
end process;

medium

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Trace count values on each clock edge

   Starting at 0, count increments each clock: 0->1->2->3->0->1 after 5 edges.

2. Step 2: Identify count after 5 edges

   After 5 rising edges (1st:1, 2nd:2, 3rd:3, 4th:0, 5th:1), count is 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Modulo-4 resets at 3, so after 5 edges count = 1 [OK]

Hint: Count resets after reaching N-1, track each clock edge [OK]

Common Mistakes:

• Counting from 1 instead of 0
• Forgetting the reset at count = 3
• Miscounting the number of clock edges

4. Identify the error in this VHDL code snippet for a Modulo-8 counter:

process(clk, reset)
begin
  if reset = '1' then
    count <= 0;
  elsif rising_edge(clk) then
    if count = 8 then
      count <= 0;
    else
      count <= count + 1;
    end if;
  end if;
end process;

medium

A. The reset condition should check for '0' instead of '1'

B. The count signal is not declared as std_logic_vector

C. The process is missing a sensitivity list

D. The count comparison should be 'count = 7' instead of 'count = 8'

Solution

1. Step 1: Check the counting limit for Modulo-8

   Modulo-8 counts from 0 to 7, so the reset should happen when count = 7.

2. Step 2: Identify the incorrect comparison

   The code compares count = 8, which is outside the valid range, causing incorrect behavior.

3. Final Answer:

   The count comparison should be 'count = 7' instead of 'count = 8' -> Option D

4. Quick Check:

   Modulo-8 max count = 7, not 8 [OK]

Hint: Check if count comparison matches N-1 for Modulo-N [OK]

Common Mistakes:

• Using count = N instead of count = N-1
• Confusing reset signal polarity
• Ignoring sensitivity list correctness

5. You want to design a Modulo-10 counter in VHDL that counts from 0 to 9 and then resets. Which of the following code snippets correctly implements this behavior inside a clocked process?

hard

A. if reset = '0' then
count <= 0;
elsif rising_edge(clk) then
if count = 10 then
count <= 0;
else
count <= count + 1;
end if;

B. if reset = '1' then
count <= 0;
elsif rising_edge(clk) then
if count = 9 then
count <= 0;
else
count <= count + 1;
end if;

C. if reset = '1' then
count <= 1;
elsif rising_edge(clk) then
if count = 10 then
count <= 1;
else
count <= count + 1;
end if;

D. if reset = '1' then
count <= 0;
elsif rising_edge(clk) then
if count = 10 then
count <= 1;
else
count <= count + 1;
end if;

Solution

1. Step 1: Check reset condition and initial count

   Reset should set count to 0, which is done correctly only in if reset = '1' then count <= 0; elsif rising_edge(clk) then if count = 9 then count <= 0; else count <= count + 1; end if;.

2. Step 2: Verify counting and reset limit

   Counting should reset when count = 9 (for Modulo-10), and then count restarts at 0, correctly shown in if reset = '1' then count <= 0; elsif rising_edge(clk) then if count = 9 then count <= 0; else count <= count + 1; end if;.

3. Final Answer:

   resets count at 9 and initializes at 0 -> Option B

4. Quick Check:

   Modulo-10 counts 0 to 9, reset at 9 [OK]

Hint: Reset at N-1 and start count at 0 for Modulo-N [OK]

Common Mistakes:

• Resetting count to 1 instead of 0
• Using count = N instead of count = N-1 for reset
• Incorrect reset signal polarity