This chapter goes beyond the two-level SOP/POS minimization of Chapter 2 into multilevel logic synthesis and advanced optimization techniques used in real CAD tools. Factoring, functional decomposition, and multilevel NAND/NOR circuit synthesis are presented as methods to reduce circuit cost when fan-in or other constraints apply. Alternative representations of logic functions are introduced: the cubical representation (using cubes and covers), and binary decision diagrams (BDDs), which are used extensively in modern CAD tools for verification and optimization. The Quine-McCluskey tabular minimization method is presented as an algorithmic alternative to Karnaugh maps that can handle functions with many variables. A cubical technique for minimization is also covered. Practical considerations for dealing with very large functions are discussed.
本章從第 2 章的兩層 SOP/POS 最小化進一步推廣到多層邏輯合成 (multilevel logic synthesis)，介紹現代 CAD 工具實際使用的進階最佳化技術。因式分解 (factoring)、功能分解 (functional decomposition)，以及 NAND/NOR 多層電路合成被作為在扇入 (fan-in) 或其他限制下降低電路成本的方法。本章還介紹邏輯函式的替代表示法：立方體表示 (cubical representation) 使用 cube 與 cover 描述函式；二元決策圖 (BDD, binary decision diagram) 則在現代 CAD 工具中廣泛用於驗證與最佳化。Quine-McCluskey 表格化最小化法則是一種能處理多變數函式的演算法替代方案——當卡諾圖 (Karnaugh map) 變得不切實際時可改用。本章亦介紹立方體最小化技術，並討論處理超大型函式時的實務考量。
Q-M minimizes any Boolean function in two phases:
Below is a worked example with $f(A,B,C) = \sum m(0,1,3,7)$. Click each phase to expand.
| Group | Minterm | $ABC$ |
|---|---|---|
| 0 | $m_0$ | 000 |
| 1 | $m_1$ | 001 |
| 2 | $m_3$ | 011 |
| 3 | $m_7$ | 111 |
Each row is a minterm where $f=1$. Grouping by 1-count means only adjacent groups can possibly merge — pairs across non-adjacent groups always differ in at least 2 bits.
Compare each minterm in group $k$ against each in group $k+1$. If the two binary patterns differ in exactly one position, replace that bit with "−":
Each merged pair is a 2-cube — covers two minterms with one literal eliminated. Mark both source minterms as "used".
Two 2-cubes combine if they have the same dash position AND differ in exactly one of the remaining bits.
No further combination possible. All three 2-cubes are prime implicants. If any 2-cube had been combined further, only the larger result would be prime.
Take a 4-variable function $f(x_1, x_2, x_3, x_4) = \sum m(0, 1, 4, 5)$. The four minterms in binary:
| Minterm | $x_1 x_2 x_3 x_4$ |
|---|---|
| $m_0$ | 0000 |
| $m_1$ | 0001 |
| $m_4$ | 0100 |
| $m_5$ | 0101 |
Step 1 — pair minterms into 2-cubes (one bit changes per pair):
Step 2 — try to combine the 2-cubes into 4-cubes:
Attempt A: $000{-}$ + $010{-}$
Attempt B: $0{-}00$ + $0{-}01$
Counter-attempt: $000{-}$ + $0{-}00$ — does this combine?
Result: the 4-cube $0{-}0{-}$ corresponds to the prime implicant $\overline{x_1}\,\overline{x_3}$ (only $x_1=0$ and $x_3=0$ are fixed). One 4-input AND gate replaces what would otherwise be four 2-input AND gates and a 4-input OR — that's the cost saving the merger produces.
K-map sanity-check. On a 4-variable K-map with rows $x_1 x_2$ and columns $x_3 x_4$, the four minterms $m_0, m_1, m_4, m_5$ all sit in the $x_3=0$ column-pair AND the $x_1=0$ row-pair — a clean $2\times 2$ quad. The cube $0{-}0{-}$ encodes exactly that quad: $x_1=0$ row, $x_3=0$ column, $x_2$ and $x_4$ both free.
Pattern recognition tip: after Phase 1b, sort your 2-cubes by dash position. Cubes with different dash positions are guaranteed not to combine, so you only need to check pairs within each dash-position group. This is what makes Q-M's tabular approach efficient compared to brute-force pairwise checks.
Rows = prime implicants, columns = original minterms. ✓ marks where the prime covers that minterm.
| Prime | Term | $m_0$ | $m_1$ | $m_3$ | $m_7$ |
|---|---|---|---|---|---|
| $P_1$ | $00{-}$ = $\overline{A}\,\overline{B}$ | ✓ | ✓ | ||
| $P_2$ | $0{-}1$ = $\overline{A}\,C$ | ✓ | ✓ | ||
| $P_3$ | $-11$ = $B\,C$ | ✓ | ✓ |
$m_0$ has only one ✓ (in $P_1$) → $P_1$ is essential.
$m_7$ has only one ✓ (in $P_3$) → $P_3$ is essential.
After picking $P_1, P_3$: $m_0, m_1, m_3, m_7$ all covered. $P_2$ is redundant.
The minimum-cost SOP is:
$$f = \overline{A}\,\overline{B} + B\,C$$2 product terms, 4 literals total + one 2-input OR. Q-M guarantees this is optimal among SOP realizations.
Why Q-M scales: a K-map needs $2^n$ cells (32 for 5 vars, 64 for 6). Q-M's table size is bounded by the number of actual minterms — typically far smaller than $2^n$. Q-M also generalizes naturally to don't-cares (treat them as minterms during Phase 1, then exclude them from the cover requirement in Phase 2) and to multi-output minimization. CAD tools use a hashed/bitmask variant of Q-M (or its successor Espresso) under the hood.
f = x₁x₃ + x₁x₄ + x₂x₃ + x₂x₄ to produce a multilevel implementation. What is the cost saving over the SOP form?f(x₁,x₂,x₃,x₄) = Σm(0,1,2,5,6,7,8,9,14).f = x₁x₂ + x̄₁x₃ with variable ordering x₁ < x₂ < x₃.f(x₁,...,x₅) = Σm(1,2,7,9,10,18,19,25,31) + D(0,15,20,26). Compare with the best SOP.