Chapter 2 - Arithmetic Logical Unit

This is the workflow problems of Chapter 2 of the "The Elements of Computing Systems" by Noam Nisan and Shimon Schocken. These are my own solutions for my own reference.

As the NAND gate is considered primitive we build all our logical gates around this gate following order of the book. The Elements of Computing Systems.

Building the ALU

The ALU. 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. Which function to compute is determined by 6 input bits denoted zx, nx, zy, ny, f, no. The computed function's value is called "out". In addition to computing out, the ALU computes two 1-bit outputs called zr and ng: if out == 0, zr = 1; otherwise zr = 0; If out < 0, ng = 1; otherwise ng = 0. The 6-bit combinations (zx,nx,zy,ny,f,no) and their effect are documented in the book.


// Implementation: the ALU manipulates the x and y
// inputs and then 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
// if (out == 0) sets zr = 1
// if (out < 0)  sets 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 f == 1) or out = 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:
    Mux16(a=x, b=false, sel=zx, out=x1);
    Not16(in=x1, out=notx);
    Mux16(a=x1, b=notx, sel=nx, out=x2);

    Mux16(a=y, b=false, sel=zy, out=y1);
    Not16(in=y1, out=noty);
    Mux16(a=y1, b=noty, 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=posf);
    Not16(in=posf, out=negf);
    Mux16(a=posf, b=negf, sel=no, out=out, out[0..7]=outlow, out[8..15]=outhi, out[15]=ng);

    Or8Way(in=outlow, out=lowor);
    Or8Way(in=outhi,  out=hior);
    Or(a=lowor, b=hior, out=nzr);
    Not(in=nzr, out=zr);
}