nand2tetrisを実装する(4)第3章 順序回路-後編-

前回の続きです。メモリ以降について記述します。

背景

メモリ

第3章にしてメモリを実装していきます。

※イメージ図

レジスタでワードを表現できたので、任意の長さのワードを記憶する「メモリ」へ進みます。
レジスタをたくさん積み重ねることで、RAM(Random Access Memory)ユニットを構築することができます。ランダムアクセスメモリの名前の由来は、ランダムに選ばれたワードに対して、そのワードが位置する場所に制限を受けることなく、書き込み/読み込みができることからです。メモリ内のワードは物理的な場所に関係なく同じ場所で直接アスセスできなければなりません。
この要件を満たすために、RAMの各ワードに対して、重複しないユニークな番号をアドレスとして割り当てます。次に、jという数字に対してアドレスがj番目のレジスタを個別に選択できる論理ゲートを構築します。「アドレス」とは、物理的な位置を意味せず、論理的な意味でアドレスを実現します。
・RAMが受け取る3つの入力

• データ入力(in)

• ロードビット(load)

• アドレス入力(address)

アドレス入力によって、現時刻で、RAMのどのレジスタにアスセスするかを指定します。メモリ操作が読み込み(load=0)の場合、選択されたレジスタの値が出力され、書き込み(load=1)の場合、次のサイクルで、選択されたメモリのレジスタの値が送られます。
RAMを設計する場合、基本的なパラメータとして、幅とサイズを指定する必要があります。幅は各ワードの幅で、サイズはRAMに存在するワードの個数です。今回実装する幅は16ビット(のはず)ですが一般的なコンピュータでは、32もしくは64ビット幅のRAM を用います。サイズは100万を超えます。※今回実装するものは約16000(のはず)

レジスタを集合させたものがRAMとなり、このコンピュータの記憶装置となります。

カウンタ(プログラムカウンタ)

プログラムカウンタはレジスタの1種で、次に実行すべき命令を保持する機能を持っています。

カウンタは順序回路であり、タイムユニットが進むごとに、out(t) = out(t-1) + cとなるように、整数が加算されます。(cは通常１が用いられます。)デジタルアーキテクチャ(恐らくコンピュータアーキテクチャの意味)において、カウンタは重要な役割を持ちます。一般的にはCPUにはプログラムカウンタが含まれ、プログラムカウンタの出力は次に実行されるプログラム演算のアドレスとして解釈されます。
カウンタ回路はレジスタに定数を加算することで、実装できます。一般的なカウンタは、追加機能として、カウンタの値をゼロにする・新しいカウンタ値を読み込む・加算の代わりに減算を行うなどの機能を持ちます。

時間

要約していくのが難しかったため、説明が冗長となっています。

本章でこれまで取り上げた回路はすべて順序回路でした。順序回路とは、一つ以上のDFF回路が、直接または、間接的に組み込まれている回路です。また、順序回路の機能(状態を保つ or 状態を操作する)はDFF回路によってもたらされています。技術面の話では、順序回路内のフィードバックループによって先の機能はもたらされます。

一方、組み合わせ回路は、時間という概念はモデル化されていないため、フィードバックループを導入するには問題があります。なぜなら、出力は入力だけに依存しますが、もし入力がその回路自身に依存するとしたら、出力も出力自身に依存することになり、矛盾が生じるからです。対照的に、順序回路は出力を同じ回路の入力に送信することに対しては、問題は生じません。なぜなら、DFFは「時間遅延」という性質を内在するからです。DFFによってt-1の出力がその回路自身に影響をあたえるということです。この性質のおかげで、制御不能の「データレース」(組み合わせ回路でフィードバックループに伴う現象)と呼ばれる現象を防止できます。
組み合わせ回路は、入力値が変われば、その出力値は時間に関係なく変わります。対照的に、順序回路アーキテクチャ内にDFFが組み込まれると、出力値が変わるタイミングは、現在のクロック周期から次のクロック周期に移行した時点で、同じクロック周期では変化しません。

順序回路の出力が”離散化”される性質は、思わぬ結果・重要な結果をもたらします。それは、コンピュータアーキテクチャ全体を同期させることができるということです。例えば、ALUにx + yを計算するように指示したとします。ここで、ｘは近くにあるレジスタに格納された値で、yは遠くにあるレジスタに格納された値と仮定します。さまざまなブ地理的規約により、xとyの電気信号がALUまでに到達する時間は異なることになるでしょう。しかし、ALUは組み合わせ回路なので、時間という概念がありません。どのような信号であれ、その入力に入ってきたとしたら、即座にその加算が求められます。そのため、ALUの出力が正しい「x + y」の値に落ち着くには、わずかな時間が必要です。その時間に達するまでALUは”ゴミ”を出力していることになります。
この問題を解決するには、ALUの出力は順序回路を常に通過させることです。これにより、この問題を考える必要は全くありません。作り手がやるべきことは、クロックを作成するときに、クロック周期の間隔を適切に決めるだけです。(アーキテクチャ内で最も距離が遠い回路間を移動するのに必要な時間を調べ、それより少し長い時間を間隔とすることです。)このようにすれば、順序回路が状態を更新するまでにはALUから受け取る値は常に正しいことが保証されます。これにより、それぞれ独立したハードウェアのコンポーネントを、調整が図られたシステムとして同期させることができます。
※これについては5章で詳しく見ていくことにします。

仕様と実装

メモリ

この章では、メモリ幅は16ビットで固定し、サイズの異なるメモリをいくつか組み立てます。

RAM8

この後のRAMを設計するのに、基本となるRAMです。
実装

// 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/03/a/RAM8.hdl

/**
 * Memory of 8 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

	// どのレジスタにアクセスするかをアドレス(address)で選択し、
	// そのレジスタに読み込むか、書き込むかを「読み込みビット」(load)
	// の値に応じて選択し、書き込みの場合はinの値(word)を次のサイクルで
	// そのレジスタに値を入力し、読み込みはoutによって出力される。
    PARTS:
    // Put your code here:
    DMux8Way(in=load,sel=address, a=a,b=b,c=c,d=d,e=e,f=f,g=g,h=h);
    Register(in=in,load=a, out=r1);
    Register(in=in,load=b, out=r2);
    Register(in=in,load=c, out=r3);
    Register(in=in,load=d, out=r4);
    Register(in=in,load=e, out=r5);
    Register(in=in,load=f, out=r6);
    Register(in=in,load=g, out=r7);
    Register(in=in,load=h, out=r8);
    Mux8Way16(a=r1,b=r2,c=r3,d=r4,e=r5,f=r6,g=r7,h=r8, sel=address, out=out);
}

RAM64

RAM8を応用して作ります。
実装

// 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/03/a/RAM64.hdl

/**
 * Memory of 64 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM64 {
    IN in[16], load, address[6];
    OUT out[16];
	
	// addressの4～６ビット目でどのRAM8を操作するのかを決める。
    PARTS:
    // Put your code here:
    DMux8Way(in=load,sel=address[3..5], a=a,b=b,c=c,d=d,e=e,f=f,g=g,h=h);
    // addressの1～3ビット目で各RAM8内のどのRegisterを操作するのかを扱う。
    RAM8(in=in,load=a,address=address[0..2], out=r1);
    RAM8(in=in,load=b,address=address[0..2], out=r2);
    RAM8(in=in,load=c,address=address[0..2], out=r3);
    RAM8(in=in,load=d,address=address[0..2], out=r4);
    RAM8(in=in,load=e,address=address[0..2], out=r5);
    RAM8(in=in,load=f,address=address[0..2], out=r6);
    RAM8(in=in,load=g,address=address[0..2], out=r7);
    RAM8(in=in,load=h,address=address[0..2], out=r8);
    Mux8Way16(a=r1,b=r2,c=r3,d=r4,e=r5,f=r6,g=r7,h=r8, sel=address[3..5], out=out);
}

RAM512以降は、RAM64と記述が酷似しているので、コードを省略します。尚、RAM16KだけはRAM4Kとサイズが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/03/a/PC.hdl

/**
 * A 16-bit counter with load and reset control bits.
 * if      (reset[t] == 1) out[t+1] = 0
 * else if (load[t] == 1)  out[t+1] = in[t]
 * else if (inc[t] == 1)   out[t+1] = out[t] + 1  (integer addition)
 * else                    out[t+1] = out[t]
 */

CHIP PC {
    IN in[16],load,inc,reset;
    OUT out[16];

    PARTS:
    // Put your code here:
    Inc16(in=fb, out=w1);	// アドレスの値を加算
    Mux16(a=fb,b=w1,sel=inc, out=w2);	// inc == 1 ならば加算したアドレスを出力
    Mux16(a=w2,b=in,sel=load, out=w3);	// load == 1 ならばinの値を出力
    Mux16(a=w3,b=false,sel=reset, out=w4);	// reset == 1 ならば記憶しているアドレスをリセット
    Register(in=w4,load=true, out=out,out=fb);	// アドレスを出力し、fbにアドレスを記録
    
}

以上で第4章後編のレポートを終わります。
次回は第4章 機械語　恐らくアセンブリに関した内容となります。

nand2tetrisを実装する(3)第3章 順序回路-前編-

記事が長くなると判断し、本記事では第3章のレジスタの部分を前編として書いていきます。メモリ以降の部分は後編をお待ちください。

第3章 順序回路

本章はフリップフロップ回路(実装済み)と既存の回路を使い、いわゆる記憶素子を実装していきます。

背景

記憶するという行為は時間に依存→「前に記憶したものを今思い返す」という行為が記憶
情報を記憶するための回路を構築するには、時間経過を表す方法を考案しなければなりません。

クロック

コンピュータでは継続的に変化する信号をマスタクロックが送信することで時間の経過を表現します。
ハードウェアでの実装はオシレーター(発振回路)に基づくのが一般的です。オシレーターは0/1などのふたつのフェーズを絶え間なく行き来します。0の始まりから0の終わりまでを周期と呼ぶ。この1周期を単位時間としてモデル化されます。
ハードウェアの回路網を使って、信号はプラットフォームの隅から隅まで、すべての順序回路に送られます。

ハードウェアに関しては専門外なのですが、本書の解説はとてもわかりやすいので理解しました。

フリップフロップ

応用情報技術者試験を受験した方や回路図に慣れ親しんでいる方であれば下図のような回路図は見たことがあるでしょう。
このフリップフロップについての詳細です。

フリップフロップ回路はコンピュータの中で基本となる回路です。フリップフロップ回路はいくつか種類がありますが、本書ではD型フリップフロップと呼ばれるタイプを用います。
D型フリップフロップ(DFF):インターフェースは1ビットのデータ入力(クロック入力？)と1ビットのデータ出力。クロック入力はマスタクロックから信号が絶えず送られます。データ入力とクロック入力が合わさることで、本回路は「時間に基づく振る舞い」が可能になります。時間に基づく振る舞いの式は、out(t)=in(t-1) inとoutはゲートの入出力値を、tは現在のタイムユニットを表します。つまり、本回路はひとつ前のタイムユニットの入力値を出力しているだけです。
コンピュータで状態を保つために用いられる装置(レジスタ、RAMなど)はこの基本となる振る舞いによって形成されます。

この回路自体は1つ前の状態を出力するだけで、後述の装置を実装していくうえで必要な回路となるということだと判断しました。

レジスタ

レジスタとは、データを格納・呼び出しする記憶装置です。out(t)=out(t-1)(ひとつ前のタイムユニットの出力値を出力する？)を実現します。
DFFは前述のout(t)=in(t-1)を実現します。
そのため、DFFの出力を入力に送信すればうまくいくのでは？←これではうまくいきません。なぜなら、新しいデータの値をこの回路(レジスタ)に読み込む方法が明らかでないからです。どのタイミングでinからのデータを読み込み、どのタイミングでoutからデータを読み込むのかをDFFに指示する方法が存在しないからです。回路設計において、一般的には、ひとつのソースだけから入力データが送られるようにする必要があります。
以上から、入力の曖昧さを回避するにはマルチプレクサを導入するのが自然です。さらに、マルチプレクサへの「選択ビット」はレジスタ回路への「読み込みビット」の役割も狙えます。レジスタに新しい値を保持させたい場合、その値を入力inに入れて、「読み込みビット」のloadに1を設定すればいいです。内部の値をレジスタに保持させたい場合、loadの値を0にすればよいです。
任意の幅のレジスタを実装する場合は、1ビットレジスタを必要な数だけそろえて、それらを配列上に並べて構築できます。多ビットレジスタは幅をパラメータとして考えなければなりません。(値の候補としては16，32，64など)多ビットのレジスタの持つ値は一般的にワードと呼ばれます。

レジスタの実装時には、マルチプレクサを使うことで、新しい値を保持するか、内部の値を保持するかを選択できることで、正しい実装ができる。
また、レジスタを複数並べることで、多ビットレジスタができるということです。

仕様と実装

レジスタ

ビット(2値素子)

背景の説明と設計通り、マルチプレクサを使うことで実装できます。
実装

// 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/03/a/Bit.hdl

/**
 * 1-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 *                 else out does not change (out[t+1] = out[t])
 */

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    // Put your code here:
    
    // if(load==0)ならば読み込み
    // if(load==1)ならば書き込み
    Mux(a=fo,b=in,sel=load, out=w1);
    DFF(in=w1, out=out,out=fo);
    
}

レジスタ(16ビット)

こちらも背景の説明と同様に、Bit回路を並べていくことで完成します。
実装

// 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/03/a/Register.hdl

/**
 * 16-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 * else out does not change
 */

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    // Put your code here:
    Bit(in=in[0],load=load, out=out[0]);
    Bit(in=in[1],load=load, out=out[1]);
    Bit(in=in[2],load=load, out=out[2]);
    Bit(in=in[3],load=load, out=out[3]);
    Bit(in=in[4],load=load, out=out[4]);
    Bit(in=in[5],load=load, out=out[5]);
    Bit(in=in[6],load=load, out=out[6]);
    Bit(in=in[7],load=load, out=out[7]);
    Bit(in=in[8],load=load, out=out[8]);
    Bit(in=in[9],load=load, out=out[9]);
    Bit(in=in[10],load=load, out=out[10]);
    Bit(in=in[11],load=load, out=out[11]);
    Bit(in=in[12],load=load, out=out[12]);
    Bit(in=in[13],load=load, out=out[13]);
    Bit(in=in[14],load=load, out=out[14]);
    Bit(in=in[15],load=load, out=out[15]);
    
}

以上で第3章前編のレポートを終わります。
次回は第3章 後編、メモリ以降の内容です。

nand2tetrisを実装する(2)第2章 ブール算術

第2章 ブール算術

本章の目的は後述の回路を全章で作った回路を元に実装することです。

背景

2進数

ここからは一部本文を抜粋・要約したものをまとめます。

2進数とは2を底とする。ある2進数の値が10011とすると、10進数の値で表現すると19となる。
例えば、Excelで「1」「9」と入力してEnterキーを入力するとレジスタのどこかに2進数の10011が格納される。
もしコンピュータが32ビットのマシンであればレジスタに格納されるビットの配列は00000000000000000000000000010011になる。

基本ですね。

2進数加算

2進数の足し算は与えられたふたつの数を右から左へ各桁で足し合わせればよい。最初に1番右の桁(最下位ビット)の和を計算する。
続いて先ほどの計算結果のキャリービット(桁上がりビット)と次の桁の和を足し合わせる。この手続きを最上位ビットに到達するまで続ける。
もし最後の桁の和でキャリービットの和が1であれば、「オーバーフロー」であることを報告する。

2進数の足し算の仕方についての解説。ｵｰﾊﾞｰﾌﾛｰﾖｸﾅｲ
加算器の実装には各桁の計算の和とキャリービットを実装する必要があるということですね。

符号付き2進数

n桁の2進数は2ⁿ通りの異なるビット配列を生成できる。2進コードで符号付き数字を表現するためには、2ⁿ通りの領域を均等に分ける。
一方は正の数、もう一方は負の数を表現するために用いる。今ほとんどすべてのコンピュータで用いられる方式は、2の補数である。
nビット2進数での2の補数の性質

• 2ⁿ個の符号付き数を表し、最大値と最小値はそれぞれ2ⁿ⁻¹－1,ー2ⁿ⁻¹になる。

• 正の数の最上位ビットは0である

• 負の数の最上位ビットは1である

• xというコードからーxを得るには、最下位ビットから桁を繰り上げて見ていき、１が出現するビットに遭遇したら、その1の場所より上位のビットを全て反転させることで実現。より簡単な実装方法はxのすべてのビットを反転させ、その結果に1を足すことで実装できる。

2の補数に関する解説です。最後の引用のxからーxを得る方法の前者に関しては、本書で始めて見ました。

2の補数を用いることで、単純なビット単位の加算が行えるハードウェアがあれば、特別なハードウェアを用いることなく正と負のどちらの加算も行える。
引き算は足し算として扱うことができる。

2の補数の利点ですね。

ここまでの理論考察から、ひとつの理論にたどり着く。それはひとつの回路(ALU:算術論理演算器)に初歩的な算術演算と論理演算のすべてをまとめることができる。(かもしれない)ということである。

1章で作ったAndの論理演算や本章で作る加算器をまとめればひとつの回路にまとめられるんじゃね？ということ(らしい)です。

仕様と実装

加算器(Adder)

半加算器

2進数の加算を行うときの初めはふたつのビットに対して、その和を求めることです。本書では最下位ビットの和はsum、キャリービットの和はcarryと定義されています。
実装

// 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/02/HalfAdder.hdl

/**
 * Computes the sum of two bits.
 */

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
    // Put you code here:
    Xor(a=a,b=b, out=sum);
    And(a=a,b=b, out=carry);
}

全加算器

全加算器は前の桁からのキャリービットを含めた３つのビットの和を計算します。
半加算器と同様に出力は和の最下位ビットとキャリービットの2本です。
実装

// 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/02/FullAdder.hdl

/**
 * Computes the sum of three bits.
 */

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
    // Put you code here:
    HalfAdder(a=a,b=b, sum=s1,carry=c1);
    HalfAdder(a=c,b=s1, sum=sum,carry=c2);
    Or(a=c1,b=c2, out=carry);
}

加算器

メモリやレジスタなどの回路では、整数を表すためにnビットの配列を用います。nの値はコンピュータのプラットフォームによって異なり、16,32,64などの数字が用いられます。
多ビットの加算を行う加算器は「多ビット加算器」または「加算器」と呼ばれます。本書では16ビットの加算器を実装します。
ちなみに、実装部分のCarry16のオーバーフローについては無視しても良いようです。
実装

// 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/02/Adder16.hdl

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
   // Put you code here:
   HalfAdder(a=a[0] ,b=b[0], sum=out[0],carry=c1);
   FullAdder(a=a[1] ,b=b[1], c=c1,  sum=out[1], carry=c2);
   FullAdder(a=a[2] ,b=b[2], c=c2,  sum=out[2], carry=c3);
   FullAdder(a=a[3] ,b=b[3], c=c3,  sum=out[3], carry=c4);
   FullAdder(a=a[4] ,b=b[4], c=c4,  sum=out[4], carry=c5);
   FullAdder(a=a[5] ,b=b[5], c=c5,  sum=out[5], carry=c6);
   FullAdder(a=a[6] ,b=b[6], c=c6,  sum=out[6], carry=c7);
   FullAdder(a=a[7] ,b=b[7], c=c7,  sum=out[7], carry=c8);
   FullAdder(a=a[8] ,b=b[8], c=c8,  sum=out[8], carry=c9);
   FullAdder(a=a[9] ,b=b[9], c=c9,  sum=out[9], carry=c10);
   FullAdder(a=a[10],b=b[10],c=c10, sum=out[10],carry=c11);
   FullAdder(a=a[11],b=b[11],c=c11, sum=out[11],carry=c12);
   FullAdder(a=a[12],b=b[12],c=c12, sum=out[12],carry=c13);
   FullAdder(a=a[13],b=b[13],c=c13, sum=out[13],carry=c14);
   FullAdder(a=a[14],b=b[14],c=c14, sum=out[14],carry=c15);
   FullAdder(a=a[15],b=b[15],c=c15, sum=out[15],carry=c16);
}

インクリメンタ

与えられた数字に1を加算することができる回路。そのような実装があると便利(らしい)です。
実装としては配列b[16]のb[0]にtrue←つまり１を入れ、それ以降のfalse←つまり0を入れることで実装します。
実装

// 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/02/Inc16.hdl

/**
 * 16-bit incrementer:
 * out = in + 1 (arithmetic addition)
 */

CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
   // Put you code here:
   Add16(a=in,b[0]=true,b[1..15]=false, out=out);
}

ALU

本章のメインの加算器回路です。これまで作った回路は一般的なもので、どのコンピュータでも使われています。しかし、ALUはHackと呼ばれる特定のコンピュータプラットフォームだけで使われる専用の回路です。
このALUはこれから先、コンピュータの中心的な役割を担う回路となるそうです。ALUのアーキテクチャは最小限の内部パーツで構成されているものの、多くの機能を持ちます。
ALUには16の関数があります。ALUに対してどの関数を実行させるかを指定するには、制御ビットと呼ばれる6ビットの入力ビットを用います。

と、いうものの実装の使用を見たときにこれまでとのギャップに驚きました。
その画像がこちら。

...うーん多い
しかし、前述の仕様をヒントにすると制御ビットに応じて、処理をさせる
つまり、マルチプレクサが活躍します！！！
細かい説明については、ソースのコメント部分を参照してください。
実装

// 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/02/ALU.hdl

/**
 * The ALU (Arithmetic Logic Unit).
 * Computes one of the following functions:
 * x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
 * x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs, 
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * In addition, the ALU computes two 1-bit outputs:
 * if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
 * if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
 */

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

CHIP ALU {
    IN  
        x[16], y[16],  // 16-bit inputs        
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
   // Put you code here:
   Mux16(a=x,b=false,sel=zx, out=w1); // zxが1のとき出力されるのはbが選択されるが、bは常にfalseなので、xを全て0にする。
   Mux16(a=y,b=false,sel=zy, out=w2); // 同上。
   
   // nx及びnyの値に応じてビットを反転する処理
   Not16(in=w1,out=nw1);
   Mux16(a=w1,b=nw1,sel=nx, out=w3); // nxが1のとき出力されるのは反転したnw1になる。
   Not16(in=w2,out=nw2);
   Mux16(a=w2,b=nw2,sel=ny, out=w4); // 同上
   
   // fが1のときに加算、0のときにAnd演算
   And16(a=w3,b=w4, out=xandy); // And演算
   Add16(a=w3,b=w4, out=addxy); // 加算
   Mux16(a=xandy,b=addxy, sel=f, out=w5); // fの値に応じて加算かAnd演算を行う。
   
   // noの値に応じて出力ビットを反転するかを決定する処理
   Not16(in=w5, out=notw5);
   Mux16(a=w5,b=notw5, sel=no, out=out,out[0..7]=out0to7,out[8..15]=out8to15,out[15]=ng); // この後、8入力Orゲートに入れる処理を行うため、1ビット目から8ビット目と9ビット目から16ビット目に分割する。また、out[15]は符号ビットなので、このビットが1ならば負数→ out < 0でtrueになる動作が実装
   
   // 出力値が0かのチェック
   Or8Way(in=out0to7, out=or0to7);
   Or8Way(in=out8to15, out=or8to15);
   Or (a=or0to7,b=or8to15,out=or0to15);
   Not(in=or0to15,out=zr); //出力値の全てのビットが0であれば、zr=1となる。
}

以上で第2章のレポートを終わります。
次回は第3章 順序回路です。

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:バスとは、複数のビットからなる配列のこと

去年作った製作物を公開する[勉強会カレンダー]

去年の「システム構築」という科目の授業中に製作した「勉強会カレンダー」というシステムを今更ながら公開します。

ダウンロード

以下のURL(Googleドライブ)から2つのファイルをダウンロードしてください。
benkyokaisystem2017 - Google ドライブ

きっかけ

そもそものきっかけとして、勉強会に月１～２回のペースで行っていた私が困ってたこととして

• 公開されるセッションの資料(パワーポイントなど)の管理が大変だった
• 1度の勉強会で複数のソフトウェアを使うことがある(パケット基礎の講座であれば、WiresharkとBurp suiteを使うなど)
• たくさんの人と交流する

ということがあり、これらをまとめるのがすごく大変だったという背景がありました。

それを解決するために、この科目ではこれらをまとめるシステムを作ることを決めました。

開発環境

• 開発言語:C#
• データベース:Access
• エディタ:VisualStudio

プログラムの機能

• メイン画面のUIをカレンダー形式にしました(あくまで勉強会用のため、祝日の表示は不要と判断)
• カレンダーに書き込むような感覚で勉強会を追加し、閲覧することができるようにする
• 勉強会情報/参加者情報の表示･検索･更新･削除

使い方

適当なファイルを作り、その中に、benkyokaisystem2017.exeとInterop.ADOX.dllを保存します。
exeファイルを実行すると、1度目は下記のようなメッセージが表示され、同じディレクトリにAccessのDBファイルが作られます。

もう1度exeファイルを実行すると下記のようなメイン画面が表示されます。
勉強会を新しく追加したい場合は、青く囲んだ部分のような日付の下のテキストボックスをダブルクリックすることで、編集画面が表示されます。

勉強会追加画面に登録する情報として、

• 勉強会名(必須項目)
• 主催者(必須項目)
• ジャンル
• 開催地
• URL
• 発表資料
• 使用プログラム等
• メモ

を用意しています。

勉強会の情報を登録して、追加ボタンを押すと、データが登録され、カレンダー内に勉強会名が表示されるようになります。また、既に勉強会が登録されている日付のテキストボックスをダブルクリックすると勉強会の情報を表示し、更新・削除もすることができます。また、主催者を表示すると、主催者についての情報を表示することができます。

参加者の情報を登録する場合は、参加者追加ボタンをクリックします。
参加者追加画面に登録する情報として、

• 参加者名(必須項目)
• 所属(必須項目)
• メール
• 会った勉強会(必須)
• Twitter
• Facebook

参加者情報を登録すると、参加者一覧及び名前検索で検索したデータのセルをダブルクリックすることで勉強会の情報を表示し、更新・削除もすることができます。また、会った勉強会をクリックすると、その勉強会の詳細情報を表示することができます。

名前検索ボタンは勉強会と参加者の検索両方に対応しています。

感想及びまとめ

感想

• カレンダーをC#で自作するのは結構難しかったです。
• テーブルのリレーションを下記のようにすることで、システム中のSQL文が複雑になりました。また、この実装をすることで、勉強会に対応する主催者を削除してしまうと、その勉強会情報を閲覧しようとするとエラーが発生することが判明しました。

• 作れば作るほど予定より多く機能を付けることになりました。(例:勉強会の主催者をダブルクリックすると、主催者の情報を表示する)
• デザイン面の工夫が出来ていなかった。
• デバッグに力を入れた※テーブルのエラーは発表中に発見したものだったので反省点
• もっと機能を拡張したい

今後の改善点

• ASP.NETで開発しWebアプリケーション化
• AccessDBは現実的な実装でないため、DBをSQLiteなどにする。
• 開催地の情報をgoogleマップから受け取り、表示する。
• URLなどリンクできるものはリンクを設定する仕様にする。
• 今回作った際の不具合を修正する。

また今後、需要があれば一般公開するサービスとして開発したいと思っています。(Googleカレンダーではできないような独自性を持たせないといけない点が大きな壁となると思います。)

CODE BLUE2018の学生スタッフになった話[参加レポート]

私はCODE BLUE2018の学生スタッフに参加しました。その中で何をやったかについて紹介します。

CODE BLUE自体の概要の説明はここでは割愛し、「学生スタッフ」としてどんなことを担当したのかなどについて本レポートは紹介します。

来年以降、学生スタッフに参加する予定が少しでもある方の参考になれば幸いです。

お金のはなし

今回、CODE BLUEに参加した時に使用したお金のお話をします。福岡からの参加なので交通手段は飛行機です。

• 交通費(飛行機)37,000円
• 交通費(電車、タクシー)4,0000円
• 食費(2次会などを含む)8,000円
• AVTOKYO参加費(CODE BLUEと無関係だけど一応含む)7,000円

合計：約56,000円

宿泊先は運営から出してもらってるので宿泊費無料とはいえこれだけの費用がかかりました。飛行機に関しては夜行バスの利用やもっと早くからチケットを予約することで何とかはなりますがそれでも40,000円はかかるでしょう。※福岡からの場合

学生スタッフとしての目的・業務内容

CODE BLUE学生スタッフにはおよそ２つの大義があります。それは

• 導通レシーバ(1台数万円の翻訳機)の紛失をゼロにする
• 参加者に楽しさが伝播するように楽しんで仕事をする

この2つです。我々学生スタッフ60名はこの大義の下にスタッフとしての仕事を全うしました。

スタッフの業務内容

学生スタッフの仕事自体にITの技術的な知識は必要ありません。必要なのは自発的に仕事ができることと元気に仕事ができることです。

業務内容は

• 誘導(会場前で会場への誘導をする。)
• 受付(受付自体はボランティアが担当し、参加証の手渡しを担当)
• スピーカーアテンド(英語力重要)
• スライド送り等発表のサポート(英語力)
• ドアキーパー(導通レシーバーを管理する上でかなり重要な役割)
• カメラ担当(いろんな人に話しかけてもらえるメリットあり)
• コアスタッフの個人付き

これらの仕事が割り振られます。

また、会場が1階と5階の2か所なので分担して作業をします。

お詫び

私は1つだけミスをしました。スタッフに支給されたTシャツをサイズを間違えて取ってしまい、コアスタッフの方に迷惑をかけてしまったのです。この件につきまして、この場を借りてお詫び申し上げます。

ここから先は、実際の活動レポートとなります

10月31日(開催前日)

はじめに、CODEBLUEの同会場にて他学生スタッフとの交流会が執り行われました。

その後、各持ち場についての概要の説明を行い、解散となりました。

解散後は0次会が執り行われましたが、私は前日に某チームの某シリーズの試合を観戦した影響での前日の寝不足と、翌日の集合時間の07:00に間に合うように05:30起きをしなければいけないという理由で参加しませんでした。

本日の夕食です pic.twitter.com/Uk5OZYxIo0

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

夕食も質素に済ませる...

ちなみに今回のホテルの情報

THE KNOT TOKYO Shinjuku | 旅するホテル

デラックストリプルという相部屋の宿泊でした。

11月1日(CODE BLUE Day1スタッフ担当日)

朝5時30分に起き、ホテルのルームメイト他2人はDay2の担当日だったので起こさないように静かに朝の支度をしました。

部屋の電気を点けることもできず、部屋でつける用のメガネを忘れていたのでほぼ何も見えない中で朝食を取り、唯一電気を点けても迷惑にならないバスルームで朝の支度をし、会場へ向かいました。

朝7時に集合し、各持ち場ごとに打ち合わせをします。

私の担当は当日券の受付と「5F遊撃隊」という5階の会場内でコアスタッフから指示があれば動き、指示がないときは何かできることがないか仕事を探す業務でした。

午前中

当日券受付を担当し、チケットアプリのPeatixの方とボランティアの方とで共同で作業しました。

基本的には事前購入した方が多かったため、約25名に受付をしました。チケットは通常13万2000円と大変高価なので会社等から無料の招待コードを持っての参加が主でした。

ただ、唯一現金でチケットを購入した韓国からの4人組が53万円をポンと出したときは精算にかなり気を付けました。

大変だったのは、受付ブースが立ちっぱなしだったので、足の疲れがあったことです。

午後以降

5階の遊撃隊担当は基本的に1時間に1度呼ばれる程度でした。

そのため、5階受付担当に合流し、受付と参加者の方の案内をしました。

特に、1階のセッション終了前後や5階のサイバー犯罪トラックのセッションの合間には参加者の移動が多くなるので、サイバー犯罪トラックのドア前の様子見をその時には行いました。

時間が経つにつれ、遊撃隊の仕事の割り振りが比較的少なくなったので、サイバー犯罪トラックのドアキーパーの手伝いを2人だけで行うのは大変だと判断し、午後の後半からは担当しました。内容は、導通レシーバの持ち出しがないように案内したり、混雑時の誘導を行いました。

ただ、5階のサイバー犯罪トラックで起こった問題ですが、セッション終了時の入場者の人数が退場者の人数よりも多く、どんどん講義室に人が増えていくという現象が発生しました。会場も1階の2つのホールと比べると狭いので人数に限りがあるため、参加者が離席しにくかったことで、ホール内の聴講者が次第に増えていったと考えられます。

Day1のすべてのセッションが終了すると、撤収作業が始まり、5階のサイバー犯罪トラックの導通レシーバを消毒し、紛失がないか個数の集計を行いました。

その結果、紛失したレシーバの数はなんと....０でした！！！

見事仕事を全うしたDay1組は満足して解散しました。

その後、2次会に参加して、アヒージョやバスタなどをワインと共に嗜みつつ会話を楽しみました。（撮影しておけばよかったと後悔...）

11月2日(CODE BLUE Day2聴講日)

 聴講日ということで、講義を聴いたり、CTFなどの競技が行われているブースの見学をしたり、各ブースで話を聞いたりするなどをしました。

ブースでは、ブロックチェーン(物理)やTシャツ・バイナリかるた・OWASPのイカすステッカーなどを貰いました。

また、ブースの方との話も楽しかったです。ディープウェブ/ダークウェブでのやり取りについてどう調査するのかの仕組みやOSSの脆弱性で危険なのは家電だということなど興味深い話をたくさん聞きました。(少しだけ採用についての話も聞けました)

※イメージ

講義は、海外からのスピーカーも多数参加していますが、日本人スピーカーも参加しています。また、前述の導通レシーバを借りることで、スピーカーの講義の同時通訳を聴くことができます。

講義終了後

全ての講義が終わると、撤収作業が始まります。撤収作業は椅子の片づけやブース用のテーブルクロスの回収など、設営の業者様が担当しない部分を学生スタッフで担当しました。

また、導通レシーバの回収作業を2日目も学生スタッフで担当して行い、集計したところ、

2日目の導通レシーバの紛失数も......０で終了！！！

というわけで、学生スタッフの目標の1つの導通レシーバ紛失0を達成した我々は、円満に解散し、ネットワーキングパーティ(懇親会)に合流しました。私は、今度参加するHardening II SecurEachの同じ参加者のN氏や今年のキャンプの同期と談話をするなどしました。また、「サイバー防御に活用できるOSINTの手法と実践」という講演をした石井 中さんの話を聞くこともできました。

ネットワーキングパーティが終わり、学生スタッフで2次会を行いました。2次会ではDay0で話ができなかった方と話したり、某まっちゃさんと話したり、LTで自分の所属する九州学生エンジニア連合についての紹介をしました。(正直めっちゃ楽しかったです)

さらに、ネットワーキングパーティと2次会であまりご飯を食べていなかったので、3次会にラーメンを食べに行きました。場所は新宿ゴールデン街にある「凪」というラーメン店です。

三次会情報のシェアでーす＾＾ pic.twitter.com/K0wIxQfYn5

— 玄界灘.io (@genkai_cs) 2018年11月2日

 (夜のゴールデン街は怖かった…) 

11月3日(AfterDay AVTOKYO)

こちらについては日記色が強くなるので、後日別の記事をアップします。

まとめ（Q＆A）

Q.CODE BLUEって何ですか？

A.

CODE BLUEとは、世界トップクラスの情報セキュリティ専門家による最先端の講演と、国や言語の垣根を越えた情報交換・交流の機会を提供する国際会議です。

 Q.学生スタッフって何をするの？

A.業者様がやらないドアマンやスピーカーアテンド、受付の手伝いなどをします。前述の2つの大義を大事にして仕事を全うしましょう！

 Q.学生スタッフって技術力がないと辛いの？

A.学生スタッフとしての作業自体は、情報セキュリティについての技術力や知識は一切不要です。(あれば他の学生スタッフと話をするときに知見を共有できる)

Q.英語が出来ないと参加しても意味ないんじゃないの？

 A.私は英語の会話が困難なレベルで参加しましたが、問題ありませんでした。基本的に同じ持ち場に英語のできる人を1人は配置するようにしているので、わからなければその人に代わりに聞いてもらうなどをすればいいです。また、講義に関しても導通レシーバーがあるので、海外のスピーカーの講義を同時通訳で聴くことできます。

Q.でもお高いんでしょう？

A.地方からの参加者には宿泊先が無料で提供されます。前述の通り、福岡から参加した私は56,000円かかりました。しかし、2日の講義全てを聴講することができるチケットは本来132,000円なので、十分安いです！

Q.学生スタッフとして参加する強みって何？

A.他の学生スタッフとの友好関係を築くことができる点。CODE BLUEの講義を無料で聴講できる点。ネットワーキングパーティでスピーカーや著名な参加者との会うことができる点。モチベーションの高い人が集まる環境で圧倒的成長ができる点。などがあります。

Q.学生スタッフはいつ応募開始するの？

A.CODE BLUEのTwitter公式アカウントから募集が開始します。今年は8月21日に募集のツイートがされました。公式アカウントをフォローして、来年応募できるようにしましょう！https://twitter.com/codeblue_jp/status/1031757059782373376

現在(2018/11/09)までの取得資格情報

資格

平成28年 10月 経済産業省基本情報技術者試験 合格

平成28年 12月 文部科学省後援ビジネス能力検定ジョブパス 3級合格

平成29年   1月 サーティファイ主催C言語プログラミング能力認定試験 1級合格

平成29年   2月 マイクロソフトオフィススペシャリストExcel2013 合格

平成29年   6月 文部科学省後援情報検定 情報活用検定 1級合格

平成29年   7月 サーティファイ主催Java言語プログラミング能力認定試験 1級合格

平成29年 10月 経済産業省応用情報技術者試験 合格

平成30年   2月 実用数学技能検定(2次:数理技能検定) 準2級合格

免許

平成29年   4月 普通自動車第一種免許 取得

備考

サーティファイ主催C言語プログラミング能力認定試験については3級も合格

サーティファイ主催Java言語プログラミング能力認定試験については3級も合格

文部科学省後援情報検定 情報活用検定については2級も合格