G5.1.2 The Shortest Path Too

EasyImplementIcarus · browser samples / server checksReview the topic

Find the contamination delay of each output of a six-gate circuit: the shortest path, with the fastest delay of each gate.

Hardware context: A status flag and a two-output control block made of timed gates in a motor controller. Find the contamination and propagation delay of both outputs of a six-gate circuit.

Two outputs of a small control block feed the next stage of a pipeline. The timing review asks two questions for each output. When is it settled? How soon after an input change can it start to move? The second answer is the one that decides hold time later.

This is an Implement problem with no logic to write. Work out each answer by hand and write it into the answer module as a constant. The first three constants are worked examples and are already correct.

The check compares every constant with the right value and names the first one that is wrong.

Signals in the Timeline

SignalWidthRole
question8input of each check
Full specification
Gate typePropagation delay (latest settle)Contamination delay (earliest change)
NOT2 ns1 ns
NAND3 ns1 ns
NOR4 ns2 ns
The circuit. Each gate lists its output first, then its inputs
// Six gates. Each lists its output first, then its inputs.
module two_out (input wire a, b, c, d, output wire y, z);
  wire n1, n2, n3, n5;
  nand g1 (n1, a, b);   // propagation 3 ns, contamination 1 ns
  not  g2 (n2, b);   // propagation 2 ns, contamination 1 ns
  nor  g3 (n3, n2, c);   // propagation 4 ns, contamination 2 ns
  nand g4 (y, n1, n3);   // propagation 3 ns, contamination 1 ns
  nor  g5 (n5, n3, d);   // propagation 4 ns, contamination 2 ns
  nand g6 (z, n5, a);   // propagation 3 ns, contamination 1 ns
endmodule
ConstantWhat to write
TPD_YThe propagation delay from any input to y in ns (b, g2, g3, g4: 2 + 4 + 3).
TCD_C_G3_G4The contamination delay of the path c, g3, g4 in ns (2 + 1).
TPD_D_G5_G6The propagation delay of the path d, g5, g6 in ns (4 + 3).
TCD_YThe contamination delay from any input to y, in ns.
TCD_ZThe contamination delay from any input to z, in ns.
TPD_ZThe propagation delay from any input to z, in ns.
TCD_B_TO_ZThe contamination delay from b to z: the earliest z can start to change after b changes, in ns.
Z_UNSUREZ may be changing from TCD_Z to TPD_Z after an input change: how many ns long is that stretch.

The propagation delay of an output is the largest sum of propagation delays along any path to it. The contamination delay is the smallest sum of contamination delays along any path to it.

These delays belong to a small exercise library, not to a real cell library. Keep the module name and the constant names.

Examples

Example 1

Worked Example: The Critical Path to y
Input
the propagation delay from any input to y in ns (b, g2, g3, g4: 2 + 4 + 3)
Output
tpd_y = 9

The slowest path to y starts at b and passes the inverter, the NOR and the NAND: 2 + 4 + 3 = 9 ns. This constant is already filled in.

Example 2

Worked Example: One Path, Earliest Change
Input
the contamination delay of the path c, g3, g4 in ns (2 + 1)
Output
tcd_c_g3_g4 = 3

Along c, g3, g4 the earliest changes are 2 ns for the NOR and 1 ns for the NAND. So y can start to move 3 ns after c changes. This constant is already filled in.

Example 3

Worked Example: One Path, Latest Settle
Input
the propagation delay of the path d, g5, g6 in ns (4 + 3)
Output
tpd_d_g5_g6 = 7

Along d, g5, g6 the NOR takes up to 4 ns and the NAND up to 3 ns: 7 ns. This constant is already filled in.

Constraints and Contract

  • Keep the module name answer and the names of the constants.
  • Every answer is a whole number of nanoseconds.

Hints

Hint 1

List every path to each output, as for a critical path. Then add the contamination delays along each one, and keep the smallest sum.

Hint 2

Look at every input of the last gate. One of them may come straight from a primary input.

Hint 3

The contamination delay of an output is a property of a whole path. The smallest delay of a single gate is not the answer unless that gate is the whole path.

What the grader checks: The check reads eight constants and compares each with a value computed from the netlist. It cannot see how a value was found. The delays are fixed numbers from an exercise library; real delays depend on load, input slope and the corner.

8 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Worked Example: The Critical Path to y

Input
the propagation delay from any input to y in ns (b, g2, g3, g4: 2 + 4 + 3)
Expected output
tpd_y = 9

The slowest path to y starts at b and passes the inverter, the NOR and the NAND: 2 + 4 + 3 = 9 ns. This constant is already filled in.

Run samples executes all 3 public checks. Check all tests runs 8 checks on the server.

Icarus · browser samples / server checks