ド・モルガンの法則を実践する：NAND のみで行う回路設計

**要約：**ド・モルガンの二つの恒等式――$\overline{A \cdot B} = \overline{A} + \overline{B}$ と $\overline{A + B} = \overline{A} \cdot \overline{B}$――を使うと、反転を分配しながら AND と OR を入れ替えられます。実用上の利点は、任意の論理関数を NAND のみ、または NOR のみの形式で実装できることです。これはまさに CMOS チップ設計者と FPGA 合成ツールが行っていることです。

ド・モルガンの二つの恒等式――$\overline{A \cdot B} = \overline{A} + \overline{B}$ と $\overline{A + B} = \overline{A} \cdot \overline{B}$――は覚えやすいものです。難しいのは、実務のエンジニアが実際にどう使うのかという問いです。答えは CMOS のトランジスタレベル設計、FPGA 合成、NAND のみ／NOR のみの実装、多段回路の最適化にまたがります。

この記事では、ド・モルガンの法則を実際の設計で使う方法に焦点を当てます。実回路のゲート数をどう減らすのか、任意の論理を NAND のみ／NOR のみの形式でどう実装するのか、そしてシミュレータが等価性をどう明らかにするのかを見ていきましょう。

まず確認：二つの法則

参照用に、ド・モルガンの二つの恒等式を示します。

これらは $n$ 個の変数へ一般化できます。

NAND ゲートの動作を調べる

応用 1：NAND のみの実装へ変換する

スタティック CMOS では、2 入力 NAND ゲートは 4 個のトランジスタで構成され、非反転 AND ゲートは NAND の後にインバータを置いて実装できます。そのため NAND は有用な基本要素ですが、設計全体を NAND だけで構成すべきとは限りません。ASIC 合成は特性評価済みライブラリの利用可能なセルへ論理をマッピングし、FPGA 合成は主に LUT と専用リソースへマッピングします。

変換の手順

任意の積和形（SOP）式は、二段階で NAND-NAND 形式に変換できます。

1. SOP から始める：$Y = AB + CD$
2. 二重否定を適用する：$Y = \overline{\overline{AB + CD}}$
3. 外側のバーにド・モルガンの法則を適用する：$Y = \overline{\overline{AB} \cdot \overline{CD}}$

結果は二段の NAND-NAND 回路です。第 1 段の NAND が $\overline{AB}$ と $\overline{CD}$ を計算し、第 2 段の NAND がそれらを結合します。

演習例：3 変数関数

$Y = A\overline{B}C + \overline{A}BC$ を NAND のみへ変換します。

ステップ 1：二重否定を入れる：$Y = \overline{\overline{A\overline{B}C + \overline{A}BC}}$

ステップ 2：外側のバーにド・モルガンの法則を適用する。

実装：

• ゲート 1（NAND）：入力は $A$、$\overline{B}$、$C$、出力は $\overline{A\overline{B}C}$
• ゲート 2（NAND）：入力は $\overline{A}$、$B$、$C$、出力は $\overline{\overline{A}BC}$
• ゲート 3（NAND）：入力はゲート 1 とゲート 2 の出力、出力は $Y$

$\overline{A}$ と $\overline{B}$ のための NOT ゲートは、NAND ゲートの 2 入力を互いに結線して実装します。

この回路図のゲート数： NAND ゲート 3 個 + NAND で構成したインバータ 2 個 = NAND ゲート 5 個です。直接的な AND-OR 回路図も 5 個のゲートを使いますが、ゲートは 3 種類です。単一種類のゲートによる構成は、使えるパッケージが限られる場合に便利です。シリコン実装は、ターゲットライブラリの面積、遅延、電力の特性データに基づいて評価すべきです。

NAND 万能論理テンプレートを試す

応用 2：NOR のみの実装へ変換する

NAND-NAND 変換の双対は積和形（POS）式に対して機能し、NOR-NOR 回路を生み出します。

変換の手順

1. POS から始める：$Y = (A + B)(C + D)$
2. 二重否定を入れる：$Y = \overline{\overline{(A+B)(C+D)}}$
3. 外側のバーにド・モルガンの法則を適用する：$Y = \overline{\overline{(A+B)} + \overline{(C+D)}}$

結果は二段の NOR-NOR 回路です。第 1 段の NOR が $\overline{A+B}$ と $\overline{C+D}$ を計算し、第 2 段の NOR がそれらを結合します。

NOR ゲートは、和の積形論理や、適切な複合セルを備えたライブラリに自然に適合する場合があります。NAND、NOR、混合ゲートのどの形式を選ぶかは、ファンイン、駆動能力、負荷、配置、ターゲットテクノロジによって決まり、万能な優先順位はありません。

応用 3：多段回路の最適化

実際の回路が二段だけで済むことはめったにありません。反転があちこちに散らばった多段論理に出会ったとき、ド・モルガンの法則を使えば、回路内で「バブルを押し通し」、余分な反転を打ち消してゲート数を減らせます。

演習例：4 ゲート式を簡略化する

簡略化する式：$Y = \overline{\overline{A \cdot B} + \overline{C \cdot D}}$

ステップ 1 — 外側のバーにド・モルガンの法則を適用します（内部の式は二つの項の和です）。

ステップ 2 — 二重否定を打ち消します。

一見すると複雑なこの式には、NAND ゲート 2 個、NOR ゲート 1 個、出力インバータ 1 個が必要です。ド・モルガンの法則を二度適用すると、1 個の 4 入力 AND ゲートにまで簡約できます。

演習例：3 段回路でのバブルプッシング

与えられた式：$Y = \overline{\overline{(A + B)} \cdot \overline{(C + D)} \cdot E}$

ステップ 1 — 外側の NAND にド・モルガンの法則を適用します。

ステップ 2 — 二重否定を打ち消します。

ブール論理記号のレベルでは、この式は補数入力を 1 つ持つ 5 入力 OR ゲートに簡約できます。実際のハードウェアで面積、速度、消費電力が改善されるかは、利用できるセルまたは LUT、そのファンイン、配線、負荷によって決まります。

応用 4：FPGA 合成とテクノロジーマッピング

Verilog や VHDL を書いても、合成ツールがコードを直接 AND ゲートや OR ゲートに翻訳するわけではありません。代わりにテクノロジーマッピングを実行し、論理を対象 FPGA や ASIC ライブラリで利用できる特定のプリミティブへ変換します。ド・モルガンの法則は、このプロセスの中核となる変換です。

合成ツールにおけるド・モルガンの法則の使い方

1. LUT マッピング：FPGA の LUT は、入力数の上限内で任意のブール関数を実装できます。合成ツールは関数を LUT にパッキングする前に論理を簡単化して因数分解します。ド・モルガン変換は、その際に利用できる等価変形の 1 つです。

2. 極性の最適化：多くのライブラリゲートは、反転出力または反転入力を本来備えています。バブルプッシングによって有用な補数信号を保ち、個別のインバータを追加せずに済む場合があります。

3. クリティカルパスの最適化：特性評価済みライブラリと配置からより良いタイミングが予測される場合、ツールは等価な NAND、NOR、または複合セルの形式を選択することがあります。最適な形式はテクノロジに依存します。

具体的な Verilog の例

次の RTL コードを考えます。

assign y = ~(a & b) | ~(c & d);

合成ツールは $\overline{AB} + \overline{CD}=\overline{ABCD}$ を認識します。個別のゲート、複合ライブラリセル、または入力数の上限内であれば 1 個の FPGA LUT で実装できます。RTL は動作を規定し、実装面積とタイミングは選択したターゲットのレポートによって確定します。

応用 5：レガシーハードウェアとゲートの代替

古いハードウェアを扱う場合や、使用可能な部品の在庫が限られている場合、ド・モルガンの法則はゲート置換のための第一の道具になります。

万能ゲートによる構成

NAND ゲートだけを使って、ほかのすべてのゲートを構成できます。

OR の構成は、ド・モルガンの法則 $A + B = \overline{\overline{A} \cdot \overline{B}}$、すなわち NAND(NOT A, NOT B) から直接導かれます。

この方法は、部品在庫が制限される場合にも有用です。74LS00 のセクションしか利用できない場合、3 つの NAND セクションで 1 つの OR 機能を実装できます。ただし、置き換え後の回路が元の回路の電圧、ファンアウト、タイミング、消費電力、未使用入力の要件を満たす必要があります。

オシロスコープによる検証

DigiSim でド・モルガン変換を構成するときは、元の回路と変換後の回路の出力を比較します。OSCILLOSCOPE_8CH を使えば、両方の出力と入力を並べて表示できます。

安定した入力の全組み合わせを網羅的に確認すれば、真理値表を検証できます。入力を遷移させると、シミュレータの伝搬遅延モデルで表現される差も観察できますが、それによって特定の物理実装のタイミングが確定するわけではありません。

論理的に等価な回路が、必ずしもタイミング的に等価とは限りません。NAND-NAND と AND-OR の回路図がどちらも 2 段論理であっても、セル遅延、入力スルーレート、ファンアウト、負荷、配線は異なる場合があります。追加の反転段はパスを長くする可能性がありますが、物理的な速度を論じるにはターゲット固有のタイミング解析が必要です。

ド・モルガンの法則を使う際のよくある落とし穴

演算子を反転し忘れる

各項を反転することは覚えていても、演算子を反転し忘れる学習者は少なくありません。すると $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$ と書いてしまいますが、これは誤りです。必ず AND を OR に、または OR を AND に変えてください。

NAND/NOR 回路のフローティング入力

DigiSim で NAND のみの回路を構成するときは、必要なすべての入力に定義済みのソースを接続します。実際の CMOS 入力をフローティングのままにすると、予測不能な電圧になり、結合ノイズによってスイッチングしたり、電源電流が増加したりする可能性があります。物理デバイスの未使用入力はデータシートに従って適切な有効論理レベルに固定し、回路図上の演習では対応する CONSTANT ソースを使用します。

論理等価とタイミング等価を混同する

真理値表が同じ二つの回路でも、伝搬遅延は大きく異なる場合があります。ド・モルガンの法則で回路を変換するときは、変換によってゲート段数が増えるか減るかを必ず確認してください。

課題：多段最適化

次の式を、最小のゲート数へ削減してみましょう。

ヒント：外側の NAND にド・モルガンの法則を適用し、二重否定を打ち消してから、何が残るかを見てください。（解答：$Y = (A + \overline{B}) + (\overline{A} + B) = A + \overline{A} + B + \overline{B} = 1$。式全体が常に真なので、ゲートは一つも必要ありません。）

これは力強い実例です。ド・モルガンの法則を補元法則と組み合わせると、回路全体を取り除けることさえあります。

カルノー図へ進んで、同じ簡略化を視覚的に捉えることもできます。あるいはブール代数の基礎を復習しましょう。NAND コンポーネントのリファレンスを開き、ここで紹介した変換を一つ配線してみてください。