卒業研究にコンピュータの理論と実装～モダンなコンピュータの作り方～ (通称:nand2tetris)を使って、コンピュータを作ることを決めたのでレポートとして経過をアップロードしていきます。
第1章 ブール論理
この章では、NotなどのゲートをNandだけでつくることができるのでそれをやってみようという章です。(結構パズルっぽい)
使用言語はハードウェア記述言語(HDL)です。
Not回路
回路図で表現すると、以下のようになります。
1つのNandだけでNotゲートが実装できるのがわかりますね
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Not.hdl
/**
* Not gate:
* out = not in
*/
CHIP Not {
IN in;
OUT out;
PARTS:
// Put your code here:
Nand(a=in,b=in,out=out);
}
Andゲート
回路図で表すと、2つの入力値をNandゲートを通し、出力した値をNandゲートに通す(前述のNot回路と同じ働き)ことで実装
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/And.hdl
/**
* And gate:
* out = 1 if (a == 1 and b == 1)
* 0 otherwise
*/
CHIP And {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Nand(a=a, b=b, out=w);
Nand(a=w, b=w, out=out);
}
Orゲート
回路図で表すと、aとbの入力をNandでNotしたそれぞれの出力結果をNandに通すと実装
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Or.hdl
/**
* Or gate:
* out = 1 if (a == 1 or b == 1)
* 0 otherwise
*/
CHIP Or {
IN a, b;
OUT out;
PARTS:
// 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);
}
Xorゲート
このあたりから回路図が複雑になっていきます。
コードは以下の通りです
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Xor.hdl
/**
* Exclusive-or gate:
* out = not (a == b)
*/
CHIP Xor {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Nand(a=a, b=b, out=w1);
Nand(a=a, b=w1, out=w2);
Nand(a=w1, b=b, out=w3);
Nand(a=w2, b=w3, out=out);
}マルチプレクサゲート
ご存じでない方もいるかもしれないので本文を引用すると、
3入力のゲートである。「データビット」と呼ばれるふたつの入力からひとつを選択して出力するために、
「選択ビット」と呼ばれる入力がひとつ用いられる。このゲートは「セレクタ」と呼ぶほうがふさわしいかもしれない。
「マルチプレクサ」という名前は通信システムで採用されたもので、そのシステムではいくつかの入力信号を1本のワイヤへ
出力とシリアライズするために、同じようなデバイスが使われている。
という回路で、aとbの入力に対し、選択ビットのselの値によってaを出力するかbを出力するかを決める論理ゲートです。
※これ以降は回路図を省略します。
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux.hdl
/**
* Multiplexor:
* out = a if sel == 0
* b otherwise
*/
CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
// Put your code here:
Nand(a=sel, b=sel, out=w1);
Nand(a=a, b=w1, out=w2);
Nand(a=sel, b=b, out=w3);
Nand(a=w2, b=w3, out=out);
}
デマルチプレクサ
デマルチプレクサはマルチプレクサの逆のことを行います。
入力されたinをselの値によって、aに出力するか、bに出力するかを選択します。
コードは以下の通りです。
// File name: projects/01/DMux.hdl
/**
* Demultiplexor:
* {a, b} = {in, 0} if sel == 0
* {0, in} if sel == 1
*/
CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
// Put your code here:
Nand(a=in, b=sel, out=w1);
Nand(a=in, b=w1, out=w2);
Nand(a=w2, b=w2, out=a);
Nand(a=w1, b=w1, out=b);
}
多ビットNot
Notゲートの入力を16ビットで行うものです。各ビットに対してNot演算を行います。
コードは以下の通りです。(全てNandで書くことはできますがコードを書くのがすごく面倒ですね...)
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Not16.hdl
/**
* 16-bit Not:
* for i=0..15: out[i] = not in[i]
*/
CHIP Not16 {
IN in[16];
OUT out[16];
PARTS:
// Put your code here:
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
説明は省略
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/And16.hdl
/**
* 16-bit bitwise And:
* for i = 0..15: out[i] = (a[i] and b[i])
*/
CHIP And16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put your code here:
Nand(a=a[0], b=b[0], out=w0);
Nand(a=w0, b=w0, out=out[0]);
Nand(a=a[1], b=b[1], out=w1);
Nand(a=w1, b=w1, out=out[1]);
Nand(a=a[2], b=b[2], out=w2);
Nand(a=w2, b=w2, out=out[2]);
Nand(a=a[3], b=b[3], out=w3);
Nand(a=w3, b=w3, out=out[3]);
Nand(a=a[4], b=b[4], out=w4);
Nand(a=w4, b=w4, out=out[4]);
Nand(a=a[5], b=b[5], out=w5);
Nand(a=w5, b=w5, out=out[5]);
Nand(a=a[6], b=b[6], out=w6);
Nand(a=w6, b=w6, out=out[6]);
Nand(a=a[7], b=b[7], out=w7);
Nand(a=w7, b=w7, out=out[7]);
Nand(a=a[8], b=b[8], out=w8);
Nand(a=w8, b=w8, out=out[8]);
Nand(a=a[9], b=b[9], out=w9);
Nand(a=w9, b=w9, out=out[9]);
Nand(a=a[10], b=b[10], out=w10);
Nand(a=w10, b=w10, out=out[10]);
Nand(a=a[11], b=b[11], out=w11);
Nand(a=w11, b=w11, out=out[11]);
Nand(a=a[12], b=b[12], out=w12);
Nand(a=w12, b=w12, out=out[12]);
Nand(a=a[13], b=b[13], out=w13);
Nand(a=w13, b=w13, out=out[13]);
Nand(a=a[14], b=b[14], out=w14);
Nand(a=w14, b=w14, out=out[14]);
Nand(a=a[15], b=b[15], out=w15);
Nand(a=w15, b=w15, out=out[15]);
}
多ビットOr
説明省略
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Or16.hdl
/**
* 16-bit bitwise Or:
* for i = 0..15 out[i] = (a[i] or b[i])
*/
CHIP Or16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put your code here:
Nand(a=a[0], b=a[0], out=wa0);
Nand(a=b[0], b=b[0], out=wb0);
Nand(a=wa0, b=wb0, out=out[0]);
Nand(a=a[1], b=a[1], out=wa1);
Nand(a=b[1], b=b[1], out=wb1);
Nand(a=wa1, b=wb1, out=out[1]);
Nand(a=a[2], b=a[2], out=wa2);
Nand(a=b[2], b=b[2], out=wb2);
Nand(a=wa2, b=wb2, out=out[2]);
Nand(a=a[3], b=a[3], out=wa3);
Nand(a=b[3], b=b[3], out=wb3);
Nand(a=wa3, b=wb3, out=out[3]);
Nand(a=a[4], b=a[4], out=wa4);
Nand(a=b[4], b=b[4], out=wb4);
Nand(a=wa4, b=wb4, out=out[4]);
Nand(a=a[5], b=a[5], out=wa5);
Nand(a=b[5], b=b[5], out=wb5);
Nand(a=wa5, b=wb5, out=out[5]);
Nand(a=a[6], b=a[6], out=wa6);
Nand(a=b[6], b=b[6], out=wb6);
Nand(a=wa6, b=wb6, out=out[6]);
Nand(a=a[7], b=a[7], out=wa7);
Nand(a=b[7], b=b[7], out=wb7);
Nand(a=wa7, b=wb7, out=out[7]);
Nand(a=a[8], b=a[8], out=wa8);
Nand(a=b[8], b=b[8], out=wb8);
Nand(a=wa8, b=wb8, out=out[8]);
Nand(a=a[9], b=a[9], out=wa9);
Nand(a=b[9], b=b[9], out=wb9);
Nand(a=wa9, b=wb9, out=out[9]);
Nand(a=a[10], b=a[10], out=wa10);
Nand(a=b[10], b=b[10], out=wb10);
Nand(a=wa10, b=wb10, out=out[10]);
Nand(a=a[11], b=a[11], out=wa11);
Nand(a=b[11], b=b[11], out=wb11);
Nand(a=wa11, b=wb11, out=out[11]);
Nand(a=a[12], b=a[12], out=wa12);
Nand(a=b[12], b=b[12], out=wb12);
Nand(a=wa12, b=wb12, out=out[12]);
Nand(a=a[13], b=a[13], out=wa13);
Nand(a=b[13], b=b[13], out=wb13);
Nand(a=wa13, b=wb13, out=out[13]);
Nand(a=a[14], b=a[14], out=wa14);
Nand(a=b[14], b=b[14], out=wb14);
Nand(a=wa14, b=wb14, out=out[14]);
Nand(a=a[15], b=a[15], out=wa15);
Nand(a=b[15], b=b[15], out=wb15);
Nand(a=wa15, b=wb15, out=out[15]);
}
多ビットマルチプレクサ
例題の場合、16ビット入力されるaとbに対してselの値に応じてaを出力するかbを出力するかを決めます。
入力値のみが変化していますね。
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux16.hdl
/**
* 16-bit multiplexor:
* for i = 0..15 out[i] = a[i] if sel == 0
* b[i] if sel == 1
*/
CHIP Mux16 {
IN a[16], b[16], sel;
OUT out[16];
PARTS:
// Put your code here:
Nand(a=sel, b=sel, out=wa0);
Nand(a=a[0], b=wa0, out=wb0);
Nand(a=sel, b=b[0], out=wc0);
Nand(a=wb0, b=wc0, out=out[0]);
Nand(a=sel, b=sel, out=wa1);
Nand(a=a[1], b=wa1, out=wb1);
Nand(a=sel, b=b[1], out=wc1);
Nand(a=wb1, b=wc1, out=out[1]);
Nand(a=sel, b=sel, out=wa2);
Nand(a=a[2], b=wa2, out=wb2);
Nand(a=sel, b=b[2], out=wc2);
Nand(a=wb2, b=wc2, out=out[2]);
Nand(a=sel, b=sel, out=wa3);
Nand(a=a[3], b=wa3, out=wb3);
Nand(a=sel, b=b[3], out=wc3);
Nand(a=wb3, b=wc3, out=out[3]);
Nand(a=sel, b=sel, out=wa4);
Nand(a=a[4], b=wa4, out=wb4);
Nand(a=sel, b=b[4], out=wc4);
Nand(a=wb4, b=wc4, out=out[4]);
Nand(a=sel, b=sel, out=wa5);
Nand(a=a[5], b=wa5, out=wb5);
Nand(a=sel, b=b[5], out=wc5);
Nand(a=wb5, b=wc5, out=out[5]);
Nand(a=sel, b=sel, out=wa6);
Nand(a=a[6], b=wa6, out=wb6);
Nand(a=sel, b=b[6], out=wc6);
Nand(a=wb6, b=wc6, out=out[6]);
Nand(a=sel, b=sel, out=wa7);
Nand(a=a[7], b=wa7, out=wb7);
Nand(a=sel, b=b[7], out=wc7);
Nand(a=wb7, b=wc7, out=out[7]);
Nand(a=sel, b=sel, out=wa8);
Nand(a=a[8], b=wa8, out=wb8);
Nand(a=sel, b=b[8], out=wc8);
Nand(a=wb8, b=wc8, out=out[8]);
Nand(a=sel, b=sel, out=wa9);
Nand(a=a[9], b=wa9, out=wb9);
Nand(a=sel, b=b[9], out=wc9);
Nand(a=wb9, b=wc9, out=out[9]);
Nand(a=sel, b=sel, out=wa10);
Nand(a=a[10], b=wa10, out=wb10);
Nand(a=sel, b=b[10], out=wc10);
Nand(a=wb10, b=wc10, out=out[10]);
Nand(a=sel, b=sel, out=wa11);
Nand(a=a[11], b=wa11, out=wb11);
Nand(a=sel, b=b[11], out=wc11);
Nand(a=wb11, b=wc11, out=out[11]);
Nand(a=sel, b=sel, out=wa12);
Nand(a=a[12], b=wa12, out=wb12);
Nand(a=sel, b=b[12], out=wc12);
Nand(a=wb12, b=wc12, out=out[12]);
Nand(a=sel, b=sel, out=wa13);
Nand(a=a[13], b=wa13, out=wb13);
Nand(a=sel, b=b[13], out=wc13);
Nand(a=wb13, b=wc13, out=out[13]);
Nand(a=sel, b=sel, out=wa14);
Nand(a=a[14], b=wa14, out=wb14);
Nand(a=sel, b=b[14], out=wc14);
Nand(a=wb14, b=wc14, out=out[14]);
Nand(a=sel, b=sel, out=wa15);
Nand(a=a[15], b=wa15, out=wb15);
Nand(a=sel, b=b[15], out=wc15);
Nand(a=wb15, b=wc15, out=out[15]);
}
多入力Or
この問題は全8ビットの入力のうち、1つでも1がある場合、1を出力します。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Or8Way.hdl
/**
* 8-way Or:
* out = (in[0] or in[1] or ... or in[7])
*/
CHIP Or8Way {
IN in[8];
OUT out;
PARTS:
// Put your code here:
Nand(a=in[0], b=in[0], out=wa1);
Nand(a=in[1], b=in[1], out=wb1);
Nand(a=wa1, b=wb1, out=wc1);
Nand(a=wc1, b=wc1, out=wa2);
Nand(a=in[2], b=in[2], out=wb2);
Nand(a=wa2, b=wb2, out=wc2);
Nand(a=wc2, b=wc2, out=wa3);
Nand(a=in[3], b=in[3], out=wb3);
Nand(a=wa3, b=wb3, out=wc3);
Nand(a=wc3, b=wc3, out=wa4);
Nand(a=in[4], b=in[4], out=wb4);
Nand(a=wa4, b=wb4, out=wc4);
Nand(a=wc4, b=wc4, out=wa5);
Nand(a=in[5], b=in[5], out=wb5);
Nand(a=wa5, b=wb5, out=wc5);
Nand(a=wc5, b=wc5, out=wa6);
Nand(a=in[6], b=in[6], out=wb6);
Nand(a=wa6, b=wb6, out=wc6);
Nand(a=wc6, b=wc6, out=wa7);
Nand(a=in[7], b=in[7], out=wb7);
Nand(a=wa7, b=wb7, out=out);
}
多入力/多ビットマルチプレクサ
4入力16ビットマルチプレクサの場合は4本の16ビット入力バス*1からひとつを選択し、1本の16ビット出力バスへ出力します。
コードは以下の通り※これ以降、Nandのみで書くとコードが難読化するので、Nandで作成済みの各ゲートを呼び出す形式で記述します。(つまり元をたどれば全てNandで記述されているということになります。)
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux4Way16.hdl
/**
* 4-way 16-bit multiplexor:
* out = a if sel == 00
* b if sel == 01
* c if sel == 10
* d if sel == 11
*/
CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];
PARTS:
// Put your code here:
Mux16(a=a, b=b, sel=sel[0], out=out1);
Mux16(a=c, b=d, sel=sel[0], out=out2);
Mux16(a=out1, b=out2, sel=sel[1], out=out);
}8入力16ビットマルチプレクサの場合は8本の16ビット入力バスからひとつを選択し、1本の16ビット出力バスへ出力します。
コードは以下の通り
// File name: projects/01/Mux8Way16.hdl
/**
* 8-way 16-bit multiplexor:
* out = a if sel == 000
* b if sel == 001
* etc.
* h if sel == 111
*/
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:
// Put your code here:
Mux16(a=a, b=b, sel=sel[0], out=ab);
Mux16(a=c, b=d, sel=sel[0], out=cd);
Mux16(a=e, b=f, sel=sel[0], out=ef);
Mux16(a=g, b=h, sel=sel[0], out=gh);
Mux16(a=ab, b=cd, sel=sel[1], out=abcd);
Mux16(a=ef, b=gh, sel=sel[1], out=efgh);
Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
}
多入力/多ビットデマルチプレクサ
4入力1ビットのデマルチプレクサはinの入力値を4本ある出力バスのいずれかに振り分けます
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/DMux4Way.hdl
/**
* 4-way demultiplexor:
* {a, b, c, d} = {in, 0, 0, 0} if sel == 00
* {0, in, 0, 0} if sel == 01
* {0, 0, in, 0} if sel == 10
* {0, 0, 0, in} if sel == 11
*/
CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
// 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);
}4入力1ビットのデマルチプレクサはinの入力値を4本ある出力バスのいずれかに振り分けます
コードは以下の通りです。
// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/DMux8Way.hdl
/**
* 8-way demultiplexor:
* {a, b, c, d, e, f, g, h} = {in, 0, 0, 0, 0, 0, 0, 0} if sel == 000
* {0, in, 0, 0, 0, 0, 0, 0} if sel == 001
* etc.
* {0, 0, 0, 0, 0, 0, 0, in} if sel == 111
*/
CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
// Put your code here:
DMux4Way (in=in, sel[0]=sel[1], sel[1]=sel[2], a=w1, b=w2, c=w3, d=w4);
DMux (in=w1, sel=sel[0], a=a, b=b);
DMux (in=w2, sel=sel[0], a=c, b=d);
DMux (in=w3, sel=sel[0], a=e, b=f);
DMux (in=w4, sel=sel[0], a=g, b=h);
}以上が第1章の実習になります。
次回は2章以降の内容について取り扱います。
※イメージ