I try doing [Nand to Tetris](https://www.nand2tetris.org/) in Rust.
半加算器や Alu 等の算術演算系のチップを実装します。
半加算器、すなわち下位からの繰り上がりを考慮しない 2bit の足し算の実装は、真理値表を見ると明らかです。
| $a$ | $b$ | $\text{carry}$ | $\text{sum}$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
よって繰り上がりには And を、 1bit 同士の和には Xor を用いれば実装できます。またこのとき、 And と Xor を Nand に分解すると $\lnot(a \land b)$ が共通することが分かるので、よって最小 Nand 数での実装は次のようになります。
pub fn half_adder(a: bool, b: bool) -> (bool, bool) {
let tmp = nand(a, b);
(not(tmp), nand(nand(a, tmp), nand(tmp, b)))
}
全加算器は半加算器を2回用いることで実装できます。また HalfAdder と同様に各チップを Nand に分解すると共通部分が見つかり、よって次のような実装で最小 Nand 数となります。
pub fn full_adder(a: bool, b: bool, c: bool) -> (bool, bool) {
let nab = nand(a, b);
let xor_ab = nand(nand(a, nab), nand(nab, b));
let tmp = nand(xor_ab, c);
(nand(nab, tmp), nand(nand(xor_ab, tmp), nand(tmp, c)))
}
16bit 同士の和の計算は全加算器を繰り返し用いることで実装できます。特に工夫できそうな点も無かったため素直に実装しました。
pub fn add16(a: &[bool; 16], b: &[bool; 16]) -> [bool; 16] {
let mut output = [false; 16];
let (c, s) = half_adder(a[15], b[15]);
let mut carry = c;
output[15] = s;
for i in 0..15 {
let (c, s) = full_adder(a[14 - i], b[14 - i], carry);
carry = c;
output[14 - i] = s;
}
output
}
Inc16 は Add16 に入力値と1を渡せば実装できます。
pub fn inc16(input: &[bool; 16]) -> [bool; 16] {
add16(
input,
&[
false, false, false, false, false, false, false, false, false, false, false, false,
false, false, false, true,
],
)
}
Alu は入出力ともに色々ありますが、これまでに実装したものを用いれば比較的簡単に実装できます。
pub fn alu(
a: &[bool; 16],
b: &[bool; 16],
zero_a: bool,
negate_a: bool,
zero_b: bool,
negate_b: bool,
f: bool,
negate_output: bool,
) -> ([bool; 16], bool, bool) {
let a = &and16(&[not(zero_a); 16], a);
let a = &mux16(a, ¬16(a), negate_a);
let b = &and16(&[not(zero_b); 16], b);
let b = &mux16(b, ¬16(b), negate_b);
let and_ab = &and16(a, b);
let add_ab = &add16(a, b);
let output = &mux16(and_ab, add_ab, f);
let output = mux16(output, ¬16(output), negate_output);
let zero = not(or(
or(
or(or(output[0], output[1]), or(output[2], output[3])),
or(or(output[4], output[5]), or(output[6], output[7])),
),
or(
or(or(output[8], output[9]), or(output[10], output[11])),
or(or(output[12], output[13]), or(output[14], output[15])),
),
));
let negate = output[0];
(output, zero, negate)
}
これで Project 2 完了です。