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章 順序回路です。