Multilevel synthesis

Multilevel synthesis is the deliberate factoring of a Boolean expression into more than two levels of gates, trading propagation delay for smaller fan-in or fewer total gates. The alternative — two-level SOP or POS — minimizes literal count but can produce gates with very high Fan-in.

Two levels means: AND gates feeding an OR (SOP) or OR gates feeding an AND (POS). Every output passes through exactly two gates of logic. Predictable, fast, but each gate may have many inputs.

Multilevel means: more stages of smaller gates. Slower per output (more gate delays in series), but each stage is small enough to manufacture cleanly and to fit in FPGA LUTs.

When to factor

Two reasons to leave the two-level form:

1. Fan-in problem. A two-level circuit might require a 12-input AND or a 16-input OR, both impractical in CMOS or LUT-based FPGAs. Factoring reduces fan-in at the cost of latency.

2. Gate count. Even when fan-in is OK, factoring can extract common subexpressions and reduce the total transistor count, because shared factors are computed once and reused. This can go the other way too: the worked example below trades 5 gates with max fan-in 4 for 6 gates with max fan-in 2, so total gate count goes up while individual gates shrink. Whether factoring saves transistors depends on the specifics.

Worked example

Start from this SOP:

$f=x_1{x}_3{x}_6+x_1{x}_4{x}_5{x}_6+x_2{x}_3{x}_7+x_2{x}_4{x}_5{x}_7$

Two levels need: four ANDs (fan-in 3, 4, 3, 4) feeding a 4-input OR. Total: 5 gates, max fan-in 4.

Factor by spotting that $x_3$ and $x_4{x}_5$ recur, as do $x_1{x}_6$ and $x_2{x}_7$:

$f=x_1{x}_6(x_3+x_4{x}_5)+x_2{x}_7(x_3+x_4{x}_5)$

Both terms share $(x_3+x_4{x}_5)$. Pull it out:

$f=(x_1{x}_6+x_2{x}_7)(x_3+x_4{x}_5)$

Now you need:

• One AND for $x_4{x}_5$.
• One OR for $x_3+x_4{x}_5$.
• Two ANDs for $x_1{x}_6$ and $x_2{x}_7$.
• One OR for $x_1{x}_6+x_2{x}_7$.
• One AND for the final product.

That’s 6 gates with max fan-in 2 — but three levels deep instead of two. Two LUTs in an FPGA could handle it (each LUT being itself a multi-input gate).

How synthesis tools do it

Industrial tools (Synopsys Design Compiler, Vivado, Quartus) start from a behavioral description, generate a two-level form internally, then iteratively apply factoring transformations (Boolean algebra identities, common-cube extraction, kernel extraction) to reduce gate count and meet timing constraints. The result is usually multilevel — the two-level form is rarely optimal once technology constraints (LUT size, gate library, target frequency) are taken into account.

For a small hand-design, you can usually find a useful factoring by inspection — look for repeated subexpressions across product terms.

The trade-off remains fundamental: each level you add costs one more gate delay in the longest signal path. If you have spare clock period, factor freely; if you’re chasing maximum frequency, keep it shallow.