Chapter 2

Combinational Chips

HalfAdder chip

Half Adder（半加器）：将两个一位二进制数相加，產生和（sum）和進位信號（carry）輸出，輸出的進位信號代表了輸出兩個數相加溢出的高一位數值。這兩個一位二級制數的和等於$$2*carry＋sum$$。

$$ sum = ab' + a'b $$

$$ carry = ab $$

圖片來源：https://commons.wikimedia.org/w/index.php?curid=1023090

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);
}

FullAdder chip

Full Adder(全加器):全加器将两个一位二进制数相加，并根据接收到的低位进位信号，输出和、进位输出。全加器的三个输入信号为两个加数A、B和低位进位Cin全加器通常可以通过级联（cascade）的方式，构成多位（如8位、16位、32位）二进制数加法器的基本部分。全加器的输出和半加器类似，包括向高位的进位信号Cout和本位的和信号S，相加结果的总和表达为 $$sum = 2 * Cout + S$$

$$S = A⊕B⊕Cin$$

$$Cout = (A∙B) + (B∙C) + (A∙C)$$

圖片來源：https://commons.wikimedia.org/w/index.php?curid=1023334

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 = x,carry = carry1);
    HalfAdder(a = x,b = c,sum = sum,carry = carry2);
    Or(a = carry1,b = carry2,out = carry);
}

Add16 chip

16-bit Adder:利用半加器和全加器完成16-bit的加法。

最低位用半加器因為不需要考慮來自低位的進位。

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 = carry0);
   FullAdder(a = a[1],b = b[1],c = carry0,sum = out[1],carry = carry1);
   FullAdder(a = a[2],b = b[2],c = carry1,sum = out[2],carry = carry2);
   FullAdder(a = a[3],b = b[3],c = carry2,sum = out[3],carry = carry3);
   FullAdder(a = a[4],b = b[4],c = carry3,sum = out[4],carry = carry4);
   FullAdder(a = a[5],b = b[5],c = carry4,sum = out[5],carry = carry5);
   FullAdder(a = a[6],b = b[6],c = carry5,sum = out[6],carry = carry6);
   FullAdder(a = a[7],b = b[7],c = carry6,sum = out[7],carry = carry7);
   FullAdder(a = a[8],b = b[8],c = carry7,sum = out[8],carry = carry8);
   FullAdder(a = a[9],b = b[9],c = carry8,sum = out[9],carry = carry9);
   FullAdder(a = a[10],b = b[10],c = carry9,sum = out[10],carry = carry10);
   FullAdder(a = a[11],b = b[11],c = carry10,sum = out[11],carry = carry11);
   FullAdder(a = a[12],b = b[12],c = carry11,sum = out[12],carry = carry12);
   FullAdder(a = a[13],b = b[13],c = carry12,sum = out[13],carry = carry13);
   FullAdder(a = a[14],b = b[14],c = carry13,sum = out[14],carry = carry14);
   FullAdder(a = a[15],b = b[15],c = carry14,sum = out[15],carry = carry15);
}

Inc16 chip

16-bit incrementer:完成16－bit的自加1。

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

    PARTS:
   // Put you code here:
   HalfAdder(a = in[0],b = true,sum = out[0],carry = carry0);
   HalfAdder(a = in[1],b = carry0,sum = out[1],carry = carry1);  
   HalfAdder(a = in[2],b = carry1,sum = out[2],carry = carry2);
   HalfAdder(a = in[3],b = carry2,sum = out[3],carry = carry3);
   HalfAdder(a = in[4],b = carry3,sum = out[4],carry = carry4);
   HalfAdder(a = in[5],b = carry4,sum = out[5],carry = carry5);
   HalfAdder(a = in[6],b = carry5,sum = out[6],carry = carry6);
   HalfAdder(a = in[7],b = carry6,sum = out[7],carry = carry7);
   HalfAdder(a = in[8],b = carry7,sum = out[8],carry = carry8);
   HalfAdder(a = in[9],b = carry8,sum = out[9],carry = carry9);
   HalfAdder(a = in[10],b = carry9,sum = out[10],carry = carry10);
   HalfAdder(a = in[11],b = carry10,sum = out[11],carry = carry11);
   HalfAdder(a = in[12],b = carry11,sum = out[12],carry = carry12);
   HalfAdder(a = in[13],b = carry12,sum = out[13],carry = carry13);
   HalfAdder(a = in[14],b = carry13,sum = out[14],carry = carry14);
   HalfAdder(a = in[15],b = carry14,sum = out[15],carry = carry15);
}

ALU chip

Arithmetic Logic Unit:ALU能對兩個輸入的16-bit的二進制數進行以下操作:$$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$$

對於6個額外的輸入1-bit二進制數是對輸入的兩個16-bit數進行重新定義，若zx ＝ 1，則置x ＝ 0；若nx ＝ 1，則置x ＝ !x,若zy ＝ 1，則置y ＝ 0；若ny ＝ 1，則置y ＝ !y;若f ＝ 1，則控制輸出out ＝ x ＋ y，若f ＝ 0，則控制輸出out = x & y;若no ＝ 1，則out ＝ !out;若out = 0,則置1-bit輸出zr = 1;若out < 0,則置1-bit輸出ng ＝ 1。

//因為ALU涉及到選擇輸出，所以我用了Mux16來選擇輸出數。

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:
   //zx = 1,x = 0
   Mux16(a = x,b = false,sel = zx,out = x1);

   // nx = 1,x = !x
   Not16(in = x1,out = negx);
   Mux16(a = x1,b = negx,sel = nx,out = x2);

   // zy = 1,y = 0
   Mux16(a = y,b = false,sel = zy,out = y1);

   // ny = 1,y = !y
   Not16(in = y1,out = negy);
   Mux16(a = y1,b = negy,sel = ny,out = y2);

   // f = 1,out = x + y,f = 0,out = x & y
   Add16(a = x2,b = y2,out = out1);
   And16(a = x2,b = y2,out = out2);
   Mux16(a = out2,b = out1,sel = f,out = xy);

   // out < 0 then ng = 1,else ng = 0
   Not16(in = xy,out = notxy);
   Mux16(a = xy,b = notxy,sel = no,out[15] = ng,out[0..7] = part1,out[8..15] = part2,out = out);

   // out == 0 then zr = 1,else zr = 0
   Or8Way(in = part1,out = or1);
   Or8Way(in = part2,out = or2);
   Or(a = or1,b = or2,out = nzr);
   Not(in = nzr,out = zr);
}