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

# はじめに

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

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


# プロジェクトに対するレポート

## 目標
* 1章で作成した論理ゲートを使い、算術用の論理回路を作成する。

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

## 実装

### 半加算器
半加算器の真理値表は、以下の通りである。

| a | b | carry | sum |
|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |

半加算器は、AndゲートとXorゲートにより構成できることが真理値表からわかる。

```hdl:HalfAdder.hdl
    // Put your code here:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
```

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

### 全加算器
全加算器の真理値表は、以下の通りである。

| a | b | c | carry | sum |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |

まず、aとbを半加算器で計算し、その出力とcを半加算器で計算した結果を出力する。

```hdl:FullAdder.hdl
    // Put your code here:
    HalfAdder(a=a, b=b, sum=w1, carry=w2);
    HalfAdder(a=w1, b=c, sum=sum, carry=w3);
    Or(a=w2, b=w3, out=carry);
```

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


### 加算器
全加算器を16個並列に並べ、0桁目から順に計算していく。
最初の桁にはcは定数0とし、最後のcarryも特に利用しない(オーバフローのチェックに利用できる)。

```hdl:Add16.hdl
    // Put your code here:
   FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=w1);
   FullAdder(a=a[1], b=b[1], c=w1, sum=out[1], carry=w2);
   FullAdder(a=a[2], b=b[2], c=w2, sum=out[2], carry=w3);
   FullAdder(a=a[3], b=b[3], c=w3, sum=out[3], carry=w4);
   FullAdder(a=a[4], b=b[4], c=w4, sum=out[4], carry=w5);
   FullAdder(a=a[5], b=b[5], c=w5, sum=out[5], carry=w6);
   FullAdder(a=a[6], b=b[6], c=w6, sum=out[6], carry=w7);
   FullAdder(a=a[7], b=b[7], c=w7, sum=out[7], carry=w8);
   FullAdder(a=a[8], b=b[8], c=w8, sum=out[8], carry=w9);
   FullAdder(a=a[9], b=b[9], c=w9, sum=out[9], carry=w10);
   FullAdder(a=a[10], b=b[10], c=w10, sum=out[10], carry=w11);
   FullAdder(a=a[11], b=b[11], c=w11, sum=out[11], carry=w12);
   FullAdder(a=a[12], b=b[12], c=w12, sum=out[12], carry=w13);
   FullAdder(a=a[13], b=b[13], c=w13, sum=out[13], carry=w14);
   FullAdder(a=a[14], b=b[14], c=w14, sum=out[14], carry=w15);
   FullAdder(a=a[15], b=b[15], c=w15, sum=out[15], carry=w16);
```

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

### インクリメンタ
加算器を使い、bに定数1を入力する。

```hdl:Inc16.hdl
    // Put your code here:
   Add16(a=in, b[0]=true, b[1..15]=false, out=out);
```

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

### ALU
ALUを手順に従い作成する。

```hdl:ALU.hdl
    // Put your code here:
   // zero the x input
   Mux16(a=x, b[0..15]=false, sel=zx, out=w1);
   // negate the x input
   Not16(in=w1, out=w2);
   Mux16(a=w1, b=w2, sel=nx, out=w3);
   // zero the y input
   Mux16(a=y, b[0..15]=false, sel=zy, out=w4);
   // negate the y input
   Not16(in=w4, out=w5);
   Mux16(a=w4, b=w5, sel=ny, out=w6);
   // compute out=x + y (if f=1) or out=x&y (if f=0)
   And16(a=w3, b=w6, out=w7);
   Add16(a=w3, b=w6, out=w8);
   Mux16(a=w7, b=w8, sel=f, out=w9);
   // negate the out output
   Not16(in=w9, out=w10);
   Mux16(a=w9, b=w10, sel=no, out=out);
```

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

ngとzrについて検討する。ngは最上位ビットが0か1かで正負が決まるため、out[15]を使う。zrは、全ビットがゼロであることをチェックする。

```hdl:ALU.hdl
   Mux16(a=w9, b=w10, sel=no, out[0..7]=w11, out[8..15]=w12, out[15]=ng, out=out);
   // zr=1 if out==0, 0 otherwise
   Or8Way(in=w11, out=w13);
   Or8Way(in=w12, out=w14);
   Or(a=w13, b=w14, out=w15);
   Not(in=w15, out=zr);
```

## 考察
各論理回路のNandゲートの個数をいかにまとめる。説明のカッコ内に第1章で数えたNandゲートの個数を記載している。

| 論理回路 | Nandゲートの個数 | 説明 |
|:-:|:-:|:-:|
| HalfAdder | 7 | Xorゲート(5)＋Andゲート(2) |
| FullAdder | 17 | HalfAdder2個＋Orゲート(3)  |
| Add16 | 272 | FullAdder16個 |
| Inc16 | 272 | Add16 1個 |
|  ALU | 782 | Mux16(64) 6個 Not16(16) 3個 And16(32) 1個 Add16(272) 1個 Or8Way(21) 2個 Or(3) 1個 Not(1) 1個 |