Elements of Computing Systems - Chapter 1 - Understandings

Great book and I am proud to own one!

So some notes and my understandings from Chapter 1 , mostly for future reference..
  • Every digital device is based on a set of Chips designed to store and process information.
  • Chips are made from (Elementary Logic) Gates.

Gate Logic
A Gate is a physical device that implements a Boolean Function.

If a Boolean function f operates on n variables and returns m binary results (in all our examples so far, m was 1), the gate that implements f will have n input pins and m output pins.

Representation of Elementary Gates:



Gate Interface & Gate Implementation:


Logic Design

  • The construction seen above is an example of Gate Logic also called Logic Design.
  • Logic Design is the art of interconnecting gates in order to implement more complex functionality, leading to the notion of Composite Gates.
Gate interface is unique. 
The interface, however, can be realised using several implementations, some of which will be better in terms of cost, speed or simplicity.

Nand Gate
Starting point will be a Nand Gate, from which all other Gates and Chips will be built.

The Nand Gate is designed to compute the following Boolean Function:
f(a,b) = Nand(a,b)
 
a b | f(a,b)
-------------
0 0 |   1 
0 1 |   1
1 0 |   1
1 1 |   0

Nand API
Chip name: Nand
Inputs: a, b
Outputs: out
Function: If a=b=1 then out=0 else out=1
Comment: This gate is considered primitive and thus there is no need to implement it.

My Gate Implementations Based on Nand Gate

Not Gate
Chip name: Not
Inputs: in
Outputs: out
Function: If in = 0, out = 1. If in = 1, out = 0.
CHIP Not {
    IN in;
    OUT out;
 
    PARTS:
    Nand(a=in, b=true, out=out);
}

And Gate
Chip name: And
Inputs: a, b
Outputs: out
Function: If a = 1 and b = 1, out = 1. Else, out = 0.
CHIP And {
    IN a, b;
    OUT out;
 
    PARTS:
    Nand(a=a, b=b, out=x);
    Nand(a=x, b=x, out=out);
}

Here is a representation I made in Excel:


Or Gate
Chip name: Or
Inputs: a, b
Outputs: out
Function: If a=b=0 then out=0 else out=1.
CHIP Or {
    IN a, b;
    OUT out;
 
    PARTS:
    Nand(a=a, b=a, out=x);
    Nand(a=b, b=b, out=y);
    Nand(a=x, b=y, out=out);
}

Xor Gate
Chip name: XOr
Inputs: a, b
Outputs: out
Function: If a≠b then out=1 else out=0.
CHIP Xor {
    IN a, b;
    OUT out;
 
    PARTS:
    Nand(a=a, b=b, out=root);
    Nand(a=a, b=root, out=x1);
    Nand(a=root, b=b, out=x2);
    Nand(a=x1, b=x2,out=out);
}

Let 's see how our Xor implementation looks like using this great web page:





Mux Gate (Multiplexor)
A multiplexor is a three-input gate that uses one of the inputs, called "selection bit" to select and output one of the other two inputs, called ""data bit"s. Thus, a better name for this device might have been Selector.

Chip name: Mux
Inputs: a, b, sel
Outputs: out
Function: If sel=0 then out=a else out=b.

Here is my implementation for a Mux Gate:
CHIP Mux {
    IN a, b, sel;
    OUT out;
 
    PARTS:
    Not(in=sel,out=notsel);
    Nand(a=a, b=notsel, out=anandnotsel);
    Nand(a=sel, b=b, out=selb);
    Nand(a=anandnotsel, b=selb, out=out);
}

Let 's see this implementation described above with some nice graphics:





Of course there are 3 inputs, they can all have 2 different possible values, which means a total of 2x2x2 = 8 possible conditions are available, but I am too lazy too add images for all. Believe me, it works..

Remember, before we also said a different implementation may be possible for a given interface. Here is a different implementation for the given interface: Mux


What is so special about this? We have the same interface, same functionality with different implementations. This is cool.

Demux Gate (Demultiplexor)
Chip name: DMux
Inputs: in, sel
Outputs: a, b
Function: If sel=0 then a=in, b=0 else a=0, b=in.

And here is my implementation:
CHIP DMux {
    IN in, sel;
    OUT a, b;
 
    PARTS:
    Not(in=sel, out=notsel);
    Not(in=notsel, out=notnotsel);
    And(a=notnotsel,b=in,out=b);
    And(a=notsel, b=in, out=a);
}

I hope this post helped you somehow. These are my notes from Chapter - 01 of nand2tetris.