Unit 7: Multi-Level Gate Circuits

Unit Overview (click to expand)

Welcome to Unit 7, where we move from the idealized world of AND-OR circuits into the practical reality of how digital logic is actually built. In real integrated circuits, the gates of choice are NAND and NOR. Understanding why — and learning how to convert your designs accordingly — is the focus of this unit. NAND and NOR gates are called universal gates because each one can implement any Boolean function. You can build AND, OR, and NOT from NANDs alone, or from NORs alone. This universality matters because NAND and NOR gates are cheaper, faster, and smaller at the transistor level. A two-level SOP circuit transforms directly into a NAND-NAND circuit. The trick is that by De Morgan's theorem, the inversions cancel at the internal connections. The same logic applies to POS expressions, which convert to NOR-NOR circuits. For more complex, multi-level circuits, we use bubble pushing. The idea is to push inversion bubbles through the circuit, converting each gate's type as you go, until every gate is either a NAND or a NOR. You start at the output and work backward, applying De Morgan's theorem at each level. Multi-level circuits introduce additional propagation delay because signals pass through more gate stages. The longest path from input to output — the critical path — determines maximum operating speed. Designers constantly balance gate count, literal count, and delay. **Key Takeaways** 1. NAND and NOR are universal gates — each can implement any Boolean function — and they are the preferred building blocks in real integrated circuits due to their efficiency at the transistor level. 2. SOP expressions convert to NAND-NAND circuits and POS expressions convert to NOR-NOR circuits through systematic application of De Morgan's theorem and the bubble pushing technique. 3. Multi-level circuit design involves balancing gate count, literal count, and propagation delay along the critical path to meet area, power, and speed constraints.

Summary

This unit explores the implementation of Boolean functions using multi-level gate circuits, with particular emphasis on NAND and NOR gate implementations. While two-level AND-OR or OR-AND circuits provide straightforward realizations of Boolean expressions, practical considerations often favor implementations using only NAND gates or only NOR gates due to their universal nature and manufacturing advantages. Students will learn systematic methods for converting SOP and POS expressions to NAND-only and NOR-only implementations, analyze propagation delays in multi-level circuits, and optimize circuits for gate count, literal count, and timing performance.

Concepts Covered

1. Two-Level vs Multi-Level Circuits
2. Universal Gates (NAND and NOR)
3. NAND Gate Universality Proof
4. NOR Gate Universality Proof
5. AND-OR to NAND-NAND Conversion
6. OR-AND to NOR-NOR Conversion
7. Mixed Gate Conversions
8. De Morgan's Theorem in Gate Conversion
9. Bubble Pushing Technique
10. Multi-Level Circuit Analysis
11. Fan-in and Fan-out Constraints
12. Gate Loading Effects
13. Propagation Delay in Multi-Level Circuits
14. Critical Path Analysis
15. Level Reduction Techniques
16. Gate Count Optimization
17. Literal Count vs Gate Count Trade-offs
18. Factoring for Multi-Level Optimization
19. Decomposition Techniques
20. Technology Mapping
21. AOI and OAI Complex Gates
22. Wired Logic Implementations
23. Transmission Gate Circuits
24. Multi-Level Synthesis Tools

Prerequisites

Before studying this unit, students should be familiar with:

• Boolean algebra fundamentals (Unit 2)
• Basic logic gates and their truth tables (Unit 2)
• SOP and POS forms (Unit 4)
• K-map and QM simplification methods (Units 5-6)
• De Morgan's theorems (Unit 2)

---

7.1 Introduction to Multi-Level Circuits

In previous units, we focused primarily on two-level circuit implementations—AND-OR circuits for Sum of Products (SOP) expressions and OR-AND circuits for Product of Sums (POS) expressions. These two-level circuits offer the minimum propagation delay since signals pass through only two gates from input to output. However, two-level implementations can demand gates with impractically many inputs and a large overall gate count, especially for complex functions with many product or sum terms.

Multi-level circuits use more than two levels of logic gates between inputs and outputs. Although they introduce additional gate delays, multi-level circuits provide significant practical advantages that make them the preferred choice in real integrated circuit design.

Circuit Type	Levels	Delay	Gate Count	Fan-in Required
Two-level SOP	2	Minimum	Often high	Can be high
Two-level POS	2	Minimum	Often high	Can be high
Multi-level	3+	Higher	Often lower	Usually lower

Example: Factoring Reduces Complexity

Consider \(F = ABCDE + ABCDF + ABCDG\). A two-level SOP needs three 5-input AND gates and one 3-input OR gate. After factoring:

\(F = ABCD(E + F + G)\) — three levels but smaller gates (max 4-input).

The key advantages of multi-level circuits include:

Reduced gate count

Sharing common sub-expressions

Lower fan-in

Within standard gate library constraints

Better utilization

Most standard cells have 2–4 inputs

Reduced chip area

In VLSI implementations

Practical Consideration

Standard logic families (TTL, CMOS) typically provide gates with a maximum of 2, 3, 4, or 8 inputs. Any function requiring higher fan-in must be decomposed into multi-level form, regardless of the delay penalty.

Diagram: Two-Level vs Multi-Level Comparison

---

7.2 Universal Gates

A gate is called universal (or functionally complete) if any Boolean function can be implemented using only that gate type. Both the NAND gate and the NOR gate are universal. This property has profound practical significance: an entire integrated circuit can be fabricated using only one type of transistor configuration, simplifying manufacturing and reducing cost.

7.2.1 NAND Gate Universality Proof

To prove that the NAND gate is universal, we must show it can implement the three basic operations—NOT, AND, and OR—since any Boolean function can be expressed using these operations.

NOT from NAND: Connect both inputs of a NAND gate to the same signal \(A\):

\[\overline{A \cdot A} = \overline{A}\]

AND from NAND: Cascade two NAND gates. The first computes \(\overline{AB}\); the second inverts it:

\[\overline{\overline{A \cdot B}} = A \cdot B\]

OR from NAND: First invert each input using NAND-as-inverter, then NAND the results. By De Morgan's theorem:

\[\overline{\overline{A} \cdot \overline{B}} = A + B\]

NAND Universality Summary

Operation	NAND Implementation	Gates
NOT \(A\)	\(A \text{ NAND } A\)	1
\(A \cdot B\)	\((A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)\)	2
\(A + B\)	\((A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B)\)	3

7.2.2 NOR Gate Universality Proof

The NOR gate universality proof follows a dual structure. We demonstrate that NOT, OR, and AND can all be built from NOR gates alone.

NOT from NOR: Connect both inputs of a NOR gate to the same signal \(A\):

\[\overline{A + A} = \overline{A}\]

OR from NOR: Cascade two NOR gates. The first computes \(\overline{A+B}\); the second inverts it:

\[\overline{\overline{A + B}} = A + B\]

AND from NOR: First invert each input using NOR-as-inverter, then NOR the results. By De Morgan's theorem:

\[\overline{\overline{A} + \overline{B}} = A \cdot B\]

NOR Universality Summary

Operation	NOR Implementation	Gates
NOT \(A\)	\(A \text{ NOR } A\)	1
\(A + B\)	\((A \text{ NOR } B) \text{ NOR } (A \text{ NOR } B)\)	2
\(A \cdot B\)	\((A \text{ NOR } A) \text{ NOR } (B \text{ NOR } B)\)	3

Duality Principle

Notice the duality: NAND implements AND directly (2 gates) and OR with more effort (3 gates), while NOR implements OR directly (2 gates) and AND with more effort (3 gates). This duality guides the choice of universal gate based on the dominant operation in a given function.

Diagram: NAND Gate Universality — Building AND, OR, NOT from NAND

graph LR
    subgraph NOT["NOT from NAND"]
        A1["A"] --> N1["NAND"]
        A1 --> N1
        N1 --> O1["A'"]
    end

    subgraph AND["AND from NAND"]
        B1["A"] --> N2["NAND"]
        B2["B"] --> N2
        N2 --> N3["NAND<br/>(as NOT)"]
        N3 --> N3
        N3 --> O2["A · B"]
    end

    subgraph OR["OR from NAND"]
        C1["A"] --> N4["NAND<br/>(as NOT)"]
        C1 --> N4
        C2["B"] --> N5["NAND<br/>(as NOT)"]
        C2 --> N5
        N4 --> N6["NAND"]
        N5 --> N6
        N6 --> O3["A + B"]
    end

    style NOT fill:#EEF4FF,stroke:#5A3EED
    style AND fill:#EEF4FF,stroke:#5A3EED
    style OR fill:#EEF4FF,stroke:#5A3EED
    style N1 fill:#FFF7DD,stroke:#F0D87A,color:#333
    style N2 fill:#FFF7DD,stroke:#F0D87A,color:#333
    style N3 fill:#FFF7DD,stroke:#F0D87A,color:#333
    style N4 fill:#FFF7DD,stroke:#F0D87A,color:#333
    style N5 fill:#FFF7DD,stroke:#F0D87A,color:#333
    style N6 fill:#FFF7DD,stroke:#F0D87A,color:#333

Diagram: Universal Gate Implementations

---

7.3 AND-OR to NAND-NAND Conversion

The most common conversion in digital design transforms a two-level AND-OR (SOP) circuit into an equivalent NAND-only implementation. This conversion is direct and elegant, relying on the double inversion principle and De Morgan's theorem.

Conversion Procedure

SOP → NAND-NAND Conversion Steps

Starting with an SOP expression, apply these steps:

1. Write the SOP expression: \(F = AB + CD\)
2. Apply double inversion (which does not change the function): \(F = \overline{\overline{AB + CD}}\)
3. Apply De Morgan's theorem to the inner complement: \(F = \overline{\overline{AB} \cdot \overline{CD}}\)
4. Recognize NAND operations: Each \(\overline{XY}\) is a NAND, and the outer \(\overline{X \cdot Y}\) is also a NAND

Result: \(F = (A \text{ NAND } B) \text{ NAND } (C \text{ NAND } D)\)

Key Insight

The general rule is remarkably simple: replace every AND gate and the OR gate with NAND gates. No additional inverters are needed for a standard two-level SOP form.

This works because the first-level NAND gates each produce the complement of what AND gates would produce, and by De Morgan's theorem, a NAND gate receiving complemented inputs performs the equivalent of OR on the original (uncomplemented) values.

Worked Example: Convert F = XY + X'Z + YZ

\[F = XY + X'Z + YZ\]

\[= \overline{\overline{XY + X'Z + YZ}}\]

\[= \overline{\overline{XY} \cdot \overline{X'Z} \cdot \overline{YZ}}\]

This requires three first-level NAND gates (for \(XY\), \(X'Z\), and \(YZ\)) feeding one second-level NAND gate. Note that \(X'\) is still needed — the complement of \(X\) must be provided by an additional NAND inverter.

Handling Complemented Inputs and Single Literals

Two special cases require attention:

Complemented Variables

Use a NAND gate as an inverter (both inputs tied to \(A\)) to produce \(\overline{A}\).

Single Literal Terms

A single-literal term (e.g., \(A\) in \(F = A + BC\)) must pass through a NAND inverter before the final NAND gate.

Example: F = A + BC

\[F = \overline{\overline{A} \cdot \overline{BC}}\]

This requires: one NAND inverter for \(A\), one 2-input NAND for \(BC\), and one 2-input NAND for the output.

Diagram: AND-OR to NAND-NAND Conversion

---

7.4 OR-AND to NOR-NOR Conversion

Converting a two-level OR-AND (POS) circuit to an equivalent NOR-only implementation is the dual of the NAND-NAND conversion. The procedure mirrors the AND-OR conversion but operates on sum terms instead of product terms.

Conversion Procedure

POS → NOR-NOR Conversion Steps

1. Write the POS expression: \(F = (A+B)(C+D)\)
2. Apply double inversion: \(F = \overline{\overline{(A+B)(C+D)}}\)
3. Apply De Morgan's theorem: \(F = \overline{\overline{A+B} + \overline{C+D}}\)
4. Recognize NOR operations: Each \(\overline{X+Y}\) is a NOR, and the outer \(\overline{X + Y}\) is also a NOR

Result: \(F = (A \text{ NOR } B) \text{ NOR } (C \text{ NOR } D)\)

Key Insight

The general rule: replace every OR gate and the AND gate with NOR gates.

Worked Example: Convert F = (A+B)(A'+C)(B+C')

\[F = (A+B)(A'+C)(B+C')\]

\[= \overline{\overline{(A+B)(A'+C)(B+C')}}\]

\[= \overline{\overline{A+B} + \overline{A'+C} + \overline{B+C'}}\]

Three first-level NOR gates feed one second-level NOR gate. The complemented variables \(A'\) and \(C'\) are generated using NOR-as-inverter gates.

Conversion Summary Table

All Two-Level Conversions

Original Form	Target Form	Conversion Rule	Type
SOP (AND-OR)	NAND-NAND	Replace all gates with NAND	Natural
POS (OR-AND)	NOR-NOR	Replace all gates with NOR	Natural
SOP (AND-OR)	NOR-NOR	Requires added levels + inverters	Cross
POS (OR-AND)	NAND-NAND	Requires added levels + inverters	Cross

Natural vs. Cross Conversions

The first two conversions (natural conversions) are straightforward — the circuit structure directly maps to the target gate type. The latter two (cross conversions) are more involved because the structure does not align naturally, requiring extra gate levels and inverters.

---

7.5 Mixed Gate Conversions

Not all circuits fit neatly into two-level AND-OR or OR-AND structures. Mixed gate conversions handle circuits that contain a combination of AND, OR, NAND, NOR, and NOT gates, converting them to use a single gate type.

Cross Conversions

SOP → NOR-Only

AND-OR does not map directly to NOR-NOR, so additional levels are needed.

For \(F = AB + CD\):

1. De Morgan's on products: \(AB = \overline{\overline{A} + \overline{B}}\)
2. Substitute: \(F = \overline{\overline{A} + \overline{B}} + \overline{\overline{C} + \overline{D}}\)
3. Double inversion for OR: \(F = \overline{\overline{\overline{\overline{A} + \overline{B}} + \overline{\overline{C} + \overline{D}}}}\)

Requires 3 levels of NOR gates + input inverters.

POS → NAND-Only

OR-AND does not map directly to NAND-NAND, so each sum term must be restructured.

For \(F = (A+B)(C+D)\):

1. De Morgan's on sums: \(A+B = \overline{\overline{A} \cdot \overline{B}}\)
2. Substitute: \(F = \overline{\overline{A} \cdot \overline{B}} \cdot \overline{\overline{C} \cdot \overline{D}}\)
3. Double inversion for AND: \(F = \overline{\overline{\overline{\overline{A} \cdot \overline{B}} \cdot \overline{\overline{C} \cdot \overline{D}}}}\)

Requires 3 levels of NAND gates + input inverters.

Design Guideline

Cross conversions (SOP→NOR or POS→NAND) add extra gate levels and inverters. In practice, convert the expression to the form that naturally maps to the target gate type first — convert SOP to POS before implementing with NOR gates, or POS to SOP before implementing with NAND gates.

Key Insight: Natural vs Cross Conversions

Conversion	Levels	Complexity
SOP → NAND-NAND	2	Direct — just replace gates
POS → NOR-NOR	2	Direct — just replace gates
SOP → NOR-only	3+	Cross — requires restructuring with De Morgan's
POS → NAND-only	3+	Cross — requires restructuring with De Morgan's

Rule of thumb: Always prefer the natural conversion. Cross conversions cost extra gates and delay.

---

7.6 De Morgan's Theorem in Gate Conversion

De Morgan's theorems are the mathematical engine behind every gate conversion technique. Understanding how they transform gate types is essential for systematic circuit conversion.

The Two Forms

First Theorem

\[\overline{A \cdot B} = \overline{A} + \overline{B}\]

A NAND gate is equivalent to an OR gate with inverted inputs.

Second Theorem

\[\overline{A + B} = \overline{A} \cdot \overline{B}\]

A NOR gate is equivalent to an AND gate with inverted inputs.

Graphical Interpretation

Each theorem provides two equivalent gate symbols:

Original Gate	De Morgan Equivalent
NAND (AND + output bubble)	OR with input bubbles
NOR (OR + output bubble)	AND with input bubbles
AND (no bubbles)	NOR with input and output bubbles
OR (no bubbles)	NAND with input and output bubbles

Key Takeaway

When you see a gate with a bubble on its output, you can push that bubble to the inputs by changing the gate type (AND ↔ OR), and vice versa. This is the foundation of the bubble pushing technique covered next.

Worked Example: 3-Input NAND Equivalence

Show that a 3-input NAND is equivalent to a 3-input OR with inverted inputs:

\[\overline{ABC} = \overline{A} + \overline{B} + \overline{C}\]

This follows directly from the generalized form of De Morgan's first theorem. In circuit terms, a 3-input NAND gate with inputs \(A\), \(B\), \(C\) produces the same output as a 3-input OR gate receiving \(\overline{A}\), \(\overline{B}\), \(\overline{C}\).

---

7.7 The Bubble Pushing Technique

Bubble pushing is a visual method for converting circuits between gate types by systematically moving inversion "bubbles" through a circuit. It provides an intuitive alternative to algebraic manipulation for gate conversion.

Rules for Bubble Pushing

Three Rules of Bubble Pushing

1. Move a bubble from output to all inputs (or vice versa) while changing the gate type (AND ↔ OR)
2. Paired bubbles cancel: A bubble on a wire's output meeting a bubble on the connected input results in no inversion
3. Unpaired bubbles become inverters: Any bubble that cannot be canceled must be implemented as an explicit inverter at the circuit input

Step-by-Step Example

Worked Example: Convert F = AB + CD to NAND-only

Step 1 — Original AND-OR circuit:

• Gate 1 (AND): inputs \(A\), \(B\) → output \(P_1 = AB\)
• Gate 2 (AND): inputs \(C\), \(D\) → output \(P_2 = CD\)
• Gate 3 (OR): inputs \(P_1\), \(P_2\) → output \(F = P_1 + P_2\)

Step 2 — Push bubbles:

Add a bubble to the output of the OR gate and to both of its inputs. The OR with input bubbles becomes a NAND gate. Also add bubbles to the outputs of the AND gates — they become NAND gates. These output bubbles cancel with the input bubbles of the final gate.

Step 3 — All bubbles paired and cancel. The result is three NAND gates with no remaining inversions.

Extended Example with Single Literal

Worked Example: Convert F = A + BC to NAND-only

Step 1: The OR gate receives single literal \(A\) and product \(BC\).

Step 2: The AND gate for \(BC\) gets an output bubble (becoming NAND). The OR gate gets input bubbles (becoming NAND). The bubble on input \(A\) of the final NAND is unpaired.

Step 3: The unpaired bubble requires a NAND inverter: \(\overline{A}\) enters the final NAND gate.

Result: NAND(\(\overline{A}\), NAND(\(B\), \(C\))) \(= \overline{\overline{A} \cdot \overline{BC}} = A + BC\)

Bubble Pushing Shortcut

For two-level conversions, bubble pushing always yields the same result as the algebraic method: simply replace all gates with the target universal gate type, then add inverters for any remaining unpaired bubbles.

Diagram: Bubble Pushing Rules Flowchart

graph TD
    Start["Start: Identify gate<br/>with output bubble"] --> Step1["Move bubble from<br/>output to ALL inputs"]
    Step1 --> Step2["Change gate type:<br/>AND ↔ OR"]
    Step2 --> Check{"Check each<br/>bubble on<br/>connecting wires"}
    Check -- "Bubble meets<br/>another bubble" --> Cancel["Paired bubbles cancel<br/>(no inversion needed)"]
    Check -- "Bubble has<br/>no partner" --> Inverter["Insert explicit inverter<br/>at that input"]
    Cancel --> Next{"More gates<br/>to convert?"}
    Inverter --> Next
    Next -- Yes --> Start
    Next -- No --> Done["All gates converted<br/>to target type<br/>(NAND or NOR)"]

    style Start fill:#EEF4FF,stroke:#5A3EED,color:#333
    style Step1 fill:#EEF4FF,stroke:#5A3EED,color:#333
    style Step2 fill:#EEF4FF,stroke:#5A3EED,color:#333
    style Check fill:#FFF7DD,stroke:#F0D87A,color:#333
    style Cancel fill:#E7F7E7,stroke:#81C784,color:#333
    style Inverter fill:#FFF0F0,stroke:#E57373,color:#333
    style Next fill:#FFF7DD,stroke:#F0D87A,color:#333
    style Done fill:#E7F7E7,stroke:#2E7D32,color:#333

Diagram: Bubble Pushing Interactive Demo

---

7.8 Multi-Level Circuit Analysis

Analyzing multi-level circuits requires systematically tracing signals through multiple gate layers to derive the output expression and understand timing behavior. This section covers the analytical techniques for evaluating multi-level designs.

7.8.1 Deriving the Boolean Expression

Analysis Procedure

1. Label all gate outputs with intermediate variables (\(G_1\), \(G_2\), etc.)
2. Write the expression for each gate output in terms of its inputs
3. Substitute intermediate expressions to obtain the final output in terms of primary inputs
4. Simplify the result if desired

Worked Example: Three-Level Circuit

• Gate 1 (AND): inputs \(A\), \(B\) → \(G_1 = AB\)
• Gate 2 (OR): inputs \(C\), \(D\) → \(G_2 = C + D\)
• Gate 3 (AND): inputs \(G_1\), \(G_2\) → \(G_3 = G_1 \cdot G_2 = AB(C+D)\)
• Gate 4 (OR): inputs \(G_3\), \(E\) → \(F = G_3 + E = AB(C+D) + E\)

Expanding: \(F = ABC + ABD + E\)

This three-level implementation uses gates with max fan-in of 2, whereas the two-level SOP requires two 3-input AND gates and one 3-input OR gate.

7.8.2 Critical Path and Propagation Delay

Key Concept: Propagation Delay & Critical Path

The propagation delay of a multi-level circuit is determined by the longest path from any input to the output, measured in gate delays. This path is called the critical path.

For a circuit with \(n\) levels, the worst-case propagation delay is:

\[t_{pd(total)} = \sum_{i=1}^{n} t_{pd(gate_i)}\]

where \(t_{pd(gate_i)}\) is the propagation delay of gate \(i\) along the critical path.

Worked Example: Path Delay Analysis

In the circuit above (gates 1→3→4 and 2→3→4):

• Path from \(A\) or \(B\): Gate 1 → Gate 3 → Gate 4 = 3 gate delays
• Path from \(C\) or \(D\): Gate 2 → Gate 3 → Gate 4 = 3 gate delays
• Path from \(E\): Gate 4 = 1 gate delay

The critical path has 3 gate delays. Input \(E\) arrives fastest (1 delay), while \(A\)–\(D\) experience the full 3.

Input	Path	Gate Delays
\(A\)	Gate 1 → Gate 3 → Gate 4	3
\(B\)	Gate 1 → Gate 3 → Gate 4	3
\(C\)	Gate 2 → Gate 3 → Gate 4	3
\(D\)	Gate 2 → Gate 3 → Gate 4	3
\(E\)	Gate 4	1

7.8.3 Fan-in and Fan-out Constraints

Fan-in

The number of inputs to a gate. Exceeding limits causes:

• Increased propagation delay (more transistors in series)
• Reduced noise margins
• Unavailability in standard cell libraries

Fan-out

The number of gate inputs driven by a single output. Exceeding limits causes:

• Increased output transition time (higher capacitive load)
• Potential signal integrity issues
• Need for buffer insertion

Parameter	Typical CMOS Limit	Effect of Exceeding
Fan-in	4–8 inputs	Increased delay, decomposition needed
Fan-out	4–10 loads	Increased delay, buffer insertion needed

7.8.4 Gate Loading Effects

Gate loading refers to the electrical impact of connecting gate outputs to gate inputs. Each input presents a capacitive load to the driving output. As fan-out increases, the driving gate must charge/discharge more capacitance, slowing its transition time.

Delay vs. Load Formula

\[t_{pd} = t_{pd0} + k \cdot C_{load}\]

where \(t_{pd0}\) is the intrinsic delay, \(k\) is a technology-dependent constant, and \(C_{load}\) is the total load capacitance.

Buffer Insertion

When a signal must drive many inputs, buffer insertion restores signal strength. A buffer (two cascaded inverters) adds one gate delay but restores the output drive capability.

Diagram: Propagation Delay and Critical Path Analyzer

---

7.9 Level Reduction Techniques

When a multi-level circuit has too many levels (and therefore too much delay), level reduction techniques restructure the circuit to decrease the number of gate levels while potentially increasing gate count or fan-in.

Flattening

Worked Example: Flattening (4 levels → 2 levels)

The most direct approach — expand back to two-level SOP/POS using the distributive law.

Reduce \(F = A(B(C+D) + E)\) from 4 levels to 2 levels:

\[F = A(BC + BD + E) = ABC + ABD + AE\]

The two-level form requires higher fan-in (3-input AND, 3-input OR) but achieves minimum delay (2 gate delays).

Partial Flattening

When full flattening creates impractical fan-in, partial flattening expands only select portions to reduce levels without exceeding fan-in constraints.

Example

For a 5-level circuit, reduce to 3 levels by expanding the innermost nesting while keeping outer factoring.

Comparison of Techniques

Technique	Levels	Gate Count	Fan-in	Delay
Original multi-level	4	Low	Low	High
Partial flattening	3	Medium	Medium	Medium
Full flattening	2	High	High	Low

Algebraic Restructuring

Key Insight: Alternative Factoring

Sometimes an expression can be rewritten in an alternative factored form that uses fewer levels:

\[F = AC + AD + BC + BD + E = (A+B)(C+D) + E\]

• SOP form: 3 levels — five 2-input ANDs → one 5-input OR
• Factored form: 3 levels — two 2-input ORs → one 2-input AND → one 2-input OR, but uses smaller gates

---

7.10 Gate Count Optimization

Gate count optimization minimizes the total number of gates in a circuit, directly reducing chip area and manufacturing cost. While two-level minimization (K-maps, Quine-McCluskey) minimizes literals within a fixed two-level structure, multi-level optimization explores a broader design space.

Sharing Common Sub-expressions

Worked Example: Shared Sub-expression

Consider two output functions:

\[F_1 = AC + AD + BC + BD\]

\[F_2 = AC + AD + E\]

Both share \(AC + AD = A(C+D)\). Computing \(A(C+D)\) once and sharing it saves gates:

\[F_1 = A(C+D) + B(C+D) = (A+B)(C+D)\]

\[F_2 = A(C+D) + E\]

The shared term \(C+D\) appears once in the circuit, driving both \(F_1\) and \(F_2\).

Literal Count vs Gate Count Trade-offs

Key Concept

Minimizing literal count (K-maps, QM) does not always minimize gate count. Consider three forms of the same function:

\[F = AB + AC + BC \quad \text{(6 literals, 4 gates, 2 levels)}\]

\[F = A(B+C) + BC \quad \text{(5 literals, 4 gates, 3 levels)}\]

\[F = (A+B)(A+C) \quad \text{(4 literals, 3 gates, 2 levels)}\]

The POS form wins on both gates and literals — but requires recognizing that \(BC\) is a redundant consensus term.

Form Comparison

Form	Literals	Gates	Levels	Best For
SOP	6	4	2	Speed (min delay)
Factored	5	4	3	Balance
POS	4	3	2	Area (min gates)

Design Takeaway

The optimal form depends on the design priority — delay, area, or power. Always evaluate multiple forms before committing to an implementation.

---

7.11 Factoring for Multi-Level Optimization

Factoring transforms a two-level expression into a multi-level form by extracting common factors. This technique is the primary tool for reducing gate count and fan-in in practical circuit design.

Common Factor Extraction

Example 1: Simple Factoring

\[F = ABC + ABD + ABE\]

\[= AB(C + D + E)\]

Original: 4 gates (three 3-input ANDs + one 3-input OR). Factored: 3 gates (one 2-input AND for \(AB\), one 3-input OR, one 2-input AND).

Example 2: Multi-Step Factoring

\[F = ACD + ADE + BCD + BDE\]

\[= AD(C+E) + BD(C+E)\]

\[= (A+B)D(C+E)\]

Factor each pair first, then extract the common \(D(C+E)\).

Factoring Trade-offs (Example 2)

Form	Gates	Max Fan-in	Levels
Original SOP	5 (4 AND + 1 OR)	3	2
Single factor	5 (2 AND + 2 OR + 1 AND)	2	3
Fully factored	4 (2 OR + 2 AND)	2	4

Decomposition Techniques

When to Use Decomposition

Decomposition breaks a complex function into simpler subfunctions. Use it when:

• The function has too many variables for a single implementation
• Standard cell libraries have limited gate sizes
• Power or area constraints require simpler gates

General form: \(F(A, B, C, D) = g(A, B,\; h(C, D))\)

where \(h(C, D)\) and \(g(A, B, h)\) are each simpler than \(F\).

Worked Example: Functional Decomposition

\(F = AB\overline{C}\overline{D} + \overline{A}BCD + ABCD\)

Observing that \(CD\) appears as a sub-expression, let \(h = CD\):

\[F = AB\overline{h} + \overline{A}Bh + ABh = AB\overline{h} + Bh(\overline{A} + A) = AB\overline{h} + Bh = B(A\overline{h} + h)\]

Result: Stage 1 computes \(h = CD\), Stage 2 computes \(F = B(A\overline{h} + h)\).

Diagram: Factoring and Decomposition Explorer

---

7.12 AOI and OAI Complex Gates

CMOS technology enables efficient AND-OR-Invert (AOI) and OR-AND-Invert (OAI) complex gates. These implement multi-level functions within a single gate structure, achieving the logic of two gate levels with the delay of approximately one gate.

AOI Gates (AND-OR-Invert)

AND groups of inputs, OR results, then invert. The numbers indicate group sizes.

AOI21: \(F = \overline{AB + C}\)

AOI22: \(F = \overline{AB + CD}\)

AOI221: \(F = \overline{AB + CD + E}\)

OAI Gates (OR-AND-Invert)

OR groups of inputs, AND results, then invert. The numbers indicate group sizes.

OAI21: \(F = \overline{(A+B) \cdot C}\)

OAI22: \(F = \overline{(A+B)(C+D)}\)

Advantages of Complex Gates

Feature	Discrete Gates	AOI/OAI Complex Gate
Transistor count	Higher	Lower (shared structures)
Propagation delay	2 gate delays	~1 gate delay
Power consumption	Higher (more transitions)	Lower
Chip area	Larger	Smaller

Complex gates are fundamental building blocks in standard cell libraries. Logic synthesis tools automatically identify opportunities to use AOI and OAI cells during technology mapping.

Example: Implement F = AB + CD (inverted)

• Discrete gates: 2 AND + 1 OR + 1 NOT = 4 gates, 3 levels
• AOI22: 1 complex gate, 1 level

Diagram: AOI and OAI Gate Structures

---

7.13 Wired Logic Implementations

Wired logic exploits the electrical properties of certain gate output types to implement logic functions without additional gates. When multiple gate outputs are connected together, the resulting logic depends on the output driver technology.

Open-Collector/Open-Drain Outputs

Wired-AND Function

In open-collector (TTL) or open-drain (CMOS) configurations, outputs connected with a shared pull-up resistor perform a wired-AND:

\[F = G_1 \cdot G_2 \cdot G_3\]

where \(G_1\), \(G_2\), \(G_3\) are individual gate outputs. Output is LOW if any gate pulls low; HIGH only if all gates are high-impedance.

Wired-AND with NAND Gates

Key Insight: Free AOI Gate

Connecting open-collector NAND outputs creates composite functions. If Gate 1 outputs \(\overline{AB}\) and Gate 2 outputs \(\overline{CD}\):

\[F = \overline{AB} \cdot \overline{CD} = \overline{AB + CD}\]

This implements an AND-OR-Invert function without a separate OR gate — effectively a "free" AOI gate using only wiring and a pull-up resistor.

Limitations of Wired Logic

Drawbacks

• Speed: Pull-up resistor creates RC delay on LOW→HIGH transitions
• Power: Static dissipation when outputs pull against resistor
• Fan-out: Limited by resistor value and electrical characteristics
• Noise margin: Reduced compared to active gate outputs
• Testing: Wired connections are harder to test and debug

Wired Configuration	Function	Output Technology Required
Wired-AND	Product of outputs	Open-collector / open-drain
Wired-OR	Sum of outputs	Emitter-coupled logic (ECL)

Modern Usage

Wired logic is less common in modern ASIC design due to speed and power disadvantages. However, it remains relevant in bus architectures and I/O interfaces where multiple devices share a common signal line.

---

7.14 Transmission Gate Circuits

A transmission gate (also called a pass gate) is a CMOS switch that can pass both logic 0 and logic 1 with full voltage swing. It consists of an NMOS and PMOS transistor connected in parallel, controlled by complementary signals.

Structure and Operation

Four Terminals

• Input: The signal to be passed
• Output: Connected to input when gate is ON
• Control (\(C\)): Connects to NMOS gate and PMOS gate (complemented)
• Control complement (\(\overline{C}\)): Connects to PMOS gate

When \(C = 1\): Both transistors ON → low-resistance path (signal passes).

When \(C = 0\): Both transistors OFF → high-impedance (disconnected).

Multiplexer Using Transmission Gates

Worked Example: 2:1 MUX

\[F = \begin{cases} A & \text{if } S = 0 \\ B & \text{if } S = 1 \end{cases}\]

• TG1: passes \(A\) when \(S = 0\) (\(\overline{S} = 1\))
• TG2: passes \(B\) when \(S = 1\)
• Outputs connected together (only one active at a time)

Uses only 4 transistors (2 per TG) + inverter for \(\overline{S}\), compared to ~16 transistors for a gate-level MUX.

XOR Using Transmission Gates

Key Insight: Efficient XOR

\[F = A \oplus B\]

Using a transmission gate controlled by \(B\): when \(B=0\), pass \(A\); when \(B=1\), pass \(\overline{A}\). Only one TG, one inverter, and complementary control needed — far fewer transistors than a gate-level XOR.

XOR Implementation Comparison

Implementation	Transistors	Gate Delays
NAND-only XOR	16	3–4
AOI-based XOR	10–12	2
Transmission gate XOR	6	1–2

Design Trade-off

Transmission gates offer excellent area and power efficiency but can suffer from signal degradation when cascaded through many stages, since they lack the regenerative property of logic gates. In practice, buffers are inserted periodically to restore signal quality.

---

7.15 Technology Mapping

Technology mapping is the process of converting a technology-independent Boolean network into a circuit that uses gates from a specific library (cell library). This bridges the gap between abstract logic optimization and physical implementation in ASIC and FPGA design.

The Technology Mapping Flow

Four Phases

1. Decomposition: Convert the optimized network into primitive gates (typically NAND2 + INV)
2. Matching: Identify portions that correspond to cells in the target library
3. Covering: Select a minimum-cost set of library cells for the entire function
4. Optimization: Iterate to improve area, delay, or power metrics

Decomposition

Any Boolean network can be decomposed into 2-input NAND gates and inverters. This uniform representation enables systematic pattern matching against library cells.

Worked Example: Decompose a 3-Input AND

\[ABC = \overline{\overline{\overline{\overline{AB}} \cdot C}}\]

This is: INV(NAND(INV(NAND(A,B)), C)) = NAND2 + INV + NAND2 + INV

Library Cells and Cost

A typical standard cell library contains cells ranging from simple inverters to complex gates:

Cell	Function	Area (units)	Delay (ps)
INV	\(\overline{A}\)	1	30
NAND2	\(\overline{AB}\)	2	50
NAND3	\(\overline{ABC}\)	3	70
NOR2	\(\overline{A+B}\)	2	60
AOI21	\(\overline{AB+C}\)	3	65
AOI22	\(\overline{AB+CD}\)	4	75
OAI21	\(\overline{(A+B)C}\)	3	65
MUX2	\(S\text{?}B\text{:}A\)	4	80

Covering Algorithm

Key Concept

The covering problem selects library cells to minimize total cost (area, delay, or weighted combination). For tree-structured networks, dynamic programming finds the optimal covering in polynomial time. For DAG networks with shared nodes, the problem is NP-hard and heuristic approaches are used.

Industry Practice

Commercial synthesis tools like Synopsys Design Compiler, Cadence Genus, and open-source tools like Yosys and ABC automate technology mapping. Understanding the underlying principles helps designers write better HDL code and interpret synthesis reports.

---

7.16 Multi-Level Synthesis Tools

Modern digital design relies on automated synthesis tools that perform multi-level optimization and technology mapping far beyond what is practical by hand. Understanding the capabilities and workflow of these tools is essential for effective digital design.

Logic Synthesis Flow

Synthesis Pipeline

1. HDL Input: Design described in Verilog or VHDL
2. Elaboration: HDL parsed into generic Boolean network
3. Technology-Independent Optimization: Algebraic and Boolean optimization
4. Technology Mapping: Map to target library cells
5. Gate-Level Netlist Output: Optimized circuit in target technology

Common Optimization Commands

Command	Action
Flatten	Convert multi-level to two-level (full flattening)
Factor	Extract common sub-expressions
Simplify	Apply Boolean minimization
Restructure	Change circuit structure to improve a target metric
Map	Perform technology mapping to a cell library
Retime	Move flip-flops to balance pipeline stages

Open-Source Tools

ABC (Berkeley)

Academic logic synthesis and verification tool

Yosys

Open-source synthesis suite for Verilog

OpenSTA

Static timing analysis

Why This Matters

These tools implement the same fundamental algorithms (factoring, decomposition, technology mapping) covered in this unit. Hand optimization is primarily a learning exercise, but understanding the principles is essential for effective tool usage and interpreting synthesis reports.

---

7.17 Summary and Key Takeaways

Unit 7 Summary

This unit covered the transformation of Boolean expressions into practical multi-level circuits:

• Two-level vs. multi-level circuits — fundamental trade-off between delay and gate count/fan-in
• Universal gates (NAND, NOR) — can implement any Boolean function; NAND for SOP, NOR for POS
• NAND-NAND conversion — double inversion + De Morgan's: replace all AND and OR with NAND
• NOR-NOR conversion — dual transformation: replace all OR and AND with NOR
• Mixed/cross conversions — require extra levels; prefer natural conversions
• Bubble pushing — visual gate conversion by moving inversion bubbles (AND ↔ OR)
• Circuit analysis — trace signals through levels for expressions, delays, and critical paths
• Fan-in/fan-out — constrain gate sizes and drive; require decomposition and buffers
• Level reduction — flattening and restructuring decrease delay at cost of gate count
• Gate count optimization — share common sub-expressions to reduce area
• Factoring and decomposition — extract factors and break into simpler subfunctions
• AOI/OAI complex gates — multi-level logic in single CMOS structures (~1 gate delay)
• Wired logic — open-collector/open-drain outputs for "free" AND/OR functions
• Transmission gates — efficient CMOS switches for MUX and XOR
• Technology mapping — convert Boolean networks to library cells (area/delay/power)
• Synthesis tools — automate all of the above; understanding principles is essential

Core Design Trade-offs

Goal	Technique	Cost
Min delay	Flattening to 2 levels	More gates, higher fan-in
Min area	Factoring, sub-expression sharing	More levels, more delay
Min power	Complex gates (AOI/OAI), transmission gates	Design complexity
Single gate type	NAND-NAND or NOR-NOR conversion	Possible extra inverters

Self-Check Questions

Why can't you simply replace all gates with NANDs in any circuit?

The direct replacement only works for two-level AND-OR (SOP) circuits because the double inversion principle creates matching pairs of inversions that cancel. For arbitrary multi-level circuits or for cross conversions (SOP→NOR), additional inverters or gate levels are required to handle unpaired inversions.

What is the critical path delay of a 4-level circuit where each gate has a 3ns propagation delay?

The critical path delay is \(4 \times 3\text{ns} = 12\text{ns}\). This assumes all gates on the critical path have equal delay. In practice, different gate types have different delays, and the critical path delay is the sum of individual gate delays along the longest path.

How does an AOI22 gate achieve less delay than its discrete equivalent?

The discrete implementation of \(F = \overline{AB + CD}\) requires 2 AND gates + 1 OR gate + 1 inverter = 3 gate levels. The AOI22 implements the same function in a single CMOS structure where the transistors are arranged to compute the entire function in one stage, achieving approximately 1 gate delay instead of 3.

---

Interactive Walkthrough

Step through converting an AND-OR circuit to all-NAND using bubble pushing:

---

Take the Unit Quiz | See Annotated References