コンピュータシステムの理論と実装読書ログ

Nand2tetris読書ログ 1 〜 Not, And, Or, Xor

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

続きは次回にします。次はマルチプレクサからです。

Nand2tetris読書ログ 2

2 Comments

  1. このエントリでは And と Nand の真理値表が一致していますが,ミスだと思います.
    おそらくそれが原因で,
    >まずNandをとると、出力は0 0 0 1になるので、その後Notをとれば目的の1 1 1 0になります。
    このステートメントも偽です.
    Nand をとると出力は 1 1 1 0 となり,その Not は 0 0 0 1 になります.これは And の真理値に一致します.
    PARTS: 部分のコードは正しいです.
    ご参考まで.

    1. > radix_soupさん
      ご指摘ありがとうございます!修正しておきました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です