Propagation Delay, Contamination Delay and the Critical Path

Add gate delays along each path of a circuit to find when its output starts to change and when it settles.

You Will Be Able To

  • Tell the propagation delay of a gate from its contamination delay.
  • List the paths of a circuit and add the delays along each one.
  • Find the critical path and the short path of a circuit.
  • Read rise, fall and min:typ:max delays in Verilog.
Lesson
G5.1
Time
25 min
Runs on
Your browser
Check
5 questions

A team gated a reset with a small block of logic and assumed its output stayed still until it settled. When one input fell, a fast path moved the output after 5 ns. A slow path moved it back 5 ns later, and the reset saw the pulse.

b Falls at t = 50: Two Paths, Two ArrivalsOne column per ns, from t = 49 to t = 61. n4 is on the short path, n1 and n3 on the long path.
01234567891011bn4 (short path)n1 (long path)n3 (long path)yfirst change: 5 nssettled: 10 ns
Scroll horizontally ↔
  1. Cycle 1

    b falls at t = 50. Two paths lead from b to y.

  2. Cycle 3

    After 2 ns the AND gate u4 has seen it: n4 falls.

  3. Cycle 6

    After 5 ns y falls. This is the first moment y can change: the short path.

  4. Cycle 11

    After 10 ns the long path arrives and y rises again. From here on y is settled.

Measured on the circuit model below, whose frames are checked against an Icarus run of the same netlist.

Two Delays for Every Gate

A gate needs time to answer an input change. Two numbers describe that time.

DelaySymbolWhat it promises
Propagation delaytpdThe output is settled at its new value no later than this.
Contamination delaytcdThe output keeps its old value at least this long.

Both are measured from the input change. Between them, the output may be changing.

A gate can also be faster in one direction. The rise delay is the time for the output to go 0 to 1. The fall delay is the time for 1 to 0. In Verilog, not #(3, 1) gives a rise delay of 3 ns and a fall delay of 1 ns.

Paths Through a Circuit

A path starts at an input and follows wires through gates to the output. Its delay is the sum of the delays of its gates. Wires take no time in this model.

Five Gates, Five Delays
Five Gates, Five Delaysu1 · NANDn1=1u2 · NOTn2=1u3 · ANDn3=1u4 · ANDn4=0u5 · ORy=1a=1b=0c=0d=1
a=1 b=0 c=0 d=1
u1 · NANDa=1, b=0 → n1=1
u2 · NOTc=0 → n2=1
u3 · ANDn1=1, n2=1 → n3=1
u4 · ANDb=0, d=1 → n4=0
u5 · ORn3=1, n4=0 → y=1
Read the connections
GateKindInputsOutput
u1NANDa, bn1
u2NOTcn2
u3ANDn1, n2n3
u4ANDb, dn4
u5ORn3, n4y

Outputs: y. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 60. Settled after 60 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960yxxxxxxxxxx000000000001111111110000000011111111111111111000001
Scroll horizontally ↔
Every computed frame
Timey
0x
1x
2x
3x
4x
5x
6x
7x
8x
9x
100
110
120
130
140
150
160
170
180
190
200
211
221
231
241
251
261
271
281
291
300
310
320
330
340
350
360
370
381
391
401
411
421
431
441
451
461
471
481
491
501
511
521
531
541
550
560
570
580
590
601

  1. Step 21 · a fell at 11. The change runs through u1 (3), u3 (4) and u5 (3). y rises at 21: 10 gate delays later.
  2. Step 30 · c rose at 22. The inverter is fast (1), then u3 and u5: y falls 8 later, at 30.
  3. Step 38 · d rose at 33. Only u4 (2) and u5 (3) lie between d and y: 5 later, at 38.
  4. Step 49 · a and c changed at 44 and 47. n1 and n2 move, but n3 stays 0 because the other input of u3 is 0. A change can stop inside the circuit.
  5. Step 60 · b fell at 50. b feeds two paths. The short one (u4, u5) pulls y low at 55. The long one (u1, u3, u5) lifts it back at 60.

Time is in ns here: each gate has its own delay. Click an input pin to change it and step again.

PathGatesDelay
a → yu1, u3, u510 ns
b → yu1, u3, u510 ns
c → yu2, u3, u58 ns
b → yu4, u55 ns
d → yu4, u55 ns

Every path of the circuit, slowest first. The lab below measures the same numbers.

An input can start several paths. Input b feeds u1 and u4, so it reaches y after 5 ns along one path and after 10 ns along the other.

A change does not always reach the output. When c fell at t = 47, n2 rose, but n3 stayed 0 because n1 was 0. An AND gate with a 0 on one input blocks the others.

The Critical Path and the Short Path

The critical path is the path with the largest delay. Its delay is the propagation delay of the whole circuit: after any input change, the output is settled by then. Here it is 10 ns, from a or b through u1, u3 and u5.

The short path is the path with the smallest delay. Its delay is the contamination delay of the circuit: the output keeps its old value at least that long. Here it is 5 ns, from b or d through u4 and u5.

What the Two Circuit Delays MeanArrows show time order after one input change.
  • Step
  • Structure
What the two circuit delays meanArrows show time order after one input change. step Input change t = 0 step Old value held until t_cd = 5 ns step May be changing 5 ns to 10 ns step New value settled from t_pd = 10 ns short path not thereyetshort path arrivescritical path arrives
  1. step Input changet = 0
    • short path not there yet → Old value held
  2. step Old value helduntil t_cd = 5 ns
    • short path arrives → May be changing
  3. step May be changing5 ns to 10 ns
    • critical path arrives → New value settled
  4. step New value settledfrom t_pd = 10 ns
  1. Old value

    For 5 ns no path has reached y, so it still shows its old value.

  2. Unsure

    From 5 ns to 10 ns some paths have arrived and some have not. y may glitch.

  3. Settled

    After 10 ns every path has arrived. y holds its new value.

Read the diagram as text
  • Input change: t = 0
  • Old value held: until t_cd = 5 ns
  • May be changing: 5 ns to 10 ns
  • New value settled: from t_pd = 10 ns
  • Input change → Old value held: short path not there yet
  • Old value held → May be changing: short path arrives
  • May be changing → New value settled: critical path arrives

The propagation delay sets how fast a clock can be (G5.8). The contamination delay sets the hold check.

Use the propagation delay of each gate to find the critical path. Use the contamination delay of each gate to find the short path. Lesson G5.8 uses both: one for setup, one for hold.

Delays in Code and on Silicon

A Verilog delay can hold three numbers, #(min:typ:max). A datasheet lists delays the same way, for the fastest part, a typical part and the slowest part. The simulator uses one of the three; Icarus uses the typical value unless told otherwise.

This lesson used fixed delays to show the idea. Lesson G9.6 measures real gate delays in SPICE, and the STA track finds the critical path of a full design.

Asked in interviews
  1. What is the difference between propagation delay and contamination delay?

    Propagation delay is the longest time until an output is settled after an input change. Contamination delay is the shortest time until it can start to change. The first comes from the slowest path, the second from the fastest.

  2. What is a critical path?

    The path with the largest delay from an input or a flip-flop to an output or a flip-flop. It sets the highest clock frequency. It is the path with the most delay, which need not be the one with the most gates.

  3. Why do we care about the shortest path?

    It decides how soon an output starts to change. Between flip-flops, a path that is too fast breaks the hold time of the next flop. A slower clock does not fix that.

Try It

Predict each line before you press Run. The path table above has every delay you need.

A change on a takes the critical path: 10 ns. A change on c passes the fast inverter: 8 ns. A change on d takes the short path: 5 ns.

When a rises and then c falls, nothing reaches y: a 0 on one input of u3 blocks the other input. When b falls, both of its paths reach y, one 5 ns after the change and one 10 ns after it.

Now change the delay of u3 from #4 to #1 and run again. Which lines change, and which path is critical now?

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: a falls y changes at: +10 ns (now y=1) c rises y changes at: +8 ns (now y=0) d rises y changes at: +5 ns (now y=1) a rises y changes at: none (now y=1) c falls y changes at: none (now y=1) b falls y changes at: +5 ns +10 ns (now y=1)
Read included file: tb.sv
// tb.sv: changes one input every 11 ns and lists when y changed (read-only).
`timescale 1ns/1ns
module tb;
  logic  a = 1, b = 1, c = 0, d = 0;
  wire   y;
  time   t0;
  string seen;
  paths dut (.a(a), .b(b), .c(c), .d(d), .y(y));
  always @(y) if (t0 > 0) seen = {seen, $sformatf(" +%0d ns", $time - t0)};
  task automatic change(input string what);
    t0 = $time; seen = "";
    #11 if (seen.len() == 0) seen = " none";
    $display("%-8s y changes at:%s  (now y=%b)", what, seen, y);
  endtask
  initial begin
    #11;                       // let the gates settle first
    a = 0; change("a falls");
    c = 1; change("c rises");
    d = 1; change("d rises");
    a = 1; change("a rises");
    c = 0; change("c falls");
    b = 0; change("b falls");
  end
endmodule

Check Yourself

ConceptA circuit has three paths to its output, with delays of 4 ns, 9 ns and 6 ns. What are its propagation and contamination delays?
Read the waveformOne input changes at the start of cycle 1. Each cycle is 1 ns. What are the contamination and propagation delays from that input to y?
One input change
012345678iny
Scroll horizontally ↔

y settles at 0 in cycle 7.

ConceptWhich statement about the critical path is true?
ConceptA gate has a contamination delay of 1 ns and a propagation delay of 4 ns. Its input changes at t = 10. When is its output certain to show the new value?
Predict the outputThis copy of the lab circuit has u3 at #1 in place of #4. With b = 1, c = 0 and d = 0, a falls. Predict the exact line.
`timescale 1ns/1ns
module tb;
  logic a = 1, b = 1, c = 0, d = 0;
  wire  n1, n2, n3, n4, y;
  time  t0;
  nand #3 u1 (n1, a, b);
  not  #1 u2 (n2, c);
  and  #1 u3 (n3, n1, n2);
  and  #2 u4 (n4, b, d);
  or   #3 u5 (y, n3, n4);
  initial begin
    #20 t0 = $time; a = 0;
    @(y) $display("y=%b after %0d ns", y, $time - t0);
  end
endmodule

Common Mistakes

Wrong Add up the delays of every gate in the circuit.

No signal passes every gate. A change travels along one path at a time, so the sum of all gates is far too large.

Fix Sum the gates along each path. The largest sum is the propagation delay.

Wrong Take the path with the most gates as the critical path.

One slow gate can make a short path the slowest. Two gates of 5 ns each are slower than three gates of 2 ns each.

Fix Compare total delays, not gate counts.

Wrong Assume the output stays still until the propagation delay has passed.

The short path reaches the output first. When b falls in the lab, y moves after 5 ns, long before it settles at 10 ns.

Fix The output may change at any time from the contamination delay to the propagation delay.

Wrong Expect the # delays of a netlist to reach the chip.

Synthesis ignores # delays. Real gate delays come from the cell library and depend on load and input slope.

Fix Use # delays to study timing in simulation, and static timing analysis for the real chip.

Remember

  • A gate holds its old output for its contamination delay and settles within its propagation delay.
  • A path delay is the sum of the gate delays along it; wires take no time in this model.
  • The critical path has the largest delay and sets the circuit's propagation delay.
  • The short path has the smallest delay and sets the contamination delay; between the two, the output may glitch.
  • Synthesis ignores # delays; real delays come from the cell library and STA.

Practice

Report a problem with this page