Comp 200 Lecture
circuits

00.Mar.22-29

Reading: finish chpt 6 (measuring algorithms).


Big picture: we want to show how each Jelly instruction
can be implemented by a machine.


Circuits:

  We use wires which are on/off, 1/0, true/false, +5V/+0V, whatever 
    (The use of binary values is convenient in engineering,
     not critical in computation.)

  AND/OR/NOT; their truth tables 
    [draw the gate next to the table, with the wires labeled]
    [For continuity, put Scheme notation for and/or/not on the table.]
    [write "AND" and "OR" inside the gates, for the first day]

  Remember, a OR b means "inclusive-or": a or b or both.
  (In english, "or" sometimes means inclusive, sometimes exclusive.)
  [N.B. we'll use all-caps as the names of these gates, as opoposed to
  the english or scheme word "or".] 

Now let's build bigger circuits out of these smaller, given circuits:

a -----\
        OR----\
b --+--/      |
    |         \--\
    |             AND----
    \--NOT-------/

Note the dot ("+") to indicate that we've soldered two wires together.
What does this circuit yield, for a=1, b=0?   For 0,0?
   (Propogate the values throuth, to see.)
   (This circuit isn't too interesting: it's "a and not b";
     we could actually get by without its OR gate.)


Now let's *design* some circuits:

  all3
     "A circuit with three inputs, and an output is on if all inputs are on"
     Phrase this in english, using just and/or/not (no "all").
     Draw the circuit
     Trace through a few cases by hand.
     Note that we can box this up: conceptually, this is a new
     circuit (gate) with three inputs, and a more complicated output.

  Problem to work on write now, for 2min:
    Design a circuit "atleast-1-of-3", with three inputs, the output
    is on if atleast one of the inputs is on.
    (This is as easy as previous example.)
    Remember, phrase the circuit using english words and/or/not, 
    instead of things like "at least".

    Trace through a couple of sample inputs, to satisfy yourself this works.


  atleast-2-of-3?
     phrase this in english, using just and/or/not, and all3:
     "(a and b), or (a and c), or (b and c)"
     (or (and a b) (or (and a c) (and b c)))
     write truth-table, or trace through a few cases by hand.

   If we have three input wires, how many possible input-combinations
   are there?  (e.g.,  1/0/1 is one input-combo.)
   Write the truth-table for all3; for atleast-2-of-3.


--------
00.mar.24 (fri)


  Revisiting atleast-2-of-3:
    There are different phrasings, which lead to different (but equivalent)
    circuits:   "(a and (b or c)), or (b and c)"
    How can we check that this is correct? 
    If nothing else, try all possible inputs.
    Essentially, we're saying "compare the truth tables".

  Note that if nothing else, if i give you a truth table, you
  can make a (possibly large, bulky) circuit for it.  How?
  (If you take Elec326, you'll learn methodologies for 
   writing such circuits and minimizing them.)



  Working with a neighbor, build circuit exactly-2-of-3.
    Remember: Phrase in english, *using previous circuits*!
    One possible answer: "atleast-2-of-3, and not all3"

  Working with a neighbor, how would you write "exactly-1-of-3"?
    Remember: Phrase in english, *using previous circuits*!
    One possible answer: 
      "atleast-1, and not atleast-2-of-3, and not all3".
      question: don't we also need "and not none-of-three"?
         We *could* include that caveat; 
         note that "none-of-three" is "not atleast-1-of-3",
         which would make our phrasing include 
            "atleast-1-of-3 and not (not atleast-1-of-3)"
         which is redundant.  So no need to add the redundancy.
      In fact, look more closely at our proposed
      "atleast-1, and not atleast-2-of-3, *and* not all3".
      the "and not all3" is redundant after the "not atleast-2-of-3":
      if there aren't at least 2 of 3, then there can't be all3.
      (This is because we are connecting them with "and".)
      ** Thus, a simpler final answer:
      "atleast-1, and not atleast-2-of-3".

------------
00.mar.27 (mon)

  Review of elementary-school addition, but easier: just use binary.

  1-bit adder
     Two input binary digits, a carry-in;    an output digit and a carry-out.
     The carry digit: atleast-2-of-3
     The output digit: exactly-1-of-3 or all3 inputs on.
  Write an 8-bit adder

  In general you could worry about minimizing gates, and time-delay.
  Take elec 326 :-)


  Note that when doing base-10 addition in elementary school:
    We have to just plum memorize all the single-digit sums in a table.
    Then we learn a (more interesting) algo. involving columns, carries, etc
    to do arbitrary addition.
      Here, we are essentially having circuits encoding the table 
      (exactly-1-of-3, atleast-2-of-3 each a 2x2 table; 
      for decimal we'd have to make a bigger 10x10 table.)
      Linking together the circuits would still be the same in base 10.


  Okay, this explains how a machine can do addition.
  But there were two more things that Jelly2000 can do: 
    "if", "load/store memory"
  These are developed a bit on the homework.


--------------
00.mar.29 (wed)

  And also, there is memory itself:
  How can we retain information?
  A circuit to do so can't just flow left-to-right, as everything has so far.
  Instead, we'll use feedback: two cross-coupled NOR gates:
R___________
      _____ OR--NOT-------+--------q
     /                    |
    |     _______________/
    |    /               
     \--+-----------------\
         \                | qBar
S_________OR---NOT--------/

     We'll name the inputs R,S;   we also have wires q and qBar.
     An "R-S flip-flop".
       'R-S' stands for 'reset-set': 
       we can 'reset' the circuit to 0, or 'set' it to 1.

     The intent: R and S are usually 0;
     q will be the remembered output; qBar will end up being q's complement

     To figure out what's happening here,
     we need names for what things are like in one moment.
     Let "q'","qBar'" refer to the value of the wires "q","qBar" a moment later.


    R  S    q qBar | q'  qBar'
   ----------------+-----------
    0  0    0  1   |  0  1       (no change)
    0  0    1  0   |  1  0       (no change)
    1  0  any any  |  0  1       (reset)
    0  1  any any  |  1  0       (set)
    1  1  any any  |  0  0       leads to ...
    0  0    0  0   |  1  1       leads to ...
    0  0    1  1   |  1  1       leads to previous line  Uh-oh!
                                 We'd better not ever have both R/S be on!

  The upshot is, we can use R and S to "store" a 0 or 1;
  from then on the value is remembered (by q) until R or S changes.

  Note that if R and S are both 1, the circuit enters an unstable state.
  We don't want this to happen.
  What if it did? Well, it would eventually settle into one a stable
  state, but *which* stable state depends on whether one wire is a teensy bit
  shorter than another, etc.
  
  (If this circuit were to control, say, a traffic light,
   and a lightning-zap scrambles voltages levels on wires,
   we could enter such an unstable state.
   A good design would ensure that it finds its way back to all-red.
   (rather than all-green).  This is called "fail-safe".)


  So this "R-S flipflop" stores one (binary) digit of memory.
  To store eight digits, we'd just use eight of them, and eight output wires.
  (A single R/S input wire would control all eight flipflops.)
 

  Now you can use, say, 32 copies of this to make a memory of size 100000 (base 2).
  How do we look thing up in memory?
      Input: 5 address-wires (location 00000 to 11111).
      Output: 8 digits.
  A homework problem suggests how you can translate some address wires
  to select *which* of the flip-flops to use on the output.
  (The homework problem uses a memory of size 4, not 32, but same idea.)

                                     /
  Consider:                     ----/  ------LoadInputNow
                                |
                                |
                                |
                                |
         /                                -------
 in1 ---/  -------                     ---|S   q|----
                                          |     |
                                       ---|R    |    
                                          -------

         /                                -------
 in2 ---/  -------                     ---|S   q|----
                                          |     |
                                       ---|R    |    
                                          -------
  Exercise: hook these up so that if i press the switch "LoadInputNow",
  then the two RS flipflops will capture the setting of the switches on
  the left.  (If "LoadInputNow" is not pressed, then the RS flipflops just
  store the previous setting, ignoring the current value of the inputs.)
  Remember, if an input is "0", we also want to capture that in the flipflop.

  Answer [don't peek til you've tried!]:
    (1ni woNtupnIlaol dna) si S ot tupni;
    ((1ni ton) woNtupnIlaol dna) si R ot tupni;

  Originally, electronic computers were indeed programmed with switches
  on the front, and a circuit like this did load values into memory.
  Note also: the RS flip-flops might be the ACCumulator,
    in1/in2 might be signals coming out of the memory unit, and we want
    the "LoadInputNow" wire to correspond to the instruction being "ld".
    How to do that?


Circuits to decode and execute assembly instructions:
  Note that in Jelly2000, an memory location is just
  a bunch of these RS flip-flops (an 8-bit number would be 8 flip-flops).
  Similarly, the ACC and PC are just a row of flip-flops.
  Recall the assembly instruction "(bez addr)": 
  If the ACC = 0, then put addr into the PC.
  Could you write a circuit whose input was the eight bits of the ACC, 
    and told whether or not it was 0?
  Could you write a circuit whose input was an encoded assembly instruction,
    and told whether or not it was the bez instruction?
  Could you write a circuit whose input included 
     (a) a wire indicating whether the current instruction is bez,
     (b) a wire indicating whether or not the ACC is currently 0,
  whose output is "hey-PC-load-input-now"?
  Note that the PC would also have as in1,in2,... the part
  of the current assembly instruction comprising the addr.



  By the way: there are other ways to store info.
  This way is nice because it meshes with the rest of Jelly circuits.
  But you can use magnetic tape, bubble memory, iron cores, ...




Implementation of AND/OR/NOT
  (aka, how does your toilet flush?)
  
  -Electrical implementation:
      The inputs control switches:  an "on" input closes the switch.
      (This could be a wire around a coil, which pulls the switch closed.)
  AND: two switches in a row
  OR:  two switches in parallel
  NOT: A bit tougher.
       A power source connected to the output,
       but the switch connects it to ground (via resistor).

  Water implementation of and/or/not (toilets)
  OR:  pour inputs into a single bucket (which might overflow)
--------
99.apr.16 (fri)
  AND: pour inputs into a intermediate-bucket whose overflow (if any) will
       go into the answer-bucket
  NOT: we'll use a siphon on this one.
       Do you know how a toilet works?
       The answer-bucket starts *full*; it has a gooseneck tube
       connected at the bottom, whose gooseneck is just above the top.
       - if empty input, the bucket just stays full; no siphon.
       - if full input, the gooseneck is filled and siphon starts.


Levels of abstraction:
transistor
gate
small circuit (+, if, memory)
CPU
Jam machine code
Jam assembly code
C
  (operating systems)
  (window managers)
Scheme
applications

We have zoomed to the other end, from high-level computation.
Note that Scheme == Jelly2000, as far as power goes.
(Church-Turing thesis: all formalizations of "computation" are
equivalently powerful)
Also, for primitive building blocks: NOR would suffice(!)





A History of computing hardware:
1614 - Napier (logarithm tables)
1622 - first slide rule
1642 - Pascaline (add, subtract)
1694: leibniz's wheel (add, subtract, mult, divide)

1801: joseph jacqard's loom
      program was a sequence of punched cards
      luddites (1811)
1822: charles babbage
      difference-engine: 6-digit arith; some poly eq'ns, etc.
      he had plans for a 20-digit machine.
      Analytic engine: plans for a steam-powered machine.
      Countess Ada Lovelace (daughter of byron) made the instruction set

1880: census took 8yrs to tabluate; a reward offered for a better way.
      Hollerith put data on punch cards.  Had a tabulator, and a sorter.
1890: census took 2 years
1902: he formed "computing-tabluating-recording company",
      which renamed itself to IBM.
      [draw pict of measuring the punch-cards:
       the card is over a tray of mercury (which conducts electricity);
       needles lowered over every potential-punch;
       if the needle touches the mercury it advances a counter (ka-ching!)
       

1931-44: Mark I: binary (using vacuum tubes) and mechanical relays
        72 numbers of memory; 23-digit numbers multiplied in 4sec.
        Used for 15yrs.
1943-6  ENIAC ("electrical numerical integrator and calculator")
        Needed for war dept's gunnery tables.
        18,000 tubes.  A room 100' x 10'   30 tons
        programmed by 6000 switches
Others: ABC (U-Iowa 39-42 (first)), Colossus, Z1
1946 :   Von Neumann suggested program in memory