Boolean circuit

A Boolean circuit is a finite directed acyclic graph of Boolean gates with designated inputs and outputs.

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 transient output error caused by timing differences 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 cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

A transient output error caused by timing differences 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 cannot detect these timing effects. Consensus theorem terms can remove single-input static hazards in a sum of products, while simultaneous input changes may still produce other hazards.

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.

A physical or idealized component implementing a fixed Boolean function on one or more input bits. For example, an AND gate outputs one exactly when both input bits are one. A Boolean circuit connects logic gates; circuit size counts components and circuit depth measures the longest chain of dependencies.

A two-input logic gate whose output is one exactly when its two input bits agree. Its Boolean function is $(a\wedge b)\vee (\neg a\wedge \neg b)$, equivalently $(a\vee \neg b)\wedge (\neg a\vee b)$. This follows by considering the two cases in which inputs are equal. It implements logical equivalence of the input truth values.

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.

A logic gate computing $\neg (a\vee b)=\neg a\wedge \neg b$. This is distinct from exclusive or.

A logic gate computing the logical negation of the logical conjunction of its inputs. Thus $\mathrm{NAND}(x_1,\dots ,x_k)=\neg (x_1\wedge \cdots \wedge x_k)$. It implements a logical disjunction of complemented inputs by De Morgan laws.

The size of a Boolean circuit counts its gates, or in another common convention its wires. The convention must be fixed when stating quantitative bounds. In switching arguments, new clauses created from a decision tree are not separate original gates to be charged in the failure union bound.

Circuit depth is the largest number of counted gates on any input-to-output path in the Boolean circuit. For an AND/OR circuit with negations on input literals, only the AND/OR gates are counted. This convention makes the restriction argument for the Linial-Mansour-Nisan theorem precise.

Given a finite acyclic Boolean circuit and its input assignment, determine the output bit. Topological gate evaluation places the problem in P; it is a standard P-complete problem under logspace many-one reductions. Boolean circuit evaluation is different from Circuit satisfiability problem, which asks whether some assignment succeeds.

The circuit value problem restricted to AND and NOT gates remains P-complete. Replace each OR by $\neg (\neg x\wedge \neg y)$, using a constant-size gadget. Gate indices and gadget positions can be emitted in logarithmic space, and assignments are preserved. Constants, when needed, can be represented by fixed-valued input nodes.

The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.

A threshold Boolean function outputs one exactly when a weighted sum of its input bits reaches a specified threshold. The unweighted threshold function $f_{n,r}$ tests whether at least $r$ of its $n$ inputs are one.

A majority Boolean function outputs one when more than half its input bits are one. An odd number of inputs avoids a tie convention. For three bits its unique multilinear polynomial is $x_1{x}_2+x_1{x}_3+x_2{x}_3-2x_1{x}_2{x}_3$, so the polynomial method for quantum query lower bounds requires at least two exact queries.

Its $n$ disjoint triples give a product of degree-three multilinear polynomials, with all-variable coefficient $(-2{)}^n$. Hence its degree is $3n$ and its exact quantum query complexity is at least $\lceil 3n/2\rceil$. At the input consisting of repeated $110$ triples, each of the $2n$ one bits is a disjoint sensitive singleton. Thus block sensitivity is at least $2n$, implying a bounded-error quantum query complexity lower bound $\Omega (\sqrt{n})$.

The dual of a Boolean function $f$ is $f^{\ast }(x)=\neg f(\neg x)$. Swapping AND with OR and zero with one in a monotone circuit for $f$ produces a circuit for $f^{\ast }$ by De Morgan's laws.