Boolean Arithmetic and the ALU – Nand2Tetris (Week 2)

Binary Numbers

0s and 1s can represent integers based on 2^n

computers we usually have a fixed number of bits

unsigned 8 bit can represent 256 different possibilities

Binary Addition

We want to add, subtract, multiply and divide

we will implement multiplication and division in software

machine add binary with carry numbers

for overflows we ignore the most significant carry number

is not true integer addition, but module (2^wordsize)

half adder takes in a, b and outputs sum and carry

full adder takes in a, b, c and outputs sum and carry

add multiple bits with full adders and a half adder at last step

Negative numbers

We give up half of our possibilities for negative values

Could use the most significant digit as negative signal, but have repetitive zeros and makes manipulation difficult

two’s complement the most significant position is negative

pos number range: 0.. 2^(2-1) -1

neg number range: -1 .. -2^(n-1)

This gives us addition and subtraction for free

If we can get number negation (pos to negative) we get subtraction

2^n – x = 1 + ((2^n) -1) – x

e.g. (11111 – 10101) + 1

ALU (Arithmetic Logic Unit)

computes a function on two inputs

we will take in x (16 bits), y (16 bit), and the following:

zx: if zx then x = 0

nx: if nx then x = !x

zy: if zy then y = 0

ny: if ny then y = !y

f: if f then out = x+y else x&y

no: if no then out = !out

output: out, zr, ng

Project 2

Half-Adder: sum can be implemented with XOR and carry with AND

Full-Adder: can be built from two half-adders

16-bit adder: n full-address chips. carry bit is piped from right to left. drop most significant carry

16-bit Incrementor

ALU: build with 16 bit adders. can do with less than 20 lines in HDL

Perspectives

Are these chips standard? most, but not the ALU. simplified.

How come ALU doesn’t have more operations? Opted for simplicity. can implement in software.

Are these efficient? Most are except the adder. made up of multiple full-adders and needs to iterate over them for the carry. Can use carry look ahead to optimize.

Why is it recommended to use built-in chips? Local failures. So we know mistakes are only from the current project. unit testing. focus on just the interface.