シルバーウィークは特にやることもないので、ひたすら「コンピュータシステムの理論と実装」を写経することにしました。NANDゲートだけ与えられた状態から、CPUを作りコンピュータを作りOSを作り、最終的にTetrisのようなゲームを動かすところを目指すというコンセプトの教科書です。通称"Nand2Tetris"。まだ一章を読み終わったところ。
コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方
付属のJava製シミュレーターをインストールして、あくまでシミュレーションとして作成してゆくので、別にハンダゴテとかは使いません。答えは付属していないけれど、テストケースが付属しているので簡単に正しいかどうか確かめられます。
読み捨てるのも勿体無いので、解いた結果をメモを残していきます。(自分用なので特に読みやすさとか意識せずに書きます）
一章 ブール論理
Nandゲートから、次章以降で使うゲートを一通り用意します。 作ったものは次の実装に使って良いものとなっているので、一つ解くたびに"Achivement Unlocked!!"みたいな感じで、使える道具が増えていきます。
Nand
この本だとNandゲートは既にあるものとして使って良いことになっています。 他の回路はNandから創りだしてゆきます。
| a | b | nand |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
回路図だとこんな風に書くらしい。
Not
一つのinをNandのaとb両方に食わせてやると、Notの出力になります。
And
NandはAndの否定形なのだから、Nandの出力をNotで否定すればAndの出力が得られます。
Or
だんだん難しくなってきました。aとbをそれぞれ否定して、更にNandを取ればOrと同じ出力になります。
Xor
排他的論理和とかいうやつ。aとbが同じなら0, 違う値なら1を返します。
| a | b | xor |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
最初思いついたのは、Orの結果とNandの結果をAndすればちょうどXorになるのですが、もう少し素子を減らしたいところ。色々試した結果、Nand4つでいけるっぽい。
Mux(マルチプレクサ)
inputにa,bともう一つ、selの3つを取り、sel==0ならばaと同じものを出力、sel==1ならばbと同じものを出力するというのがマルチプレクサです。
| a | b | sel | Mux |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 |
3入力なのでここで少し苦戦しました。フォーラムを見ていても、結構壮大な答えが多い。うーん、、もっとシンプルに出来ないものか。
カルノー図
カルノー図というものを使うともっとシンプルな論理回路が作れるらしいので、書いてみることに。
さっきの真偽値表を並べ直して、こんな感じにします。
1が長方形または正方形に並んでいる部分を見つけて、それぞれ論理式を作り、最後にOrで組み合わせると回路が出来上がります。
(1) はa && !selで、(2)はb && selなので、最終的な回路はa && !sel || b && selでいけるはず。
Notが二重になっているのは無駄なので消してしまうと、最終的にNand4つで書けました。いい感じ。
DMux(デマルチプレクサ)
Muxの逆で、selに応じてinの値をaかbに振り分けるというもの。これはaとbを独立に考えればいいので、Muxに比べれば楽。
多入力/多出力
ここから先は多出力や多入力を扱うので、まともに絵を描いているとすごいサイズになってしまいます。使うゲートの数もかなり増えます。HDLで記述するだけでいいや。
たぶん続く。たぶん。