多入力論理ゲート：3 入力 AND からその先へ

多入力論理ゲートは幅広いバスを一つの信号へ圧縮します。カスケード実装とツリー実装を比較し、設計に適した方式を選びます。

Denny

2026年1月13日読了まで約8分

Chalkboard feature illustration for “多入力論理ゲート：3 入力 AND からその先へ”

要約： 幅広い AND／OR／XOR ゲートは二通りに作れます。カスケードでは遅延は線形で $(n-1) \cdot t_{gate}$ 、平衡ツリーでは対数的で $\lceil\log_2 n\rceil \cdot t_{gate}$ です。ゲート数は同じであり、ツリーが速いのは最長信号経路を短くするためです。

基本論理ゲートは二つの入力を扱いますが、実際のシステムはもっと多くを扱います。メモリアドレスデコーダーでは 20 本の信号線を AND することがあり、パリティ生成器はデータバス全体を XOR します。小さなゲートで大きなゲートを作る際の配置は、回路速度へ直接かつ測定可能な影響を与えます。

この記事では、多入力ゲートを構成する二つの主要戦略（カスケードとツリー）を比較し、伝搬遅延の式を導き、各方式が適する場面を説明します。

AND ゲートコンポーネント図

デジタル階層における定義と役割

多入力論理ゲートは、AND、OR、XOR のような基本ブール演算を三つ以上の入力に対して実行し、一つの出力を作るデジタル部品です。デジタルシステムの階層では、二入力の基本要素のすぐ上に位置し、複雑な条件の「判断役」となります。

32 ビット CPU では、信号は対ではなくバス全体として届きます。多入力論理は、この幅広いデータ経路を意味ある制御信号へ圧縮します。これはデコーダーとエンコーダーの基礎です。

AND： 「すべて」のゲートです。 $n$ 入力 AND は、全入力が 1 のとき、かつそのときだけ 1 を出します。
OR： 「いずれか」のゲートです。 $n$ 入力 OR は、 $n$ 個の入力の少なくとも一つが 1 なら 1 を出します。
XOR： 「奇数パリティ」のゲートです。 $n$ 入力 XOR は、1 の入力数が奇数なら 1 を出します。これは二入力版から自然に拡張される重要な性質です。

AND ゲートの動作を試す

技術仕様：3 入力 AND の基準

規模を理解するために、3 入力 AND の真理値表を見ます。任意の $n$ 入力ゲートには $2^n$ 通りの入力組み合わせがあります。 $n$ とともに表は指数的に大きくなりますが、論理は変わりません。

入力 A	入力 B	入力 C	出力 Y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

すべての入力が HIGH の最終行だけが HIGH を出力します。この厳密さが、AND をアドレス復号とイネーブル信号生成の主要な道具にします。

ブール式とスケーリング

これらのゲートの数式表現は、ブール代数の結合法則に従います。 $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ が、大きなゲートを小さなゲートから作れる理論的根拠です。

$n$ 入力 AND： $Y = A \cdot B \cdot C \cdot \dots \cdot N$

$n$ 入力 OR： $Y = A + B + C + \dots + N$

$n$ 入力 XOR（パリティ）： $Y = A \oplus B \oplus C \oplus \dots \oplus N$

NAND と NOR では、規模拡大時の挙動を理解するためにド・モルガンの定理を適用します。 $n$ 入力 NAND は NAND を直列に並べただけではなく、AND 演算の後に一つの NOT を置いたものです。

重要なトレードオフ：伝搬遅延

物理ライブラリが提供するゲートのファンインには限りがあり、プログラマブル論理は利用可能な LUT と配線へブール関数をマッピングします。そのため 128 入力 AND のような非常に広いリダクションは、理想的な一つの記号としてではなく、普通は小さなセルまたは LUT へ分解されます。

小さなゲートの配置は、入力変化が出力へ届くまでの 伝搬遅延（ $t_{pd}$ ）を左右します。以下の式は、遅延 $t_{gate}$ が同じ二入力ゲートを仮定し、配線と負荷を無視します。これは論理段数を明らかにするモデルです。実際の結果は、マッピングされたセル遅延、遷移時間、ファンアウト、配線、配置、動作コーナーにも依存します。

実装戦略 A：カスケード（遅い方法）

8 入力 AND を作るもっとも直感的な方法は連鎖です。最初の二入力 AND の出力を次のゲートへ入力し、これを続けます。

$Output = ((((((A \cdot B) \cdot C) \cdot D) \cdot E) \cdot F) \cdot G) \cdot H$

このカスケード構造では、入力 A の信号は出力まで七つの連続ゲートを通ります。総遅延は線形です。

T_{cascade} = (n-1) \cdot t_{gate}

$t_{gate}$ が 1ns なら、8 入力ゲートには 7ns かかります。小さく見えても、同期システムでは最大クロック周波数を制限します。

実装戦略 B：ツリー構造（速い方法）

ツリー、またはトーナメント構造では、入力を組にします。A と B、C と D、E と F、G と H をそれぞれ一つのゲートへ入れ、その四出力を次段の二ゲートへ、最後に一つのゲートへ入れます。

総遅延は対数的に増えます。

T_{tree} = \lceil \log_2(n) \rceil \cdot t_{gate}

8 入力では $\lceil\log_2(8)\rceil = 3$ です。遅延は $3 \times 1\text{ns} = 3\text{ns}$ 、カスケードの 7ns の半分未満です。

並べて比較する

指標	カスケード（n=8）	ツリー（n=8）
遅延式	$(n-1) \cdot t_{gate}$	$\lceil\log_2(n)\rceil \cdot t_{gate}$
総遅延	$7 \cdot t_{gate}$	$3 \cdot t_{gate}$
ゲート数	$n - 1 = 7$	$n - 1 = 7$
配線の複雑さ	単純な連鎖	平衡二分木

同一二入力ゲートのモデルでは、両方とも $n-1$ 個のゲートを使いますが、平衡ツリーは最悪論理段数を $n-1$ から $\lceil\log_2 n\rceil$ へ減らします。実装では合成がより幅広いゲート、LUT、因数分解、配置固有の構造を使うことがあるため、ゲート数と遅延が理想式どおりになるとは限りません。

AND ゲートセキュリティシステムテンプレート

セキュリティアラーム回路を開く

インタラクティブデモ：digisim.io で遅延を可視化する

両構造を作り、横に並べて観察することが遅延差を理解する最良の方法です。

準備： キャンバスに八つの INPUT_SWITCH コンポーネントを置きます。
カスケード： 七つの AND ゲートの連鎖を作り、最終出力を OUTPUT_LIGHT へ接続します。
ツリー： その下に七つの AND ゲートでツリーを作り、最終出力を別の OUTPUT_LIGHT へ接続します。
試験： すべてのスイッチを ON にします。二つのライトが点いたら、最初のスイッチ（入力 A）を OFF にします。

シミュレータがゲートごとの遅延をモデル化するなら、カスケード全体を通る遷移ではツリー出力の方が早く安定するはずです。理想的なゼロ遅延モデルでは両者は同時に更新されるので、依存する論理段数を数えてください。

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

チャンネル 1 を切り替えた入力、チャンネル 2 をツリー出力、チャンネル 3 をカスケード出力へ接続します。等遅延の教育モデルでは、オフセットはおよそ $3t_{gate}$ と $7t_{gate}$ です。この実験は経路の深さを説明します。実際の FPGA／ASIC のタイミングクロージャには、実装済みネットリストと配線による静的タイミング解析を使います。ハードウェアオシロスコープやロジックアナライザは特定基板を診断できますが、全シリコンと全環境コーナーを網羅するものではありません。

オシロスコープコンポーネント

実世界の用途

1. メモリアドレス復号

メモリマップされた周辺装置は、多くの場合アドレスの範囲に応答します。上位アドレスビットを基準パターンと比較し、下位ビットがデバイス内のレジスタまたは位置を選びます。

ブール論理の水準では、完全一致は真または補数のアドレスビットの AND です。物理実装では、この比較を使えるゲート、比較器セル、LUT へ因数分解し、階層的に復号することもあります。正しい構造は、手描きの二分木であることではなく、実装後にバスタイミングと電気要件を満たすことです。

2. データバスのパリティ生成

信頼性が重要なとき、データの一バイトへ誤り検出のためのパリティビットを追加します。偶数パリティビットは、データ中の 1 の数が奇数なら 1 となり、総数を偶数にします。

これはまさに多入力 XOR ゲートの働きです。

XOR ゲートコンポーネント

二入力 XOR ゲートの平衡ツリーは、 $\log_2 64=6$ なので、64 入力では六つの論理段を持ちます。パリティやより豊かな誤り訂正符号は多くの記憶・通信経路で使われますが、正確な符号、保護範囲、更新位置はアーキテクチャ固有です。誤り検出における XOR と XNOR も参照してください。

カリキュラムの関連項目

digisim.io でデジタル論理を学び続けるなら、次の項目が理解を深めます。

基本論理ゲート（基本要素）
ブール代数とド・モルガン（数学）
伝搬遅延とタイミング図（性能）
デコーダー（多入力 AND の主要用途）

まとめ：設計指針

指針	詳細
依存段数を減らす	二入力ゲートしか使えない場合、平衡リダクションは強い出発点です。合成にターゲット資源へマッピングさせます。
ライブラリのファンインを尊重する	利用可能で効率のよいファンインは、論理ファミリ、標準セルライブラリ、FPGA の LUT 構成によって異なります。
ファンアウトを考慮する	多数の入力を駆動するゲート出力には追加遅延があります。高ファンアウトノードはバッファします。
配線と負荷を含める	ゲート数が等しくても、実装後の面積、電力、配置、遅延が等しいとは限りません。
適切な検証を使う	DigiSim では論理段数とモデル化遅延を比較し、物理タイミングはターゲット実装ツールで検証します。

二入力ゲートから多入力システムへの移行は、コンピュータアーキテクチャへの第一歩です。そこでは正しさが必要条件であり、性能が真の設計課題になります。

伝搬遅延とタイミングを続けて学ぶか、AND ゲートコンポーネントのリファレンスを開き、8 入力ツリーとカスケードを配線してみてください。