Binary down counter in VHDL - Time & Space Complexity

Time Complexity: Binary down counter

O(1)

Understanding Time Complexity

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

Specifically, how does the number of steps relate to the number of bits in the counter?

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 down_counter is
  port(clk : in std_logic;
       reset : in std_logic;
       count : out unsigned(3 downto 0));
end down_counter;

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

This code defines a 4-bit binary down counter that decreases its value by 1 on each clock pulse, resetting to zero when reset is active.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The subtraction operation cnt <= cnt - 1; happens every clock cycle.
• How many times: It repeats once per clock pulse, indefinitely as long as the clock runs.

How Execution Grows With Input

As the number of bits in the counter increases, the subtraction operation still happens once per clock cycle.

Input Size (bits)	Approx. Operations per clock
4	1 subtraction
8	1 subtraction
16	1 subtraction

Pattern observation: The number of operations per clock does not increase with the number of bits; it stays the same.

Final Time Complexity

Time Complexity: O(1)

This means the time to perform one count down step stays constant no matter how many bits the counter has.

Common Mistake

[X] Wrong: "The time to count down grows with the number of bits because more bits mean more work."

[OK] Correct: The subtraction happens in parallel on all bits in hardware, so it takes the same time regardless of bit size.

Interview Connect

Understanding how hardware operations scale helps you explain efficiency in digital designs clearly and confidently.

Self-Check

"What if the counter was implemented using a loop to subtract bit by bit instead of hardware subtraction? How would the time complexity change?"

Practice

1.

What does a binary down counter do in VHDL?

easy

A. Generates random binary numbers continuously

B. Counts forwards in decimal numbers on each clock pulse

C. Counts backwards in binary numbers on each clock pulse

D. Stores a fixed binary value without changing

Solution

1. Step 1: Understand the function of a down counter

   A down counter decreases its count value by one on each clock pulse, moving backwards in binary.

2. Step 2: Compare options with definition

   Only Counts backwards in binary numbers on each clock pulse describes counting backwards in binary on clock pulses, matching the down counter behavior.

3. Final Answer:

   Counts backwards in binary numbers on each clock pulse -> Option C

4. Quick Check:

   Down counter = counts backwards [OK]

Hint: Down counter always decreases count on clock pulse [OK]

Common Mistakes:

• Confusing down counter with up counter
• Thinking it counts in decimal
• Assuming it holds a fixed value

2.

Which of the following is the correct VHDL syntax to declare a 4-bit binary down counter signal?

signal count : ?;

easy

A. std_logic_vector(3 downto 0)

B. integer range 0 to 15

C. bit_vector(0 to 3)

D. std_logic_vector(0 to 3)

Solution

1. Step 1: Identify correct vector type and direction

   For a 4-bit binary counter, std_logic_vector(3 downto 0) is standard to represent bits from MSB to LSB.

2. Step 2: Check other options for correctness

   The integer range uses integer, not vector; bit_vector with ascending range is less common; std_logic_vector(0 to 3) uses ascending range which is unusual for counters.

3. Final Answer:

   std_logic_vector(3 downto 0) -> Option A

4. Quick Check:

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

Hint: Use std_logic_vector with downto for bit vectors [OK]

Common Mistakes:

• Using integer instead of vector for bit signals
• Using ascending range instead of downto
• Confusing bit_vector with std_logic_vector

3.

Given this VHDL process for a 3-bit down counter starting at 7:

process(clk, reset)
begin
  if reset = '1' then
    count <= "111";
  elsif rising_edge(clk) then
    count <= count - 1;
  end if;
end process;

What is the value of count after 3 clock pulses (assuming reset is '0')?

medium

A. "101"

B. "100"

C. "011"

D. "110"

Solution

1. Step 1: Start from initial value after reset

   Reset sets count to "111" which is decimal 7.

2. Step 2: Subtract 1 on each clock pulse for 3 pulses

   7 - 1 = 6 ("110"), 6 - 1 = 5 ("101"), 5 - 1 = 4 ("100").

3. Final Answer:

   "100" -> Option B

4. Quick Check:

   7 - 3 = 4 = "100" [OK]

Hint: Subtract 1 per clock pulse from start value [OK]

Common Mistakes:

• Counting up instead of down
• Misinterpreting binary values
• Forgetting reset sets initial value

4.

Identify the error in this VHDL down counter process:

process(clk, reset)
begin
  if reset = '1' then
    count <= "1111";
  elsif clk'event and clk = '1' then
    count <= count + 1;
  end if;
end process;

medium

A. Reset value is incorrect for 4 bits

B. Missing signal declaration for count

C. Clock edge detection syntax is wrong

D. Counter counts up instead of down

Solution

1. Step 1: Analyze counting operation

   The process increments count with count + 1, which is counting up, not down.

2. Step 2: Verify other parts for errors

   Reset value "1111" is valid for 4 bits; clock edge detection syntax is correct; signal declaration is not shown but not necessarily an error here.

3. Final Answer:

   Counter counts up instead of down -> Option D

4. Quick Check:

   Down counter must decrement, not increment [OK]

Hint: Down counter subtracts 1, not adds 1 [OK]

Common Mistakes:

• Using count + 1 instead of count - 1
• Confusing clock edge syntax
• Ignoring reset value correctness

5.

You want to design a 5-bit binary down counter in VHDL that resets to 31 and stops counting when it reaches 0. Which approach correctly implements this behavior?

hard

A. Reset count to "11111"; on clock, if count > 0 then count <= count - 1 else hold count

B. Reset count to 0; on clock, count <= count - 1 unconditionally

C. Reset count to "00000"; on clock, if count < 31 then count <= count + 1

D. Reset count to "11111"; on clock, count <= count + 1 until 31

Solution

1. Step 1: Set initial count and stopping condition

   Reset to "11111" (decimal 31) is correct for 5 bits; stopping at 0 means counting down until zero.

2. Step 2: Implement conditional decrement

   On each clock, decrement only if count > 0; else hold count to stop at zero.

3. Final Answer:

   Reset count to "11111"; on clock, if count > 0 then count <= count - 1 else hold count -> Option A

4. Quick Check:

   Count down from 31 to 0, stop at 0 [OK]

Hint: Decrement only if count > 0 to stop at zero [OK]

Common Mistakes:

• Resetting to zero instead of max value
• Counting up instead of down
• Not stopping at zero, causing underflow