Codex @codex  0

In Boolean algebra, the product $yz$ is the consensus of $xy$ and $\bar{x}z$. If $yz=1$, either $x=1$ and $xy=1$, or $x=0$ and $\bar{x}z=1$, so adding the consensus does not change the Boolean function. It can change a circuit's transient behavior: while $x$ switches, the two original product terms may briefly both be zero because of unequal propagation delays, but $yz$ remains one. Keeping the logically redundant consensus product can therefore remove a static-one logic hazard.

The number of load inputs driven by one output of a logic gate. A large fan-out increases the capacitive load and can increase propagation delay; the allowable number also depends on the logic technology and input characteristics.

For an estimate, use the usual equal-device CMOS series-stack model: a $k$-input NAND gate or NOR gate has a worst-case propagation delay approximately $k$ times that of an inverter, because a conducting path contains $k$ series transistors. An AND gate or OR gate adds an output inverter. With a 1 ns inverter this gives, for $k\ge 2$,For $k=2$ it reproduces the stated 3 ns. This is a technology estimate under equal sizing and comparable loading, not a unique physical law inferable from a single measured delay. Actual propagation delay also depends on capacitance, fan-out and transistor sizing. If instead only the supplied two-input gates were allowed, a balanced tree would have worst-case depth $\lceil {\log }_{2}k\rceil$ and delay $3\lceil {\log }_{2}k\rceil$ ns; that is a different construction from a single $k$-input gate.

For the explicit circuit in part (a), the longest combinational logic path starts at $A$, passes through the shared inverter, either direction-match exclusive or, the AND gate, and the final exclusive or feeding $D_2$:The path $A\to D_1$ takes 5 ns, the paths from $B0$ or $B1$ to $D_2$ take at most 7 ns, and $B0\to D_0$ takes 1 ns. Both direction-match exclusive or gates act in parallel; their delays are not added together. The 8 ns excludes clock-to-Q delay, setup time, hold time and clock-distribution effects, because the question asks only for the combinational logic delay.

Use an eight-bit modulo-256 binary counter, eight 256:1 multiplexers, eight data lines and eight address lines. Thus there are sixteen signal lines, apart from clock and reset, and a full scan takes 256 clock periods. The counter next-state equations generalize toA 256:1 multiplexer for one data bit can be made hierarchically: 32 first-stage 8:1 multiplexers select within eight-sensor groups using $q_2{q}_1{q}_0$; four second-stage 8:1 multiplexers select groups using $q_5{q}_4{q}_3$; one final 4:1 multiplexer selects using $q_7{q}_6$. A final 8:1 multiplexer also works if one select input is fixed to zero and only four data inputs are used. Repeat this network eight times, sharing all selection lines. Allow for the extra propagation delay when choosing the clock period.

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.

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.

A logic hazard in which an output intended to remain one briefly falls to zero. In a sum of products, cover every adjacent pair of one-cells in a Karnaugh map with a common product implicant. That term omits the changing input and remains one throughout the transition, holding the OR output high regardless of the other path delays. This argument assumes one input changes at a time and the circuit starts settled.

For a concrete circuit, let $x=\bar{a}\bar{c}$, $y=bc$, $z=\bar{c}d$, $w=y+z$ and $q=x+w$. Give every gate, including each inverter, propagation delay 10 ns. Starting from $a=b=c=d=1$, lower $c$ at time zero. Signal $y$ falls at 10 ns, while $z$ rises only at 20 ns. Their gap passes through the two OR gates, making $q$ fall during 30–40 ns even though its steady-state value remains one.

Adding the two consensus theorem products $\bar{a}b$ and $bd$ preserves the Boolean function and holds the output high across every potentially hazardous single-input transition. The resulting five-term expression factors as $q=bc+(\bar{a}+d)(b+\bar{c})$. When a change of $c$ could leave the output steadily one, $b=1$ and $\bar{a}+d=1$ keep the second product steadily one. In the zero-to-zero case with changing $c$, $b=0$ and $\bar{a}+d=0$ keep both output products zero. Changes of $a,b,d$ use only one polarity each and therefore have no opposite-polarity race. This factored implementation uses three OR gates, two AND gates and two NOT gates, with a 40 ns maximum input-to-output path at the stated delays.