nand2tetris

All files of this project are part of www.nand2tetris.org and the book "The Elements of Computing Systems" by Nisan and Schocken, MIT Press.

Implement computer's hardware

My solution for the project nand2tetris. This first part of the project consist to build a basic simulated functional computer with the Hardware simulator tool.

When this is done, the second part consists to build an operating system for this computer.

Contents

• Introduction
• Chapters
  • Chapter 1: Boolean Logic
  • Chapter 2: Boolean Arithmetic
  • Chapter 3: Memory
  • Chapter 4: Machine Language

I will be adding chapters as I progress in the course

Introduction

The course provides you with tools and resources to develop the entire project. Each of the modules of the project consists of exercises that must be completed. As the modules are completed, they are used to develop the next one, and so on.

I use Logisim tool too to make diagrams to facilitate and better understand my implementations.

Chapter 1: Boolean Logic

Starting with one primitive logic gate, Nand, and build all the other necessary logic gates, Not, And, Or, Xor, Mux and DMux. The target computer will be designed to operate on 16-bit values, then 16-bit versions of the basic gates, like Not16, And16, and so on, will also be build.

The implementations have been made using basic HDL(Hardware Description Language).

Elementary logic gates

• Not
• And
• Or
• Xor
• Mux (Multiplexer)
• DMux (Demultiplexer)

16-bit variants

• Not16
• And16
• Or16
• Mux16

Multi-Way variants

• Or8Way
• Mux4Way16
• Mux8Way16
• DMux4Way
• DMux8Way

Chapter 2: Boolean Arithmetic

The purpose here is to continue implementing chips but a little higher level, and finally build an ALU(Arithmetic Logical Unit). The chips implemented here avoids to make arithmetic and bitwise operations.

Two's complement

If we want to represent signed numbers(negatives), we can use half of the bit representations for it.

The two's complement of $\ x$ is defined to be $\ 2^n - x $, where $\ n$ = num of bits.

For example, the TC of -5

$\ 2^4 - 5$ ---> $\ 16 - 5 =$ $\color{green}{11} $

Regular addition $\ \mod 2^n $

With this info, we can make subtraction too. Then if you want to compute $\ -2 + (-5) $

$\ 14 + 11 = 25$

$\ 25 \mod 16 = 9$ ---> $\ 2^4 - 9 =$ $\color{green}{-7} $

ALU

Challenges

• Use 0’s and 1’s for representing numbers
• Use logic gates for realizing arithmetic functions.

Functions (f)

• Arithmetic:
  • (x + y), (x - y), (y - x)
  • (x + 1), (y + 1)
  • (x - 1), (y - 1)
• Logical:
  • (x & y), (x | y)
  • (!x), (!y)

The inputs zx, nx, zy, etc... indicate whether these operations are performed or not on the inputs x and y. On each step the value of x/y is or not modified.

If you want to compute (out = y - x), where x = 4 and y = 6, the control bits(zx, nx, ...) are in the table.

x = 0100

y = 0110

In pre-setting, the only operation to do is (!y), so:

x = 0100

y = 1001

Next step, select between (+) and (&) is true, then out = x + y:

0100 + 1001 = 1101

And finally the output post-setting is true, then out = !out:

!(1101) = 0010 = 2

Chips to implement, including ALU:

• HalfAdder
• FullAdder
• Add16 (16-bit adder)
• Inc16 (16-bit incrementor)
• ALU

Chapter 3: Memory

In the third module the target its to build the computer's main memory unit, also known as Random Access Memory (RAM). Going bottom-up frmo elementary flip-flop gates to one-bit registers to n-bit registers to a family of RAM chips.

Unlike the chips implemented so far, which are based on combinational logic, the computer's memory logic requires a clock-base secuential logic.

D-Flip-Flop and 1-bit Register

DFF is the most elementary sequential gate; outputs the input in the previous time-step $\color{grey}{ (out[t] = in[t - 1])}$

Combining DFF with 1-bit register, it can store one bit over time.

Types of memory:

• DRAM
• SRAM (Cache)
• ROM
• Flash

Chips to implement:

• Register (1-bit, 16-bit)
• RAM-n (8, 64, 512, 4096, 16384)
• PC (Program Counter)

Chapter 4: Machine Language

Control

Conditional and unconditional branching