Nand2Tetrisやってみたその１〜Nandからブール演算編〜

#はじめに
###Nand2Tetrisとは
オライリーの「コンピュータシステムの理論と実装ーーモダンなコンピュータの作り方」という書籍の通称。

本書を書いた理由は、多くの学生が「木を見て森を見ず」の状態であるように思えたからである。（中略）彼ら彼女らは、コンピュータの中がどのようになっているかを理解していない。そして、そのことを心許なく思っているはずである。

今日のコンピュータサイエンスにおいて、各専門分野はどんどん複雑になってきています。
１つの分野のある一面を修めるだけでも相当な労力がかかり、CS全体を俯瞰する機会を得るのはなかなか難しいです。
この書籍は、「コンピュータを理解する最善の方法は、コンピュータをゼロから作り上げることである」をテーマに掲げ、そのような情報工学を学ぶ迷える学生の助けとなるべく書かれました。
###Nand２Tetrisの構成
コンピュータを構成する要素を、ブール論理から始まり高水準言語、コンパイラまで各分野について学びます。
それぞれの章では、各要素の概要を学んでから、実際に実装を行います。
各章は独立してモジュール化されていて、現在取り組んでいるレイヤよりも下位レイヤに属するモジュールは使い回すことができます。

#Nandからブール演算
この記事では、第１章の「ブール論理」まで扱います。
####コンピュータにおけるブールゲート
ブールゲートとは、ブール関数を物理的に実装したものです。その実装方法は様々ですが、それは情報工学の範疇を超えるので、ここでは論理的な振る舞いだけに着目します。

####正順表現
すべてのブール関数は（当然ですが）真理値表によって表現することができます。

例

x	y	z	f(x,y)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

真理表が分かっているすべてのブール関数は正順表現と呼ばれるブール式で表現できます。

出力が１となる各行に注目して、その入力の組み合わせの時のみ１を出力するブール式を考えます。
１を出力する全ての行について、得られたブール式たちをOrで繋げば仕様を満たす関数が得られます。

その入力の組み合わせの時のみ１を出力するブール式　とは

その行で０になっている入力を反転（Not）させて、すべての入力をAndで繋ぎます。
例えば、上の例では(x,y,z)=(0,1,0)の行で１を出力しています。ここで、((not x) and y and (not z))は、入力が（0,1,0）の時のみ１を出力します。

正順表現に使ったのはAnd,Not,Orだけです。
つまり、And,Not,Orだけであらゆるブール関数を表現できるということです。

そして、And,Not,OrもすべてNandだけで構成することができますから、Nandだけですべてのブール関数を表現できることになります。

#実装
(AndとかOrなどの予約後になりがちな名前を宣言してるのでqiitaのシンタックスハイライトがおかしい)
####Not実装

CHIP And {
    IN in;
    OUT out;

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

####And実装

CHIP And {
    IN a, b;
    OUT out;

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

####Or実装

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
	Not(in=a,out=nota);
	Not(in=b,out=notb);
	Nand(a=nota,b=notb, out=out);
}

###その他主要論理ゲート
ここでは割愛しますが、Xorやマルチプレクサ,デマルチプレクサ,それぞれの回路の16bit版なども実装しました。

#感想
コンピュータの最下層レイヤを触るにあたって、普段とかなり違う部分の脳を使っていたと思います。
今回実装したブールゲートたちは次のブール演算の実装で大活躍するので、愛着があります。
次回、「ブール関数からブール演算編」です。頑張って書きます。