End-of-Unit Problems: Multi-Level Gate Circuits
Work through these problems to reinforce your understanding of universal gates, NAND/NOR conversions, bubble pushing, and multi-level circuit design.
Section A: Universal Gate Proofs (4 problems)
Problem 1
Show how to implement the following functions using only NAND gates:
a) NOT (inverter) b) AND c) OR d) XOR
Show Solution
a) NOT from NAND: Connect both inputs together.
b) AND from NAND: Use one NAND, then invert with another.
Total: 2 NAND gates.
c) OR from NAND: Invert each input, then NAND.
Total: 3 NAND gates.
d) XOR from NAND: Let \(P = A \text{ NAND } B\). Then:
Total: 4 NAND gates.
Problem 2
Show how to implement the following functions using only NOR gates:
a) NOT (inverter) b) OR c) AND d) XNOR
Show Solution
a) NOT from NOR: Connect both inputs together.
b) OR from NOR: Use one NOR, then invert with another.
Total: 2 NOR gates.
c) AND from NOR: Invert each input, then NOR.
Total: 3 NOR gates.
d) XNOR from NOR: Let \(P = A \text{ NOR } B\). Then:
Compute \(P = A \text{ NOR } B\), then \(Q = P \text{ NOR } A\), \(R = P \text{ NOR } B\), and finally invert: \(S = Q \text{ NOR } R\), \(\text{XNOR} = S \text{ NOR } S\).
Total: 5 NOR gates.
Problem 3
Prove that a 2-input NAND gate is universal by showing how many NAND gates are needed for each of the 16 possible two-input Boolean functions.
Show Solution
| Function | Expression | NAND Gates |
|---|---|---|
| \(F_0 = 0\) | Constant 0 | 2 |
| \(F_1 = AB\) | AND | 2 |
| \(F_2 = AB'\) | Inhibition | 2 |
| \(F_3 = A\) | Identity | 0 |
| \(F_4 = A'B\) | Inhibition | 2 |
| \(F_5 = B\) | Identity | 0 |
| \(F_6 = A \oplus B\) | XOR | 4 |
| \(F_7 = A + B\) | OR | 3 |
| \(F_8 = (A+B)'\) | NOR | 4 |
| \(F_9 = (A \oplus B)'\) | XNOR | 5 |
| \(F_{10} = B'\) | NOT | 1 |
| \(F_{11} = A + B'\) | Implication | 3 |
| \(F_{12} = A'\) | NOT | 1 |
| \(F_{13} = A' + B\) | Implication | 3 |
| \(F_{14} = (AB)'\) | NAND | 1 |
| \(F_{15} = 1\) | Constant 1 | 2 |
Every function is achievable, proving NAND universality.
Problem 4
Design a half adder using: a) Only NAND gates b) Only NOR gates
Show Solution
Half adder equations: \(\text{Sum} = A \oplus B\), \(\text{Carry} = AB\)
a) NAND implementation:
Let \(P = A \text{ NAND } B\)
- Sum: \((A \text{ NAND } P) \text{ NAND } (B \text{ NAND } P)\)
- Carry: \(P \text{ NAND } P = ((AB)')' = AB\)
Total: 5 NAND gates (1 shared + 2 for Sum + 2 for Carry)
b) NOR implementation:
- \(A' = A \text{ NOR } A\), \(B' = B \text{ NOR } B\), \(P = A \text{ NOR } B\)
- Sum: \((A' \text{ NOR } P) \text{ NOR } (B' \text{ NOR } P)\)
- Carry: \((A' \text{ NOR } B')\) then invert with self-NOR
Total: 8 NOR gates
Section B: AND-OR to NAND Conversion (4 problems)
Problem 5
Convert the following SOP expression to a NAND-only implementation. Draw the circuit and count the number of gates.
Show Solution
Apply double inversion to the SOP form:
Each \(\overline{XY}\) is a NAND, and the outer inversion of an AND is also a NAND.
NAND-only circuit:
- Gate 1: \(A \text{ NAND } B = \overline{AB}\)
- Gate 2: \(C \text{ NAND } D = \overline{CD}\)
- Gate 3: \(E \text{ NAND } E = E'\) (NAND as inverter for the single literal)
- Gate 4: 3-input NAND of Gates 1, 2, 3 outputs \(= F\)
Total: 4 gates (3 two-input NANDs + 1 three-input NAND)
Problem 6
Convert \(F = A'BC + AB'C + ABC'\) to a NAND-only implementation.
Show Solution
Step 1 — Generate complements (NAND as inverter):
- Gate 1: \(A \text{ NAND } A = A'\)
- Gate 2: \(B \text{ NAND } B = B'\)
- Gate 3: \(C \text{ NAND } C = C'\)
Step 2 — Product terms (3-input NANDs):
- Gate 4: \(\text{NAND}(A', B, C) = \overline{A'BC}\)
- Gate 5: \(\text{NAND}(A, B', C) = \overline{AB'C}\)
- Gate 6: \(\text{NAND}(A, B, C') = \overline{ABC'}\)
Step 3 — Output (3-input NAND acts as OR of complements):
- Gate 7: \(\text{NAND}(\text{G4}, \text{G5}, \text{G6}) = \overline{\overline{A'BC} \cdot \overline{AB'C} \cdot \overline{ABC'}} = F\)
Total: 7 NAND gates (3 inverters + 3 three-input + 1 three-input)
Problem 7
Convert the following POS circuit to use only NAND gates:
Show Solution
This is a cross conversion (POS → NAND). Use De Morgan's theorem:
Implement \(A+B = \overline{A' \cdot B'} = A' \text{ NAND } B'\):
- Gate 1: \(A \text{ NAND } A = A'\)
- Gate 2: \(B \text{ NAND } B = B'\)
- Gate 3: \(C \text{ NAND } C = C'\)
- Gate 4: \(D \text{ NAND } D = D'\)
- Gate 5: \(A' \text{ NAND } B' = \overline{A'B'} = A + B\)
- Gate 6: \(C' \text{ NAND } D' = \overline{C'D'} = C + D\)
- Gate 7: \(\text{G5} \text{ NAND } \text{G6} = \overline{(A+B)(C+D)} = F'\)
- Gate 8: \(\text{G7} \text{ NAND } \text{G7} = F\)
Total: 8 NAND gates (cross conversion requires more gates than natural conversion)
Problem 8
A function is given as \(F = AB + A'C + BC\).
a) Simplify using Boolean algebra b) Implement simplified form using NAND gates only
Show Solution
a) Simplification using the consensus theorem (\(XY + X'Z + YZ = XY + X'Z\)):
The term \(BC\) is the redundant consensus term and can be removed.
b) NAND implementation of \(F = AB + A'C\):
- Gate 1: \(A \text{ NAND } A = A'\)
- Gate 2: \(A \text{ NAND } B = \overline{AB}\)
- Gate 3: \(A' \text{ NAND } C = \overline{A'C}\)
- Gate 4: \(\text{G2} \text{ NAND } \text{G3} = \overline{\overline{AB} \cdot \overline{A'C}} = AB + A'C = F\)
Total: 4 NAND gates
Section C: OR-AND to NOR Conversion (4 problems)
Problem 9
Convert the following POS expression to a NOR-only implementation:
Show Solution
Apply double inversion to the POS form:
Each \(\overline{X+Y}\) is a NOR, and the outer inversion of an OR is also a NOR.
NOR-only circuit:
- Gate 1: \(A \text{ NOR } B = \overline{A+B}\)
- Gate 2: \(C \text{ NOR } D = \overline{C+D}\)
- Gate 3: \(E \text{ NOR } G = \overline{E+G}\)
- Gate 4: 3-input NOR of Gates 1, 2, 3 outputs \(= F\)
Total: 4 NOR gates (3 two-input + 1 three-input)
Problem 10
Convert \(F = (A' + B)(A + C')\) to NOR-only implementation.
Show Solution
This POS has complemented variables, requiring extra NOR inverters.
Step 1 — Generate complements:
- Gate 1: \(A \text{ NOR } A = A'\)
- Gate 2: \(C \text{ NOR } C = C'\)
Step 2 — Form OR terms (NOR + self-NOR to invert):
Since NOR naturally inverts, we form each sum, then complement:
- Gate 3: \(A' \text{ NOR } B = \overline{A'+B}\)
- Gate 4: \(A \text{ NOR } C' = \overline{A+C'}\)
- Gate 5: \(\text{G3} \text{ NOR } \text{G4} = \overline{\overline{A'+B} + \overline{A+C'}} = (A'+B)(A+C') = F\)
Total: 5 NOR gates (2 inverters + 2 first-level NOR + 1 output NOR)
Problem 11
Design the carry output of a full adder using only NOR gates. The carry equation is \(C_{out} = AB + C_{in}(A + B)\).
Show Solution
Rewrite the carry in a form suited to NOR implementation by applying De Morgan's:
NOR implementation using the AND-from-NOR pattern (\(X \cdot Y = (X' + Y')'\)):
- Gate 1: \(A \text{ NOR } B = \overline{A+B}\)
- Gate 2: \(A \text{ NOR } A = A'\)
- Gate 3: \(B \text{ NOR } B = B'\)
- Gate 4: \(A' \text{ NOR } B' = \overline{A'+B'} = AB\)
- Gate 5: \(\text{G1} \text{ NOR } \text{G1} = A+B\)
-
Gate 6: Combine \(C_{in}\) and \((A+B)\) for AND: need \(C_{in}' \text{ NOR } \overline{A+B}\)
- Gate 6: \(C_{in} \text{ NOR } C_{in} = C_{in}'\)
- Gate 7: \(C_{in}' \text{ NOR } \text{G1} = \overline{C_{in}' + \overline{A+B}} = C_{in} \cdot (A+B)\)
-
Combine the two products for OR:
- Gate 8: \(\text{G4} \text{ NOR } \text{G4} = \overline{AB}\)... (this is getting complex)
Practical count: The carry output requires approximately 9 NOR gates. This demonstrates why NOR-only implementations of SOP functions (cross conversions) are less efficient than the natural NOR-NOR approach for POS forms.
Problem 12
Show that \((A + B)' = A' \cdot B'\) (De Morgan's theorem) by constructing both sides using only NOR gates and verifying they produce identical circuits.
Show Solution
Left side: \((A + B)' = A \text{ NOR } B\)
This is 1 NOR gate — the NOR operation directly computes the complement of OR.
Right side: \(A' \cdot B'\)
To compute AND using NOR gates, use the identity \(X \cdot Y = (X' + Y')'\):
- Gate 1: \(A \text{ NOR } A = A'\)
- Gate 2: \(B \text{ NOR } B = B'\)
- Gate 3: $(A')' = $ Gate 1 output NOR'd with itself \(= A\)
- Gate 4: $(B')' = $ Gate 2 output NOR'd with itself \(= B\)
- Gate 5: \(A \text{ NOR } B = (A+B)' = A' \cdot B'\)
Both sides reduce to the same single NOR gate \(A \text{ NOR } B\), confirming De Morgan's theorem: \(\overline{A+B} = \overline{A} \cdot \overline{B}\).
Section D: Bubble Pushing and Analysis (4 problems)
Problem 13
Apply bubble pushing to convert this AND-OR circuit to all-NAND:
\(F = AB + CD\) (two AND gates feeding one OR gate)
Show Solution
Step 1: Insert bubble pairs on each connecting wire (double inversion = no change to function).
Step 2: Absorb the left bubble of each pair into the AND gate output:
Step 3: Absorb the right bubble of each pair into the OR gate input. OR with input bubbles = NAND (De Morgan's):
Result: 3 NAND gates total:
- \(\text{NAND}(A, B)\)
- \(\text{NAND}(C, D)\)
- \(\text{NAND}(\text{result}_1, \text{result}_2) = F\)
Problem 14
Analyze the following NAND-only circuit and find the output expression:
Gate 1: NAND(A, B) Gate 2: NAND(A, C) Output: NAND(G1, G2) = F
Show Solution
Gate-by-gate analysis:
Simplify using De Morgan's:
Output expression: \(F = A(B + C) = AB + AC\)
Problem 15
Determine whether the following NAND circuit implements \(F = A'B + AB'\) (XOR):
Gate 1: NAND(\(A'\), \(B\)) Gate 2: NAND(\(A\), \(B'\)) Output: NAND(G1, G2) = F
Show Solution
Analysis:
Apply De Morgan's:
Yes — this circuit implements the XOR function. This is in fact the standard 3-gate XOR implementation when \(A'\) and \(B'\) are available, or a 5-gate implementation when NAND inverters generate the complements.
Problem 16
Convert the following multi-level circuit to use only 2-input NAND gates:
Show Solution
Expand to SOP: \(F = AB + ACD\)
NAND-NAND implementation:
- Gate 1: \(A \text{ NAND } B = \overline{AB}\)
- Gate 2: \(C \text{ NAND } D = \overline{CD}\)
- Gate 3: \(\text{G2} \text{ NAND } \text{G2} = CD\) (invert to recover \(CD\))
- Gate 4: \(A \text{ NAND } \text{G3} = \overline{ACD}\)
- Gate 5: \(\text{G1} \text{ NAND } \text{G4} = \overline{\overline{AB} \cdot \overline{ACD}} = AB + ACD = F\)
Total: 5 two-input NAND gates
Alternative (keeping original structure): Use \(B + CD = \overline{B' \cdot \overline{CD}} = B' \text{ NAND } \overline{CD}\):
- Gate 1: \(B \text{ NAND } B = B'\)
- Gate 2: \(C \text{ NAND } D = \overline{CD}\)
- Gate 3: \(B' \text{ NAND } \overline{CD} = B + CD\)
- Gate 4: \(A \text{ NAND } \text{G3} = \overline{A(B+CD)}\)
- Gate 5: \(\text{G4} \text{ NAND } \text{G4} = F\)
Also 5 two-input NAND gates.
Section E: Multi-Level Optimization (4 problems)
Problem 17
The function \(F = ABCD + ABCE + ABDE + ACDE\) can be implemented in two-level or factored form.
a) How many gates for two-level SOP?
b) Factor the expression and implement
c) Compare gate counts
Show Solution
a) Two-level SOP: 4 four-input AND gates + 1 four-input OR gate = 5 gates, 16 gate inputs
b) Factoring:
Group by common terms:
Verify: \(ABC(D+E) = ABCD + ABCE\) ✓ and \(ADE(B+C) = ABDE + ACDE\) ✓
Multi-level implementation:
- Level 1: \(D+E\) (OR), \(B+C\) (OR)
- Level 2: \(ABC\) (AND), \(ADE\) (AND)
- Level 3: \(ABC \cdot (D+E)\) (AND), \(ADE \cdot (B+C)\) (AND)
- Level 4: Sum (OR)
Total: 7 gates, 14 gate inputs
c) Comparison:
| Implementation | Gates | Gate Inputs | Levels |
|---|---|---|---|
| Two-level SOP | 5 | 16 | 2 |
| Factored | 7 | 14 | 4 |
Two-level uses fewer gates but higher fan-in. Factored uses fewer total inputs and fits fan-in-limited technologies.
Problem 18
Calculate the propagation delay for a 4-bit ripple carry adder, assuming: AND = 1 ns, OR = 1 ns, XOR = 2 ns.
Show Solution
Full adder delays:
- Sum \(= A \oplus B \oplus C_{in}\): two XOR gates in series = 4 ns
- Carry \(= AB + C_{in}(A \oplus B)\): the carry path from \(C_{in}\) passes through 1 XOR + 1 AND + 1 OR = 4 ns
4-bit ripple carry critical path (\(C_0 \to C_1 \to C_2 \to C_3 \to S_3\)):
| Signal | Ready At |
|---|---|
| \(C_1\) | 4 ns |
| \(C_2\) | 8 ns |
| \(C_3\) | 12 ns |
| \(S_3\) | 12 + 4 = 16 ns |
Total worst-case propagation delay: 16 ns
The critical path passes through 3 carry stages (4 ns each) plus the final sum computation (4 ns).
Problem 19
Design a circuit for \(F = AB + CD + EG + HK\) optimized for:
a) Minimum gate count b) Minimum propagation delay
Show Solution
a) Minimum gate count (4-input OR available):
- 4 two-input AND gates + 1 four-input OR gate = 5 gates
- Delay: 1 AND + 1 OR = 2 gate delays
b) Minimum delay with 2-input gates only:
Use a balanced OR-tree to minimize depth:
- Level 1: 4 AND gates (parallel)
- Level 2: \(\text{OR}(AB, CD)\), \(\text{OR}(EG, HK)\)
- Level 3: \(\text{OR}(\text{Level 2 outputs})\)
Total: 7 gates (4 AND + 3 OR), delay = 3 gate delays
A linear OR chain would take 4 delays; the balanced tree saves one level.
Problem 20
Explain the trade-offs between two-level and multi-level implementations in terms of: propagation delay, gate count, fan-in requirements, and power consumption.
Show Solution
| Factor | Two-Level | Multi-Level |
|---|---|---|
| Delay | Minimum (2 gate delays) | Higher (3+ gate delays) |
| Gate count | Can be high (many product terms) | Often lower (shared sub-expressions) |
| Fan-in | High (many inputs per gate) | Lower (smaller gates) |
| Power | Higher static (wide gates = more transistors) | Lower static, but more switching activity |
| Testability | Easier (fewer levels) | More complex (more reconvergent paths) |
Summary:
- Speed-critical designs → prefer two-level (minimum delay)
- Area-constrained designs → prefer multi-level (shared terms reduce gates)
- Fan-in-limited technologies → multi-level required (standard cells max 4 inputs)
- Power → depends on activity factor and technology; no universal winner
The optimal form depends on the design priority. Always evaluate multiple forms before committing.
Problem Set Summary
| Section | Topics Covered | Problems |
|---|---|---|
| A | Universal Gate Proofs | 4 |
| B | AND-OR to NAND Conversion | 4 |
| C | OR-AND to NOR Conversion | 4 |
| D | Bubble Pushing and Analysis | 4 |
| E | Multi-Level Optimization | 4 |
| Total | 20 |