論理ゲート回路の構築
前回は4種類の基本論理ゲートを学びました。今回はそれらを接続して、実際の問題を解決できる回路を組み立てます。
単一の論理ゲートはネジのようなもので、それ自体の機能は限られています。しかし、組み合わせることで、どんな複雑な機能でも構築できます。
身近な例え：レゴブロックで城を組み立てる
目の前に4色のレゴブロックがあると想像してください。
- 緑のブロック = AND ゲート：両端が接続された時のみ通電する
- オレンジのブロック = OR ゲート：どちらか一端が接続されれば通電する
- 赤のブロック = NOT ゲート：通電すると非通電に、非通電だと通電になる
- 紫のブロック = XOR ゲート：両端の状態が異なる時に通電する
これらのブロックで、何を組み立てられるでしょうか？
投票装置：3人が投票し、少数は多数に従います。これは典型的な組み合わせ論理回路です——AND/OR ゲートを接続するだけで実現できます。
パスワードロック：正しい複数のキーを同時に押すとロックが解除されます。これは本質的に AND ゲートの縦続接続です——各キーが1つの入力に対応し、全ての入力が1の時だけ出力が1になります。
警報器：いずれかのセンサーが作動すると警報が鳴ります。これは本質的に OR ゲートの応用です——1つのセンサーが1を出力すれば、警報器が鳴ります。
組み合わせ論理 vs 順序論理
回路構築を詳しく見る前に、2つの重要な概念を区別しておきましょう。
| 種類 | 特徴 | 出力の決定要因 | 記憶はあるか？ | 例 |
|---|---|---|---|---|
| 組み合わせ論理 | 出力は現在の入力のみによって決まる | 現在の入力値 | なし | 加算器、多数決回路、デコーダー |
| 順序論理 | 出力は現在の入力＋履歴状態によって決まる | 現在の入力＋以前に保存した値 | 有 | カウンタ、レジスタ、ステートマシン |
今回は組み合わせ論理に焦点を当てます。順序論理は第 9 講で詳しく説明します。
簡単な区別方法：組み合わせ論理は「入力したものがそのまま出力される」（数学の関数のようなもの）。順序論理は「以前の入力を覚えている」（人間の記憶のようなもの）。
回路構築の方法論：3ステップ法
論理ゲートを使って任意の組み合わせ論理回路を構築するには、汎用的な3ステップの手順があります。
- 真理値表を書く：入力の全組み合わせを列挙し、それぞれの場合に期待される出力を書きます。
- 論理式を書く：出力が1となる各行について、対応する「積項」（各入力のAND組み合わせ）を書き、すべての積項をORで接続します。これを「積和」（Sum of Products）形式と呼びます。
- 回路図を描く / コードを書く：論理式を論理ゲートの接続に変換します。
それでは、易しい順に3つの例を使ってこの方法を実践してみましょう。
ケース1：2入力パスワードロック
要件：簡単なパスワード検証回路を設計します。2つの入力 A と B があり、A=1 かつ B=1 の時のみ出力が1（ロック解除）、それ以外は出力0（ロック）となります。
この要件は実質的にANDゲート1つだけですが、3ステップ法のデモに使えます。
ステップ1：真理値表
| A | B | 期待出力 Y |
|---|---|---|
| 0 | 0 | 0（ロック） |
| 0 | 1 | 0（ロック） |
| 1 | 0 | 0（ロック） |
| 1 | 1 | 1（ロック解除） |
ステップ2：論理式
出力が1となるのは最後の行だけです。対応する積項は A AND B です。
したがって：Y = A AND B
ステップ3：回路実装
ANDゲート1つだけでよく、AとBを入力として、出力がYになります。
簡単すぎますか？それでは、実際に意味のある例を見てみましょう。
ケース2：多数決回路（中心ケース）
要件：3人（A、B、C）が提案に対して投票します（1は賛成、0は反対）。少なくとも2人が賛成した時、提案は可決されます（出力1）。
これは古典的な3入力多数決回路であり、デジタル回路の教科書で必ず学ぶケースです。
ステップ1：真理値表を書く
3入力で合計 23= 8 通りの組み合わせ：
| A | B | C | 賛成人数 | 可決かどうか Y | 説明 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 賛成なし |
| 0 | 0 | 1 | 1 | 0 | Cのみ賛成 |
| 0 | 1 | 0 | 1 | 0 | Bのみ賛成 |
| 0 | 1 | 1 | 2 | 1 | BとCが賛成 |
| 1 | 0 | 0 | 1 | 0 | Aのみ賛成 |
| 1 | 0 | 1 | 2 | 1 | AとCが賛成 |
| 1 | 1 | 0 | 2 | 1 | AとBが賛成 |
| 1 | 1 | 1 | 3 | 1 | 全会一致で可決 |
ステップ2：論理式を書く
出力が1となる行（4、6、7、8行目）を見つけ、各行に積項を1つ書きます：
- 4行目：NOT(A) AND B AND C
- 6行目：A AND NOT(B) AND C
- 7行目：A AND B AND NOT(C)
- 8行目：A AND B AND C
ORで接続：Y = (NOT(A) AND B AND C) OR (A AND NOT(B) AND C) OR (A AND B AND NOT(C)) OR (A AND B AND C)
この式は少し長く見えますが、論理的には非常に明確です。Y が1になるのは、任意の2つまたは3つの入力が1である場合に限られます。。
ステップ3：SVGで回路図を描く
3つのANDゲートがそれぞれ「AB」「BC」「AC」の3つのペアの組み合わせが11かどうかを判定し、ORゲートが結果をまとめます。
インタラクティブデモ：多数決回路の Python 実装
実例
# 要件：3人が投票し、少なくとも2人が賛成（1）の時だけ可決（出力1）
# ----- 第6講の基本論理ゲートを再利用 -----
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
return 1 if a == 1 or b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
# ----- 方法1：積和（SOP）標準形式 -----
def majority_voter_sop(a, b, c):
"""
多数決回路の「積和」実装。
真理値表から直接導出：出力が1となるすべての行を見つけ、
各行に積項を1つ書き、ORで接続します。
"""
term1 = AND(AND(NOT(a), b), c) # ~A·B·C
term2 = AND(AND(a, NOT(b)), c) # A·~B·C
term3 = AND(AND(a, b), NOT(c)) # A·B·~C
term4 = AND(AND(a, b), c) # A·B·C
return OR(OR(term1, term2), OR(term3, term4))
# ----- 方法2：最適化・簡略化形式 -----
def majority_voter_optimized(a, b, c):
"""
多数決回路の最適化実装：Y = AB + BC + AC。
この形式は必要なゲートが少なく、論理的には方法1と同等です。
なぜ同等なのか？
方法1のSOP形式を展開すると、ブール代数の吸収律を使って簡略化できます：
~A·B·C + A·~B·C + A·B·~C + A·B·C
= (~A·B·C + A·B·C) + (A·~B·C + A·B·C) + (A·B·~C + A·B·C)
= B·C·(~A+A) + A·C·(~B+B) + A·B·(~C+C)
= B·C + A·C + A·B
"""
return OR(OR(AND(a, b), AND(b, c)), AND(a, c))
# ============================================
# 完全な真理値表を出力し、2つの方法を比較
# ============================================
print("=" * 60)
print(" 3入力多数決回路 真理値表（サンプル デモ）")
print("=" * 60)
print()
print("┌───┬───┬───┬────────┬──────────┬──────────┐")
print("│ A │ B │ C │ 可決？ │ SOP 方法 │ 最適化方法 │")
print("├───┼───┼───┼────────┼──────────┼──────────┤")
for a in [0, 1]:
for b in [0, 1]:
for c in [0, 1]:
count = a + b + c
passed = "可決" if count >= 2 else "否決"
sop = majority_voter_sop(a, b, c)
opt = majority_voter_optimized(a, b, c)
print(f"│ {a} │ {b} │ {c} │ {passed} │ {sop} │ {opt} │")
print("└───┴───┴───┴────────┴──────────┴──────────┘")
# ============================================
# ゲート回路使用統計
# ============================================
print("\n" + "=" * 60)
print(" 2つの方法で使用するゲート回路の数の比較")
print("=" * 60)
print()
print("方法1（SOP完全形式）：")
print(" NOT ゲート: 3 個（~A, ~B, ~C）")
print(" AND ゲート: 4 個（4 つの積項、それぞれ 2 個の 2 入力 AND が必要）")
print(" OR ゲート: 3 個（4 つの積項をまとめる）")
print(" 合計: 約 14 個の基本ゲート呼び出し")
print()
print("方法2（最適化形式 Y = AB + BC + AC）：")
print(" AND ゲート: 3 個（AB、BC、AC）")
print(" OR ゲート: 2 個（3 つの積項をまとめる）")
print(" 合計: 5 個の基本ゲート呼び出し")
print()
print("最適化後、ゲート回路の使用量が約 65% 削減されました！")
print("これがブール代数の簡略化の工学的価値です。")
"真理値表から論理式への変換プロセスに注意してください。これはデジタル回路設計における最も中核的なスキルの 1 つです。真理値表を見れば式を書けます。式を見れば回路図を描けます。この 3 つは一対一対応になっています。"
ケース3：1ビット比較器
"要件""：2 つの 1 ビット 2 進数 A と B を比較します。3 つの信号を出力します：A>B、A=B、A<B" "これは非常に重要な基本回路です。多ビット比較器や CPU の条件判断は、すべてここから拡張されたものです。" "真理値表を見ると：" "A = B の検出は XOR ゲートと密接に関係していることに注意してください。XOR の出力が 1 であることは「異なる」を意味し、その NOT を取ると「等しい」が得られます。" "要件""：2 ビット 2 進数（00、01、10、11）を入力し、対応する 4 本の出力線のうち 1 本だけを 1 に、残りを 0 にします。" "デコーダは CPU の中核部品です。CPU が特定のレジスタを選択するとき、実質的にデコーダを使用しています。" デコーダは「1 対多」選択の古典のな回路です。対照的に、マルチプレクサ（MUX）は「多対 1」選択です。この 2 つは CPU のデータパス設計で非常に一般のです。デコーダは「特定のターゲットを選択する」（例：どのレジスタに書き込むか）ために使われ、マルチプレクサは「特定のソースを選択する」（例：ALU がどのレジスタからデータを読み取るか）ために使われます。 "実際のチップ製造では、NAND と NOR ゲートは AND と OR ゲートよりも「低レベル」です。" "NAND ゲート = AND + NOT""、つまり AND を行ってから反転します。NAND と NOR は「万能ゲート」（Universal Gates）と呼ばれます。それぞれ単独で全てのブール関数を実装できるためです。" "なぜチップは NAND/NOR を好むのか？CMOS プロセスでは：" "以下で NAND ゲートの「万能性」を検証します：" nand2tetris（NAND ゲートからテトリスへ）は有名なコンピュータサイエンスのコースです。NAND ゲートという 1 種類の部品だけを使って、CPU、メモリ、オペレーティングシステムを段階のに構築し、最終のにテトリスゲームを動かすという挑戦です。コンピュータの低レイヤに興味があるなら、強くお勧めします。 "以下では"vis-network"3 入力多数決回路（Y = AB + BC + AC）を可視化しています。""入力ノード A、B、C をクリックして 0/1 を切り替えます""、回路は自動的に評価され、すべての配線の色を更新します——""赤色""は信号が 1 であることを示し、""灰色""は信号が 0 であることを示します。""ステップ 1：真理値表"
A B A > B A = B A < B 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 "ステップ 2：論理式"
"ステップ 3：コード実装"
実例
"# 2 つの 1 ビット 2 進数 A と B を比較"
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
return 1 if a == 1 or b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
def one_bit_comparator(a, b):
"""
"1 ビット比較器：A と B を比較します。"
"3 要素タプル (Greater, Equal, Less) を返します"
"""
greater = AND(a, NOT(b)) "# A > B: A=1 かつ B=0"
less = AND(NOT(a), b) "# A < B: A=0 かつ B=1"
"# A = B: greater でも less でもない"
"# NOT(A XOR B) と等価。ここでは別の実装を使用"
equal = AND(NOT(greater), NOT(less))
return (greater, equal, less)
"# 真理値表を出力"
print("=" * 50)
print(" 1 ビット比較器の真理値表（サンプル デモ）")
print("=" * 50)
print()
print("┌───┬───┬────────┬────────┬────────┐")
print("│ A │ B │ A > B │ A = B │ A < B │")
print("├───┼───┼────────┼────────┼────────┤")
for a in [0, 1]:
for b in [0, 1]:
gt, eq, lt = one_bit_comparator(a, b)
print(f"│ {a} │ {b} │ {gt} │ {eq} │ {lt} │")
print("└───┴───┴────────┴────────┴────────┘")
"# いくつかの有用なシナリオをテスト"
print("\n"テストシナリオ：")
a_test, b_test = 1, 0
gt, eq, lt = one_bit_comparator(a_test, b_test)
print(f"A={a_test}, B={b_test}: A>B={gt}, A=B={eq}, A<B={lt}")
print(f"解釈：A は B より大きい" if gt else ("A は B に等しい" if eq else "A は B より小さい"))
ケース4：2-4 デコーダー
真理値表
A1 A0 Y0 Y1 Y2 Y3 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 "論理式"
実例
"# 入力：2 ビット 2 進数 A1 A0"
"# 出力：4 本の線のうちちょうど 1 本が 1"
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
def decoder_2to4(a1, a0):
"""
"2 線から 4 線へのデコーダ。"
"リスト [Y0, Y1, Y2, Y3] を返します。"
"そのうちちょうど 1 つが 1 で、残りは 0 です。"
"""
Y0 = AND(NOT(a1), NOT(a0)) # 00 → Y0
Y1 = AND(NOT(a1), a0) # 01 → Y1
Y2 = AND(a1, NOT(a0)) # 10 → Y2
Y3 = AND(a1, a0) # 11 → Y3
return [Y0, Y1, Y2, Y3]
"# 真理値表を出力"
print("=" * 50)
print(" 2-4 デコーダの真理値表（サンプル デモ）")
print("=" * 50)
print()
print("┌────┬────┬────┬────┬────┬────┐")
print("│ A1 │ A0 │ Y0 │ Y1 │ Y2 │ Y3 │")
print("├────┼────┼────┼────┼────┼────┤")
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
print(f"│ {a1} │ {a0} │ {Y[0]} │ {Y[1]} │ {Y[2]} │ {Y[3]} │")
print("└────┴────┴────┴────┴────┴────┘")
"# 実際の使用シナリオを示す"
print("\n"実際の応用シナリオ：デコーダでレジスタを選択")
registers = ["R0", "R1", "R2", "R3"]
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
idx = Y.index(1) "# どの出力線が 1 かを特定"
print(f" アドレス A1A0={a1}{a0} → レジスタ {registers[idx]} を選択")
万能ゲート：NAND と NOR の特別な点
実例
"# NAND ゲート単独で NOT、AND、OR の 3 つの基本機能を実装できます"
def NAND(a, b):
'"""NAND ゲート：AND の結果を反転。'
"Y = 0 になるのは a=1 かつ b=1 のときだけ"""
return 0 if a == 1 and b == 1 else 1
"# NAND で NOT を実装：NOT(A) = NAND(A, A)"
def NOT_from_NAND(a):
return NAND(a, a)
"# NAND で AND を実装：AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))"
def AND_from_NAND(a, b):
nand_ab = NAND(a, b)
return NAND(nand_ab, nand_ab)
"# NAND で OR を実装：OR(A,B) = NAND(NOT(A), NOT(B))"
def OR_from_NAND(a, b):
return NAND(NOT_from_NAND(a), NOT_from_NAND(b))
# ============================================
"# 検証"
# ============================================
print("=" * 60)
print(" NAND ゲートの万能性を証明（サンプル デモ）")
print("=" * 60)
print("\n"[検証：NAND で実装した NOT]")
for a in [0, 1]:
expected = 1 if a == 0 else 0
actual = NOT_from_NAND(a)
print(f" A={a}: NOT_from_NAND = {actual}, 期待値 = {expected}, {'合格' if actual == expected else '失敗'}")
print("\n"[検証：NAND で実装した AND]")
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 and b == 1 else 0
actual = AND_from_NAND(a, b)
print(f" A={a}, B={b}: AND_from_NAND = {actual}, 期待値 = {expected}, {'合格' if actual == expected else '失敗'}")
print("\n"[検証：NAND で実装した OR]")
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 or b == 1 else 0
actual = OR_from_NAND(a, b)
print(f" A={a}, B={b}: OR_from_NAND = {actual}, 期待値 = {expected}, {'合格' if actual == expected else '失敗'}")
print("\n"結論：NAND ゲート 1 種類だけで、任意のブール関数を構築できます。")
print("「だからこそ nand2tetris コースは NAND ゲートから始めてコンピュータ全体を組み立てられるのです。」")
インタラクティブデモ：多数決回路ビルダー（サンプル vis-network デモ）
3入力多数決回路（A/B/C ノードをクリックして切り替え）