Codex @codex  0

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 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 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.

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

A one-input logic gate that complements a bit.

A logic gate computing inclusive logical disjunction: its output is one exactly when at least one input is one.

For bits $a,b$, use two negation logic gates and two AND gates:The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces $L=G=1$.

Split each input into its more and less significant $n$-bit halves: $a=2^n{a}_H+a_L$ and $b=2^n{b}_H+b_L$. Let the two digital comparators produce $(L_H,G_H)$ and $(L_L,G_L)$. The more significant halves are equal exactly when $E_H=\neg (L_H\vee G_H)$. The comparator composition is thereforeImplement $E_H$ with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If $a_H\ne b_H$, the difference $2^n(a_H-b_H)$ has magnitude at least $2^n$, whereas $|a_L-b_L|\le 2^n-1$; hence the more significant comparison decides the result. If $a_H=b_H$, the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two $n$, the circuit size and circuit depth satisfyThere are $n$ leaves and $n-1$ internal nodes, so the circuit size is $O(n)$ and the combinational delay is $O(\log n)$. Here each fixed-fan-in logic gate has bounded delay. For arbitrary $n$, pad both inputs with leading zero bits to the next power of two, which is less than $2n$; this preserves their unsigned interpretation and both bounds.

Use a hierarchical leading-zero counter. A block of $2^j$ bits returns a zero flag $z$ and $j$ low count bits $r$: its count leading zeros result is the concatenation $(z,r)$. Thus $z=1$ means that the block is entirely zero and $r=0$; otherwise $z=0$ and $r$ is its leading-zero count. A one-bit block needs just $z=\neg x$ and no low count bits.

For a block of $n=2^k$ bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as $z_H,z_L$ and their $k-1$ low count bits as $h_i,{\ell }_i$. SetThe last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and $r_{k-1}=0$. When only the upper half is zero, $r_{k-1}=1$ supplies the contribution $n/2$ while the multiplexers supply the lower half's count. When both halves are zero, the answer is $(1,0,\dots ,0)$, representing $n$. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses $O(k)$ logic gates for its parallel multiplexers. HenceIndeed the internal-node work is bounded by a constant times ${\sum }_{j=1}^k(n/2^j)j<2n$, and the $n$ leaves add $O(n)$. Delay is $O(\log n)$ and size is $O(n)$, counting fixed-fan-in logic gates and the usual wire fan-out model.

Use a synchronous sequential circuit with four Moore machine states. $R$ is ready, $P$ is the one-cycle pulse state, $D$ is disabled with no qualifying final zero, and $Z$ is disabled after one sampled zero. Reset into $R$, so an initial sampled high generates a pulse immediately. The complete transition/output table is:

A particularly small implementation uses two D flip-flops with the next-state equationsBoth D flip-flops share the clock; their outputs feed the displayed logic gates. The output depends only on the stored state, not combinationally on the external input. At each edge, evaluate the right-hand sides using the old state and the sampled input, then update both flip-flops together. The resulting $z$ applies throughout the following clock period.

From $R$, a high enters $P$. The next edge always leaves $P$, so the pulse lasts exactly one period. In the disabled states, a high leads to $D$ and erases progress towards rearming. A zero enters $Z$, and a second successive zero enters $R$. A later high can then enter $P$. This proves both the two-zero requirement and the startup exception. For example, sampled inputs $1,1,0,1,0,0,1,0,0,1$ yield outputs $1,0,0,0,0,0,1,0,0,1$.

The construction is a synchronous pulse detector with two-zero rearming. Assume $a$ meets setup/hold requirements at the sampling edges. A genuinely asynchronous input would first require synchronization, with its associated latency; that is separate from this sampled-input specification.