= Solution
To implement the two additional <prime implicants> explicitly, add \b[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 \b[40 ns] is
$$
u=bc+bd,\qquad v=\bar a\bar c+\bar ab,\qquad w=u+\bar cd,\qquad q=v+w.
$$
The 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 cd$ settle by 20 ns, so $v$ and $w$ settle by 30 ns, and $q$ by 40 ns. In particular, \b[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 is
$$
u=\bar a+d,\qquad v=b+\bar c,\qquad t=uv,\qquad q=bc+t.
$$
Expanding this expression gives all five terms from part (b). It needs three OR gates, two AND gates and the existing two inverters: add \b[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.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/digital-systems-hazard-free-factorization.png]
{title=A factored <logic hazard> correction using three OR gates and two AND gates}
{description=The extra OR gate and rewiring replace explicit separate consensus-product gates. Labels identify all intermediate signals; the worst-case gate delay remains forty nanoseconds.}
Back to article page
