一からコンピュータを作る ~ブール論理~


コンピュータシステムの理論と実装のアウトプットをしていくための記事です。
[コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方](https://www.amazon.co.jp/%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E3%81%AE%E7%90%86%E8%AB%96%E3%81%A8%E5%AE%9F%E8%A3%85-%E2%80%95%E3%83%A2%E3%83%80%E3%83%B3%E3%81%AA%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%81%AE%E4%BD%9C%E3%82%8A%E6%96%B9-Noam-Nisan/dp/4873117127)

実装は下記にまとめてあります。
[GitHub - sanoyo/nand2tetris](https://github.com/sanoyo/nand2tetris)

参考にした記事は下記になります。
[「コンピュータシステムの理論と実装」をやりきりました - Qiita](https://qiita.com/y-meguro/items/dc11c31cc2667aa20b3c)
[第1回「コンピュータシステムの理論と実装」の勉強会 - Cloudii blog](https://cloudii.atomitech.jp/entry/nand2tetris-01)
[コンピュータシステムの理論と実装 - 資料一覧 - connpass](https://nandtetris.connpass.com/presentation/?page=4)

## 全体像
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148392/3b8ed0a2-c741-2e4e-9443-12b66fe7e3c7.png)
[コンピュータシステムの理論と実装 – むくゆう](https://mukuyuu.com/planning/elements-of-computing-systems/) より引用


## ブール論理

### ブール式の基本
NOT / OR / AND が基本になります。
また上記3つの関数を NAND関数で表現することができます。

#### Nand関数(Not And関数)
名称から見てもわかる通り、Andの反対の性質を持ちます。

| a | b | Nand(a, b) |
|--:|--:|--:|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

一つ目の課題は、NAND だけ与えられた状態から、NOT / OR / AND / XOR などを実装することになります。

#### AND
NANDの真反対の結果になります。

| a | b | And(a, b) |
|--:|--:|--:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

ANDを作成するための実装は下記のようになります。

```hdl
# ゲート名
CHIP And {
    IN a, b;
    OUT out;

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

上記実装のイメージは下記のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148392/8102d660-26c8-1676-a1ee-c741a3e05049.png)


#### OR
| a | b | OR(a, b) |
|--:|--:|--:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |


#### NOT
`0` を `1` に、`1` を `0` にします。

#### XOR
| a | b | XOR(a, b) |
|--:|--:|--:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

#### MUX(マルチプレクサ)
3入力のゲートで、一つのアウトプットを返します。
[マルチプレクサ (MUX)とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典](https://wa3.i-3-i.info/word13228.html)

下記の実装だと、`sel`の部分が条件文になるイメージです。
この後のALUの実装で活躍してくれます。

```
CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
        Not(in=sel, out=notsel);

        And(a=a, b=notsel, out=and1);
        And(a=sel, b=b, out=and2);

        Or(a=and1, b=and2, out=out);
}
```

#### DMUX(デマルチプレクサ)
マルチプレクサとは反対のことを行います。
一つの入力に対して、複数の出力を返します。
[デマルチプレクサ (DEMUX)とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典](https://wa3.i-3-i.info/word13229.html)

下記実装の場合だと、 `sel`の条件文によって、出力を4パターン作成する実装になっています。


```DMux4Way.hdl
CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
        Not(in=sel[0], out=notsel0);
        Not(in=sel[1], out=notsel1);

        And(a=notsel0, b=notsel1, out=asel);
        And(a=in, b=asel, out=a);

        And(a=notsel1, b=sel[0], out=bsel);
        And(a=in, b=bsel, out=b);

        And(a=notsel0, b=sel[1], out=csel);
        And(a=in, b=csel, out=c);

        And(a=sel[0], b=sel[1], out=dsel);
        And(a=in, b=dsel, out=d);
}
```

## 準備
### 諸々インストール
[MacにNand2Tetrisのハードウェアシミュレータをインストールする - Qiita](https://qiita.com/daisukeokaoss/items/9cbc1a010e90000de370)
[Software \| nand2tetris](https://www.nand2tetris.org/software#comp-j92z7kw7)
[Java SE Development Kit 14 - Downloads](https://www.oracle.com/java/technologies/javase-jdk14-downloads.html)

### ハードウェアシミュレータ立ち上げ
`sh tools/HardwareSimulator.sh`

[O'REILLY コンピューターシステムの理論と実装【第1章②】 - sota0113](https://sota0113.hatenablog.com/entry/2019/01/13/153532)


### テストファイルの実行方法
- hdlファイルを読み込む
- Scriptを読み込んで、実行する

### 各ファイルの役割
**hdl**
実装が必要なファイル

**tst**
テスト用のファイル

**cmp**
正しい抽出結果か確認できるテスト用のファイル
And.cmpに書かれている条件のようにアウトプットできればOK

### VSCode拡張
[VSCodeをVerilogHDLのすごいエディタにする - たいちょーの雑記](https://xztaityozx.hatenablog.com/entry/2016/11/08/213413)