Down counter design in Verilog - Time & Space Complexity

Time Complexity: Down counter design

O(n)

Understanding Time Complexity

We want to understand how the time it takes for a down counter to run changes as the count size changes.

How does the number of steps grow when the counter counts down from a bigger number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

always @(posedge clk or posedge rst) begin
  if (rst)
    count <= 4'd10;
  else if (count > 0)
    count <= count - 1;
end
endmodule

This code counts down from 10 to 0, decreasing the count by 1 each clock cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The count decreases by 1 every clock cycle.
• How many times: The operation repeats once per clock cycle until count reaches zero.

How Execution Grows With Input

Each step reduces the count by one, so the total steps equal the starting count.

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

Pattern observation: The number of steps grows directly with the starting count size.

Final Time Complexity

Time Complexity: O(n)

This means the time to count down grows in a straight line with the starting number.

Common Mistake

[X] Wrong: "The counter finishes instantly regardless of the start value."

[OK] Correct: Each count step takes one clock cycle, so bigger start values take more steps and more time.

Interview Connect

Understanding how counters scale helps you reason about timing and delays in hardware designs, a useful skill in many projects.

Self-Check

What if we changed the counter to count down by 2 each step? How would the time complexity change?

Practice

1.

What is the main function of a down counter in Verilog?

easy

A. Counts backward from a start value to zero

B. Counts forward from zero to a maximum value

C. Generates a clock signal

D. Resets the system to initial state

Solution

1. Step 1: Understand the counting direction

   A down counter decreases its count value each clock cycle, moving backward.

2. Step 2: Compare with other options

   Counting forward is for up counters, clock generation and reset are different functions.

3. Final Answer:

   Counts backward from a start value to zero -> Option A

4. Quick Check:

   Down counter = counts backward [OK]

Hint: Down counter always counts backward from start [OK]

Common Mistakes:

• Confusing down counter with up counter
• Thinking it generates clock signals
• Assuming it resets the system

2.

Which of the following is the correct Verilog syntax to declare a 4-bit down counter register?

?

easy

A. integer counter;

B. reg [3:0] counter;

C. reg counter[3:0];

D. wire [4:0] counter;

Solution

1. Step 1: Identify correct register declaration

   In Verilog, a 4-bit register is declared as reg [3:0] name; where 3:0 means 4 bits.

2. Step 2: Check other options

   wire is for connections, reg counter[3:0] is an array of 4 registers, integer is 32-bit signed.

3. Final Answer:

   reg [3:0] counter; -> Option B

4. Quick Check:

   4-bit reg = reg [3:0] name [OK]

Hint: Use reg [3:0] for 4-bit counters [OK]

Common Mistakes:

• Using wire instead of reg for storage
• Declaring array instead of vector
• Using integer for fixed bit width

3.

Given this Verilog code snippet for a 3-bit down counter starting at 5, what is the value of count after 3 clock cycles?

reg [2:0] count = 3'd5;
always @(posedge clk) begin
  if (count > 0)
    count <= count - 1;
end

medium

A. 3

B. 5

C. 0

D. 2

Solution

1. Step 1: Trace the count value each clock

   Start at 5, after 1st clock: 4, 2nd clock: 3, 3rd clock: 2.

2. Step 2: Confirm counting stops only at zero

   Since count > 0 condition is true, it decrements each cycle until zero.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   5 - 3 = 2 after 3 clocks [OK]

Hint: Subtract 1 each clock if count > 0 [OK]

Common Mistakes:

• Not decrementing count on each clock
• Stopping count too early
• Confusing initial value with current

4.

Identify the error in this down counter code and select the fix:

reg [3:0] count = 4'd10;
always @(posedge clk or posedge reset) begin
  if (reset)
    count <= 4'd0;
  else if (count >= 0)
    count <= count - 1;
end

medium

A. Remove reset from sensitivity list

B. Initialize count to zero instead of 10

C. Change count >= 0 to count > 0

D. Use count <= count + 1 instead

Solution

1. Step 1: Analyze the condition for decrement

   Condition count >= 0 is always true for unsigned, causing underflow.

2. Step 2: Correct condition to prevent underflow

   Use count > 0 to stop decrement at zero and avoid wrap-around.

3. Final Answer:

   Change count >= 0 to count > 0 -> Option C

4. Quick Check:

   Prevent underflow by checking count > 0 [OK]

Hint: Use > 0, not >= 0, to stop at zero [OK]

Common Mistakes:

• Using >= 0 causes counter to wrap
• Ignoring reset sensitivity
• Incrementing instead of decrementing

5.

You want to design a 4-bit down counter that stops at zero and asserts an output done signal when zero is reached. Which Verilog code snippet correctly implements this behavior?

?

hard

A. reg [3:0] count = 4'd10;
reg done = 0;
always @(posedge clk or posedge reset) begin
if (reset) begin
count <= 4'd10;
done <= 0;
end else if (count > 0) begin
count <= count - 1;
done <= 0;
end else begin
done <= 1;
end
end

B. reg [3:0] count = 4'd10;
reg done = 0;
always @(posedge clk) begin
if (count >= 0) begin
count <= count - 1;
done <= (count == 0);
end
end

C. reg [3:0] count = 4'd0;
reg done = 1;
always @(posedge clk or posedge reset) begin
if (reset) begin
count <= 4'd10;
done <= 0;
end else begin
count <= count - 1;
done <= (count == 0);
end
end

D. reg [3:0] count = 4'd10;
reg done = 0;
always @(posedge clk or posedge reset) begin
if (reset) begin
count <= 4'd10;
done <= 0;
end else if (count >= 0) begin
count <= count - 1;
done <= 0;
end else begin
done <= 1;
end
end

Solution

1. Step 1: Check initialization and reset behavior

   Count starts at 10, done is 0, reset sets count and done correctly.

2. Step 2: Verify counting and done signal logic

   Count decrements only if > 0, done set to 1 when count reaches zero, stopping count.

3. Step 3: Compare with other options

   reg [3:0] count = 4'd10; reg done = 0; always @(posedge clk) begin if (count >= 0) begin count <= count - 1; done <= (count == 0); end end allows underflow. Other options either start count at 0 or use >= 0 causing wrap-around.

4. Final Answer:

   A -> Option A

5. Quick Check:

   Stop at zero and assert done = 1 [OK]

Hint: Stop count at zero, set done signal then [OK]

Common Mistakes:

• Allowing count to underflow below zero
• Incorrect done signal timing
• Wrong initial count value