Up-down counter with control in VHDL - Time & Space Complexity

Time Complexity: Up-down counter with control

O(n)

Understanding Time Complexity

We want to understand how the time it takes for an up-down counter to run changes as the count size grows.

Specifically, we ask: how does the number of steps grow when the counter counts up or down?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity up_down_counter is
  port(
    clk : in std_logic;
    reset : in std_logic;
    up_down : in std_logic;
    count : out unsigned(7 downto 0)
  );
end up_down_counter;

architecture Behavioral of up_down_counter is
  signal cnt : unsigned(7 downto 0) := (others => '0');
begin
  process(clk, reset) is
  begin
    if reset = '1' then
      cnt <= (others => '0');
    elsif rising_edge(clk) then
      if up_down = '1' then
        cnt <= cnt + 1;
      else
        cnt <= cnt - 1;
      end if;
    end if;
  end process;
  count <= cnt;
end Behavioral;

This code defines an 8-bit up-down counter that increments or decrements on each clock pulse depending on the control signal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The counter increments or decrements by 1 on each clock cycle.
• How many times: This operation repeats once every clock pulse, potentially many times as the counter runs.

How Execution Grows With Input

Each clock cycle causes one increment or decrement operation, so the number of operations grows directly with the number of clock cycles.

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

Pattern observation: The operations increase one-to-one with the input size; doubling the input doubles the operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to count grows directly in proportion to how many steps the counter takes.

Common Mistake

[X] Wrong: "The counter updates instantly no matter how big the count is."

[OK] Correct: Each increment or decrement happens step-by-step on each clock pulse, so more steps mean more time.

Interview Connect

Understanding how counters work and how their operations scale helps you reason about timing and performance in hardware design, a useful skill in many technical roles.

Self-Check

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

Practice

1. What does an up-down counter do in VHDL when the control signal is set to '1'?

easy

A. It counts down by decreasing the value on each clock pulse.

B. It resets the counter to zero immediately.

C. It holds the current count value without change.

D. It counts up by increasing the value on each clock pulse.

Solution

1. Step 1: Understand the control signal meaning

   In an up-down counter, the control signal '1' usually means count up.

2. Step 2: Identify the counting behavior

   When control is '1', the counter increments its value on each clock pulse.

3. Final Answer:

   It counts up by increasing the value on each clock pulse. -> Option D

4. Quick Check:

   Control '1' means count up [OK]

Hint: Control '1' means count up, '0' means count down [OK]

Common Mistakes:

• Confusing control '1' with reset signal
• Thinking control '1' holds the value
• Mixing up count up and count down signals

2. Which of the following is the correct VHDL syntax to declare a 4-bit up-down counter signal named count?

easy

A. signal count : bit_vector(4 downto 1);

B. signal count : std_logic_vector(3 downto 0);

C. signal count : integer range 0 to 15;

D. signal count : std_logic_vector(0 to 3);

Solution

1. Step 1: Identify correct type and range for 4-bit vector

   std_logic_vector(3 downto 0) is the standard way to declare a 4-bit vector from bit 3 down to 0.

2. Step 2: Check other options for errors

   signal count : integer range 0 to 15; uses integer, not vector; signal count : bit_vector(4 downto 1); uses bit_vector with wrong range; signal count : std_logic_vector(0 to 3); uses ascending range which is less common and may cause confusion.

3. Final Answer:

   signal count : std_logic_vector(3 downto 0); -> Option B

4. Quick Check:

   4-bit vector uses std_logic_vector(3 downto 0) [OK]

Hint: Use std_logic_vector(3 downto 0) for 4-bit signals [OK]

Common Mistakes:

• Using integer instead of vector for bit signals
• Incorrect range direction (0 to 3 instead of 3 downto 0)
• Using bit_vector instead of std_logic_vector

3. Given the following VHDL process for a 3-bit up-down counter with control signal up_down and synchronous reset rst, what is the value of count after 3 clock cycles if rst = '0' and up_down = '0' initially?

process(clk)
begin
  if rising_edge(clk) then
    if rst = '1' then
      count <= "000";
    else
      if up_down = '1' then
        count <= count + 1;
      else
        count <= count - 1;
      end if;
    end if;
  end if;
end process;

medium

A. "111"

B. "011"

C. "101"

D. "001"

Solution

1. Step 1: Understand initial conditions and counting direction

   Reset is '0', so no reset occurs. up_down = '0' means count down. Initial count is unknown but assumed 0 at start.

2. Step 2: Calculate count after each clock cycle

   Cycle 1: count = 0 - 1 = 7 (since 3-bit unsigned wraps around)
   Cycle 2: count = 7 - 1 = 6
   Cycle 3: count = 6 - 1 = 5 (binary "101")

3. Final Answer:

   "101" -> Option C

4. Quick Check:

   Counting down 3 times from 0 wraps to 5 [OK]

Hint: Count down wraps around 0 to max value in unsigned [OK]

Common Mistakes:

• Assuming count starts at zero without reset
• Ignoring wrap-around behavior in unsigned counters
• Mixing up count up and count down logic

4. Identify the error in this VHDL snippet for an up-down counter process:

process(clk)
begin
  if clk'event and clk = '1' then
    if rst = '1' then
      count <= (others => '0');
    elsif up_down = '1' then
      count <= count + 1;
    else
      count <= count - 1;
    end if;
  end if;
end process;

medium

A. Using clk'event and clk = '1' instead of rising_edge(clk)

B. Missing asynchronous reset handling

C. Incorrect use of (others => '0') for resetting count

D. No error; code is correct

Solution

1. Step 1: Check clock edge detection method

   Using clk'event and clk = '1' is legal but less safe and less recommended than rising_edge(clk) in modern VHDL.

2. Step 2: Identify best practice for clock edge

   rising_edge(clk) is preferred for clarity and synthesis compatibility.

3. Final Answer:

   Using clk'event and clk = '1' instead of rising_edge(clk) -> Option A

4. Quick Check:

   Use rising_edge(clk) for clock detection [OK]

Hint: Use rising_edge(clk) for reliable clock detection [OK]

Common Mistakes:

• Using clk'event instead of rising_edge(clk)
• Confusing synchronous and asynchronous reset
• Incorrect reset assignment syntax

5. You want to design a 4-bit up-down counter in VHDL with a control signal dir where dir = '1' counts up and dir = '0' counts down. The counter should reset to "1000" on reset. Which code snippet correctly implements this behavior inside a synchronous process?

process(clk)
begin
  if rising_edge(clk) then
    if rst = '1' then
      count <= "1000";
    else
      if dir = '1' then
        count <= count + 1;
      else
        count <= count - 1;
      end if;
    end if;
  end if;
end process;

hard

A. Correct implementation for the described behavior.

B. Reset value should be "0000" instead of "1000".

C. Counting direction logic is reversed; dir='1' should count down.

D. Process should use asynchronous reset instead of synchronous.

Solution

1. Step 1: Check reset behavior

   Reset sets count to "1000" as required, synchronously on rising clock edge.

2. Step 2: Verify counting direction logic

   dir='1' triggers count increment, dir='0' triggers decrement, matching the requirement.

3. Step 3: Confirm synchronous reset usage

   Reset is synchronous, which is acceptable and matches the problem statement.

4. Final Answer:

   Correct implementation for the described behavior. -> Option A

5. Quick Check:

   Synchronous reset and correct dir logic [OK]

Hint: Match reset value and dir logic exactly as specified [OK]

Common Mistakes:

• Using wrong reset value
• Reversing count up/down logic
• Confusing synchronous and asynchronous reset