XORしない数学者 (ゲームに学ぶFPGA)

MHRD 楽しんでらっしゃいますでしょうか?

3つのハードウェアデザインゲーム(The Nand Game、MHRD、Digital Logic Design (The Game))のうち、わたしの超推しはMHRDです。コードを画面内に納めないといけないとか、コピペもままならない(できるけども)とか、このもどかしさとわけわからなさを味わっていただきたい。

『すべてがNANDになる』という言説どおり、そしてそれらの3つのゲームどおり、NOTもANDもORもNANDになりました。すべてがNANDになります。

XOR

NOT、AND、ORときたら、次はXOR。

Pythonだと ^ ですよね。

print(False ^ False) # False
print(True ^ False)  # True
print(False ^ True)  # True
print(True ^ True)   # False

XORもNANDになりますか。

Trick XOR Treat

前回同様にハロウィンでXORを再確認。

https://www.reddit.com/r/funny/comments/jhzdp5/trick_xor_treat/

今回注目したいのは右上。Trick XOR Treat。

じっと見ると見えてくる、XORの作り方。ANDで重ねあわせれば、同じ色のところだけ残ると。

Pythonで書き下せば、Trick ^ Treatはこのとおり。

(Trick or Treat) and (not (Trick and Treat))

テストしときましょう。

Trick = False
Treat = False
assert (Trick ^ Treat) == ((Trick or Treat) and (not (Trick and Treat)))

Trick = True
Treat = False
assert (Trick ^ Treat) == ((Trick or Treat) and (not (Trick and Treat)))

Trick = False
Treat = True
assert (Trick ^ Treat) == ((Trick or Treat) and (not (Trick and Treat)))

Trick = True
Treat = True
assert (Trick ^ Treat) == ((Trick or Treat) and (not (Trick and Treat)))

記号で書き表すと、こう。

ANDも、ORも、さくっとNANDに変換できましたよね。

完成!

って、なんかNANDの数、多くないですか。XORに6個もNAND必要?

ブール代数による解法

こっから先はANDとかORとかNOTとかNANDとかよりも、数学的にわかりやすいブール代数を使わざるを得ない。

ブール代数とか、かしこまっていっても、結局orを+にして、ANDを・にして、NOTは頭に−をかぶせるだけ(NANDはNOT ANDだから、ANDを・にして、頭に−をかぶせるだけ)。

なんでブール代数を使うかというと、分配法則が使いたいから。

ブール代数!? 分配法則!? なんかややこしそう。

って実は、中学数学での分配法則と同じ。これ。

(A + B) × C = (A × C) + (B × C)

ブール代数式でのXORのうち、A + Bを分配すると、このとおり。

記号で描いて見ましょう。これが分配前のXOR。

そして分配法則により(A or B)が分配されて、(A and (A nand B)) or (B and (A nand B))に。

ORの階層を上げて、OR以下をまるっとコピーした感じですね。

しかし、何かだまされた感。本当に同じかどうか、Pythonでテストしときましょう。

def nand(a, b):
    return not (a and b)


def xor(a, b):
    return a ^ b


def xor_version1(a, b):
    return (a or b) and nand(a, b)


def xor_version2(a, b):
    return (a and nand(a, b)) or (b and nand(a, b))


A = False
B = False
assert xor(A, B) == xor_version1(A, B) == xor_version2(A, B)

A = True
B = False
assert xor(A, B) == xor_version1(A, B) == xor_version2(A, B)

A = False
B = True
assert xor(A, B) == xor_version1(A, B) == xor_version2(A, B)

A = True
B = True
assert xor(A, B) == xor_version1(A, B) == xor_version2(A, B)

あって... いる、だと? あってます。

で、分配法則はわかったけど、なんで分配したのか説明してなくない? それは、その方がNANDの数が減るから。あとで記号で表すと見えてくる。

この式で、目ざわりなのは +。つまり OR。ORはNANDを3つも使うので消し去りたい。

何度もやっているように、NOTを2回つけても、式としては変化なし。

NOTにORとくれば、おなじみド・モルガンの法則。

Pythonでド・モルガンの法則を書けば、以下のとおり。

not (A or B) == ((not A) and (not B))

Javascriptなら、こう。

!(A || B) == (!A && !B)

ブール代数のXOR式にあてはめれば、このとおり。

完成!

... 完成?

完成!

なぜならば、この最終形態はNANDのみでできてます。まずこの二ヶ所。

次に、一つ上のこの二ヶ所。

最後に、式全体。

つまり、5個のNANDですね。

... ではなく、このA nand Bを使いまわせば、4個ですむんです。

記号で描けば一目瞭然。

念のため、一つ一つ確認してみます。まず、一番内側のNAND。このA nand Bを使いまわせば、の部分ですね。

次に、一つ上のこの二ヶ所。

最後に、式全体。

以上で、XOR完成!

Pythonでテストしときます。

def nand(a, b):
    return not (a and b)


def xor(a, b):
    nand_a_b = nand(a, b)
    return nand(nand(A, nand_a_b), nand(B, nand_a_b))


A = False
B = False
assert (A ^ B) == xor(A, B)

A = True
B = False
assert (A ^ B) == xor(A, B)

A = False
B = True
assert (A ^ B) == xor(A, B)

A = True
B = True
assert (A ^ B) == xor(A, B)

問題なし!

論理回路からの解法

分配法則をあてた後の論理回路から見直してみます。

同じ論理回路である(A nand B)は、当然一つにまとめられます。

ANDも、ORも、さくっとNANDに変換できましたよね。

見やすさを優先してNANDではなくNOTを使ってます。

うーん... 冗長だ。

NOT NOTは、二重否定的に、消せないわけはないですよね。

消した! あ、NANDが4個だけ! さっきと同じ!

ということで、XOR完成!

Verilog HDLからの図式

JavascriptでのXORは

OUT = B ^ A

Verilog HDLだと

module top (
    input A,
    input B,
    output OUT
);
assign OUT = B ^ A;
endmodule

こんなんですね。

呪文を唱えて、このVerilog HDLコードを図式してみると

yosys -q -p "
read_verilog xor.v
synth -top top
abc -g NAND
show -format svg -prefix xor
write_json -compat-int xor.json
"

Yosys abcによる変換だと、NANDは5個でした。

netlistsvg and.json

すべてがNANDになる

難関XORもNANDになりました。すべてがNANDになります。

次は超難関MUX!