Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 2

The internal Boolean functions are $x=\bar{a}\bar{c}$, $y=bc$, $z=\bar{c}d$, $w=y+z$ and $q=x+w$. Put the falling edge of $c$ at $t=0$. Since $a=1$ throughout, $x=0$ throughout. The remaining transitions, including every stated propagation delay, areThe inverter delays the rise of $\bar{c}$ by ten nanoseconds, and the $z$ AND gate adds another ten. Consequently $y$ and $z$ are simultaneously zero for ten nanoseconds. This gap propagates through the two OR gates. The output has a static-one logic hazard: a low glitch on $30\le t<40$ ns, despite its equal initial and final logical values.

The steady-state output is $q=\bar{a}\bar{c}+bc+\bar{c}d$. Its Karnaugh map, with rows $ab$ and columns $cd$ in Gray code order, isThe existing prime implicants cover adjacent ones except for some transitions in $c$. The consensus theorem supplies the two missing bridging implicants $\bar{a}b$ and $bd$, givingBoth are needed in a hazard-free sum of products retaining the original terms. At $a=0,b=1,d=0$, the two values of $c$ require a common implicant, necessarily covered by $\bar{a}b$; at $a=1,b=1,d=1$, the corresponding transition requires $bd$. Neither bridge covers the other's critical edge. All other adjacent-one pairs already share a term. Thus two is the least number of additional prime implicants. This addresses single-input static hazards; simultaneous input changes require separate analysis.

To implement the two additional prime implicants explicitly, add two 2-input AND gates and two 2-input OR gates. Reuse $\bar{a}$ from the existing inverter. An OR-tree arrangement that keeps the maximum propagation delay at 40 ns isThe five product gates feed four OR gates; the original circuit already supplied three of the product gates and two OR gates. From the primary inputs, $bc$ and $bd$ settle by 10 ns, so $u$ settles by 20 ns. The two products in $v$ and the product $\bar{c}d$ settle by 20 ns, so $v$ and $w$ settle by 30 ns, and $q$ by 40 ns. In particular, no increase in worst-case delay is necessary. Merely appending two OR gates to the old output would unnecessarily lengthen some paths.

If arbitrary rewiring and factoring are allowed, an even smaller added-hardware implementation isExpanding this expression gives all five terms from part (b). It needs three OR gates, two AND gates and the existing two inverters: add one OR gate, reuse two existing AND gates and leave the third unused. Both $u$ and $v$ settle by 20 ns, $t$ by 30 ns and $q$ by 40 ns. During a potentially hazardous change of $c$, the bridging condition $b=u=1$ holds $v=t=1$ regardless of $c$; zero-to-zero cases keep either both $b,u$ zero or all relevant products steadily zero. The factored circuit therefore retains single-input hazard protection. The four-gate count above is the minimum when the two extra product implicants are required as separate AND outputs; factoring changes that implementation constraint.

Removing logic hazards prevents transient false control pulses, incorrect triggering of asynchronous state changes and avoidable switching activity. It also makes behavior less sensitive to unequal propagation delays. These benefits matter especially when an output directly controls another circuit rather than being sampled only after settling.

The usual costs are redundant logic gates, larger area and capacitance, more wiring and possibly a longer critical path. Power can rise from extra hardware even when glitch power falls. A synchronous design may instead sample after a sufficiently long clock period, trading settling time against additional hazard-correction logic. A circuit proved free of single-input static hazards need not be safe under arbitrary simultaneous input changes; metastability at an asynchronous input is a different problem.