Combinational timing and static hazards

A truth table is a settled-value contract

Boolean equivalence says what outputs are after inputs and internal nodes settle. It does not say two implementations produce identical transient waveforms. A physically delayed circuit can briefly change output even when the initial and final Boolean values agree. We will distinguish timing bounds, a specific delay simulation, and structural hazard prevention.

Prerequisites: gates, Boolean algebra, Karnaugh maps and full adders. Sequential setup/hold is used only to connect the output delay to a sampling deadline. All numerical delays below are illustrative, not device specifications. Wires have zero delay unless stated; there is no clock skew in the register example.

A gate's propagation delay t_pd is an upper bound on time to a valid settled output after its relevant inputs have become valid and stable. Its contamination delay t_cd is a lower bound on how soon its previous valid output can begin to change after an input change. The interval between them is not a promised pulse duration. A valid specification has 0≤t_cd≤t_pd.

For acyclic logic, a conservative total propagation bound is the maximum sum of gate propagation delays over input-to-output paths. A conservative contamination bound is the minimum path sum of contamination delays. These are bounds, not claims that every input transition exercises every path. A path can be blocked by side-input values; Boolean constraints can make some structural paths unsensitizable. Use a tighter value only after proving the relevant path restrictions.

Propagate arrival times, not gate counts

Worked example 1: u=a AND b, v=c XOR d, F=u OR v. AND has (t_cd,t_pd)=(1,3) ns, XOR (2,5) ns, and OR (1,2) ns. With all primary inputs valid at time zero, the AND branch bound is 3+2=5 ns and XOR branch is 5+2=7 ns. Thus t_pd for the network is bounded by 7 ns. Minimum path contamination sum is min(1+1,2+1)=2 ns.

For each gate, latest output arrival is max(latest input arrivals)+t_pd. If c arrives at time 2 ns while a,b,d arrive at zero, v is valid by max(2,0)+5=7 ns, and F by max(3,7)+2=9 ns. Counting two logic levels and multiplying by a single “gate delay” would miss that difference. All four inputs must then remain stable long enough for these guarantees to apply.

Between zero-skew edge-triggered registers, a setup bound is T_clock≥t_cq,max+t_pd,logic+t_setup. With 0.8 ns clock-to-Q, 7 ns logic and 0.7 ns setup, T_clock≥8.5 ns. The corresponding ideal upper frequency is 1/(8.5 ns)≈117.65 MHz. Hold is separate: t_cq,min+t_cd,logic≥t_hold. If these are 0.4,2 and 0.6 ns, respectively, 2.4≥0.6 holds. A longer clock period does not repair a same-edge hold violation.

Carry timing needs a declared starting condition

Use a ripple adder with p_i=a_i XOR b_i, g_i=a_i b_i, c_(i+1)=g_i OR (p_i AND c_i), and s_i=p_i XOR c_i. This is one explicit implementation; other full-adder gates can have other delays.

Worked example 2: p_i XOR delay is 2 ns, g_i AND delay 1 ns, each carry-path AND 2 ns, each carry OR 1 ns, and each sum XOR 2 ns. If operands and c_0 become valid at time zero, all p_i are valid by 2 ns and g_i by 1 ns. Therefore c_1 is valid by max(1,max(2,0)+2)+1=5 ns. The next carry bounds are c_2 at 8 ns, c_3 at 11 ns, and c_4 at 14 ns. The most-significant sum s_3 is valid by max(2,11)+2=13 ns. The four-bit adder's outputs are all valid by the larger bound, 14 ns.

If instead p_i and g_i have already settled before c_0 changes, a propagated carry traverses only carry AND plus OR, 3 ns per stage. Then c_4 changes no later than 12 ns after c_0, and s_3 by 11 ns. The different answers reflect different starting conditions, not contradictory arithmetic. Adding p-generation delay again at every ripple stage would double-count work already done in parallel.

A static-1 hazard with a concrete waveform

Consider the two-level AND-OR implementation F=xy+x′z, with y=z=1 held fixed. Its settled output is 1 for either value of x. Assume initially settled x=1 and a single change x:1→0 at t=0. For this example only, use exact transport delays: inverter 3 ns, each product AND 2 ns, final OR 1 ns, equal for rising and falling transitions. Transport means a pulse is delayed, not filtered out for being short.

The xy term falls at 2 ns. The inverted x rises at 3 ns, so x′z rises at 5 ns. Between 2 and 5 ns both OR inputs are zero. The output consequently falls at 3 ns and rises at 6 ns: a three-nanosecond zero pulse, despite both endpoint values being one. This is a static-1 hazard. A hazard means a glitch is possible for some allowed delays; other delay choices or inertial filtering can change or suppress this observed pulse. Do not infer this exact waveform from upper/lower delay bounds alone.

Add the consensus term yz: F_safe=xy+x′z+yz. It does not change the truth table. If yz=1, then y=z=1 and either x=1 makes xy true or x=0 makes x′z true; thus the extra term only covers existing ones. During the stated transition yz stays one, so a stable input holds the final OR output high. The redundancy has a timing purpose, although ordinary Boolean minimization would remove it.

K-map interpretation and the static-0 dual

In a two-level SOP implementation under a single-input-change assumption, cover every adjacent pair of on-set cells with at least one common implicant to remove static-1 hazards. For F above, cells xyz=011 and 111 are adjacent across x but originally covered by different terms. The shared group yz bridges them. Keep a physical implementation consistent with that cover; arbitrary later factoring can alter its hazard behavior.

The dual example is G=(x+y)(x′+z). With y=z=0, its settled output should stay zero while x changes. An interval when both sum terms are one can produce a static-0 hazard. Multiplying by the redundant sum factor (y+z) gives G_safe=(x+y)(x′+z)(y+z), with the same truth table and a stable zero factor in the stated case. In POS/K-map terms, common zero groups bridge adjacent zero cells.

These results assume one external input changes at a time and remaining inputs stay fixed. Multiple simultaneous input changes, unequal input arrival times, multilevel dynamic hazards and asynchronous clock/control safety need separate analysis. A dynamic hazard is repeated output switching when one final change was expected. Neither “minimum literals” nor one added consensus term proves a completely glitch-free physical system.

Key points and common mistakes

Use maximum path delay for settled-output deadlines and minimum path delay for earliest-change guarantees. Include nonzero input arrival times. Separate operand-generation delay from already-settled carry propagation. Hazard analysis is about implementation and transitions, not only truth-table equality. A static-1 glitch briefly falls from an expected one; a static-0 glitch briefly rises from an expected zero. State delay and input-change models before giving a pulse width or a hazard-free claim.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. For the worked AND/XOR branches feeding OR, what are the conservative (t_cd,t_pd) bounds with all inputs valid at zero?

A. (3,5) ns B. (2,7) ns C. (7,2) ns D. (1,5) ns

Answer: B

A is incorrect: it does not select the minimum contamination and maximum propagation paths.

B is correct: min(1+1,2+1)=2 and max(3+2,5+2)=7.

C is incorrect: minimum/maximum roles are reversed, and t_cd cannot exceed t_pd here.

D is incorrect: it omits the final OR delay.

C02. In that same network, only c becomes valid at 2 ns; a,b,d are valid at zero. By what latest time is F guaranteed valid?

A. 5 ns B. 7 ns C. 9 ns D. 11 ns

Answer: C

A is incorrect: it counts only the short AND-to-OR branch.

B is incorrect: that is v's arrival, not the final output's arrival.

C is correct: v arrives by 2+5=7 and final OR adds 2, giving 9 ns.

D is incorrect: the 2 ns input lateness is counted twice.

C03. In the stated four-bit ripple model with p_i and g_i already settled before c_0 changes, what is the c_0-to-c_4 propagation bound?

A. 12 ns B. 14 ns C. 8 ns D. 11 ns

Answer: A

A is correct: four carry stages each contribute 2+1=3 ns.

B is incorrect: 14 ns was the bound when p_i also had to be generated from time zero.

C is incorrect: it omits each carry OR's 1 ns.

D is incorrect: 11 ns is the corresponding c_0-to-s_3 bound, not c_4.

C04. For F=xy+x′z, y=z=1 and x:1→0, use exact transport delays NOT=3, AND=2, OR=1 ns. What output glitch occurs?

A. High from 2 to 5 ns B. Low from 2 to 5 ns C. No glitch because the endpoint outputs agree D. Low from 3 to 6 ns

Answer: D

A is incorrect: expected output is high; the hazard is a low pulse.

B is incorrect: those are the OR-input gap times, before the final OR delay.

C is incorrect: truth-table endpoints do not exclude transients.

D is correct: product terms are both zero from 2 to 5; the 1 ns OR delay shifts the pulse to 3…6.

C05. Which redundant term bridges the stated single-input static-1 hazard of xy+x′z without changing its function?

A. xz B. yz C. y+z D. x+x′

Answer: B

A is incorrect: xz is not redundant in general; at x=1,y=0,z=1 it changes the output.

B is correct: yz is the consensus term and stays one throughout the stated transition.

C is incorrect: ORing y+z changes the function for many input rows.

D is incorrect: x+x′ is one, so adding it would make the function always one.

C06. Which conclusion is justified by bridging every adjacent on-set pair in a two-level SOP with a common implicant?

A. Every asynchronous system is safe. B. All multiple-input-change glitches are impossible. C. Static-1 hazards are removed under the stated single-input-change model and preserved two-level implementation. D. The circuit necessarily has minimum area.

Answer: C

A is incorrect: system-level asynchronous safety needs more assumptions and analysis.

B is incorrect: multiple-input transitions are outside this guarantee.

C is correct: a common product term remains asserted across each covered single-input transition.

D is incorrect: hazard-removing redundant terms can increase area.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• MIT delay-bound definitions and path composition
• IISc NPTEL Digital Systems: hazard conventions

Sources checked 14 October 2026.