Boolean Functions and Gate Logic – Nand2Tetris (Week 1)

  1. Boolean Logic
    • 0/1, True/False, On/Off, Yes/No, Positive/Negative
    • AND, OR, NOT are simple operators
    • We can combine e.g. NOT(0 OR (1 AND 1))
    • They can be generalized e.g. f(x,y,z) = (x AND y) OR (NOT(x) AND z)
    • All combos can be expressed as a truth table
    • Can follow communicative, associative and distributive laws
      • communicative: (x AND y) = (y AND x)
      • associative: (x AND (y AND z)) = ((x AND y) AND z)
      • distributive: (x AND (y OR z)) = (x AND y) OR (x AND z)
      • De Morgan’s Law: NOT(x AND y) = NOT(x) OR NOT(y)
  2. Boolean Functions Synthesis
    • Can compose from truth tables
    • Construct functions by going line by line of a truth table and tacking on an OR
    • NAND function can represent AND, NOT, and OR
    • NAND is negation of x and y. outputs 0 if x and y = 1 else 1.
    • NOT(x) = (x NAND x) // 0 input will always be 1 and 1 input will always be 0
    • (x AND y) = NOT(x NAND y) // 1 only if x and y are 1
  3. Logic Gates
    • chips can be thought of as simple logic gates
    • can combine to build other logic gates
    • interface is abstraction that describes what it’s doing
    • there should only be 1 abstraction/interface, but can be multiple implementations
  4. Hardware Description Language (HDL)
    • language for specifying these logic gates
    • Interface will be something like “IN a, b” and “OUT out”
    • Implementation will be statements such as “Not(in=a, out=nota)” (describe intermediary connections with names)
    • Some common HDLs in industry: VHDL and Verilog
  5. Hardware Simulation
    • included with class
    • can run interactive or systematic tests
    • compare files can be used to compare output and test for accuracy
    • compare files can be created with high level language
    • Typically designer (teacher) decides what sub-chips required and API and the developers (students in this course) will implement
  6. Multi-Bit Buses
    • A bunch of bits can be described as a bus
    • described with e.g. A[16], a[0..7] = lsb
    • buses are indexed right to left
    • In a 16 bit bus, A[0] is right most bit and a[15] is left-most or most-significant bit
  7. Project 1 Overview
    • Start with NAND which will be given and will build a computer
    • Will start with 15 gates
    • Multiplexor: takes in 3 inputs a,b,sel and 1 output (out). out is a if sel == 0 else b
    • Demultiplexor: takes in a input, sel and outputs to a or b based on sel
    • practical application of multiplexor and demultiplexor is sending 2 groups of data in one stream over a network and splitting out at the end
    • Try to build chips in order
    • You can design helper chips like methods, but shouldn’t need to and is discouraged
    • Use as few parts as possible
  8. Perspective (FAQs)
    • Can you start with something other than NAND? You can use NOR or AND, NOT, OR, but NAND is popular bc cheap to build and used a lot already
    • How are NAND gates implemented? We try to stay away bc more physics and electrical engineering than CS. One example is a positive and negative charge between an output and two transistors. If the input a and b are active, the negative charge becomes output. A bit outdated, many implementations. (+) (output) (a) (b) (-)
    • How does the HDL we use compare to ones used in industry? Simpler, but is all we need to build our computers or any computer. Others are more advanced, but more complex.
    • How do you design complex chips? Some optimizers, but not perfect algorithm. NP complete problem. Like any software. modularity and abstraction. easier to optimize simpler components.