ひとりNand2Tetris(1) -NANDから他のゲートを作る

Posted by Hiraku on 2015-09-20

シルバーウィークは特にやることもないので、ひたすら「コンピュータシステムの理論と実装」を写経することにしました。NANDゲートだけ与えられた状態から、CPUを作りコンピュータを作りOSを作り、最終的にTetrisのようなゲームを動かすところを目指すというコンセプトの教科書です。通称"Nand2Tetris"。まだ一章を読み終わったところ。


コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方

付属のJava製シミュレーターをインストールして、あくまでシミュレーションとして作成してゆくので、別にハンダゴテとかは使いません。答えは付属していないけれど、テストケースが付属しているので簡単に正しいかどうか確かめられます。

読み捨てるのも勿体無いので、解いた結果をメモを残していきます。(自分用なので特に読みやすさとか意識せずに書きます)

一章 ブール論理

Nandゲートから、次章以降で使うゲートを一通り用意します。 作ったものは次の実装に使って良いものとなっているので、一つ解くたびに"Achivement Unlocked!!"みたいな感じで、使える道具が増えていきます。

Nand

この本だとNandゲートは既にあるものとして使って良いことになっています。 他の回路はNandから創りだしてゆきます。

abnand
001
011
101
110

回路図だとこんな風に書くらしい。

nand.jpg

Not

一つのinをNandのaとb両方に食わせてやると、Notの出力になります。

not.jpg

And

NandはAndの否定形なのだから、Nandの出力をNotで否定すればAndの出力が得られます。

and.jpg

Or

だんだん難しくなってきました。aとbをそれぞれ否定して、更にNandを取ればOrと同じ出力になります。

or.jpg

Xor

排他的論理和とかいうやつ。aとbが同じなら0, 違う値なら1を返します。

abxor
000
011
101
110

最初思いついたのは、Orの結果とNandの結果をAndすればちょうどXorになるのですが、もう少し素子を減らしたいところ。色々試した結果、Nand4つでいけるっぽい。

xor.jpg

Mux(マルチプレクサ)

inputにa,bともう一つ、selの3つを取り、sel==0ならばaと同じものを出力、sel==1ならばbと同じものを出力するというのがマルチプレクサです。

abselMux
0000
0100
1001
1101
0010
0111
1010
1111

3入力なのでここで少し苦戦しました。フォーラムを見ていても、結構壮大な答えが多い。うーん、、もっとシンプルに出来ないものか。

Chapter 1 - Mux

カルノー図

カルノー図というものを使うともっとシンプルな論理回路が作れるらしいので、書いてみることに。

さっきの真偽値表を並べ直して、こんな感じにします。

mux1.jpg

1が長方形または正方形に並んでいる部分を見つけて、それぞれ論理式を作り、最後にOrで組み合わせると回路が出来上がります。

(1) はa && !selで、(2)はb && selなので、最終的な回路はa && !sel || b && selでいけるはず。

Mux2.jpg

Notが二重になっているのは無駄なので消してしまうと、最終的にNand4つで書けました。いい感じ。

Mux3.jpg

DMux(デマルチプレクサ)

Muxの逆で、selに応じてinの値をaかbに振り分けるというもの。これはaとbを独立に考えればいいので、Muxに比べれば楽。

DMux.jpg

多入力/多出力

ここから先は多出力や多入力を扱うので、まともに絵を描いているとすごいサイズになってしまいます。使うゲートの数もかなり増えます。HDLで記述するだけでいいや。

hirak/nand2tetris-memo

たぶん続く。たぶん。

etcの最新記事

×

この広告は180日以上新しい記事の投稿がないブログに表示されております。