1章 ブール論理 (コンピュータシステムの理論と実装)

# はじめに
これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第１章 ブール論理のプロジェクトに対するレポートである。

Qiitaでは、画像の利用に制約があるため、論理ゲート図など掲載することは省いている。

# プロジェクトに対するレポート
## 目標
* Nandゲートにより、各論理ゲートを表現すること
* Notからデマルチプレクサまでは、Nandゲートのみ利用する。

## 材料
* Nand2Tetrisで定義しているHDL言語
* ハードウェアエミュレータ

## 実装
### Notゲート
Notゲートの真理値表は、以下の通りである。

| in  | out |
|:---:|:---:|
|  0  |  1  |
|  1  |  0  |

Nandゲートの真理値表と比較して、Nandゲートのa, bに同じ入力を入れたときと同じであるため、
NotゲートをHDLで実装すると以下の通りである。

```hdl:Not.hdl
    // Put your code here:
    Nand(a=in, b=in, out=out);
```

ハードウェアエミュレータを使い、Not.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### Andゲート
Andゲートの真理値表は、以下の通りである。

| a | b | out |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |


Andゲートは、NandゲートをNotしたものであるから、
AndゲートをHDLで実装すると以下の通りである。

```hdl:And.hdl
    // Put your code here:
    Nand(a=a, b=b, out=w1);
    Nand(a=w1, b=w1, out=out);
```

ハードウェアエミュレータを使い、And.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### Orゲート
Orゲートの真理値表は、以下の通りである。

| a | b | out |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |


Orゲートは、ド・モルガンの定理により、以下のようにAndにより表現できる。

```math
　\overline{(a + b)} = \overline{a} \cdot \overline{b}
```

OrゲートをHDLで実装すると以下の通りである。

```hdl:Or.hdl
    // Put your code here:
    Nand(a=a, b=a, out=w1);
    Nand(a=b, b=b, out=w2);
    Nand(a=w1, b=w2, out=out);
```

ハードウェアエミュレータを使い、Or.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### Xorゲート
Xorゲートの真理値表は、以下の通りである。

| a | b | out |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Xorゲートは、Nand2Tetrisに例として記載されており、それを利用することで実装する。

XorゲートをHDLで実装すると以下の通りである。

```hdl:Aor.hdl
    // Put your code here:
    Nand(a=a, b=a, out=nota);
    Nand(a=b, b=b, out=notb);
    Nand(a=a, b=notb, out=w1);
    Nand(a=nota, b=b, out=w2);
    Nand(a=w1, b=w2, out=out);
```

ハードウェアエミュレータを使い、Xor.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### マルチプレクサ
マルチプレクサの簡易的に記述した真理値表（真理値表ではない）は、以下の通りである。

| sel | out |
|:-:|:-:|
| 0 | a |
| 1 | b |

簡易的な真理値表から以下のとおりである。

```math
　out = \overline{sel} \cdot a + sel \cdot b
```

マルチプレクサをHDLで実装すると以下の通りである。

```hdl:Mux.hdl
    // Put your code here:
    Nand(a=sel, b=sel, out=notsel);
    Nand(a=a, b=notsel, out=w1);
    Nand(a=b, b=sel, out=w2);
    Nand(a=w1, b=w2, out=out);
```

ハードウェアエミュレータを使い、Mux.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### デマルチプレクサ
デマルチプレクサの簡易的に記述した真理値表（真理値表ではない）は、以下の通りである。

| sel | a | b |
|:-:|:-:|:-:|
| 0 | in | 0  |
| 1 | 0  | in |

簡易的な真理値表から以下のとおりである。

```math
  a = \overline{sel} \cdot in \\
  b + sel \cdot in
```

デマルチプレクサをHDLで実装すると以下の通りである。

```hdl:DMux.hdl
    // Put your code here:
    Nand(a=sel, b=sel, out=notsel);
    Nand(a=in, b=notsel, out=w1);
    Nand(a=in, b=sel, out=w2);
    Nand(a=w1, b=w1, out=a);
    Nand(a=w2, b=w2, out=b);
```

ハードウェアエミュレータを使い、Dmux.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

### 16ビットNotゲート
Notゲートを16個並列に並べる。

16ビットのNotゲートをHDLで実装すると以下の通りである。

```hdl:Not16.hdl
    // Put your code here:
    Not(in=in[0], out=out[0]);
    Not(in=in[1], out=out[1]);
    Not(in=in[2], out=out[2]);
    Not(in=in[3], out=out[3]);
    Not(in=in[4], out=out[4]);
    Not(in=in[5], out=out[5]);
    Not(in=in[6], out=out[6]);
    Not(in=in[7], out=out[7]);
    Not(in=in[8], out=out[8]);
    Not(in=in[9], out=out[9]);
    Not(in=in[10], out=out[10]);
    Not(in=in[11], out=out[11]);
    Not(in=in[12], out=out[12]);
    Not(in=in[13], out=out[13]);
    Not(in=in[14], out=out[14]);
    Not(in=in[15], out=out[15]);
```

ハードウェアエミュレータを使い、Not16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 16ビットAndゲート
Andゲートを16個並列に並べる。

16ビットのAndゲートをHDLで実装すると以下の通りである。

```hdl:And16.hdl
    // Put your code here:
    And(a=a[0], b=b[0], out=out[0]);
    And(a=a[1], b=b[1], out=out[1]);
    And(a=a[2], b=b[2], out=out[2]);
    And(a=a[3], b=b[3], out=out[3]);
    And(a=a[4], b=b[4], out=out[4]);
    And(a=a[5], b=b[5], out=out[5]);
    And(a=a[6], b=b[6], out=out[6]);
    And(a=a[7], b=b[7], out=out[7]);
    And(a=a[8], b=b[8], out=out[8]);
    And(a=a[9], b=b[9], out=out[9]);
    And(a=a[10], b=b[10], out=out[10]);
    And(a=a[11], b=b[11], out=out[11]);
    And(a=a[12], b=b[12], out=out[12]);
    And(a=a[13], b=b[13], out=out[13]);
    And(a=a[14], b=b[14], out=out[14]);
    And(a=a[15], b=b[15], out=out[15]);
```

ハードウェアエミュレータを使い、And16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 16ビットOrゲート
Orゲートを16個並列に並べる。

16ビットのOrゲートをHDLで実装すると以下の通りである。

```hdl:Or16.hdl
    // Put your code here:
    Or(a=a[0], b=b[0], out=out[0]);
    Or(a=a[1], b=b[1], out=out[1]);
    Or(a=a[2], b=b[2], out=out[2]);
    Or(a=a[3], b=b[3], out=out[3]);
    Or(a=a[4], b=b[4], out=out[4]);
    Or(a=a[5], b=b[5], out=out[5]);
    Or(a=a[6], b=b[6], out=out[6]);
    Or(a=a[7], b=b[7], out=out[7]);
    Or(a=a[8], b=b[8], out=out[8]);
    Or(a=a[9], b=b[9], out=out[9]);
    Or(a=a[10], b=b[10], out=out[10]);
    Or(a=a[11], b=b[11], out=out[11]);
    Or(a=a[12], b=b[12], out=out[12]);
    Or(a=a[13], b=b[13], out=out[13]);
    Or(a=a[14], b=b[14], out=out[14]);
    Or(a=a[15], b=b[15], out=out[15]);
```

ハードウェアエミュレータを使い、Or16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 16ビットマルチプレクサ
マルチプレクサを16個並列に並べる。

16ビットのマルチプレクサをHDLで実装すると以下の通りである。

```hdl:Mux16.hdl
    // Put your code here:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
```

ハードウェアエミュレータを使い、Mux16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 8入力のOrゲート
多入力のゲートは、2入力を段階的に繰り返していく。高校野球のトーナメントのようなイメージである。

8入力のOrゲートは、まず、8入力をOrゲートに入れ結果を出す。
その結果を再度Orゲートに入力していき、最終的に1つに絞る。

8入力のOrゲートをHDLで実装すると以下の通りである。

```hdl:Or8Way.hdl
    // Put your code here:
    Or(a=in[0], b=in[1], out=w1);
    Or(a=in[2], b=in[3], out=w2);
    Or(a=in[4], b=in[5], out=w3);
    Or(a=in[6], b=in[7], out=w4);
    Or(a=w1, b=w2, out=w5);
    Or(a=w3, b=w4, out=w6);
    Or(a=w5, b=w6, out=out);
```

ハードウェアエミュレータを使い、Or8Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 多入力のマルチプレクサ
多入力のマルチプレクサは、まず、sel[0]でマルチプレクサの結果を
一つ出し、その結果をsel[1]でマルチプクサに入力し結果とする。
4入力のマルチプレクサをHDLで実装すると以下の通りである。

```hdl:Mux4Way16.hdl
    // Put your code here:
    Mux16(a=a, b=b, sel=sel[0], out=w1);
    Mux16(a=c, b=d, sel=sel[0], out=w2);
    Mux16(a=w1, b=w2, sel=sel[1], out=out);
```

ハードウェアエミュレータを使い、Mux4Way16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

8入力のマルチプレクサをHDLで実装すると以下の通りである。

```hdl:Mux8Way16.hdl
    // Put your code here:
    Mux16(a=a, b=b, sel=sel[0], out=w1);
    Mux16(a=c, b=d, sel=sel[0], out=w2);
    Mux16(a=e, b=f, sel=sel[0], out=w3);
    Mux16(a=g, b=h, sel=sel[0], out=w4);
    Mux16(a=w1, b=w2, sel=sel[1], out=w5);
    Mux16(a=w3, b=w4, sel=sel[1], out=w6);
    Mux16(a=w5, b=w6, sel=sel[2],out=out);
```

ハードウェアエミュレータを使い、Mux8Way16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

### 多出力のデマルチプレクサ
多出力のデマルチプレクサは、まず、sel[1]でデマルチプレクサの結果を
一つ出し、その結果をsel[0]でデマルチプクサに入力し結果とする。
4出力のデマルチプレクサをHDLで実装すると以下の通りである。

```hdl:DMux4Way.hdl
    // Put your code here:
    DMux(in=in, sel=sel[1], a=w1, b=w2);
    DMux(in=w1, sel=sel[0], a=a, b=b);
    DMux(in=w2, sel=sel[0], a=c, b=d);
```

ハードウェアエミュレータを使い、DMux4Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

8出力のマルチプレクサをHDLで実装すると以下の通りである。

```hdl:DMux8Way.hdl
    // Put your code here:
    DMux(in=in, sel=sel[2], a=w1, b=w2);
    DMux(in=w1, sel=sel[1], a=w3, b=w4);
    DMux(in=w2, sel=sel[1], a=w5, b=w6);
    DMux(in=w3, sel=sel[0], a=a, b=b);
    DMux(in=w4, sel=sel[0], a=c, b=d);
    DMux(in=w5, sel=sel[0], a=e, b=f);
    DMux(in=w6, sel=sel[0], a=g, b=h);
```

ハードウェアエミュレータを使い、DMux8Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。

## 考察
各論理ゲートをNandゲートのみで実装した。Nandゲートの利用個数を以下の表にまとめる。Mux4Way16、Mux8Way16は16ビットあるが、マルチプレクサとしては、16個分あるわけではく1つ分で処理している。

| 論理ゲート | Nandゲート個数 | 説明 |
|:-:|:-:|:-:|
| Not | 1 ||
| And | 2 ||
| Or | 3 ||
| Xor | 5 ||
| Mux | 4 ||
| DMux | 5 ||
| Not16 | 16 | Notが16個のため |
| And16 | 32 | Andが16個 |
| Or16 | 48 | Orが16個 |
| Mux16 | 64 | Muxが16個 |
| Or8Way | 21 | Orが7個 |
| Mux4Way16 | 12 | Muxが3個 |
| Mux8Way16 | 28 | Muxが7個 |
| DMux4Way | 15 | Dmuxが3個 |
| DMux8Way | 35 | DMuxが7個 |