nand2tetrisを実装する(1)第1章 ブール演算

卒業研究にコンピュータの理論と実装～モダンなコンピュータの作り方～ (通称:nand2tetris)を使って、コンピュータを作ることを決めたのでレポートとして経過をアップロードしていきます。

第1章 ブール論理

この章では、NotなどのゲートをNandだけでつくることができるのでそれをやってみようという章です。(結構パズルっぽい)
使用言語はハードウェア記述言語(HDL)です。

Not回路

回路図で表現すると、以下のようになります。
1つのNandだけでNotゲートが実装できるのがわかりますね

Nand回路でNot回路を作りました。 pic.twitter.com/MtII9xtc9u

— 玄界灘.io (@genkai_cs) 2018年9月10日

コードは以下の通りです。

// 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回路と同じ働き)ことで実装

And回路もできました
少し見づらいかも pic.twitter.com/EQf3cChOHW

— 玄界灘.io (@genkai_cs) 2018年9月10日

コードは以下の通りです。

// 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に通すと実装

これはOr回路です pic.twitter.com/ZdCxPHrcqD

— 玄界灘.io (@genkai_cs) 2018年9月10日

コードは以下の通りです。

// 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ゲート

このあたりから回路図が複雑になっていきます。

入力中を省略&図が雑ですがXor回路です。 pic.twitter.com/BIy3kt7eGf

— 玄界灘.io (@genkai_cs) 2018年9月10日

コードは以下の通りです

// 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章以降の内容について取り扱います。

*1:バスとは、複数のビットからなる配列のこと