Other Two-Level Implementations
Two-level forms beyond AND-OR: NAND-NAND, NOR-NOR, AND-OR-INVERT, OR-AND-INVERT.
Description
Any function has several equivalent two-level realizations. Besides AND-OR (SOP) and OR-AND (POS), there are NAND-NAND, NOR-NOR, AND-OR-INVERT (AOI), and OR-AND-INVERT (OAI) forms. Choosing among them matches the cheapest cells in the target technology.
- AND-OR and its NAND-NAND equivalent (from SOP).
- OR-AND and its NOR-NOR equivalent (from POS).
- AND-OR-INVERT (AOI): SOP then invert.
- OR-AND-INVERT (OAI): POS then invert.
- All eight realize the same function or its complement.
- AOI/OAI are single compact CMOS complex gates.
- NAND-NAND is the default for SOP in standard cells.
- Bubble-pushing (DeMorgan) converts between forms.
- Degenerate forms can collapse to a single gate.
- Pick the form with the fewest/cheapest cells.
At a glance
What
The family of equivalent two-level gate structures for a function.
Why
Different forms map to different (cheaper/faster) standard cells.
How
Apply DeMorgan/bubble-pushing to convert between the forms.
Where
Technology mapping after minimization.
When
When choosing the gate structure for a given cell library.
Think of it like…
Same destination, different routes: AOI/OAI/NAND-NAND are alternate roads to the identical logic — pick the smoothest for your vehicle (technology).
The eight forms
- AND-OR and its NAND-NAND equivalent (from SOP).
- OR-AND and its NOR-NOR equivalent (from POS).
- AND-OR-INVERT (AOI): SOP then invert.
- OR-AND-INVERT (OAI): POS then invert.
- All eight realize the same function or its complement.
Choosing a form
- AOI/OAI are single compact CMOS complex gates.
- NAND-NAND is the default for SOP in standard cells.
- Bubble-pushing (DeMorgan) converts between forms.
- Degenerate forms can collapse to a single gate.
- Pick the form with the fewest/cheapest cells.
Two-level map
| Start | Equivalent |
|---|---|
| AND-OR (SOP) | NAND-NAND |
| OR-AND (POS) | NOR-NOR |
| SOP + invert | AND-OR-INVERT |
| POS + invert | OR-AND-INVERT |
NAND / NOR equivalences
▶ live simulatorClick a terminal (A/B) to toggle it · glowing wires carry a logic 1 · the lamp is output Y
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Real-world applications
The 5 Whys
- 1
Why other forms? Match the cheapest cells.
- 2
Why AOI/OAI? One compact CMOS gate does AND-OR-INVERT.
- 3
Why bubble-pushing? It converts forms without changing logic.
- 4
Why care? Cell choice affects area, speed, power.
- 5
Root cause: equivalent structures let you fit logic to the technology.
Cheat sheet
Working principle
- Apply DeMorgan/bubble-pushing to convert between the forms.
- The family of equivalent two-level gate structures for a function.
Formulas & Boolean expressions
- AND-OR (SOP) = NAND-NAND
- OR-AND (POS) = NOR-NOR
- SOP + invert = AND-OR-INVERT
- POS + invert = OR-AND-INVERT
Key facts
- AND-OR and its NAND-NAND equivalent (from SOP).
- AOI/OAI are single compact CMOS complex gates.
Why it exists
- Root cause: equivalent structures let you fit logic to the technology.