Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 1

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.