I try doing [Nand to Tetris](https://www.nand2tetris.org/) in Rust.
And, Or 等の基本的なチップを実装します。また本家ではHDLを使っており、 Nand はプリミティブなものとして扱っていますが、ここでは Nand のみ Rust 言語の演算子を組み合わせて使い、以降は Nand を使って実装します。
Nand を演算子で実装しようとすると、結局 And と Not の組み合わせになってしまいます。
pub fn nand(a: bool, b: bool) -> bool {
!(a && b)
}
Not は単項演算なので、 Nand に渡す際に入力を複製することになります。すると、自動的に Not の完成です。
pub fn not(input: bool) -> bool {
nand(input, input)
}
今回は Nand に Rust 言語の And を使っているのでわざわざ And を実装するのは手間に感じますが、既に Nand も Not もできているので単純に組み合わせるだけです。
pub fn and(a: bool, b: bool) -> bool {
not(nand(a, b))
}
Or は少し考える必要があります。ド・モルガンの法則より、 $\lnot{(a \land b)}=\lnot{a}\lor\lnot{b}$ が成り立つので、これを用いて以下のように実装します。
pub fn or(a: bool, b: bool) -> bool {
nand(not(a), not(b))
}
Xor の実装は個人的に Or より少し難しかったです。真理値表を考えると、
| $a$ | $b$ | $a \oplus b$ |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
であり、入力それぞれの否定を考えると、
| $a$ | $b$ | $\lnot{a}$ | $\lnot{b}$ | $a \oplus b$ |
|---|---|---|---|---|
| F | F | T | T | F |
| F | T | T | F | T |
| T | F | F | T | T |
| T | T | F | F | F |
すなわち、 $a \oplus b=(a \land \lnot{b})\lor(\lnot{a} \land b)$ で表されることが分かります。また、これらを Nand に分解していくと、
\[\begin{aligned} a \oplus b &= (a \land \lnot{b})\lor(\lnot{a} \land b)\\ &\iff \lnot{(\lnot{(a \land \lnot{b})}\land\lnot{(\lnot{a} \land b)})}\\ &\iff \text{Nand}(\text{Nand}(a,\lnot{b}),\text{Nand}(\lnot{a},b)) \end{aligned}\]となり、さらに $\text{Nand}(a, \lnot{b})=\text{Nand}(a, \text{Nand}(a, b))$ が成り立つことに注意すると、最小 Nand 数の実装は次のようになります。
pub fn xor(a: bool, b: bool) -> bool {
let tmp = nand(a, b);
nand(nand(a, tmp), nand(tmp, b))
}
Mux は multiplexor すなわち、 selector のことです。 selector 信号が On か Off かでそれぞれの入力と And を取れば良く、また Or が入力それぞれの論理否定を取った後 Nand していることと、 And が Nand の論理否定として実装されていることを考えると、次のように実装すれば最小 Nand 数で実装できます。
pub fn mux(a: bool, b: bool, selector: bool) -> bool {
nand(nand(not(selector), a), nand(selector, b))
}
DMux は demultiplexor すなわち、 Mux の逆です。 Mux が簡単に実装できたように、これも簡単に実装できます。
pub fn dmux(input: bool, selector: bool) -> (bool, bool) {
(and(input, not(selector)), and(input, selector))
}
multi-ways や multi-bits なものはほとんどこの繰り返しでテストコードが長くなるだけなので、この記事では省略します。よってこれで Project 1 は無事完了です。