はじめに
これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第１章 ブール論理のプロジェクトに対するレポートである。
Qiitaでは、画像の利用に制約があるため、論理ゲート図など掲載することは省いている。
プロジェクトに対するレポート
目標
- Nandゲートにより、各論理ゲートを表現すること
- Notからデマルチプレクサまでは、Nandゲートのみ利用する。
材料
- Nand2Tetrisで定義しているHDL言語
- ハードウェアエミュレータ
実装
Notゲート
Notゲートの真理値表は、以下の通りである。
| in | out |
|---|---|
| 0 | 1 |
| 1 | 0 |
Nandゲートの真理値表と比較して、Nandゲートのa, bに同じ入力を入れたときと同じであるため、
NotゲートをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=in, b=in, out=out);
ハードウェアエミュレータを使い、Not.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
Andゲート
Andゲートの真理値表は、以下の通りである。
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Andゲートは、NandゲートをNotしたものであるから、
AndゲートをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=a, b=b, out=w1);
Nand(a=w1, b=w1, out=out);
ハードウェアエミュレータを使い、And.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
Orゲート
Orゲートの真理値表は、以下の通りである。
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Orゲートは、ド・モルガンの定理により、以下のようにAndにより表現できる。
\overline{(a + b)} = \overline{a} \cdot \overline{b}
OrゲートをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=a, b=a, out=w1);
Nand(a=b, b=b, out=w2);
Nand(a=w1, b=w2, out=out);
ハードウェアエミュレータを使い、Or.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
Xorゲート
Xorゲートの真理値表は、以下の通りである。
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Xorゲートは、Nand2Tetrisに例として記載されており、それを利用することで実装する。
XorゲートをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=a, b=a, out=nota);
Nand(a=b, b=b, out=notb);
Nand(a=a, b=notb, out=w1);
Nand(a=nota, b=b, out=w2);
Nand(a=w1, b=w2, out=out);
ハードウェアエミュレータを使い、Xor.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
マルチプレクサ
マルチプレクサの簡易的に記述した真理値表（真理値表ではない）は、以下の通りである。
| sel | out |
|---|---|
| 0 | a |
| 1 | b |
簡易的な真理値表から以下のとおりである。
out = \overline{sel} \cdot a + sel \cdot b
マルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=sel, b=sel, out=notsel);
Nand(a=a, b=notsel, out=w1);
Nand(a=b, b=sel, out=w2);
Nand(a=w1, b=w2, out=out);
ハードウェアエミュレータを使い、Mux.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
デマルチプレクサ
デマルチプレクサの簡易的に記述した真理値表（真理値表ではない）は、以下の通りである。
| sel | a | b |
|---|---|---|
| 0 | in | 0 |
| 1 | 0 | in |
簡易的な真理値表から以下のとおりである。
a = \overline{sel} \cdot in \\
b + sel \cdot in
デマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
Nand(a=sel, b=sel, out=notsel);
Nand(a=in, b=notsel, out=w1);
Nand(a=in, b=sel, out=w2);
Nand(a=w1, b=w1, out=a);
Nand(a=w2, b=w2, out=b);
ハードウェアエミュレータを使い、Dmux.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。
16ビットNotゲート
Notゲートを16個並列に並べる。
16ビットのNotゲートをHDLで実装すると以下の通りである。
// Put your code here:
Not(in=in[0], out=out[0]);
Not(in=in[1], out=out[1]);
Not(in=in[2], out=out[2]);
Not(in=in[3], out=out[3]);
Not(in=in[4], out=out[4]);
Not(in=in[5], out=out[5]);
Not(in=in[6], out=out[6]);
Not(in=in[7], out=out[7]);
Not(in=in[8], out=out[8]);
Not(in=in[9], out=out[9]);
Not(in=in[10], out=out[10]);
Not(in=in[11], out=out[11]);
Not(in=in[12], out=out[12]);
Not(in=in[13], out=out[13]);
Not(in=in[14], out=out[14]);
Not(in=in[15], out=out[15]);
ハードウェアエミュレータを使い、Not16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
16ビットAndゲート
Andゲートを16個並列に並べる。
16ビットのAndゲートをHDLで実装すると以下の通りである。
// Put your code here:
And(a=a[0], b=b[0], out=out[0]);
And(a=a[1], b=b[1], out=out[1]);
And(a=a[2], b=b[2], out=out[2]);
And(a=a[3], b=b[3], out=out[3]);
And(a=a[4], b=b[4], out=out[4]);
And(a=a[5], b=b[5], out=out[5]);
And(a=a[6], b=b[6], out=out[6]);
And(a=a[7], b=b[7], out=out[7]);
And(a=a[8], b=b[8], out=out[8]);
And(a=a[9], b=b[9], out=out[9]);
And(a=a[10], b=b[10], out=out[10]);
And(a=a[11], b=b[11], out=out[11]);
And(a=a[12], b=b[12], out=out[12]);
And(a=a[13], b=b[13], out=out[13]);
And(a=a[14], b=b[14], out=out[14]);
And(a=a[15], b=b[15], out=out[15]);
ハードウェアエミュレータを使い、And16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
16ビットOrゲート
Orゲートを16個並列に並べる。
16ビットのOrゲートをHDLで実装すると以下の通りである。
// Put your code here:
Or(a=a[0], b=b[0], out=out[0]);
Or(a=a[1], b=b[1], out=out[1]);
Or(a=a[2], b=b[2], out=out[2]);
Or(a=a[3], b=b[3], out=out[3]);
Or(a=a[4], b=b[4], out=out[4]);
Or(a=a[5], b=b[5], out=out[5]);
Or(a=a[6], b=b[6], out=out[6]);
Or(a=a[7], b=b[7], out=out[7]);
Or(a=a[8], b=b[8], out=out[8]);
Or(a=a[9], b=b[9], out=out[9]);
Or(a=a[10], b=b[10], out=out[10]);
Or(a=a[11], b=b[11], out=out[11]);
Or(a=a[12], b=b[12], out=out[12]);
Or(a=a[13], b=b[13], out=out[13]);
Or(a=a[14], b=b[14], out=out[14]);
Or(a=a[15], b=b[15], out=out[15]);
ハードウェアエミュレータを使い、Or16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
16ビットマルチプレクサ
マルチプレクサを16個並列に並べる。
16ビットのマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
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]);
ハードウェアエミュレータを使い、Mux16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
8入力のOrゲート
多入力のゲートは、2入力を段階的に繰り返していく。高校野球のトーナメントのようなイメージである。
8入力のOrゲートは、まず、8入力をOrゲートに入れ結果を出す。
その結果を再度Orゲートに入力していき、最終的に1つに絞る。
8入力のOrゲートをHDLで実装すると以下の通りである。
// Put your code here:
Or(a=in[0], b=in[1], out=w1);
Or(a=in[2], b=in[3], out=w2);
Or(a=in[4], b=in[5], out=w3);
Or(a=in[6], b=in[7], out=w4);
Or(a=w1, b=w2, out=w5);
Or(a=w3, b=w4, out=w6);
Or(a=w5, b=w6, out=out);
ハードウェアエミュレータを使い、Or8Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
多入力のマルチプレクサ
多入力のマルチプレクサは、まず、sel[0]でマルチプレクサの結果を
一つ出し、その結果をsel[1]でマルチプクサに入力し結果とする。
4入力のマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
Mux16(a=a, b=b, sel=sel[0], out=w1);
Mux16(a=c, b=d, sel=sel[0], out=w2);
Mux16(a=w1, b=w2, sel=sel[1], out=out);
ハードウェアエミュレータを使い、Mux4Way16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
8入力のマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
Mux16(a=a, b=b, sel=sel[0], out=w1);
Mux16(a=c, b=d, sel=sel[0], out=w2);
Mux16(a=e, b=f, sel=sel[0], out=w3);
Mux16(a=g, b=h, sel=sel[0], out=w4);
Mux16(a=w1, b=w2, sel=sel[1], out=w5);
Mux16(a=w3, b=w4, sel=sel[1], out=w6);
Mux16(a=w5, b=w6, sel=sel[2],out=out);
ハードウェアエミュレータを使い、Mux8Way16.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
多出力のデマルチプレクサ
多出力のデマルチプレクサは、まず、sel[1]でデマルチプレクサの結果を
一つ出し、その結果をsel[0]でデマルチプクサに入力し結果とする。
4出力のデマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
DMux(in=in, sel=sel[1], a=w1, b=w2);
DMux(in=w1, sel=sel[0], a=a, b=b);
DMux(in=w2, sel=sel[0], a=c, b=d);
ハードウェアエミュレータを使い、DMux4Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
8出力のマルチプレクサをHDLで実装すると以下の通りである。
// Put your code here:
DMux(in=in, sel=sel[2], a=w1, b=w2);
DMux(in=w1, sel=sel[1], a=w3, b=w4);
DMux(in=w2, sel=sel[1], a=w5, b=w6);
DMux(in=w3, sel=sel[0], a=a, b=b);
DMux(in=w4, sel=sel[0], a=c, b=d);
DMux(in=w5, sel=sel[0], a=e, b=f);
DMux(in=w6, sel=sel[0], a=g, b=h);
ハードウェアエミュレータを使い、DMux8Way.Tstスクリプトを動作させると、Comparison ended successfullyと表示された。
考察
各論理ゲートをNandゲートのみで実装した。Nandゲートの利用個数を以下の表にまとめる。Mux4Way16、Mux8Way16は16ビットあるが、マルチプレクサとしては、16個分あるわけではく1つ分で処理している。
| 論理ゲート | Nandゲート個数 | 説明 |
|---|---|---|
| Not | 1 | |
| And | 2 | |
| Or | 3 | |
| Xor | 5 | |
| Mux | 4 | |
| DMux | 5 | |
| Not16 | 16 | Notが16個のため |
| And16 | 32 | Andが16個 |
| Or16 | 48 | Orが16個 |
| Mux16 | 64 | Muxが16個 |
| Or8Way | 21 | Orが7個 |
| Mux4Way16 | 12 | Muxが3個 |
| Mux8Way16 | 28 | Muxが7個 |
| DMux4Way | 15 | Dmuxが3個 |
| DMux8Way | 35 | DMuxが7個 |