Close
0%
0%

Computer build from first principals

Complete computer build from the logic to the compiler and operating system.

Public Chat
Similar projects worth following
187 views
I'm currently working on building a complete computer from the logic up. I will be implementing it 3 ways with bread boards, in Logisim and on an emulator.

Stage 1) Boolean Logic & Arithmetic

Stage 2) Sequential Logic

Stage 3) Machine Language and Computer Architecture

Stage 4) Assembler

Stage 5) Stack Arithmetic, Program Control and high level language design.

Stage 6) Compiler syntax analysis and code generation.

Stage 7) Operating system.

MUX.jpg

Multiplexer 8 way 16bit

JPEG Image - 29.96 kB - 06/25/2019 at 08:46

Preview
Download

DMUX.jpg

Demultiplexer 8 way

JPEG Image - 13.30 kB - 06/25/2019 at 08:46

Preview
Download

XOR.png

XOR. Nand implementation.

Portable Network Graphics (PNG) - 7.94 kB - 06/25/2019 at 08:47

Preview
Download

SINGLEMUX.jpg

Multiplexer Nand implementation.

JPEG Image - 21.94 kB - 06/25/2019 at 08:47

Preview
Download

SINGLEDMUX.jpg

Demultiplexer Nand implementation.

JPEG Image - 21.69 kB - 06/25/2019 at 08:48

Preview
Download

View all 6 files

  • 1 × ALU 16 Function Arithmetic Logic Unit.

  • ALU Implemented

    Michael Walker06/26/2019 at 06:10 0 comments

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

  • 16 Bit +1 Increment implementation. + HDL

    Michael Walker06/26/2019 at 00:13 0 comments

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

  • HDL Completed for Boolean Logic.

    Michael Walker06/25/2019 at 09:21 0 comments

    Finished the HDL code for the logic, starting work on the ALU.

View all 3 project logs

  • 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

Enjoy this project?

Share

Discussions

Michael Walker wrote 08/11/2019 at 04:32 point

Absolutely was! Such a great project / book / video series.  These guys are amazing educators.

  Are you sure? yes | no

DocInfinity wrote 08/06/2019 at 01:22 point

inspired(?) by Shimon Schocken and Noam Nisan‘s nand2tetris project?

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates