6 / 63 · 概念

万能ゲート：NAND だけで回路を作る

NAND・NOR の機能的完全性を回路構成で示し、XOR の中間信号を検証します。

「あらゆる回路」の意味する範囲

NAND だけで NOT・AND・OR を作れます。有限個の入力を持つ任意の組合せ論理関数は、これらの演算で表せます。この意味で NAND は万能ゲート^{万能ゲート一種類のゲートを繰り返して任意のブール関数を構成できるとき、そのゲートを万能ゲートと呼びます。代表例は NAND と NOR です。}です。記憶・クロック・配線・電力の条件まで、一つの NAND が解決するという意味ではありません。

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

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

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

NAND の両端子に同じ入力を接続すると NOT になります。AND は NAND の後でさらに否定^{否定 0 を 1 に、1 を 0 に変える NOT 演算です。式の上の線は、その下の式全体に NOT を適用することを表します。詳しく見る}し、OR はド・モルガンの法則^{ド・モルガンの法則 AND の結果の否定は各入力を否定した OR と等しく、OR の結果の否定は各入力を否定した AND と等しくなります。詳しく見る}で構成します。NOR も入力をまとめて NOT にでき、同様の構成で万能性を示せます。

四つの NAND で 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

共有する中間信号で XOR を作る

最初の NAND: n0 = NAND(a, b)
中間の二つの NAND: n1 = NAND(a, n0); n2 = NAND(b, n0)
最後の NAND: y = NAND(n1, n2)

第 2 段の二つの NAND は並列です。ゲート数は合計 4 個ですが、最長の論理経路は 3 段です。各ゲートが最大 2 ns の単純なモデルなら、最大経路の遅延和は 6 ns です。実際の負荷と配線による変化は別途考慮します。

四つの NAND の結果を XOR と照合

XOR · 真理値表
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

表の四行を自分で埋め、上の XOR と比較してください。機能等価とは、すべての入力で出力が一致するという主張であり、ゲート数や伝搬遅延^{伝搬遅延入力が変わってから、出力が正しい値に安定するまでの時間です。論理式の等価性と時間特性は別の性質です。詳しく見る}も同じという主張ではありません。

自分で考えてみましょう

NOR だけで NOT と AND を作る式を書いてください。AND 構成のゲート数と最長経路の段数はいくつですか。

解説を見る

NOT a=NOR(a,a) です。AND は NOR(NOR(a,a), NOR(b,b)) です。二つの入力否定と最後の NOR で合計 3 ゲート、最長経路は 2 段です。