Consensus theorem 2026-10-31
In Boolean algebra, the product is the consensus of and . If , either and , or and , so adding the consensus does not change the Boolean function. It can change a circuit's transient behavior: while switches, the two original product terms may briefly both be zero because of unequal propagation delays, but remains one. Keeping the logically redundant consensus product can therefore remove a static-one logic hazard.
Electronic comparator 2026-11-05
An electronic comparator is an electrical circuit that converts the ordering of two input electric potential differences into an output state. For the usual non-inverting convention, the output is high when and low when . Unlike a linear amplifier, an electronic comparator deliberately makes a threshold decision; its output does not report how large the input difference is. A sensor signal can therefore become a pulse marking the instant it crosses a reference.
Real threshold decisions have an input offset voltage and a finite propagation delay. The permitted input range and the output drive also matter: an open-drain output needs a pull-up resistor, whereas a push-pull output drives both states. The manufacturer’s inverting example explicitly includes the pull-up resistor and explains how input offset voltage, resistor tolerances and internal hysteresis affect the thresholds.[ref]
With a single threshold, a slowly varying input plus electrical noise can cause repeated transitions. A Schmitt trigger adds hysteresis: the threshold depends on the existing output state. For an illustrative non-inverting design, suppose the output switches high on a rise through and low on a fall through . At , either output is possible, depending on the preceding input. The interval is deliberate memory of the last state, rather than an ambiguous instantaneous comparison. Positive feedback can produce this behavior; the cited design derives the two thresholds from the feedback resistor network.[ref]
A useful bench demonstration applies a slow triangular input with a small superposed ripple and displays both input and output on an oscilloscope. Record the rising and falling switching levels separately. Repeated transitions near one level demonstrate noise sensitivity; distinct rising and falling levels demonstrate hysteresis. The time between an input crossing and the output transition measures propagation delay, a different quantity from the separation between the two thresholds.
Fan-out 2026-10-31
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.
Hazard (logic) Created 2026-10-31 Updated 2026-11-05
A logic hazard is a transient output error caused by unequal propagation delays along paths in a Boolean circuit. A static hazard temporarily changes an output that should remain constant; a dynamic hazard introduces extra transitions when the output should change once. A steady-state truth table records final values and therefore does not describe these timing effects.
For example, implement with AND gates, an OR gate and a NOT gate. With , changing should leave . But if the first product falls before the second rises, both OR inputs can momentarily be zero. Adding the redundant term gives : it does not change the Boolean function, by the consensus theorem, and remains one throughout that single-input transition. This argument assumes the other inputs remain fixed and the circuit begins settled. Simultaneous input changes and more general implementations require their own timing analysis.
For an estimate, use the usual equal-device CMOS series-stack model: a -input NAND gate or NOR gate has a worst-case propagation delay approximately times that of an inverter, because a conducting path contains series transistors. An AND gate or OR gate adds an output inverter. With a 1 ns inverter this gives, for ,
For 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 and delay ns; that is a different construction from a single -input gate.
For the explicit circuit in part (a), the longest combinational logic path starts at , passes through the shared inverter, either direction-match exclusive or, the AND gate, and the final exclusive or feeding :
The path takes 5 ns, the paths from or to take at most 7 ns, and 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 to
A 256:1 multiplexer for one data bit can be made hierarchically: 32 first-stage 8:1 multiplexers select within eight-sensor groups using ; four second-stage 8:1 multiplexers select groups using ; one final 4:1 multiplexer selects using . 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 , , , and . Put the falling edge of at . Since throughout, throughout. The remaining transitions, including every stated propagation delay, are
The inverter delays the rise of by ten nanoseconds, and the AND gate adds another ten. Consequently and 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 ns, despite its equal initial and final logical values.
Figure 1.
Delayed transitions produce a ten-nanosecond static-one logic hazard
. The shaded interval marks the incorrect output pulse. Exact ten-nanosecond gate delays are used, including propagation of the pulse. Details.
To implement the two additional prime implicants explicitly, add two 2-input AND gates and two 2-input OR gates. Reuse from the existing inverter. An OR-tree arrangement that keeps the maximum propagation delay at 40 ns is
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, and settle by 10 ns, so settles by 20 ns. The two products in and the product settle by 20 ns, so and settle by 30 ns, and 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 is
Expanding 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 and settle by 20 ns, by 30 ns and by 40 ns. During a potentially hazardous change of , the bridging condition holds regardless of ; zero-to-zero cases keep either both 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.
Figure 1.
A factored logic hazard correction using three OR gates and two AND gates
. 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. Details.
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.
Static-one logic hazard 2026-10-31
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 , , , and . Give every gate, including each inverter, propagation delay 10 ns. Starting from , lower at time zero. Signal falls at 10 ns, while rises only at 20 ns. Their gap passes through the two OR gates, making fall during 30–40 ns even though its steady-state value remains one.
Figure 1.
A static-one logic hazard from unequal inversion and product paths
. Details.
Adding the two consensus theorem products and preserves the Boolean function and holds the output high across every potentially hazardous single-input transition. The resulting five-term expression factors as . When a change of could leave the output steadily one, and keep the second product steadily one. In the zero-to-zero case with changing , and keep both output products zero. Changes of 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.
Figure 2.
A shared-factor implementation of the consensus theorem correction
. Details.