Technology-Independent Optimization

The Synthesis Flow named this as the step where the actual logic minimization happens — after elaboration, before any real cell exists. This page covers what that minimization actually does, and why the technique Digital Design already taught doesn't reach the scale a real design operates at.

Two-level minimization doesn't extend to real designs

Digital Design's own logic-minimization page covered Karnaugh maps by hand, and named Quine-McCluskey as the algorithmic version of the same idea — both produce a minimal two-level form: a sum of products, or a product of sums, exactly two logic levels deep. That's genuinely optimal for a handful of inputs. It stops being practical long before a real design's scale: the number of terms a two-level form can require grows explosively with input count, and a real block has far more than the four or five variables a K-map comfortably handles. Two-level logic has a real hardware analog, too — it's structurally what a PLA already is, AND-plane feeding OR-plane, which is exactly why PLAs stop being used for anything but small, specialized blocks at real chip scale.

Multi-level logic: trading levels for size

Multi-level logic optimization allows more than two levels of gates, in exchange for a network that's dramatically smaller for the same function. The core technique is algebraic factoring — finding a common factor shared across multiple terms and pulling it out, the same idea as factoring an algebraic expression by hand:

Two-level (unfactored):  Y = ABC + ABD
Multi-level (factored):  Y = AB(C + D)

Both compute the identical function. The first needs 6 literals (A, B, C appearing once each, A, B, D appearing once each); the factored version needs 4 (A, B, C, D, each exactly once) — fewer literals means fewer transistors, directly. Multiplied across a real network with thousands of terms sharing structure this way, the size difference between unfactored and factored logic is not a minor tweak — it's often the difference between a design that fits and one that doesn't.

Kernels: how a tool finds what to factor, automatically

A human spots AB(C+D) by inspection. A synthesis tool operating on a network with thousands of terms needs an algorithmic way to find factoring opportunities — that's what a kernel is. A kernel of a function is found by repeatedly dividing out the largest cube (a product term with no shared structure left to simplify) until nothing more can be divided out; what's left is cube-free by construction, and is exactly the kind of term worth checking for reuse elsewhere in the network. Algebraic division — given a function F and a candidate divisor D, finding a quotient Q and remainder R such that F = D·Q + R — is the actual mechanism a tool uses to test whether a given kernel is worth factoring out across multiple terms at once, not just the one it was found in.

Co-kernels: the other half of a kernel

Dividing out a kernel doesn't just leave the kernel itself — it also leaves behind a co-kernel: the cube that was divided out to produce that kernel in the first place. In Y = AB(C + D), (C + D) is the kernel and AB is its co-kernel — the quotient side of the same algebraic division. A tool doesn't just collect kernels in isolation; it pairs each one with its co-kernel specifically because two different terms in a network that share the same kernel, found via two different co-kernels, are exactly the case worth factoring together across the whole network, not just within one term.

What's next

Technology-independent optimization decides the network's logical shape — how many levels, how much sharing — with no real cell in the picture yet. The next page covers what happens once real cells actually enter the process: matching this optimized, still-abstract network onto the library from Section A.