Digital comparator

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

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.