Edge detector design in VHDL - Time & Space Complexity

Time Complexity: Edge detector design

O(n)

Understanding Time Complexity

We want to understand how the time needed to detect edges changes as the input signal size grows.

How does the design handle more input bits or longer signals?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

process(clk)
begin
  if rising_edge(clk) then
    prev_signal <= signal_in;
    edge_detected <= signal_in and not prev_signal;
  end if;
end process;

This code detects a rising edge by comparing the current input with its previous value on each clock cycle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The process runs once every clock cycle.
• How many times: It repeats for each clock tick, processing one input bit at a time.

How Execution Grows With Input

Each clock cycle handles one input bit, so the total work grows directly with the number of bits.

Input Size (n)	Approx. Operations
10	10 clock cycles
100	100 clock cycles
1000	1000 clock cycles

Pattern observation: The time grows linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to detect edges grows in direct proportion to the number of input bits.

Common Mistake

[X] Wrong: "The edge detector checks all bits at once, so time does not grow with input size."

[OK] Correct: The design processes one bit per clock cycle, so more bits mean more cycles and more time.

Interview Connect

Understanding how hardware designs scale with input size helps you explain efficiency clearly and confidently.

Self-Check

"What if we changed the design to process multiple bits in parallel? How would the time complexity change?"

Practice

1. What is the main purpose of an edge detector in VHDL?

easy

A. To generate a clock signal

B. To store a constant value permanently

C. To convert analog signals to digital

D. To detect changes in a signal from low to high or high to low

Solution

1. Step 1: Understand the role of edge detectors

   Edge detectors monitor signals to find when they change state, either rising or falling edges.

2. Step 2: Identify the correct function

   Detecting changes in signal levels is exactly what edge detectors do, unlike storing values or generating clocks.

3. Final Answer:

   To detect changes in a signal from low to high or high to low -> Option D

4. Quick Check:

   Edge detection = signal change detection [OK]

Hint: Edge detectors track signal changes, not constants or clocks [OK]

Common Mistakes:

• Confusing edge detection with clock generation
• Thinking edge detectors store constant values
• Assuming edge detectors convert signal types

2. Which VHDL code snippet correctly declares a signal to store the previous value for edge detection?

easy

A. signal prev_signal : integer range 0 to 1;

B. signal prev_signal : std_logic;

C. constant prev_signal : std_logic_vector(1 downto 0);

D. variable prev_signal : integer;

Solution

1. Step 1: Identify correct signal declaration for previous value

   For edge detection, we store the previous signal value as a signal of type std_logic.

2. Step 2: Compare options

   signal prev_signal : std_logic; declares a signal of type std_logic, suitable for storing previous signal state. Variables or constants are not appropriate here.

3. Final Answer:

   signal prev_signal : std_logic; -> Option B

4. Quick Check:

   Previous value storage = signal std_logic [OK]

Hint: Use 'signal' with std_logic for previous signal storage [OK]

Common Mistakes:

• Using variable instead of signal for previous value
• Declaring constant instead of signal
• Using incorrect data types like integer

3. Given the following VHDL process for a rising edge detector:

process(clk)
begin
  if rising_edge(clk) then
    prev_signal <= signal_in;
    if signal_in = '1' and prev_signal = '0' then
      edge_detected <= '1';
    else
      edge_detected <= '0';
    end if;
  end if;
end process;

What will be the value of edge_detected if signal_in changes from '0' to '1' at the clock edge?

medium

A. '0'

B. Undefined

C. '1'

D. Signal error

Solution

1. Step 1: Understand signal update timing in VHDL

   In VHDL, signal assignments inside a clocked process update after the process ends, so prev_signal still holds old value during evaluation.

2. Step 2: Evaluate condition at clock edge

   At the clock edge, prev_signal still equals '0' (old value), signal_in is '1'. prev_signal <= signal_in schedules update after process. Condition signal_in='1' and prev_signal='0' is true, so edge_detected <= '1'.

3. Final Answer:

   '1' -> Option C

4. Quick Check:

   Signal update delay enables edge detection with old prev_signal [OK]

Hint: prev_signal lags one cycle, allowing correct rising edge detection [OK]

Common Mistakes:

• Assuming prev_signal updates immediately within process
• Confusing signal and variable assignment timing
• Thinking edge_detected remains '0' due to update order

4. Identify the error in this VHDL code snippet for a falling edge detector:

process(clk)
begin
  if rising_edge(clk) then
    prev_signal <= signal_in;
    if signal_in = '0' and prev_signal = '1' then
      edge_detected <= '1';
    else
      edge_detected <= '0';
    end if;
  end if;
end process;

medium

A. No error; code is correct

B. prev_signal should be updated after edge_detected assignment

C. prev_signal must be a variable, not a signal

D. The condition should check for rising_edge(signal_in)

Solution

1. Step 1: Analyze signal update order

   Due to VHDL signal semantics, prev_signal retains its prior value ('1') during the condition check even though assigned first, allowing correct falling edge detection when signal_in='0'.

2. Step 2: Confirm code correctness

   This is the standard implementation for a synchronous falling edge detector; no error exists.

3. Final Answer:

   No error; code is correct -> Option A

4. Quick Check:

   Standard order works due to delta-delay updates [OK]

Hint: VHDL signal reads use pre-process values; code detects edge correctly [OK]

Common Mistakes:

• Misunderstanding that assignment order requires swapping
• Using rising_edge on signal_in instead of clk
• Declaring prev_signal as variable

5. You want to design an edge detector in VHDL that detects both rising and falling edges of a signal signal_in. Which approach correctly implements this?

hard

A. Compare current and previous values: edge_detected <= '1' when signal_in /= prev_signal else '0'; update prev_signal after

B. Use two separate processes for rising and falling edges with different clocks

C. Assign edge_detected <= '1' when signal_in = '1' else '0'; no previous value needed

D. Use a variable to store signal_in and assign edge_detected <= '1' when variable = '0'

Solution

1. Step 1: Understand dual edge detection logic

   Detecting both edges means detecting any change in signal_in compared to its previous value.

2. Step 2: Implement comparison and update order

   Comparing current and previous values with signal_in /= prev_signal detects any edge. Updating prev_signal after ensures correct timing.

3. Final Answer:

   Compare current and previous values: edge_detected <= '1' when signal_in /= prev_signal else '0'; update prev_signal after -> Option A

4. Quick Check:

   signal_in /= prev_signal detects any edge [OK]

Hint: Detect edges by comparing current and previous signal values [OK]

Common Mistakes:

• Using separate clocks for edge detection
• Ignoring previous signal value
• Assigning edge_detected based only on current signal