一からコンピュータを作るぞ！ ~ブール算術~

2章の目標は、ALUを理解し、実装することです。
頑張っていきましょう！！

参考にした記事
CPUの演算処理を司るALUの仕組み - Qiita
実装を助けてくれるリポジトリ
GitHub - y-meguro/nand2tetris: 「コンピュータシステムの理論と実装」の演習用
GitHub - ikenox/nand2tetris: 『コンピュータシステムの理論と実装』演習問題の回答・メモ
GitHub - youkidearitai/nand2tetris: nand2tetris.org / コンピュータシステムの理論と実装の解答

PCで使用される計算

PCで使用される計算 = 論理演算 + 算術演算
コンピュータシステムの理論と実装2

加算器

• 半加算器
  2つのビットの和を求める
• 全加算器
  3つのビットの和を求める
• 加算器
  2つのnビットの和を求める
• インクリメンタ
  与えられた数値に1を加算するように設計される

この4つを組み合わせて、ALUをどう設計していくかを考えるのが2章の醍醐味になってきます。
加算器 - Wikipedia

半加算器

Xor と And で構成されます。
sum は、 Xor を指し、carry は And を指します。

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
        Xor(a=a, b=b, out=sum);
        And(a=a, b=b, out=carry);
}

全加算器

上記の半加算器と全加算器の違いは、繰り上がりを処理するかどうかになります。
論理回路の半加算器と全加算器の違いは何ですかすみませんが教え... - Yahoo!知恵袋

加算器には、下の桁からの桁上がりを考慮した全加算器と、考慮しない半加算器がある
CPUの中枢「ALU」を作ってみよう

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
        HalfAdder(a=a, b=b, sum=s1, carry=cr1);
        HalfAdder(a=s1, b=c, sum=sum, carry=cr2);
        Or(a=cr1, b=cr2, out=carry);
}

加算器(多ビット加算器)

Add16.hdlファイルの実装をどのようにしていくのか
加算器を実装することになります。
下記全体図はがわかりやすいです。

組合せ回路の例（加算回路） より引用

a[16]の16は、16ビットを指します。

インクリメンタ

どのようにしてビット演算で 1を足すことを実現するのかを考えていくことになります。
このときのポイントは反転させることにあります。
ビット演算は反転させるだけで、1を足したことになる

Indoor Space Cowboy: コンピュータシステムの理論と実装 第２章 ブール算術 回答例
2の補数表現における演算
O'REILLY コンピューターシステムの理論と実装【第2章①】 - sota0113

ALU

算術論理演算器と呼ばれています。
第二章は、ALUの実装を目指します。
最初は難しいですが、 単なる組み合わせ回路と思えば少し気が楽になります。

考え方とかは下記の記事とかが非常にわかりやすいです。
加算器の実装など (nand to tetris(6))

考えるべきこと

if文がかなり出てくるので、Muxが便利になる

// if (zx == 1) set x = 0のような条件式の場合は、 Muxが便利です。
Mux16 (a=x, b=false, sel=zx, out=w1);のようにselを起点に実装することができます。

set x = !xをどう実現するか

これは単純に Not で実装することができます。
Not16(in=x, out=notx);

f の条件分岐をどう実現するか

// if (f == 1) set out = x + y と // if (f == 0) set out = x & y には、 Add と And を実装することで解決することができます。

Or8way

１章　ブール理論（番外編）｜tango｜note

最上位、最下位ビット

最上位ビット - Wikipedia より引用

最下位ビット - Wikipedia より引用

足し算

XOR演算は「繰り上がりが無ければ、足し算と同じ結果」
AND演算は「繰り上がるかどうかが分かる(結果が1なら繰り上がる)」
ビット演算(AND,XOR,左シフト)だけで、足し算を行う。単純なようでいて、結構難しい…。 | メサイア・ワークス より引用

その他

ひとりNand2Tetris(2) - ALUまで: Architect Note