Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 57 ยท Boolean Algebra

Two-Level Logic and NAND-NAND Implementations

Understand two-level logic: AND-OR, OR-AND, NAND-NAND and NOR-NOR forms, which of the 16 gate pairings are degenerate, and how to convert SOP to NAND-only with Python checks.

A two-level circuit is a network where every signal passes through at most two gates on its way to the output: a first level that combines the inputs, and a second level that combines the first-level outputs. The classic example is sum-of-products (SOP): a first level of AND gates (one per product term) feeding a single OR gate.

Two-level circuits are popular because their delay is small and predictable: two gate delays, no matter how many terms there are. This lesson shows the four everyday forms, the surprising fact that you can swap every gate for a NAND (or every gate for a NOR) without changing the function, and which of the 16 possible gate pairings are useful and which collapse into a single gate.

The four everyday forms

Given an expression in sum-of-products or product-of-sums form, each has a direct two-level circuit.

Form First level Second level Function with two terms
AND-OR AND OR ab + cd
OR-AND OR AND (a + b)(c + d)
NAND-NAND NAND NAND ab + cd
NOR-NOR NOR NOR (a + b)(c + d)

NAND-NAND computes the same function as AND-OR. This follows from De Morgan's law applied once:

Text
NAND(NAND(a,b), NAND(c,d)) = ((ab)' (cd)')' = ab + cd

The inverter-like second-level NAND turns "none of the product terms are false-ish" back into an OR of the terms. In the same way NOR-NOR computes the same function as OR-AND.

Why bother? Because NAND and NOR are the cheapest gates in CMOS (see Universal Gates and Gate Counts) and a whole circuit with only one gate type is easier to manufacture. The recipe for turning a minimized SOP into a NAND-NAND circuit is mechanical:

  1. Write the minimized SOP.
  2. Replace every AND gate with a NAND and the OR gate with a NAND.
  3. A product term that is a single literal (like c) has no first-level gate: feed its complement c' straight into the second-level NAND, which turns it back into c.

All 16 pairings

You can pick any of four gate types (AND, OR, NAND, NOR) for each level, giving 16 combinations. Only eight of them are real two-level circuits. The other eight are degenerate: they reduce to one wide gate, so the second level was wasted.

Take two groups of two inputs, (a, b) and (c, d):

  • AND-AND gives abcd, which is a single 4-input AND. Likewise OR-OR gives a + b + c + d.
  • AND-NAND gives (abcd)', a 4-input NAND. Likewise OR-NOR gives (a + b + c + d)'.
  • NAND-OR gives (ab)' + (cd)' = (abcd)', again a NAND.
  • NOR-AND gives (a + b)'(c + d)' = (a + b + c + d)', again a NOR.
  • NAND-NOR gives ((ab)' + (cd)')' = abcd, an AND.
  • NOR-NAND gives ((a + b)'(c + d)')' = a + b + c + d, an OR.

The non-degenerate forms are the useful ones:

Pairing Function
AND-OR ab + cd
NAND-NAND ab + cd
NOR-OR a'b' + c'd'
AND-NOR (ab + cd)'
OR-AND (a + b)(c + d)
NOR-NOR (a + b)(c + d)
NAND-AND (a' + b')(c' + d')
OR-NAND ((a + b)(c + d))'

The first-level gates produce product or sum terms, the second level combines them, and a complement may appear at the output or at the inputs. The two that implement plain SOP are AND-OR and NAND-NAND; the two that implement plain POS are OR-AND and NOR-NOR. The other four are the complemented or "inverted-input" cousins, useful when you need the complement of the output for free.

Python Classify all 16 gate pairings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program prints eight degenerate and eight genuine pairings, matching the table above.

From a minimized SOP to NAND-NAND

Take the function F(a, b, c) = a'b + ac + bc'. The AND-OR circuit uses three 2-input ANDs and one 3-input OR. The NAND-NAND version swaps in NAND gates throughout.

Python AND-OR versus NAND-NAND

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The inputs a' and c' still need inverters in both versions, unless the source supplies both polarities (as the outputs of flip-flops do).

Advantages and limits of two-level logic

Advantages. Only two gate delays from input to output. The design method (K-map or Quine-McCluskey) maps directly onto the hardware. Regular shapes make PLAs possible: an AND plane followed by an OR plane is a two-level circuit.

Limits.

  • A term may need many inputs, but real gates have limited fan-in. A 10-input AND must be built as a tree, so the circuit is no longer two-level.
  • Some functions need exponentially many product terms. The 8-input parity function (XOR of all inputs) needs 128 terms in SOP, while a chain of XOR gates does it with 7 gates.
  • Shared sub-expressions are not exploited, so multi-level circuits are often smaller even if they are slower.
  • A single input change can still cause a static hazard; see Don't-Cares and Hazards.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which two-level NAND-only circuit is equivalent to AND-OR?

    By De Morgan, NAND(NAND(a,b), NAND(c,d)) equals ab + cd, the same function as AND-OR.
  2. 2. Which pairing is degenerate?

    AND-AND just computes abcd, one 4-input AND. The second level adds nothing.
  3. 3. How many of the 16 pairings of AND, OR, NAND and NOR are non-degenerate?

    Eight collapse to a single wide gate; the other eight (AND-OR, OR-AND, NAND-NAND, NOR-NOR, NOR-OR, AND-NOR, NAND-AND, OR-NAND) are genuine.
  4. 4. What does the NOR-NOR form implement?

    NOR-NOR gives (a+b)(c+d), a product of sums, just as OR-AND does.

Summary

  • A two-level circuit has at most two gates between any input and the output.
  • AND-OR and NAND-NAND both implement SOP; OR-AND and NOR-NOR both implement POS.
  • Of the 16 pairings of the four gate types, eight are degenerate (they collapse to one wide gate) and eight are genuine.
  • Converting a minimized SOP to NAND-NAND replaces every gate with a NAND, letting a chip use one gate type.
  • Fan-in limits, parity-like functions and hazards are the limits of two-level design.

Next: Karnaugh Maps, the tool that finds the minimized SOP in the first place.