はじめに

「コンピュータシステムの理論と実装」の第 1 章ブール論理まで終えました。
次に進む前に復習として、NAND だけで基本論理回路を再現してみます。

NAND ゲート（否定論理積回路）

「Not AND」。2 つの入力が両方とも 1 の時は 0 を出力し、それ以外は 1 を出力する。

A NAND B = !(A && B)

a	b	AND	NAND (= NOT(AND))
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

NAND で基本ゲートを作る

NOT ゲート

Inverter。入力信号を反転させる。0→1、1→0。

in	out
0	1
1	0

out = NOT(in)

これを NAND で構成する。
NAND に同じ信号を 2 つ入れると反転器になる。

A NAND A = !(A && A) = !A

つまり NotA は NAND で以下のように表現できる。

NOT A = A NAND A

Hack HDL で書くと

Not.hdl

CHIP Not {
    IN in;
    OUT out;

    PARTS:
        Nand(a=in, b=in, out=out);
}

AND ゲート

AND は両方 1 の時だけ 1、それ以外は 0 を出力する。

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

考え方。

A AND B = NOT(A NAND B)
        = (A NAND B) NAND (A NAND B)

POINT
NAND に同じ信号を 2 つ入れると反転する（NOT）。

And.hdl

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=b, out=nandOut);
    Nand(a=nandOut, b=nandOut, out=out);
}

OR ゲート

少なくとも 1 つが 1 の時に 1 を出力、それ以外は 0。

a	b	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

ド・モルガンの法則を使う

A OR B = NOT(NOT A AND NOT B)
       = (A NAND A) NAND (B NAND B)

ド・モルガンの法則
AND と OR の関係を反転して書き換えることが可能。

NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)

Or.hdl


CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=a, out=nota); // NOT A
    Nand(a=b, b=b, out=notb); // NOT B
    Nand(a=nota, b=notb, out=out); // 反転
}

XOR ゲート

排他的論理和。2 つの入力が異なる場合に 1 を、それ以外は 0 を出力する。

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

つまり、どちらか一方だけが 1 なら 1。
以下で定義。

A XOR B = (A AND !B) OR (!A AND B)

AND、OR、NOT をひとつずつ段階的に作っていく。

NOT を作る

NOT A = A NAND A
NOT B = B NAND B

AND 部分を作る

A AND !B = (A NAND !B) NAND (A NAND !B)
!A AND B = (!A NAND B) NAND (!A NAND B)

OR をド・モルガンの法則で NAND 化

X OR Y = (X NAND X) NAND (Y NAND Y)

HDL で書く。

Xor.hdl

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    //NOT
    Nand(a=a, b=a, out=nota);
    Nand(a=b, b=b, out=notb);

    //AND
    Nand(a=a, b=notb, out=and1);
    Nand(a=and1, b=and1, out=and1out);
    Nand(a=nota, b=b, out=and2);
    Nand(a=and2, b=and2, out=and2out);

    //OR
    Nand(a=and1out, b=and1out, out=notAnd1);
    Nand(a=and2out, b=and2out, out=notAnd2);
    Nand(a=notAnd1, b=notAnd2, out=out);
}

ちなみに、XOR は NAND4 つで構成可能。

A XOR B = (A NAND (A NAND B)) NAND (B NAND (A NAND B))

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=b, out=nand1);
    Nand(a=a, b=nand1, out=nand2);
    Nand(a=b, b=nand1, out=nand3);
    Nand(a=nand2, b=nand3, out=out);
}

オブジェクティブグループでは X の投稿も平日毎日行っています！
IT 関連の小ネタや便利技から、日常のアニメ・ゲーム布教なども幅広く投稿してるので、
ご興味のある方は是非フォロー・いいねをお願いします。