02. Boolean Arithmetic
ALU
ALU（Algorithmic Logic Unit）算术逻辑单元，将所有的基础算术操作和逻辑操作都封装起来。
MSB（Most Significant Bits）最高有效位。
LSB（Least Significant Bits）最低有效位。
Chip API
芯片名： HalfAdder
输入： a, b
输出： sum, carry
功能： sum = LSB of a + b
carry = MSB of a + b芯片名： FullAdder
输入： a, b, c
输出： sum, carry
功能： sum = LSB of a + b + c
carry = MSB of a + b + c芯片名： Add16
输入： a[16], b[16]
输出： out[16]
功能： out = a + b
说明： 2 补码的整数加法，不处理溢出的情况芯片名： Inc16
输入： in[16]
输出： out[16]
功能： out = in + 1
说明： 2 补码的整数加法，不处理溢出的情况芯片名： ALU
输入： x[16], y[16], // 两个 16 位数据输入
zx, // x 输入置零
nx, // x 输入取反
zy, // y 输入置零
ny, // y 输入取反
f, // 功能码：为 1 代表 Add，为 0 则代表 And
no // out 输出取反
输出： out[16], // 16 位输出
zr, // 当 out=0 则为 True，否则 False
ng // 当 out<0 则为 True，否则 False
功能： if zx then x = 0 // 16 位常量 0
if nx then x = !x // 按位取反
if zy then y = 0 // 16 位常量 0
if ny then y = !y // 按位取反
if f then out = x + y else out = x & y // 2 补码的整数加法，按位与运算 And
if no then out = !out // 按位取反
if out = 0 then zr = 1 else zr = 0 // 16 位 eq，比较
if out < 0 then ng = 1 else ng = 0 // 16 位 neg，比较
说明： 不处理溢出的情况Project 02
The centerpiece of the computer's architecture is the CPU, or Central Processing Unit, and the computational centerpiece of the CPU is the ALU, or Arithmetic-Logic Unit. In this project you will gradually build a set of chips that carry out arithmetic addition, culminating in the construction of the ALU chip of the Hack computer.
Objective
Build the following chips:
HalfAdder
FullAdder
Add16
Inc16
ALUWe note in passing that all the chips listed above are standard, except for the ALU, which varies from one computer architecture to another.
Implementation Tips
All the Implementation Tips of project 1 apply to this project also, so read them now.
There is only one modification: When implementing the chips of project 2, you can use, as chip-parts, any of the chips listed in project 1 and in project 2. If you are using the desktop simulator, don’t add any files to the projects/2 folder: the desktop simulator will use builtin chip implementations, as needed.
The Hack ALU computes a 16-bit value named out. In addition, it computes two 1-bit outputs named zr and ng. We recommend building the ALU in two stages. First, implement a basic ALU that computes out, ignoring the zr and ng outputs. Then implement a final version that computes out as well as zr and ng. We provide two sets of files for testing each stage: ALU-basic.tst and ALU-basic.cmp for testing the basic version; ALU.tst and ALU.cmp for testing the final version.
If you are using the online simulator, which is the preferred option, you can select the ALU test script from the Test drop-down menu; If you are using the desktop simulator, you can load the ALU test script from the projects/2 folder.
Solutions
/**
* 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:
And(a=a, b=b, out=carry);
Xor(a=a, b=b, out=sum);
}/**
* 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:
HalfAdder(a=a, b=b, sum=sum1, carry=carry1);
HalfAdder(a=sum1, b=c, sum=sum, carry=carry2);
Or(a=carry1, b=carry2, out=carry);
}/**
* 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:
FullAdder(a=a[0], b=b[0], c=false, 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);
}/**
* 16-bit incrementer:
* out = in + 1
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
Add16(a=in, b[0]=true, b[1..15]=false, out=out);
}/**
* 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:
Mux16(a=x, b=false, sel=zx, out=x1);
Not16(in=x1, out=notx1);
Mux16(a=x1, b=notx1, sel=nx, out=x2);
Mux16(a=y, b=false, sel=zy, out=y1);
Not16(in=y1, out=noty1);
Mux16(a=y1, b=noty1, sel=ny, out=y2);
Add16(a=x2, b=y2, out=addxy);
And16(a=x2, b=y2, out=andxy);
Mux16(a=andxy, b=addxy, sel=f, out=fout);
Not16(in=fout, out=notfout);
Mux16(a=fout, b=notfout, sel=no, out=out, out[15]=ng, out[0..7]=low, out[8..15]=high);
Or8Way(in=low, out=orlow);
Or8Way(in=high, out=orhigh);
Or(a=orlow, b=orhigh, out=nzr);
Not(in=nzr, out=zr);
}