Up-down counter with direction control in Verilog - Time & Space Complexity

Time Complexity: Up-down counter with direction control

O(n)

Understanding Time Complexity

We want to understand how the time needed to run an up-down counter changes as the input size changes.

Specifically, how does the counting process scale when we control the direction?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

module up_down_counter(
  input wire clk,
  input wire rst,
  input wire dir, // 1 for up, 0 for down
  output reg [3:0] count
);
  always @(posedge clk or posedge rst) begin
    if (rst) count <= 0;
    else if (dir) count <= count + 1;
    else count <= count - 1;
  end
endmodule

This code counts up or down by 1 on each clock pulse depending on the direction signal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counting update happens once every clock cycle.
• How many times: It repeats for each clock pulse, which depends on how long the system runs.

How Execution Grows With Input

Each clock cycle triggers one count update, so the number of operations grows directly with the number of clock cycles.

Input Size (n)	Approx. Operations
10	10 count updates
100	100 count updates
1000	1000 count updates

Pattern observation: The operations grow linearly as the input size (number of clock cycles) increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the counter grows directly in proportion to how many times it counts.

Common Mistake

[X] Wrong: "The counter updates all bits at once, so it takes constant time regardless of count size."

[OK] Correct: While the hardware updates all bits simultaneously, the number of updates depends on the number of clock cycles, which grows with input time, not the bit width.

Interview Connect

Understanding how simple counters scale helps you reason about timing and performance in hardware design, a key skill for many projects.

Self-Check

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

Practice

1. What does the direction signal control in an up-down counter in Verilog?

easy

A. The reset state of the counter

B. The speed of the clock signal

C. Whether the counter counts up or down

D. The width of the counter output

Solution

1. Step 1: Understand the role of the direction signal

   The direction signal determines if the counter increments or decrements its value.

2. Step 2: Relate direction to counting behavior

   If direction is high, the counter counts up; if low, it counts down.

3. Final Answer:

   Whether the counter counts up or down -> Option C

4. Quick Check:

   Direction controls count direction = C [OK]

Hint: Direction signal decides count up or down [OK]

Common Mistakes:

• Confusing direction with clock speed
• Thinking reset controls counting direction
• Assuming direction changes output width

2. Which of the following is the correct Verilog syntax to declare a 4-bit up-down counter with direction input?

easy

A. wire [4:0] count; input direction; always @(negedge clk) begin if(reset) count = 0; else if(direction) count = count + 1; else count = count - 1; end

B. reg [3:0] count; input dir; always @(posedge clk) begin if(reset) count <= 0; else if(dir) count <= count + 1; else count <= count - 1; end

C. reg [3:0] count; input dir; always @(posedge clk) begin if(reset) count = 0; else if(dir) count = count + 1; else count = count - 1; end

D. reg [3:0] count; input dir; always @(posedge clk) begin if(reset) count <= 0; else if(dir) count <= count - 1; else count <= count + 1; end

Solution

1. Step 1: Check variable declarations and types

   Count should be a 4-bit reg, direction input is 'dir'.

2. Step 2: Verify always block and assignments

   Use posedge clk, non-blocking assignments '<=' for sequential logic, reset sets count to 0, dir controls increment or decrement.

3. Final Answer:

   Correct syntax with reg, posedge clk, non-blocking assignments, and direction control -> Option B

4. Quick Check:

   Proper reg and non-blocking assignments = A [OK]

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

Common Mistakes:

• Using wire instead of reg for count
• Using blocking '=' in sequential always block
• Incorrect clock edge sensitivity
• Reversing increment and decrement logic

3. Given this Verilog code snippet for a 3-bit up-down counter with direction control:

reg [2:0] count = 3'b000;
always @(posedge clk) begin
  if(reset) count <= 3'b000;
  else if(dir) count <= count + 1;
  else count <= count - 1;
end

If reset=0, dir=1, and the clock pulses 5 times starting from 0, what is the value of count after 5 pulses?

medium

A. 3'b101

B. 3'b111

C. 3'b100

D. 3'b110

Solution

1. Step 1: Understand initial conditions and direction

   Count starts at 0, reset is inactive, dir=1 means count up.

2. Step 2: Calculate count after 5 increments

   Counting up 5 times from 0: 0->1->2->3->4->5, which is 3'b101 in binary.

3. Final Answer:

   3'b101 -> Option A

4. Quick Check:

   0 + 5 increments = 5 (binary 101) [OK]

Hint: Count up adds 1 each clock pulse [OK]

Common Mistakes:

• Forgetting initial count is zero
• Confusing binary values
• Counting down instead of up

4. Identify the error in this Verilog code for an up-down counter:

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

medium

A. Using blocking assignment '=' for reset inside always block

B. Missing sensitivity to negedge clk

C. Count should be declared as wire, not reg

D. Direction signal 'dir' is not declared

Solution

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

   Sequential logic requires non-blocking assignments '<=' for all assignments inside always @(posedge clk).

2. Step 2: Identify inconsistent assignment usage

   Reset uses blocking '=' which can cause simulation mismatches; it should use '<=' like other assignments.

3. Final Answer:

   Using blocking assignment '=' for reset inside always block -> Option A

4. Quick Check:

   Use '<=' for all sequential assignments [OK]

Hint: Use non-blocking '<=' in sequential always blocks [OK]

Common Mistakes:

• Mixing blocking and non-blocking assignments
• Ignoring declaration of signals
• Wrong sensitivity list for clock

5. You want to design a 4-bit up-down counter with direction control and synchronous reset in Verilog. The counter should wrap around when it reaches max or min values (i.e., counting up from 15 goes to 0, counting down from 0 goes to 15). Which code snippet correctly implements this behavior?

hard

A. always @(posedge clk) begin
if(reset) count <= 0;
else if(dir) count <= count + 1;
else count <= count - 1;
end

B. always @(posedge clk) begin
if(reset) count <= 0;
else if(dir) count <= (count == 4'b0000) ? 4'b1111 : count - 1;
else count <= (count == 4'b1111) ? 0 : count + 1;
end

C. always @(posedge clk) begin
if(reset) count <= 0;
else if(dir) count <= count - 1;
else count <= count + 1;
end

D. always @(posedge clk) begin
if(reset) count <= 0;
else if(dir) count <= (count == 4'b1111) ? 0 : count + 1;
else count <= (count == 4'b0000) ? 4'b1111 : count - 1;
end

Solution

1. Step 1: Understand wrap-around conditions

   When counting up at max (15), reset to 0; when counting down at 0, reset to 15.

2. Step 2: Check code logic for direction and wrap-around

   always @(posedge clk) begin if(reset) count <= 0; else if(dir) count <= (count == 4'b1111) ? 0 : count + 1; else count <= (count == 4'b0000) ? 4'b1111 : count - 1; end correctly uses conditional operator to wrap count on max and min values based on direction.

3. Final Answer:

   Code with conditional wrap-around for max and min counts -> Option D

4. Quick Check:

   Wrap-around logic matches direction and limits [OK]

Hint: Use conditional operator to wrap count at limits [OK]

Common Mistakes:

• Not wrapping count at max/min values
• Reversing increment and decrement logic
• Using incorrect boundary values