Combinational logic

A Boolean circuit whose current output depends only on its current input, with no stored state or feedback dependency. Its delay is bounded by the longest input-to-output path of logic gates. This differs from a synchronous sequential circuit, whose output can depend on state stored at earlier clock edges.

A combinational logic circuit mapping a binary input code to selected output lines. In a one-of-$k$ register-address decoder, line $i$ is asserted exactly when the address equals $i$, optionally combined with an enable. This selects which processor register may capture a common write-data word.

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 $F=ab+\bar{a}c$ with AND gates, an OR gate and a NOT gate. With $b=c=1$, changing $a$ should leave $F=1$. But if the first product falls before the second rises, both OR inputs can momentarily be zero. Adding the redundant term $bc$ gives $F=ab+\bar{a}c+bc$: 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.

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.

The elapsed time between a change at a logic gate's input and the corresponding settled change at its output, under specified loading and transition conditions. Dependent gate delays add along a path. The combinational critical path gives the longest such input-to-output path; reconvergent paths of unequal delay can produce a logic hazard even when the final Boolean function value does not change.

The combinational critical path is a longest propagation-delay path through a combinational logic circuit. Register-to-register clock timing also includes launch delay, setup time and clock uncertainty. Putting two functional units in series adds their dependent delays; operating them in parallel instead contributes the slower branch plus any subsequent selection delay.

A barrel shifter moves a machine word by a variable number of bit positions through a bounded-depth combinational logic circuit. For a $2^k$-bit machine word, cascade $k$ banks of multiplexers selecting optional shifts of $1,2,\dots ,2^{k-1}$. The binary shift-amount bits select the stages; the chosen distances add. Logical shifts fill vacated positions with zero, whereas bit rotations reconnect the discarded positions. A 32-bit logical barrel shifter can use five banks of 32 two-input multiplexers.

The number of zero bits before the first one, reading a fixed-width binary representation from its most significant bit. The all-zero $n$-bit input has count $n$. Thus ${\mathrm{clz}}_8(00000101)=5$, and ${\mathrm{clz}}_8(00000000)=8$; the width is part of the definition.

For leading-zero count, inspect a word's bytes from most significant to least significant. Every zero byte contributes eight; the first nonzero byte contributes its table value in the title. If all bytes are zero, a word of width $w$ contributes $w$. Defining the zero table entry explicitly makes the all-zero argument a regular case rather than an out-of-range logarithm.

For a block of $2^k$ bits, encode its count leading zeros result as a zero flag $z$ followed by $k$ low count bits $r$. An all-zero block has $(z,r)=(1,0)$; otherwise $z=0$. Two half-block encoders supply flags $z_H,z_L$ and low counts $h,\ell$. Combine them using $z=z_H\wedge z_L$, $r_{k-1}=z_H\wedge \neg z_L$, and $r_i=\mathrm{mux}(z_H,h_i,{\ell }_i)$ for $i<k-1$. A one-bit leaf has $z=\neg x$ and no low count bits. Checking whether the upper half is nonzero, only the lower half is nonzero, or both halves are zero proves the formula.

All count bits are selected in parallel, so $D(n)=D(n/2)+O(1)$ for circuit depth. The circuit size satisfies $S(n)=2S(n/2)+O(\log n)$; summing the work over levels gives $S(n)=O(n)$. Sharing the all-zero flags avoids a serial adder along the critical path.

A Boolean circuit computing the sum of binary representations, possibly including input and output carry bits. Its delay depends on how carries are propagated; specifying an adder does not by itself imply constant circuit depth as the input width grows.

A combinational logic circuit adding two input bits $a,b$ to a sum bit $s=a\oplus b$ and carry bit $c=a\wedge b$. An exclusive or gate and an AND gate implement it. The identity $a+b=(a\oplus b)+2(a\wedge b)$ follows by checking the four input pairs. A half adder has no input carry, so adding three equally weighted bits needs a different circuit or multiple stages.

A selector that routes one of several inputs to its output according to control bits. The displayed two-input version selects $a$ when $s=0$ and $b$ when $s=1$. A word selector applies the same control bit to parallel one-bit multiplexers; its circuit size grows with the word width while its added circuit depth remains constant.

A combinational logic device comparing two fixed-width binary representations. For unsigned inputs $a,b$, a two-output encoding is $L=1$ exactly when $a<b$ and $G=1$ exactly when $a>b$. Equality gives $(L,G)=(0,0)$; $(1,1)$ is unreachable. A one-bit implementation is $L=\neg a\wedge b$, $G=a\wedge \neg b$.

A digital comparator processes one pair of bits per clock cycle, storing a comparison result in a finite-state machine. For least-significant-first unsigned input, a new unequal pair overrides the stored result, while equal bits preserve it: the newest unequal pair has the greatest place value seen so far.

To combine more and less significant digital comparators, compute $E_H=\neg (L_H\vee G_H)$ and use the displayed formulas. Unequal upper blocks decide the order, because their difference outweighs every possible lower-block difference; equal upper blocks delegate the decision to the lower block. This is an associative operation on the three comparison outcomes. A balanced binary tree of these combinations has $O(n)$ circuit size and $O(\log n)$ circuit depth for $n$-bit inputs.