Edge detector (rising, falling, both) in Verilog - Time & Space Complexity

Time Complexity: Edge detector (rising, falling, both)

O(1)

Understanding Time Complexity

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

Specifically, how does the work scale when checking for rising, falling, or both edges in a signal?

Scenario Under Consideration

Analyze the time complexity of the following Verilog edge detector code.

module edge_detector(
  input wire clk,
  input wire signal_in,
  output reg rising_edge,
  output reg falling_edge
);
  reg signal_d;

  always @(posedge clk) begin
    signal_d <= signal_in;
    rising_edge <= signal_in & ~signal_d;
    falling_edge <= ~signal_in & signal_d;
  end
endmodule
    

This code detects rising and falling edges of a signal synchronized to a clock.

Identify Repeating Operations

Look for repeated checks or loops in the code.

• Primary operation: The always block runs once every clock cycle.
• How many times: It executes once per clock tick, regardless of input size.

How Execution Grows With Input

The code checks the signal edges every clock cycle, doing a fixed number of operations each time.

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

Pattern observation: The number of operations grows linearly with the number of clock cycles, but each cycle does a constant amount of work.

Final Time Complexity

Time Complexity: O(1)

This means the work done each clock cycle is constant and does not increase with input size.

Common Mistake

[X] Wrong: "The edge detector takes longer as the signal changes more often."

[OK] Correct: The detector checks edges every clock cycle with fixed steps, so frequency of changes does not affect time per cycle.

Interview Connect

Understanding fixed-time operations in hardware logic helps you explain how circuits handle signals efficiently and predictably.

Self-Check

What if we added a loop inside the always block to check multiple signals? How would the time complexity change?

Practice

1. What does a rising edge detector in Verilog detect?
always @(posedge clk) is often used in such detectors.

easy

A. Both 0 to 1 and 1 to 0 changes

B. A change of signal from 1 to 0

C. A change of signal from 0 to 1

D. No change in signal

Solution

1. Step 1: Understand rising edge meaning

   A rising edge means the signal changes from low (0) to high (1).

2. Step 2: Relate to Verilog edge detection

   The posedge keyword triggers on this rising edge.

3. Final Answer:

   A change of signal from 0 to 1 -> Option C

4. Quick Check:

   Rising edge = 0 to 1 transition [OK]

Hint: Rising edge means signal goes from 0 to 1 [OK]

Common Mistakes:

• Confusing rising edge with falling edge
• Thinking it detects no change
• Mixing up posedge and negedge keywords

2. Which of the following Verilog code snippets correctly detects a falling edge of signal sig?

easy

A. always @(negedge sig) begin // detect falling edge end

B. always @(posedge sig) begin // detect falling edge end

C. always @(sig) begin // detect falling edge end

D. always @(posedge clk) if (sig == 1) // detect falling edge

Solution

1. Step 1: Identify falling edge keyword

   Falling edge detection uses negedge in Verilog.

2. Step 2: Match code to falling edge

   always @(negedge sig) begin // detect falling edge end uses always @(negedge sig), which triggers on signal going from 1 to 0.

3. Final Answer:

   always @(negedge sig) begin // detect falling edge end -> Option A

4. Quick Check:

   Falling edge = negedge keyword [OK]

Hint: Use negedge to detect falling edges in Verilog [OK]

Common Mistakes:

• Using posedge for falling edge detection
• Using level-sensitive sensitivity list
• Confusing signal and clock edges

3. Given this Verilog code snippet for detecting both edges of sig:

reg sig_d;
always @(posedge clk) begin
  sig_d <= sig;
end
wire edge_detect = sig ^ sig_d;

What is the value of edge_detect when sig changes from 0 to 1?

medium

A. 1

B. 0

C. Undefined (X)

D. Remains previous value

Solution

1. Step 1: Understand delayed signal sig_d

   sig_d holds previous clock cycle's sig value.

2. Step 2: Calculate XOR for edge detection

   When sig changes from 0 to 1, XOR with previous 0 gives 1, indicating an edge.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   sig ^ sig_d = 1 on edge [OK]

Hint: XOR current and delayed signal to detect edges [OK]

Common Mistakes:

• Forgetting to delay signal before XOR
• Assuming edge_detect stays 0 on change
• Confusing XOR with AND or OR

4. Identify the error in this Verilog code intended to detect a rising edge of sig:

reg sig_d;
always @(posedge clk) begin
  sig_d <= sig;
end
wire rising_edge = sig & ~sig_d;

medium

A. Using blocking assignment instead of non-blocking

B. Incorrect logic for rising edge detection

C. No sensitivity list for wire rising_edge

D. Missing initial value for sig_d

Solution

1. Step 1: Analyze rising edge logic

   Rising edge is when signal changes from 0 to 1, so previous was 0 and current is 1.

2. Step 2: Check given logic expression

   The expression sig & ~sig_d correctly detects rising edge by current high and previous low.

3. Step 3: Re-examine for errors

   Actually, the logic is correct; the error is elsewhere.

4. Step 4: Identify actual error

   Missing initial value for sig_d can cause unknown behavior at start.

5. Final Answer:

   Missing initial value for sig_d -> Option D

6. Quick Check:

   Initialize delayed signal to avoid unknowns [OK]

Hint: Initialize delayed signals to avoid unknown start values [OK]

Common Mistakes:

• Assuming logic expression is wrong
• Ignoring initial values for registers
• Confusing blocking and non-blocking assignments

5. You want to design a Verilog module that outputs a pulse of 1 clock cycle width whenever sig changes either from 0 to 1 or 1 to 0. Which code snippet correctly implements this?

hard

A. reg sig_d;
always @(posedge clk) sig_d <= sig;
wire edge_pulse = sig & ~sig_d;

B. reg sig_d;
always @(posedge clk) sig_d <= sig;
wire edge_pulse = sig ^ sig_d;

C. wire edge_pulse = (sig == 1) ? 1 : 0;

D. always @(posedge sig) edge_pulse = 1;

Solution

1. Step 1: Understand requirement for both edges

   The pulse should be high for one clock cycle on any signal change (rising or falling).

2. Step 2: Analyze each option

   reg sig_d; always @(posedge clk) sig_d <= sig; wire edge_pulse = sig ^ sig_d; uses XOR between current and delayed signal, which is 1 only on change, producing a 1-cycle pulse.

3. Step 3: Confirm other options

   reg sig_d; always @(posedge clk) sig_d <= sig; wire edge_pulse = sig & ~sig_d; detects only rising edge; C is level detection; D triggers on posedge of sig, not clock, and lacks pulse width control.

4. Final Answer:

   reg sig_d; always @(posedge clk) sig_d <= sig; wire edge_pulse = sig ^ sig_d; -> Option B

5. Quick Check:

   XOR current and delayed signal for both edges pulse [OK]

Hint: XOR current and delayed signals for both edges pulse [OK]

Common Mistakes:

• Using only rising edge logic for both edges
• Triggering on signal edge instead of clock
• Not producing single clock cycle pulse