Boolean optimization rewrites logic to shorten paths or share terms. Whether it helps depends on the design, so no rewrite always wins.
Question | Precise answer | Follow-up probe | Common wrong answer |
|---|---|---|---|
When does restructuring Boolean logic help? | When it shortens the critical path or shares common terms; it can also grow area, so the gain varies by design. | Name a case where it hurts. | Optimization always reduces area and delay. |
What does technology mapping choose? | A cover of library cells for the logic with the lowest cost under the active constraints; the result varies by library and constraints. | Why does one RTL map differently for speed versus area? | There is one correct gate netlist per RTL. |
How do you compare two mappings by hand? | Sum cell count times cell area in teaching-library units; the worked block below totals 23 units. | Recompute it if the MUX2 becomes two NAND2 and an INV. | Count the gates and ignore their sizes. |
Areas below are units of the fictional teaching library course.lib, not a process. The checker at the end of this lesson recomputes both totals.
area in teaching-library units (course.lib EXAMPLE areas, not a process):
block: 4 NAND2, 2 INV, 1 MUX2, 1 DFF
area = 4 x 2 + 2 x 1 + 1 x 5 + 1 x 8
= 8 + 2 + 5 + 8 = 23 area units
second block: 2 XOR2, 3 NAND2, 2 DFF
area = 2 x 5 + 3 x 2 + 2 x 8
= 10 + 6 + 16 = 32 area unitsA select tree over N inputs needs depth ceiling of log2 of N. The program below proves the quoted areas and depths.
16:1 mux from 2:1 MUX2 cells (EXAMPLE structure):
levels = ceiling of log2(16) = 4
cells = 16 - 1 = 15
5:1 mux: levels = ceiling of log2(5) = 3, since 2^2 = 4 < 5 <= 8 = 2^3import sys
AREA = {"INV": 1, "NAND2": 2, "MUX2": 5, "DFF": 8, "XOR2": 5}
def block_area(counts):
total = 0
for k in counts:
total = total + AREA[k] * counts[k]
return total
def tree_depth(n):
d = 0
p = 1
while p < n:
p = p * 2
d = d + 1
return d
checks = [
(block_area({"NAND2": 4, "INV": 2, "MUX2": 1, "DFF": 1}), 23),
(block_area({"XOR2": 2, "NAND2": 3, "DFF": 2}), 32),
(tree_depth(16), 4),
(tree_depth(5), 3),
(16 - 1, 15),
]
for i in range(len(checks)):
got, want = checks[i]
if got != want:
print("FAIL: check " + str(i + 1) + " got " + str(got) + " want " + str(want))
sys.exit(1)
print("PASS: areas 23 and 32 with mux depths 4 and 3 confirmed")Two NAND2 give 4 units and one INV gives 1, so the replacement is 5 units and the total stays 23.
Three levels, since 4 is below 5 and 8 covers it: the ceiling of log2 of 5 is 3.