『コンピュータシステムの理論と実装』という本を買いました。
最近勉強したいと思っていた事と近そうな内容で、レビューも良かったので楽しみ。
プロプラグラマでもなく趣味で書いてるだけの私ですが、備忘録的に各章の回答を載せて行くことにします。
実行環境~
MacBook Air(M1, 2020)
macOS Big Sur 11.5.1
コンピュータシステムの理論と実装 初版第7刷
#準備 Hardware Simulatorの実行（超初心者向け)
Simulatorの準備を表示する
注意 以下3つの記述はnand2tetrisをdesktopに置いている人のみ。
違う所に置いた人はcdのところを各々変えてください。
蛇足でしょうが下のコードは1行ずつ入力してね。
cd desktop
cd nand2tetris
cd tools
chmod 777 HardwareSimulator.sh
僕のMacにはjavaが入っておらずこのままでは実行できなかったので下記。
Homebrewが入っていない人は「Homebrew インストール」とかで調べて、
Homebrew入れてから実行してください。
brew install java
sudo ln -sfn $(brew --prefix)/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk
パスワードが求められるので入力してEnter。
その後
cd ..
cd ..
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &
desktopまで戻って本書に書いてある実行用のコマンド入力。
#「1.5 プロジェクト」に挑戦
※詳細な画面操作などについて書いてます。忙しい方はこの次のタグの「回答」をご覧ください。
~/Desktop/nand2tetris/tools/HardwareSimulator.sh &
本書に記載の方法でHardware Simulatorを開きました。ここに編集したファイルを入力してテストするんですね。
ではNotから実装してみます。~/nand2tetris/projects/01/内のNot.hdlを編集。編集にはSublime Text4を使いました。
ちなみに回路の話は全くの初心者なので、実際にLEDとか使って組んでいる人の記事を色々参考にしました...後は本書の11ページ、XorのHDLプログラムのソースと図を読んでいる内になんとなく分かってきました。int 理解力 = 0。
//Put your code here:はデフォで書かれてます。あえて残しました。
その下が僕が書いたものになります。
/**
* Not gate:
* out = not in
*/
CHIP Not {
IN in;
OUT out;
PARTS:
// Put your code here:
Nand(in=a, in=b, out=out);
}
.hdlファイルを編集して保存したら、Hardware Simulatorの左上FileからLoad Chipを選択。Not.hdlを選んでLoad Chip。
次にLoad Scriptからtstを選択してload。同じ手順です。
多分Simulatorが下のように更新されたはずです。
そうしたらこれ↓を押してテスト開始です。
Simulatorの左下にEnd of Script -Compression ended successfullyが
出たら文字通り成功です。
そうすると、~/nand2tetris/projects/01/内にNot.outというファイルが勝手に出来上がります。みてみましょう。
| in | out |
| 0 | 1 |
| 1 | 0 |
入力が0の時は1を返す、入力が1の時は0を返すの2通りしかないので、成功です！
なお一々.outファイルを見に行くのも面倒なので、Hardware Simulatorの右上のView:からoutputで自分のtest結果を、compareで模範解答を見られます。
View:
Output テスト結果
Compare 模範回答
結果と模範回答の出力結果が同じなので、今回書いたNot回路が正解ということがわかります。
男子個人 詳細な操作説明記載 日本代表
回答
Not
入力 in 出力 out 関数 If in=0 then out=1 else out=0
入力と逆の出力をします。
Nandの入出力には4パターンありますが、そのうち「aとbの出力が両方0なら1を返す」、「両方1なら0を返す」という2パターンはNotと同じです。
なのでNandの入力の2つを1つに結べばNot回路になります。(...と、こちらの記事に書いてありました。)
CHIP Not {
IN in;
OUT out;
PARTS:
Nand(a=in, b=in, out=out);
}
And
入力 in 出力 out 関数 If a=b=1 then out = 1 else out = 0
Nandの結果を反転させればAndの結果になります。
Nandで2つ入力→出力されたものを(Nandで作った)Notにかける = And。
Nandだけで表現するのが目標なので2パーツともNandで書いていますが、
分かりやすく書くと下のコメントアウト内のパーツになります。
CHIP And {
IN a, b;
OUT out;
PARTS:
Nand(a=a,b=b,out=Nout);
Nand(a=Nout,b=Nout,out=out);
/*
結局こういうこと
Nand(a=a,b=b,out=Nout);
Not(in=Nout,out=out);
*/
}
Or
入力 in 出力 out 関数 If a=b=0 then out = 0 else out = 1
どちらか若しくは両方が1なら1を返します。
Nandは両方１の時のみ0を返します。Nandへの入力をNotで逆にして、
aの逆、bの逆を再度NandにかければOrと同じ結果が得られます。
(0,0) 逆に (1,1) Nand-> (0)
(1,0) 逆に (0,1) Nand-> (1)
(0,1) 逆に (1,0) Nand-> (1)
(1,1) 逆に (0,0) Nand-> (1)
これで0,0の入力時に0出力、他は1を再現できました。
CHIP Or {
IN a, b;
OUT out;
PARTS:
Nand(a=a,b=a,out=Nouta);
Nand(a=b,b=b,out=Noutb);
Nand(a=Nouta,b=Noutb,out=out);
/*
Not(in=a,out=outa);
Not(in=b,out=outb);
Nand(a=outa,b=outb,out=out);
でも可
*/
}
Xor
入力 in 出力 out 関数 If a ≠ b then out = 1 else out = 0
入力abが異なる場合にだけ1を返します。
入力(0,0)出力(0)
入力(1,0)出力(1)
入力(0,1)出力(1)
入力(1,1)出力(0)
これに関しては本書11ページ、XorのHDLのソースと図を見た方がイメージ湧くと思います...
ただNandだけで実装することが目的なので長いですがコードを書いていきます。
CHIP Xor {
IN a, b;
OUT out;
PARTS:
// Not
Nand(a=a,b=a,out=NotOutA);
Nand(a=b,b=b,out=NotOutB);
//And
Nand(a=a,b=NotOutB,out=NandOutA);
Nand(a=NandOutA,b=NandOutB,out=AndOutA);
Nand(a=b,b=NotOutA,out=NandOutB);
Nand(a=NandOutB,b=NandOutB,out=AndOutB);
//Or
Nand(a=AndOutA,b=AndOutA,out=OrOutA);
Nand(a=AndOutB,b=AndOutB,out=OrOutB);
Nand(a=OrOutA,b=OrOutB,out=out);
}
Multiplexor
aとb2つの入力から、selが0ならaから、selが1ならbを選択して出力するゲートとのこと。
入力 a,b,sel 関数 If sel = 0 then out = a else out = b
要はselが0の時はaだけ見て、selが1の時はbだけ見るので
| a | b | sel | out |
|---|---|---|---|
| 0 | - | 0 | 0 |
| 1 | - | 0 | 1 |
| - | 0 | 1 | 0 |
| - | 1 | 1 | 1 |
の表のように考えれば良いです。
aを見るときはselをNotで逆にしAndを通し、bを見る時はNotを使わずにAndを通す...すると、
a=0,sel=1 -> And 0 aを見たが0、bは見ていないので結果は0。
a=1,sel=1 -> And 1 aを見ると1、bは見ていないので結果は1。
b=0,sel=1 -> And 0 bを見たが0、aは見ていないので結果は0。
b=1,sel=1 -> And 1 bを見ると1、aは見ていないので結果は1。
とシンプルになります。つまり両方0なら0、片方が0でももう片方が1なら1を返せばOK。
両方1はあり得ません。これはOrを使えば実装することができます。
CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
//aを見る用のNot sel作成
Nand(a=sel,b=sel,out=NotSel);
Nand(a=a,b=NotSel,out=AndA);
Nand(a=AndA,b=AndA,out=NotSelA);
Nand(a=b,b=sel,out=AndB);
Nand(a=AndB,b=AndB,out=SelB);
//Or
Nand(a=NotSelA,b=NotSelA,out=outA);
Nand(a=SelB,b=SelB,out=outB);
Nand(a=outA,b=outB,out=out);
}
Demultiplexor
Multiplexorの反対。入力 in,sel 出力 a, b
関数 If sel=0 then (a=in,b=0) else (a=0,b=sel)
出力が2つに増えましたが、実装はMultiplexorより簡単です。
inが1でもselが0ならb=0、つまりinもselも両方1の必要があるのでbの出力はAndが必要です。
aですが、selをNotで逆にしないとin=sel=1と確認できません。
実装は下記の通りです。※そろそろ全てNandで書くのに疲れてきました。
CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
Not(in=sel,out=NotSel);
And(a=in,b=NotSel,out=a);
And(a=in,b=sel,out=b);
}
多ビットNot
本当にこんな力技？と思って色々調べたんですが、変数宣言もforも失敗しました。そしてNandじゃなくてNotで書けばよかった..
CHIP Not16 {
IN in[16];
OUT out[16];
PARTS:
Nand(a=in[0],b=in[0],out=out[0]);
Nand(a=in[1],b=in[1],out=out[1]);
Nand(a=in[2],b=in[2],out=out[2]);
Nand(a=in[3],b=in[3],out=out[3]);
Nand(a=in[4],b=in[4],out=out[4]);
Nand(a=in[5],b=in[5],out=out[5]);
Nand(a=in[6],b=in[6],out=out[6]);
Nand(a=in[7],b=in[7],out=out[7]);
Nand(a=in[8],b=in[8],out=out[8]);
Nand(a=in[9],b=in[9],out=out[9]);
Nand(a=in[10],b=in[10],out=out[10]);
Nand(a=in[11],b=in[11],out=out[11]);
Nand(a=in[12],b=in[12],out=out[12]);
Nand(a=in[13],b=in[13],out=out[13]);
Nand(a=in[14],b=in[14],out=out[14]);
Nand(a=in[15],b=in[15],out=out[15]);
}
多ビットAnd
ゴリ押し
CHIP And16 {
IN a[16], b[16];
OUT out[16];
PARTS:
And(a=a[0],b=b[0],out=out[0]);
・・・略・・・
And(a=a[15],b=b[15],out=out[15]);
}
多ビットOr
ゴリ押し
CHIP Or16 {
IN a[16], b[16];
OUT out[16];
PARTS:
Or(a=a[0],b=b[0],out=out[0]);
・・・略・・・
Or(a=a[15],b=b[15],out=out[15]);
}
多ビットマルチプレクサ
割愛
CHIP Mux16 {
IN a[16], b[16], sel;
OUT out[16];
PARTS:
Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}
多入力Or
Orに7回通せば良いだけなので簡単。
CHIP Or8Way {
IN in[8];
OUT out;
PARTS:
Or(a=in[0],b=in[1],out=out1);
Or(a=out1,b=in[2],out=out2);
Or(a=out2,b=in[3],out=out3);
Or(a=out3,b=in[4],out=out4);
Or(a=out4,b=in[5],out=out5);
Or(a=out5,b=in[6],out=out6);
Or(a=out6,b=in[7],out=out);
}
多入力多ビットマルチプレクサ
Mux4Way16
inとselが倍になった分、2つのMux16に一度通して最後に
もう1度Mux16を通すことで実装。
CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];
PARTS:
Mux16(a=a, b=b, sel=sel[0], out=outA);
Mux16(a=c, b=d, sel=sel[0], out=outB);
Mux16(a=outA, b=outB, sel=sel[1], out=out);
}
Mux8Way16
Mux4からinが倍になっただけなのでMux4を2つ使い、最後にinが2つのMux16に通せば完了。ただsel[0..1]に辿り着くのに時間がかかった。
これ32や64bit用の基本ゲートとかを作ればもっと大きな入出力も簡単に実装できそう。
CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];
PARTS:
Mux4Way16(a=a,b=b,c=c,d=d,sel=sel[0..1],out=outA);
Mux4Way16(a=e,b=f,c=g,d=h,sel=sel[0..1],out=outB);
Mux16(a=outA,b=outB,sel=sel[2],out=out);
}
DMux4Way
Mux4wayの要領で実装。同じ様に、
CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
DMux(in=in, sel=sel[1], a=outA, b=outB);
DMux(in=outA, sel=sel[0], a=a, b=b);
DMux(in=outB, sel=sel[0], a=c, b=d);
}
DMux8Way
も、1度Dmux4Wayを通して、出力が8個になる様にselを変えたDmuxを
4種類実装すれば完了。
CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux4Way(in=in, sel=sel[1..2], a=outA, b=outB, c=outC, d=outD);
DMux(in=outA, sel=sel[0], a=a, b=b);
DMux(in=outB, sel=sel[0], a=c, b=d);
DMux(in=outC, sel=sel[0], a=e, b=f);
DMux(in=outD, sel=sel[0], a=g, b=h);
}
#感想戦
準備〜テストで3時間くらい、qiita書くのに何故か2時間くらいかかったので、日曜日の午前中が無くなりました。
NandからNot、And、Orを作った感動は束の間、forが使えないゴリ押しの状況で多ビットが始まり「なんだこれ合ってんのか...」という感じでしたが、
多ビットを使って多in多outが簡単に作れたので達成感がありました。上でも触れましたが、応用すれば32bit、64bitの実装もできるのかな？？？
以上、githubにコード上げれば良いのに丁寧に書きすぎて失踪不可避ですが
『コンピュータシステムの理論と実装』最後まで頑張ります。