Nand2tetris project 2 ALU

HalfAdder

半加法器，兩個bit相加，輸出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:
    //// Replace this comment with your code.
    
    Xor(a = a , b = b  , out = sum) ; 

    And(a=a , b= b , out = carry) ; 

}

FullAdder

全加法器
三個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/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:
    //// Replace this comment with your code.

    HalfAdder(a=b , b=c , carry =carry1 , sum =sum1 ) ; 

    HalfAdder(a=a , b=sum1 , carry =carry2 , sum =sum) ; 

    Or(a = carry1 , b= carry2 , out = carry) ;   

}

Adder16

16位元加法，考慮進位

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/Add16.hdl
/**
 * 16-bit adder: Adds two 16-bit two's complement values.
 * The most significant carry bit is ignored.
 */
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    //// Replace this comment with your code.

    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 = false ); 




}

Inc16

進位器，輸出就是in + 1 ， 可以將 1的補數 化為2的補數，使作補數時不會有+0 -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
 */
CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
    //// Replace this comment with your code.

    Add16(a= in , b[0] = true , b[1..15] = false , out = out) ; 



}

1的補數很單純，就是對每一個bit做反向，實作signed number，但是這種做法使例如

n’s bit if n= 4 ;
+0 >> 0000 >> 1的補數 >> 1111 >> -0
+1 >> 0001 >> 1的補數 >> 1110 >> -1

但若我們使用2的補數

+0 >> 0000 >> 1的補數 >> 1111 >>再+1 >> 0000 (捨去carry out 的位元) >> +0

而4bit可以表達 7~ -8 -> 2的補數的概念有點類似模數運算，
使數字就算產生溢位也可以回到範圍內。

我們有了加法器 ，以及補數的概念，就可以開始寫ALU 算術邏輯單元

// 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
/**
 * ALU (Arithmetic Logic Unit):
 * Computes out = one of the following functions:
 *                0, 1, -1,
 *                x, y, !x, !y, -x, -y,
 *                x + 1, y + 1, x - 1, y - 1,
 *                x + y, x - y, y - x,
 *                x & y, x | y
 * on the 16-bit inputs x, y,
 * according to the input bits zx, nx, zy, ny, f, no.
 * In addition, computes the two output bits:
 * if (out == 0) zr = 1, else zr = 0
 * if (out < 0)  ng = 1, else ng = 0
 */
// Implementation: Manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) sets x = 0        // 16-bit constant
// if (nx == 1) sets x = !x       // bitwise not
// if (zy == 1) sets y = 0        // 16-bit constant
// if (ny == 1) sets y = !y       // bitwise not
// if (f == 1)  sets out = x + y  // integer 2's complement addition
// if (f == 0)  sets out = x & y  // bitwise and
// if (no == 1) sets out = !out   // bitwise not

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) or (out = x & y)?
        no; // negate the out output?
    OUT 
        out[16], // 16-bit output
        zr,      // if (out == 0) equals 1, else 0
        ng;      // if (out < 0)  equals 1, else 0

    PARTS:
    //// Replace this comment with your code.

    //zx
    And16(a=x , b = false , out = zx1 ) ; 
    Mux16(a =x ,  b = zx1 , sel = zx , out = zxOut) ; 

    //nx
    Not16(in = zxOut , out = nx1) ;
    Mux16(a =zxOut , b = nx1 , sel = nx , out = xOut) ; 

    //zy
    And16(a=y , b = false , out = zy1 ) ; 
    Mux16(a =y ,  b =zy1 , sel = zy , out = zyOut) ; 

    //ny
    Not16(in = zyOut , out = ny1) ;
    Mux16(a =zyOut, b = ny1 , sel = ny , out = yOut) ; 

    //f
    Add16(a = xOut , b = yOut , out = f1) ; 
    And16(a = xOut  , b = yOut , out =f2 ) ;
    Mux16(a = f2 , b = f1 , sel = f , out = fOut) ; 
    //n 
    Not16(in = fOut , out = NfOut) ; 
    Mux16(a = fOut , b = NfOut , sel =no ,out[0..7] = outRight , out[8..15] = outLeft ,out[15] = firstBit, out = out) ; 

    //zr
    Or8Way(in = outRight , out = ZroutRight) ; 
    Or8Way(in = outLeft , out = ZroutLeft) ; 
    Or(a = ZroutRight , b = ZroutLeft , out = Orzr ) ; 
    Not(in = Orzr , out = zr) ; 

    And(a = firstBit , b = true , out = ng)  ;


}

注意的點:
不管if else 先把功能寫出來，再利用多工器做功能選擇，sel bit 是表上的條件式
在實作zr 以及 ng這兩個bit時遇到了一些困難
zr : out == 0 時輸出 1
每個bit做or 就知道這之間有沒有出現1了
最後因為要輸出1 所以反相
ng: 是否小於0 所以要預留輸出線路為MSB (Nand2Teris為 Little Endian)

為了功能實作方便，可以指定某些範圍的bit儲存到另一個變數，因為內部pin角不可讀取特定範圍的位元。