Challenge Problems: Multi-Level Gate Circuits
These challenge problems test deeper understanding. Only final answers are provided — work through each problem on your own.
Challenge 1: Convert a 3-Level Circuit to All-NAND
Convert the following 3-level AND-OR-AND expression to an equivalent all-NAND implementation. State the total number of NAND gates required (including any inverters implemented as single-input NANDs).
Show Answer
Multi-level NAND implementation:
- Level 1: \(\overline{AB}\), \(\overline{CD}\), \(\overline{FG}\) — 3 NAND gates
- Level 2: \(AB + CD = \overline{\overline{AB} \cdot \overline{CD}}\) — 1 NAND gate; for \(E + FG\), need \(E' = \overline{E}\) via inverter (1 NAND gate), then \(\overline{E' \cdot \overline{FG}}\) — 1 NAND gate
- Level 3: AND the two Level 2 results using NAND + NAND inverter — 2 NAND gates
Total: 8 NAND gates (including inverters as single-input NANDs)
Challenge 2: Gate Count Comparison — AND-OR vs NAND-NAND
For the function \(F(A, B, C, D) = \sum m(1, 3, 5, 7, 8, 12, 13)\), find the minimum SOP expression, then implement it as:
(a) AND-OR circuit (b) NAND-NAND circuit
Compare the total gate counts for each implementation.
Show Answer
Minimum SOP (via K-map):
Minterms: 1(0001), 3(0011), 5(0101), 7(0111), 8(1000), 12(1100), 13(1101)
- \(\overline{A}\,D\) covers {1, 3, 5, 7}
- \(A\,B\,\overline{C}\) covers {12, 13}
- \(A\,\overline{B}\,\overline{C}\,\overline{D}\) covers {8}
(a) AND-OR: 3 AND gates + 1 OR gate + 3 NAND inverters (for \(\overline{A}\), \(\overline{B}\), \(\overline{C}\), \(\overline{D}\) — some shared) = 7 gates
(b) NAND-NAND: 3 NAND gates + 1 NAND output + 3 NAND inverters = 7 gates
Gate counts are identical — NAND-NAND requires the same number of gates as AND-OR for any two-level implementation.
Challenge 3: Factor a Complex SOP into Multi-Level Form
Factor the following SOP expression into a multi-level form that reduces the total literal count:
State the original literal count and the reduced literal count.
Show Answer
Original literal count: \(4 + 4 + 4 + 4 + 4 = 20\) literals
Factored form:
Reduced literal count: \(A, B, C, D, E, \overline{C}, G, H, \overline{A}, \overline{B}, D, E = 12\) literals
Multi-level factorization saves 8 literals (from 20 to 12).
Challenge 4: NOR-Only Implementation
Implement the following function using only NOR gates. State the number of NOR gates needed (including any used as inverters).
Show Answer
NOR implementation using \(X \cdot Y = \overline{\overline{X} + \overline{Y}}\):
- Gate 1: \(A \text{ NOR } B = \overline{A+B}\)
- Gate 2: \(C \text{ NOR } C = \overline{C}\) (inverter)
- Gate 3: \(\overline{C} \text{ NOR } D = \overline{\overline{C}+D}\)
- Gate 4: \(\text{G1} \text{ NOR } \text{G3} = \overline{\overline{A+B} + \overline{\overline{C}+D}} = (A+B)(\overline{C}+D) = F\)
Gate 4 uses the AND-from-NOR identity: the NOR of the complements equals the AND of the originals.
Total: 4 NOR gates
Challenge 5: Bubble Pushing Through a 3-Level Circuit
A circuit implements the following using a mix of AND, OR, NAND, and NOR gates:
Use bubble pushing to simplify, then convert to an all-NAND implementation. State the final expression and gate count.
Show Answer
Simplification:
All-NAND implementation using \(F = \overline{\overline{AB} \cdot \overline{C} \cdot \overline{D} \cdot \overline{E}}\):
- Gate 1: \(A \text{ NAND } B = \overline{AB}\)
- Gate 2: \(C \text{ NAND } C = \overline{C}\) (inverter)
- Gate 3: \(D \text{ NAND } D = \overline{D}\) (inverter)
- Gate 4: \(E \text{ NAND } E = \overline{E}\) (inverter)
- Gate 5: 4-input NAND\((\text{G1}, \overline{C}, \overline{D}, \overline{E}) = F\)
Total: 5 NAND gates (1 two-input + 3 inverters + 1 four-input)
Challenge 6: Critical Path Delay Calculation
A circuit implements $F = (AB + CD)(E + F)$ using 2-input gates only. Each gate has a propagation delay of 2 ns. Calculate the critical path delay for the multi-level implementation. Then find a 2-level SOP form and compare the delay.
Show Answer
Multi-level: Level 1: AND(A,B), AND(C,D), OR(E,F). Level 2: OR(AB,CD). Level 3: AND(result, E+F). → 3 levels × 2 ns = 6 ns.
Two-level SOP: \(F = ABE + ABF + CDE + CDF\) → 2 levels = 4 ns, but uses 4 AND gates + 1 OR gate (5 gates vs 5 gates). Faster circuit, same gate count.
Challenge 7: Fan-In Limitation with 2-Input NAND
A technology library has only 2-input NAND gates. Implement the 4-input AND function $F = ABCD$ using only 2-input NAND gates. What is the minimum number of gates, and how many levels does the circuit have?
Show Answer
Level 1: \(G_1 = \overline{AB}\), \(G_2 = \overline{CD}\) (2 gates)
Level 2: \(G_3 = \overline{G_1 \cdot G_2} = \overline{\overline{AB} \cdot \overline{CD}} = AB + CD\) (1 gate — but this gives OR, not AND!)
Correct approach: \(G_1 = \overline{AB}\), invert: \(G_2 = \overline{G_1 \cdot G_1} = AB\), similarly \(G_4 = CD\), then \(G_5 = \overline{G_2 \cdot G_4}\), \(F = \overline{G_5 \cdot G_5}\).
Total: 5 NAND gates, 4 levels. The NAND-NAND cascade naturally produces AND at even-numbered output levels.
Challenge 8: Factoring for Shared Subexpressions
Two functions share inputs: $F_1 = AC + BC + \overline{A}\overline{B}D$ and $F_2 = AC + BC + ABD$. Factor these to maximize sharing of common subexpressions. What is the total gate count for implementing both functions with sharing vs without?
Show Answer
Both share \(AC + BC = C(A+B)\). Let \(S = C(A+B)\).
\(F_1 = S + \overline{A}\,\overline{B}D\), \(F_2 = S + ABD\)
With sharing: 2 gates for S + 2 inverters + 2 AND + 2 OR = 8 gates. Without sharing: Each function independently needs 5-6 gates = ~12 gates. Sharing saves ~33%.