Up counter design in Verilog - Time & Space Complexity

Time Complexity: Up counter design

O(n)

Understanding Time Complexity

We want to understand how the time it takes for an up counter to run grows as the count value increases.

How does the number of steps change when the counter counts higher?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module up_counter(
  input wire clk,
  input wire reset,
  output reg [3:0] count
);

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

This code defines a 4-bit up counter that increases its value by 1 on each clock pulse, resetting to zero when reset is high.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Incrementing the count value on each clock cycle.
• How many times: Once per clock pulse, repeating continuously.

How Execution Grows With Input

Each clock pulse causes one increment operation, so the number of increments grows directly with the count value.

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

Pattern observation: The number of operations grows in a straight line as the count increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to reach a certain count grows directly with the size of that count.

Common Mistake

[X] Wrong: "The counter increments instantly for any count value, so time does not grow with count."

[OK] Correct: Each increment happens on a clock pulse, so counting higher means more pulses and more time.

Interview Connect

Understanding how counters work and how their operation time grows helps you reason about hardware timing and performance in real designs.

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 an up counter do in Verilog?

easy

A. It holds the value constant regardless of clock.

B. It decreases its value by 1 on each clock pulse.

C. It resets the value to zero on each clock pulse.

D. It increases its value by 1 on each clock pulse.

Solution

1. Step 1: Understand the function of an up counter

   An up counter increments its stored value by 1 every time the clock signal pulses.

2. Step 2: Compare options with the definition

   Only It increases its value by 1 on each clock pulse. describes increasing the value by 1 on each clock pulse, which matches the up counter behavior.

3. Final Answer:

   It increases its value by 1 on each clock pulse. -> Option D

4. Quick Check:

   Up counter = increments by 1 [OK]

Hint: Up counter always counts up by 1 each clock pulse [OK]

Common Mistakes:

• Confusing up counter with down counter
• Thinking reset happens every clock pulse
• Assuming counter holds value without change

2. Which of the following is the correct Verilog syntax to define a 4-bit up counter with synchronous reset?

easy

A. always @(negedge clk) if (reset) count = 0; else count = count + 1;

B. always @(posedge clk) if (reset) count <= 0; else count <= count + 1;

C. always @(posedge clk) if (reset) count = 0; else count = count - 1;

D. always @(posedge clk) if (reset) count <= 1; else count <= count + 1;

Solution

1. Step 1: Identify correct clock edge and reset behavior

   Up counters usually update on the positive edge of the clock and reset synchronously to zero.

2. Step 2: Check assignment operators and counting direction

   Non-blocking assignment '<=' is preferred in sequential logic. Counting up means adding 1, and reset sets count to 0.

3. Final Answer:

   always @(posedge clk) if (reset) count <= 0; else count <= count + 1; -> Option B

4. Quick Check:

   posedge + non-blocking + reset to 0 + count up = A [OK]

Hint: Use posedge clk and non-blocking <= for counters [OK]

Common Mistakes:

• Using negedge instead of posedge
• Using blocking '=' in sequential logic
• Resetting count to 1 instead of 0
• Counting down instead of up

3. What will be the output sequence of a 3-bit up counter starting from 0 after 5 clock pulses (assuming reset is inactive)?

module counter(input clk, input reset, output reg [2:0] count);
  always @(posedge clk) begin
    if (reset) count <= 0;
    else count <= count + 1;
  end
endmodule

medium

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

B. [1, 2, 3, 4, 5]

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

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

Solution

1. Step 1: Understand initial value and counting

   The counter starts at 0 after reset. On first clock pulse, count increments to 1.

2. Step 2: List values after each clock pulse

   After 1st pulse: 1, 2nd: 2, 3rd: 3, 4th: 4, 5th: 5.

3. Step 3: Consider 3-bit counter wrap-around

   Since it's a 3-bit counter, it counts from 0 to 7 and then wraps around. After 5 pulses starting from 0, the sequence is [1, 2, 3, 4, 5]. However, the question asks for the output sequence starting from 0 after 5 pulses, which includes the initial 0 and the next 4 increments: [0, 1, 2, 3, 4].

4. Final Answer:

   [0, 1, 2, 3, 4] -> Option A

5. Quick Check:

   Count starts at 0, increments each pulse = [0..4] [OK]

Hint: Count increments after clock pulse, starts from 0 [OK]

Common Mistakes:

• Including initial 0 before first pulse
• Counting 6 values instead of 5
• Confusing count start value

4. Identify the error in this Verilog code for a 4-bit up counter:

module counter(input clk, input reset, output reg [3:0] count);
  always @(posedge clk) begin
    if (reset == 1) count = 0;
    else count = count + 1;
  end
endmodule

medium

A. Output 'count' should not be declared as reg.

B. Reset condition should be 'if (reset != 1)'.

C. Using blocking assignments '=' instead of non-blocking '<=' inside always block.

D. Clock edge sensitivity should be negedge instead of posedge.

Solution

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

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

2. Step 2: Verify other parts of the code

   Reset condition and reg declaration are correct. Clock edge is correctly posedge.

3. Final Answer:

   Using blocking assignments '=' instead of non-blocking '<=' inside always block. -> Option C

4. Quick Check:

   Sequential logic uses '<=' not '=' [OK]

Hint: Use '<=' for sequential logic assignments [OK]

Common Mistakes:

• Using '=' in always @(posedge clk)
• Misunderstanding reset condition
• Thinking reg is wrong for output
• Changing clock edge unnecessarily

5. How can you modify a 4-bit up counter to count only when an enable signal is high?

module counter(input clk, input reset, output reg [3:0] count);
  always @(posedge clk) begin
    if (reset) count <= 0;
    else count <= count + 1;
  end
endmodule

hard

A. Add 'if (enable) count <= count + 1;' inside the always block after reset check.

B. Add 'if (enable) count = count + 1;' outside the always block.

C. Replace 'count <= count + 1;' with 'count <= count - 1;' when enable is high.

D. Add 'enable' to the sensitivity list of the always block.

Solution

1. Step 1: Understand how to control counting with enable

   Counting should happen only when enable is high, so add a condition inside the always block after reset.

2. Step 2: Implement enable check correctly

   Use 'if (enable) count <= count + 1;' with non-blocking assignment inside the always block.

3. Final Answer:

   Add 'if (enable) count <= count + 1;' inside the always block after reset check. -> Option A

4. Quick Check:

   Enable controls counting inside always block [OK]

Hint: Check enable inside always block after reset [OK]

Common Mistakes:

• Using blocking assignment outside always block
• Changing count direction instead of gating
• Adding enable to sensitivity list (not needed)