Chapter 1 -- Logical Gates

This is the workflow problems of Chapter 1 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.

Nand gate

Example NAND gate representation of a,b and out.


-------a--------> |----\
                  |     | ---> out
-------b--------> |----/

Table representation of Nand gate:

a b out
1 1 0
0 1 1
1 0 1
0 0 1

Not Gate

Note gate logic: If 0 then 1 else 0

CHIP Not {
    IN in;
    OUT out;
    
    PARTS:
    nand(a=in, b=in, out=out)
}

Basically the table below reads input 1, flip to 0, input 0 flip to 1 using the nand gate.

a b out
1 1 0
0 0 1

And Gate

The and gate should be true if a == 1 && b == 1 else 0. This is the exact opposite of the nand gate, so using the nand and not we can quickly create this gate.

CHIP And {
    IN in;
    OUT out;
    
    PARTS:
    nand(a=a,b=b,out=nandOut);
    not(in=nandOut,out=out);
}
a b out
1 1 1
1 0 0
0 1 0
0 0 0

Or Gate

An or gate is true when a == 1 or b == 1 -> 1 else 0; This gate can take advantage of the primitive NOR gate.

CHIP Or {
    IN a, b;
    OUT out;
    
    PARTS:
    not(in=a, out=notA);
    not(in=b, out=notB);
    nand(a=notA, b=notB, out=out);
}
a b out
1 1 1
1 0 1
0 1 1
0 0 0

Xor gate

The xor gate states if a = 0 and b = 0 or a = 1 and b = 1 -> 0 else 1.

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Or(a=a, b=b, out=c1);
    Nand(a=a, b=b, out=c2);
    And(a=c1, b=c2, out=out);
}
a b out
1 1 0
0 1 1
1 0 1
0 0 0

Multilpexor (Mux)

Three input gate that takes a select input as well as an a and b. If select = 0 then out = a else out =b.

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    Not(in=sel, out=nsel);
    And(a=sel, b=b, out=c1);
    And(a=a, b=nsel, out=c2);
    Or(a=c1, b=c2, out=out);
}
a b select out
0 0 0 0
0 1 0 0
1 0 0 1
1 1 0 1
0 0 1 0
0 1 1 1
1 0 1 0
1 1 1 1

Demultiplexor (Dmux)

A Dmux performs two opposite function of a multiplexor. It takes a single input and channels it to one of two possible outputs. If sel=0 then {a = in, b= 0} else {a=0, b=in}.

CHIP DMux {
    IN in, sel;
    OUT a, b;
    
    PARTS:
    not(in=sel,out=notSel);
    and(a=in,b=notSel,out=a);
    or(a=in,b=sel,out=b);
}
a b select in
1 0 0 1
0 0 0 0
0 1 1 1
0 0 1 0