= Comparator composition
{title2=$L=L_H\lor(E_H\land L_L),\quad G=G_H\lor(E_H\land G_L)$}
To combine more and less significant <digital comparators>, compute $E_H=\neg(L_H\lor 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.
Back to article page
