2019.05.08: Andの真理値表と説明を修正(コメントを参照)。
IT関係の仕事をしているのですが、コンピュータの仕組みを実はちゃんと分かっていません。
一通り学びたいと思い、コンピュータシステムの理論と実装を読み始めました。
区切りごとに練習問題のようなものがあるので、それを解いた記録を残していきます。
nand2tetrisの公式サイトからハードウェアシミュレータ等、演習をやるのに必要なものをダウンロードできます。
前提
ハードウェアシミュレータでは論理ゲートをプログラミングにおける関数のように扱いますが、書き方は以下のようになります。
入力がaとbで出力がoutで、ゲート名がGateなら、
Gate(a = xxx, b = yyy, out = zzz);
これで、xxxをaに入力、yyyをbに入力、出力結果をzzzという変数に格納、という意味です。
1.5 1章演習
課題:この章で取り上げた論理ゲートを全部実装する。
本の中で紹介されていた順でやって行くと良いので、その順で書いていきます。
Nand
基本ゲート。
このゲートだけは存在するところから始める。このゲートから他の全てのゲートと回路を実装可能(つまりNand to tetris)。またこれ以降、過去に作成したゲートは使用して良いものとする。だから実装順は重要。
a | b | out |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Not
入力:in
出力:out
a | out |
---|---|
0 | 1 |
1 | 0 |
実装方法
与えらているゲートはNandのみです。これを使うと以下のように実装できます。
Nand(a = in, b = in, out = out)
真理値表は以下のようになります。
a | a | Nand(a,a) |
---|---|---|
0 | 0 | 1 |
1 | 1 | 0 |
And
入力:a, b
出力:out
a | b | out |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
実装方法
NandというのはNot Andなので、逆にAndは Not Nandです。まずNand(a,b)を計算し、その出力のnaoutのNotを取ると目的の出力になります。
Nand(a = a, b = b, out = naout);
Not(a = naout, out = out);
まずNandをとると、出力は1 1 1 0
になるので、その後Notをとれば目的の0 0 0 1
になります。簡単ですね。
Or
入力:a, b
出力:out
a | b | out |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
実装方法
出力は0 1 1 1
です。これは、Nandの出力1 1 1 0
を「上下反転」させたようなものですね。うまく表現できているかわかりませんが、入力も同じように「上下反転」させてNandをとれば目的の出力が得られそうです。というわけで、aとbそれぞれでNotをとってその出力のNandをとれば良さそうです。
Not(in = a, out = nota);
Not(in = b, out = notb);
Nand(a = nota, b = notb, out = out);
最後のNandゲートの真理値表は以下のようになります。
Not(a) | Not(b) | Nand(nota, notb) |
---|---|---|
1 | 1 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 1 |
Xor
入力:a, b
出力:out
a | b | out |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
実装方法
今まで出てきた出力を使ってできないか考えて見ます。今までの出力は以下のようになっています。
Not a | Not b | Nand | And | Or |
---|---|---|---|---|
1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 1 |
それぞれの組み合わせを試してみるとわかりますが、Orの出力とNandの出力に対してAndをとれば目的の出力になることがわかります。
Or(a = a, b = b, out = orab);
Nand(a = a, b = b, out = nandab);
And(a = orab, b = nandab, out = out);
真理値表にすると以下のようになります。
Or(a,b) | Nand(a,b) | And(orab, nandab) |
---|---|---|
0 | 1 | 0 |
1 | 1 | 1 |
1 | 1 | 1 |
1 | 0 | 0 |
続きは次回にします。次はマルチプレクサからです。
このエントリでは And と Nand の真理値表が一致していますが,ミスだと思います.
おそらくそれが原因で,
>まずNandをとると、出力は0 0 0 1になるので、その後Notをとれば目的の1 1 1 0になります。
このステートメントも偽です.
Nand をとると出力は 1 1 1 0 となり,その Not は 0 0 0 1 になります.これは And の真理値に一致します.
PARTS: 部分のコードは正しいです.
ご参考まで.
> radix_soupさん
ご指摘ありがとうございます!修正しておきました。