Build Instructions

Collapse instructions

• 1

  Boolean Logic HDL

  /**
   * 16-bit bitwise And:
   * for i = 0..15: out[i] = (a[i] and b[i])
   */
  
  CHIP And16 {
      IN a[16], b[16];
      OUT out[16];
  
      PARTS:
      And (a=a[0], b=b[0], out=out[0]); 
      And (a=a[1], b=b[1], out=out[1]); 
      And (a=a[2], b=b[2], out=out[2]); 
      And (a=a[3], b=b[3], out=out[3]); 
      And (a=a[4], b=b[4], out=out[4]); 
      And (a=a[5], b=b[5], out=out[5]); 
      And (a=a[6], b=b[6], out=out[6]); 
      And (a=a[7], b=b[7], out=out[7]); 
      And (a=a[8], b=b[8], out=out[8]); 
      And (a=a[9], b=b[9], out=out[9]); 
      And (a=a[10], b=b[10], out=out[10]); 
      And (a=a[11], b=b[11], out=out[11]); 
      And (a=a[12], b=b[12], out=out[12]); 
      And (a=a[13], b=b[13], out=out[13]); 
      And (a=a[14], b=b[14], out=out[14]); 
      And (a=a[15], b=b[15], out=out[15]); 
  }
  /**
   * And gate:
   * out = 1 if (a == 1 and b == 1)
   *       0 otherwise
   */
  
  CHIP And {
      IN a, b;
      OUT out;
  
      PARTS:
      Nand(a=a, b=b, out=aNandb);
      Nand(a=aNandb, b=aNandb, out=out);
  }
  /**
   * 4-way demultiplexor:
   * {a, b, c, d} = {in, 0, 0, 0} if sel == 00
   *                {0, in, 0, 0} if sel == 01
   *                {0, 0, in, 0} if sel == 10
   *                {0, 0, 0, in} if sel == 11
   */
  
  CHIP DMux4Way {
      IN in, sel[2];
      OUT a, b, c, d;
  
      PARTS:
      DMux(in=in, sel=sel[1], a=inZero, b=inOne);
      DMux(in=inZero, sel=sel[0], a=a, b=b);
      DMux(in=inOne, sel=sel[0], a=c, b=d); 
  }
  /**
   * 8-way demultiplexor:
   * {a, b, c, d, e, f, g, h} = {in, 0, 0, 0, 0, 0, 0, 0} if sel == 000
   *                            {0, in, 0, 0, 0, 0, 0, 0} if sel == 001
   *                            etc.
   *                            {0, 0, 0, 0, 0, 0, 0, in} if sel == 111
   */
  
  CHIP DMux8Way {
      IN in, sel[3];
      OUT a, b, c, d, e, f, g, h;
  
      PARTS:
      DMux(in=in, sel=sel[2], a=inZero, b=inOne);
      DMux4Way(in=inZero, sel=sel[0..1], a=a, b=b, c=c, d=d);
      DMux4Way(in=inOne, sel=sel[0..1], a=e, b=f, c=g, d=h);
  }
  `/**
   * Demultiplexor:
   * {a, b} = {in, 0} if sel == 0
   *          {0, in} if sel == 1
   */
  
  CHIP DMux {
      IN in, sel;
      OUT a, b;
  
      PARTS:
      Nand(a=sel, b=sel, out=notSel);
      Nand(a=notSel, b=in, out=notSelNandb);
      Nand(a=notSelNandb, b=notSelNandb, out=a);
      Nand(a=in, b=sel, out=inAndSel);
      Nand(a=inAndSel, b=inAndSel, out=b);
  }
  /**
   * 16-bit multiplexor: 
   * for i = 0..15 out[i] = a[i] if sel == 0 
   *                        b[i] if sel == 1
   */
  
  CHIP Mux16 {
      IN a[16], b[16], sel;
      OUT out[16];
  
      PARTS:
      Mux (a=a[0], b=b[0], sel=sel, out=out[0]); 
      Mux (a=a[1], b=b[1], sel=sel, out=out[1]); 
      Mux (a=a[2], b=b[2], sel=sel, out=out[2]); 
      Mux (a=a[3], b=b[3], sel=sel, out=out[3]); 
      Mux (a=a[4], b=b[4], sel=sel, out=out[4]); 
      Mux (a=a[5], b=b[5], sel=sel, out=out[5]); 
      Mux (a=a[6], b=b[6], sel=sel, out=out[6]); 
      Mux (a=a[7], b=b[7], sel=sel, out=out[7]); 
      Mux (a=a[8], b=b[8], sel=sel, out=out[8]); 
      Mux (a=a[9], b=b[9], sel=sel, out=out[9]); 
      Mux (a=a[10], b=b[10], sel=sel, out=out[10]); 
      Mux (a=a[11], b=b[11], sel=sel, out=out[11]); 
      Mux (a=a[12], b=b[12], sel=sel, out=out[12]); 
      Mux (a=a[13], b=b[13], sel=sel, out=out[13]); 
      Mux (a=a[14], b=b[14], sel=sel, out=out[14]); 
      Mux (a=a[15], b=b[15], sel=sel, out=out[15]); 
  }
  /**
   * 4-way 16-bit multiplexor:
   * out = a if sel == 00
   *       b if sel == 01
   *       c if sel == 10
   *       d if sel == 11
   */
  
  CHIP Mux4Way16 {
      IN a[16], b[16], c[16], d[16], sel[2];
      OUT out[16];
  
      PARTS:
      Mux16(a=a, b=b, sel=sel[0], out=aMuxbSel);
      Mux16(a=c, b=d, sel=sel[0], out=cMuxdSel);
      Mux16(a=aMuxbSel, b=cMuxdSel, sel=sel[1], out=out); 
  }/**
   * 8-way 16-bit multiplexor:
   * out = a if sel == 000
   *       b if sel == 001
   *       etc.
   *       h if sel == 111
   */
  
  CHIP Mux8Way16 {
      IN a[16], b[16], c[16], d[16],
         e[16], f[16], g[16], h[16],
         sel[3];
      OUT out[16];
  
      PARTS:
      Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=abcd);
      Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=efgh);
      Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
  }
  /** 
   * Multiplexor:
   * out = a if sel == 0
   *       b otherwise
   */
  
  CHIP Mux {
      IN a, b, sel;
      OUT out;
  
      PARTS:
      Nand(a=sel, b=sel, out=notSel);
      Nand(a=a, b=notSel, out=aNotSel);
      Nand(a=b, b=sel, out=aNandb); 
      Nand(a=aNotSel, b=aNandb, out=out); 
  }/**
   * 16-bit Not:
   * for i=0..15: out[i] = not in[i]
   */
  
  CHIP Not16 {
      IN in[16];
      OUT out[16];
  
      PARTS:
      Not (in=in[0], out=out[0]); 
      Not (in=in[1], out=out[1]); 
      Not (in=in[2], out=out[2]); 
      Not (in=in[3], out=out[3]); 
      Not (in=in[4], out=out[4]); 
      Not (in=in[5], out=out[5]); 
      Not (in=in[6], out=out[6]); 
      Not (in=in[7], out=out[7]); 
      Not (in=in[8], out=out[8]); 
      Not (in=in[9], out=out[9]); 
      Not (in=in[10], out=out[10]); 
      Not (in=in[11], out=out[11]); 
      Not (in=in[12], out=out[12]); 
      Not (in=in[13], out=out[13]); 
      Not (in=in[14], out=out[14]); 
      Not (in=in[15], out=out[15]); 
  }
  /**
   * Not gate:
   * out = not in
   */
  
  CHIP Not {
      IN in;
      OUT out;
  
      PARTS:
      Nand(a=in, b=in, out=out);
  }
  /**
   * 16-bit bitwise Or:
   * for i = 0..15 out[i] = (a[i] or b[i])
   */
  
  CHIP Or16 {
      IN a[16], b[16];
      OUT out[16];
  
      PARTS:
      Or (a=a[0], b=b[0], out=out[0]); 
      Or (a=a[1], b=b[1], out=out[1]); 
      Or (a=a[2], b=b[2], out=out[2]); 
      Or (a=a[3], b=b[3], out=out[3]); 
      Or (a=a[4], b=b[4], out=out[4]); 
      Or (a=a[5], b=b[5], out=out[5]); 
      Or (a=a[6], b=b[6], out=out[6]); 
      Or (a=a[7], b=b[7], out=out[7]); 
      Or (a=a[8], b=b[8], out=out[8]); 
      Or (a=a[9], b=b[9], out=out[9]); 
      Or (a=a[10], b=b[10], out=out[10]); 
      Or (a=a[11], b=b[11], out=out[11]); 
      Or (a=a[12], b=b[12], out=out[12]); 
      Or (a=a[13], b=b[13], out=out[13]); 
      Or (a=a[14], b=b[14], out=out[14]); 
      Or (a=a[15], b=b[15], out=out[15]); 
  }/**
   * 8-way Or: 
   * out = (in[0] or in[1] or ... or in[7])
   */
  
  CHIP Or8Way {
      IN in[8];
      OUT out;
  
      PARTS:
      Or (a=in[0], b=in[1], out=out1); 
      Or (a=in[2], b=in[3], out=out2); 
      Or (a=in[4], b=in[5], out=out3); 
      Or (a=in[6], b=in[7], out=out4); 
      Or (a=out1, b=out2, out=outa);
      Or (a=out3, b=out4, out=outb);
      Or (a=outa, b=outb, out=out); 
  }
   /**
   * Or gate:
   * out = 1 if (a == 1 or b == 1)
   *       0 otherwise
   */
  
  CHIP Or {
      IN a, b;
      OUT out;
  
      PARTS:
      Nand(a=a, b=a, out=nota);
      Nand(a=b, b=b, out=notb);
      Nand(a=nota, b=notb, out=out);
  }
  /**
   * Exclusive-or gate:
   * out = not (a == b)
   */
  
  CHIP Xor {
      IN a, b;
      OUT out;
  
      PARTS:
      Nand(a=a, b=b, out=aNandb); 
      Nand(a=a, b=aNandb, out=aNandNotb); 
      Nand(a=aNandb, b=b, out=notaNandb);
      Nand(a=aNandNotb, b=notaNandb, out=out);  
  }
  

• 2

  Arithmetic HDL for ALU.

  /**
   * Adds two 16-bit values.
   * The most significant carry bit is ignored.
   */
  
  CHIP Add16 {
      IN a[16], b[16];
      OUT out[16];
  
      PARTS:
      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);
  }
  /**
   * 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=sumab, carry=coutab);
      HalfAdder(a=c, b=sumab, sum=sum, carry=coutcab);
      Or(a=coutab, b=coutcab, out=carry);
  }/**
   * 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:
      Xor(a=a, b=b, out=sum); 
      And(a=a, b=b, out=carry); 
  }
  /**
   * 16-bit incrementer:
   * out = in + 1 (arithmetic addition)
   */
  
  CHIP Inc16 {
      IN in[16];
      OUT out[16];
  
      PARTS:
      HalfAdder(a=in[0],  b=true, sum=out[0],  carry=c0);
      HalfAdder(a=in[1],  b=c0,   sum=out[1],  carry=c1);
      HalfAdder(a=in[2],  b=c1,   sum=out[2],  carry=c2);
      HalfAdder(a=in[3],  b=c2,   sum=out[3],  carry=c3);
      HalfAdder(a=in[4],  b=c3,   sum=out[4],  carry=c4);
      HalfAdder(a=in[5],  b=c4,   sum=out[5],  carry=c5);
      HalfAdder(a=in[6],  b=c5,   sum=out[6],  carry=c6);
      HalfAdder(a=in[7],  b=c6,   sum=out[7],  carry=c7);
      HalfAdder(a=in[8],  b=c7,   sum=out[8],  carry=c8);
      HalfAdder(a=in[9],  b=c8,   sum=out[9],  carry=c9);
      HalfAdder(a=in[10], b=c9,   sum=out[10], carry=c10);
      HalfAdder(a=in[11], b=c10,  sum=out[11], carry=c11);
      HalfAdder(a=in[12], b=c11,  sum=out[12], carry=c12);
      HalfAdder(a=in[13], b=c12,  sum=out[13], carry=c13);
      HalfAdder(a=in[14], b=c13,  sum=out[14], carry=c14);
      HalfAdder(a=in[15], b=c14,  sum=out[15], carry=false);
  }

• 3

  The ALU

  /**
   * 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:
      // zx
      And16(a=x, b=false, out=zxTrue);
      Mux16(a=x, b=zxTrue, sel=zx, out=zerox);
  
      // nx
      Not16(in=zerox, out=notx);
      Mux16(a=zerox, b=notx, sel=nx, out=negx);
  
      // zy
      And16(a=y, b=false, out=zyTrue);
      Mux16(a=y, b=zyTrue, sel=zy, out=zeroy);
  
      // ny
      Not16(in=zeroy, out=noty);
      Mux16(a=zeroy, b=noty, sel=ny, out=negy);
  
      // f
      And16(a=negx, b=negy, out=andfxy);
      Add16(a=negx, b=negy, out=addfxy);
      Mux16(a=andfxy, b=addfxy, sel=f, out=fxy);
  
      // no
      Not16(in=fxy, out=notfxy);
      Mux16(a=fxy, b=notfxy, sel=no, out=out);
  }

View all 3 instructions