Gate-level delay annotation in Verilog - Time & Space Complexity

Time Complexity: Gate-level delay annotation

O(n)

Understanding Time Complexity

When we add delays to gates in Verilog, it affects how long signals take to change.

We want to see how these delays impact the total time as the design grows.

Scenario Under Consideration

Analyze the time complexity of this gate-level delay example.

module delay_example(input a, b, c, output y);
  wire w1, w2;
  and #2 (w1, a, b);  // 2 time units delay
  or  #3 (w2, w1, c); // 3 time units delay
  not #1 (y, w2);     // 1 time unit delay
endmodule
    

This code models a small circuit where each gate has a fixed delay before output changes.

Identify Repeating Operations

Look for parts that repeat or grow with input size.

• Primary operation: Each gate's delay adds up in sequence.
• How many times: Number of gates in the path determines total delay.

How Execution Grows With Input

As you add more gates in a chain, delays add up one after another.

Input Size (number of gates)	Approx. Total Delay (time units)
3	6 (2+3+1)
10	About 20 (sum of delays of 10 gates)
100	About 200 (sum of delays of 100 gates)

Pattern observation: Total delay grows roughly in a straight line as gates increase.

Final Time Complexity

Time Complexity: O(n)

This means the total delay grows directly with the number of gates in the signal path.

Common Mistake

[X] Wrong: "Adding more gates won't increase delay much because they work fast."

[OK] Correct: Each gate adds its delay one after another, so more gates mean more total delay.

Interview Connect

Understanding how delays add up helps you design circuits that run efficiently and meet timing needs.

Self-Check

"What if some gates had zero delay? How would that change the total delay as the number of gates grows?"

Practice

1. What is the purpose of gate-level delay annotation in Verilog?

easy

A. To define the input and output ports of a module

B. To declare variables in a module

C. To specify the time delay for signal propagation through a gate

D. To initialize registers with default values

Solution

1. Step 1: Understand gate-level delay annotation

   Gate-level delay annotation is used to add timing delays to logic gates in simulation.

2. Step 2: Identify its purpose

   This delay models the real-world time it takes for signals to propagate through gates, helping verify timing correctness.

3. Final Answer:

   To specify the time delay for signal propagation through a gate -> Option C

4. Quick Check:

   Gate delay = specify propagation time [OK]

Hint: Gate delays model real signal timing in simulation [OK]

Common Mistakes:

• Confusing delay annotation with variable declaration
• Thinking delay sets input/output ports
• Assuming delay initializes registers

2. Which of the following is the correct syntax to add a 5-time-unit delay to an AND gate in Verilog?

easy

A. and #(5) (out, in1, in2);

B. and #5 (out, in1, in2);

C. and delay(5) (out, in1, in2);

D. and (out, in1, in2) #5;

Solution

1. Step 1: Recall Verilog gate delay syntax

   The delay is specified immediately after the gate type using #delay without parentheses.

2. Step 2: Match correct syntax

   and #5 (out, in1, in2); uses 'and #5 (out, in1, in2);' which is the correct form.

3. Final Answer:

   and #5 (out, in1, in2); -> Option B

4. Quick Check:

   Delay after gate type with #number [OK]

Hint: Use #number immediately after gate type for delay [OK]

Common Mistakes:

• Using parentheses around delay value
• Placing delay after port list
• Writing delay as a function call

3. Given the following Verilog code snippet, what is the delay before out changes after in1 or in2 changes?

and #3 (out, in1, in2);

medium

A. 0 time units

B. 5 time units

C. 1 time unit

D. 3 time units

Solution

1. Step 1: Identify the delay annotation

   The code uses '#3' after the 'and' gate, indicating a 3-time-unit delay.

2. Step 2: Understand delay effect

   This means output changes occur 3 time units after input changes.

3. Final Answer:

   3 time units -> Option D

4. Quick Check:

   Delay #3 means 3 time units [OK]

Hint: Delay number equals output wait time after input change [OK]

Common Mistakes:

• Assuming delay is zero if not explicitly stated
• Confusing delay with input change time
• Choosing wrong delay value

4. Identify the error in the following Verilog gate-level delay annotation:

or (out, in1, in2) #4;

medium

A. Delay must be specified immediately after gate type, not after port list

B. Delay value cannot be 4

C. The gate type 'or' is invalid

D. Port list must be enclosed in square brackets

Solution

1. Step 1: Check delay placement

   Delay must come immediately after the gate type, not after the port list.

2. Step 2: Analyze given code

   The code places '#4' after the port list, which is incorrect syntax.

3. Final Answer:

   Delay must be specified immediately after gate type, not after port list -> Option A

4. Quick Check:

   Delay after gate type, not ports [OK]

Hint: Place #delay right after gate type, before ports [OK]

Common Mistakes:

• Putting delay after port list
• Using invalid gate names
• Wrong port list syntax

5. You want to model an AND gate with different rise and fall delays: 2 time units for rising output and 4 time units for falling output. Which is the correct Verilog gate-level delay annotation?

hard

A. and #(2,4) (out, in1, in2);

B. and #(4,2) (out, in1, in2);

C. and #(2) #(4) (out, in1, in2);

D. and #2 #4 (out, in1, in2);

Solution

1. Step 1: Understand Verilog rise/fall delay syntax

   Verilog allows specifying rise and fall delays as #(rise, fall) after the gate type.

2. Step 2: Match delays to correct order

   The first number is rise delay, second is fall delay, so #(2,4) means 2 units rise, 4 units fall.

3. Final Answer:

   and #(2,4) (out, in1, in2); -> Option A

4. Quick Check:

   Use #(rise, fall) for different delays [OK]

Hint: Use #(rise, fall) to set different delays [OK]

Common Mistakes:

• Reversing rise and fall values
• Using multiple # delays separately
• Incorrect syntax with multiple #