#nandris コンピュータシステムの理論と実装 読書会(2) に参加してきました

「コンピュータシステムの理論と実装」は論理回路から順を追ってコンピュータの仕組みを知ろうという教科書です。
Nand回路から初めて論理回路、加算器から機械語、OSや高級言語のコンパイラを経てテトリスを作っちゃおうという、デアゴスティーニでやりそうな構成。

この本の内容はNand2Tetrisというオンライン学習コースで、私はこのTED Talksで知りました。

独習コンピュータ教程



Nandからテトリスまでつなぎ目無く作っていくというのは、なんとなく冒険心を刺激されるものがありますね。
学習コースでは資料全部、ハードウェアシミュレータのようなツールも全部公開されてるので本当に独習できるんですが、全部英語なのが難点でした。
いつかやろうと思って放置してましたが日本語訳が出たというなら、今でしょッ！　ということでちょうどよく開催されていた読書会に参加！

コンピュータシステムの理論と実装 読書会(2) - connpass



第2回は主に論理回路とブール代数でした。ここらへんは情報系工業高校に通った身なので死ぬほどやったところ。すごく懐かしかったです。
論理回路のキモはNand回路が一種類があればAnd、Or、Notがすべて構成できるってこと。さらにそれらを使ってつくるマルチプレクサなども作れます。

書いたHDLをハードウェアシミュレータで動かしてみることもできます。ハードウェアシミュレータ＋今後必要なツールはここからダウンロードできます。

The Elements of Computing Systems / Nisan & Schocken



NandかNorから他の論理素子を作れることは分かったけど、別のものを元に論理素子を作ることは出来ないのかな？　ということでマルチプレクサからAndとNotを作ってみました。
Andは $out = b \cdot sel$。

Notは $out = \overline{sel} $。

HDLのコードで書くとこんな感じ（HDLでは1,0はtrue,falseで表すらしい）。

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Mux (a=true, b=false, sel=in, out=out);
}

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
    Mux (a=false, b=a, sel=b, out=out);
}

元になる論理素子からNotが作れればなんとかなりそうですね。
And、OrだけじゃNotは作れないだろうけど、そのことってどうやって証明するんだろうなー。




ブール算術の章は2の補数のところまでで今回は終了。2の補数は2進数でマイナスの数を表す約束事ですが、これを採用すれば足し算回路だけで引き算も表現できるので超重要です。使わないと引き算回路も別に作らないといけなくなって不経済。
1の補数というのもあるのですが、これだと−０と＋０が出来てしまって効率的じゃないのです。途中で@yshigeruさんが紹介してくれた式変形が、1の補数から2の補数への変化をわかりやすく表現していて良かったです。

\[ a + \overline{a} = -1 \]
\[ \overline{a} + 1 = -a \]



次回はちょっと長めですがそのぶんゆっくりできるでしょう。興味ある人はどうぞ。
コンピュータシステムの理論と実装 読書会(3) 休日編 - connpass







【おまけ】Nandのみで作ったAnd,Or,NotのHDLコード
NandOnly.hdl