Boolean Arithmetic and the ALU – Nand2Tetris (Week 2)

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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.