Kernel Extraction and Algebraic Factoring

The idea

Two-level forms waste gates: the same subexpression is built again in every output that needs it. Multilevel optimization factors expressions and builds each shared factor once. Brayton and McMullen (1982) made the search for shared factors tractable by treating Boolean expressions as ordinary algebraic polynomials, deliberately ignoring Boolean identities such as a · a = a.

Divide an expression by a single product term (a cube). If the quotient is cube-free, meaning no single literal divides all of its terms, the quotient is a kernel of the expression and the cube is its co-kernel. Their central result: two expressions can share a common divisor of more than one term only if some kernel of one and some kernel of the other intersect in more than one term. Finding shared factors therefore reduces to intersecting sets of kernels. The optimizer picks the divisor that saves the most literals, makes it a new node, substitutes it everywhere it divides, and repeats.

A small case: f = ac + ad + bc + bd has the kernel c + d (co-kernels a and b), and factoring gives f = (a + b)(c + d), four literals instead of eight.

Watch it work: two expressions, one shared factor

Two expressions written flat as sums of products. The walkthrough divides by a cube to find a kernel, lists every kernel of both expressions, intersects them, and extracts the shared divisor as a new node, taking the network from twelve literals to seven.

The fine print

Algebraic division cannot use Boolean identities, so it misses factorizations that depend on them, for example ones that use a · ā = 0 or the don't-care conditions of the surrounding logic. Boolean division and don't-care simplification recover some of these at a higher cost. Literal count is only a proxy for area, and it says nothing about delay.

Where you meet it today

Kernel extraction was the backbone of the Berkeley multilevel synthesis systems of the late 1980s. Fast extract, a quicker algebraic extraction in the same spirit, is still the fx command in ABC, the Berkeley tool that Yosys calls for optimization and mapping.