Modulo-N counter in Verilog - 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 run changes as the size of N changes.

Specifically, how does the number of steps grow when the counter counts up to N?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module modulo_n_counter #(
  parameter int N = 16
) (
  input logic clk,
  input logic reset,
  output logic [$clog2(N)-1:0] count
);

always_ff @(posedge clk or posedge reset) begin
  if (reset) count <= 0;
  else if (count == N-1) count <= 0;
  else count <= count + 1;
end
endmodule

This code counts from 0 up to N-1, then resets back to 0, repeating continuously.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counter increments by 1 on each clock cycle.
• How many times: It repeats counting up to N times before resetting.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (N)	Approx. Operations (increments)
10	10 increments before reset
100	100 increments before reset
1000	1000 increments before reset

Pattern observation: The number of increments grows directly with N. If N doubles, the count steps double too.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete one full count grows linearly as N gets bigger.

Common Mistake

[X] Wrong: "The counter runs in constant time because it just increments once per clock."

[OK] Correct: While each increment is quick, the total time to count all the way to N depends on N itself, so it grows as N grows.

Interview Connect

Understanding how counters scale helps you reason about timing and performance in hardware design, a useful skill in many real-world projects.

Self-Check

"What if we changed the counter to increment by 2 each time instead of 1? How would the time complexity change?"

Practice

1.

What does a modulo-N counter do in Verilog?

easy

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

B. Counts only once and stops

C. Counts from N down to 0 and stops

D. Counts randomly between 0 and N

Solution

1. Step 1: Understand the counting range

   A modulo-N counter counts numbers starting from 0 up to N-1.

2. Step 2: Recognize the reset behavior

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

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: Modulo-N means count up to N-1 then restart at zero [OK]

Common Mistakes:

• Thinking it counts down instead of up
• Assuming it stops after one cycle
• Confusing modulo-N with random counting

2.

Which of the following is the correct Verilog syntax to declare a 4-bit register count for a modulo-16 counter?

easy

A. wire [3:0] count;

B. reg [4:0] count;

C. reg [3:0] count;

D. integer count;

Solution

1. Step 1: Determine bit width for modulo-16

   Modulo-16 means counting 0 to 15, which fits in 4 bits (2^4=16).

2. Step 2: Choose correct register declaration

   Use reg [3:0] count; to declare a 4-bit register named count.

3. Final Answer:

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

4. Quick Check:

   4 bits needed for 16 states [OK]

Hint: 4 bits hold 0 to 15, so use reg [3:0] [OK]

Common Mistakes:

• Using wire instead of reg for a counter
• Using 5 bits instead of 4 bits
• Using integer which is not fixed bit width

3.

What is the output sequence of count in this Verilog code snippet for a modulo-4 counter after 6 clock cycles (assuming reset is low)?

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

medium

A. [0, 1, 2, 0, 1, 2]

B. [1, 2, 3, 0, 1, 2]

C. [0, 1, 2, 3, 4, 5]

D. [0, 1, 2, 3, 0, 1]

Solution

1. Step 1: Trace count values per clock

   Starting at 0, count increments each clock until 3, then resets to 0:
   Cycle 1: 0
   Cycle 2: 1
   Cycle 3: 2
   Cycle 4: 3
   Cycle 5: 0 (reset)
   Cycle 6: 1

2. Step 2: Confirm sequence length and values

   Sequence after 6 cycles is [0, 1, 2, 3, 0, 1].

3. Final Answer:

   [0, 1, 2, 3, 0, 1] -> Option D

4. Quick Check:

   Modulo-4 cycles 0 to 3 then repeats [OK]

Hint: Count resets after reaching N-1, so watch the reset step [OK]

Common Mistakes:

• Counting beyond 3 (like 4 or 5)
• Starting count at 1 instead of 0
• Forgetting reset condition when count == 3

4.

Identify the error in this Verilog code for a modulo-8 counter:

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

medium

A. The register width is too large for modulo-8

B. The condition should be 'count == 7' instead of 'count == 8'

C. Reset should be in negedge, not posedge

D. The count variable should be declared as wire, not reg

Solution

1. Step 1: Check counting range for modulo-8

   Modulo-8 counts from 0 to 7, so max count is 7, not 8.

2. Step 2: Identify incorrect condition

   The code checks if count == 8, which is invalid since count cannot reach 8 with 3 bits.

3. Final Answer:

   The condition should be 'count == 7' instead of 'count == 8' -> Option B

4. Quick Check:

   Max count for 3 bits is 7, not 8 [OK]

Hint: Max count = 2^bits - 1, so check condition against 7 for 3 bits [OK]

Common Mistakes:

• Using count == 8 instead of count == 7
• Declaring count as wire instead of reg
• Misunderstanding reset edge sensitivity

5.

You want to design a modulo-10 counter in Verilog that counts from 0 to 9 and then resets to 0. Which code snippet correctly implements this behavior?

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

hard

A. This code is correct because 4 bits can represent 0 to 15, and count resets at 9.

B. This code is incorrect because 4 bits cannot represent 0 to 9.

C. This code is incorrect because count should reset at 10, not 9.

D. This code is incorrect because count should be declared as wire.

Solution

1. Step 1: Check bit width for modulo-10

   4 bits can represent values from 0 to 15, which covers 0 to 9 easily.

2. Step 2: Verify reset condition

   The code resets count to 0 when count reaches 9, correctly implementing modulo-10 behavior.

3. Final Answer:

   This code is correct because 4 bits can represent 0 to 15, and count resets at 9. -> Option A

4. Quick Check:

   4 bits cover 0-9; reset at 9 is correct [OK]

Hint: Use enough bits for max count; reset at N-1 for modulo-N [OK]

Common Mistakes:

• Thinking 4 bits can't hold 0 to 9
• Resetting count at 10 instead of 9
• Declaring count as wire instead of reg