6 / 63 · 概念

Universal gates: build circuits using only NAND

Construct NOT, AND, OR and XOR from NAND and distinguish gate count from delay.

翻訳はまだありません。元の講義を表示しています。 (English)

Functional completeness has a precise scope

NAND can construct NOT, AND and OR, which can express any finite combinational Boolean function. This is functional completeness, not a claim about storage, power or timing.

\overline a=\operatorname{NAND}(a,a)

AND is a NAND followed by another NAND with tied inputs. OR follows from De Morgan^{De Morgan NOT of an AND equals OR of the complemented inputs. NOT of an OR equals AND of the complemented inputs. Learn more}:

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

NOR can similarly create inversion^{inversion The NOT operation exchanges 0 and 1. An overline applies NOT to the entire expression covered by the line. Learn more} by tying inputs and is also universal.

Four NAND gates make XOR

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

Share an intermediate signal

First NAND: n0 = NAND(a, b)
Two parallel NANDs: n1 = NAND(a, n0); n2 = NAND(b, n0)
Final NAND: y = NAND(n1, n2)

There are four gates but three stages on the longest path. At a simplified 2 ns bound per gate, the maximum path sum is 6 ns. Real loading and wiring affect physical delay.

Compare the construction with XOR

XOR · Truth table
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

Verify every row. Functional equivalence says outputs agree, not that implementations have equal cost or timing.

自分で考えてみましょう

Construct NOT and AND using only NOR. How many gates and levels does your AND implementation use?

解説を見る

NOT a=NOR(a,a). AND=NOR(NOR(a,a),NOR(b,b)): three gates total and two levels on the longest path.