Common-subexpression extraction

Common-subexpression extraction. When the same subexpression appears in several places, building it once and reusing it is cheaper than building it every time. This is how multi-level logic beats flat two-level form on size.

The rows are the design's product terms; a dot means the term contains that literal. A shared subexpression is a rectangle: a set of terms that all contain a set of literals. Extracting it builds the shared factor once, and each term reuses it. Its worth is

value = R x L - R - L

for a rectangle of R terms and L literals: the R x L shared literals removed, minus the L literals to build the factor once and the R wires that replace it.

Click term rows and literal columns to select a rectangle (every selected cell must be filled). Find the rectangle with the greatest value, then Submit factor.