Multilevel Logic

Beyond two-level logic

Karnaugh maps and the Quine-McCluskey method produce two-level circuits: either SOP (AND plane feeding an OR gate) or POS (OR plane feeding an AND gate). Two-level implementations have a predictable worst-case delay (2 gate delays) but can require gates with high fan-in and can be wasteful of silicon area.

Multilevel logic interleaves AND and OR gates in a tree structure. This trades increased delay for reduced gate count and more practical fan-in requirements.

Building larger gates

A 5-input AND gate can be built from four 2-input AND gates (in a tree: two pairs combine, then a third combines those results). The delay increases from 1 to 3 gate delays, but 2-input AND gates are standard cells readily available in any logic family.

Similarly, a 4-input OR required by a K-map solution can be built from three 2-input OR gates. In general, an n-input gate can be constructed from n-1 2-input gates with delay proportional to ⌈log2 n⌉.

Common expression elimination

When multiple outputs share sub-expressions, computing the shared sub-expression once and reusing the result reduces overall gate count. This is a key multilevel optimisation.

Example: Consider three functions:

$f = a \cdot b \cdot c + a \cdot b \cdot d$ $g = a \cdot b \cdot c + a \cdot b \cdot e$ $h = a \cdot b \cdot d + a \cdot b \cdot e$

A two-level SOP implementation would use six 3-input AND gates and three 2-input OR gates. By factoring:

Let X = a · b. Then:

$f = X \cdot c + X \cdot d = X \cdot (c + d)$ $g = X \cdot c + X \cdot e = X \cdot (c + e)$ $h = X \cdot d + X \cdot e = X \cdot (d + e)$

The implementation now uses one 2-input AND (X), three 2-input ORs (c+d, c+e, d+e), and three 2-input ANDs for the final outputs — a substantial reduction from the original two-level design.

Factoring for gate reduction

General principle: factor expressions to isolate common terms.

Example: Z = a · b + a · c + b · c

Factor a from the first two terms:

$Z = a \cdot (b + c) + b \cdot c$

This reduces from three 2-input ANDs + one 3-input OR to two 2-input ANDs + one 2-input OR + one 2-input OR (or one AND, one OR, one AND-OR combination). In this case the expression is the carry-out of a full adder, which can be implemented in two levels (a·b + (a⊕b)·cin) or in the factored form shown.

Trade-offs

Aspect	Two-level	Multilevel
Delay	Fixed (2 gates)	Variable (≥ 2), typically larger
Gate count	Can be high	Reduced through factoring
Fan-in	Can be large	Bounded by 2-input gates
Wire count	Higher (no sharing)	Lower (shared sub-expressions)
Design effort	Systematic (K-maps, Q-M)	Heuristic, experience-based

Multilevel optimisation is more of an art than two-level minimisation. Modern synthesis tools (used with HDLs and FPGA/ASIC design flows) perform multilevel optimisation automatically using algorithms like algebraic factoring and common sub-expression extraction.

The key principle to remember: sharing sub-expressions reduces total gate count, at the cost of increased logical depth (delay). The designer must choose based on whether speed or area is the primary constraint.