Limitations on Computing

CS 441 Lecture, Dr. Lawlor

First, some more review: flip-flops.  It's just a two inverters in series, looped back on the other one, so it has two stable states: one inverter outputting true, or the other outputting true.
flipflop from not gates
Of course, it's handy to be able to write values into a flip flop, so a "RS" (Reset and Set) flip-flop is made from NOR gates.  (Click for the TkGate source file.)
flip flop from NOR gates
If both switches are off, the flip-flop just remembers its previous value.  If you turn on the left switch, "Reset", it makes the middle wire go high and the right wire go low, storing a zero.  If you turn on the right switch, "Set", it makes the wrap-around wire go low and the middle wire high, storing a one.
Often you want a "data" input, so you decode data and a write enable line typically called "clock" to make the set and reset lines above:
data flipflop, with decode lines

Flipflops are normally drawn with the two NOR gates' wires crossed, which looks a little more symmetrical but substantially more confusing (to me).  This is the same circuit:
D flip flop in typical style

These flip-flops can be replicated one after another to store an arbitrary number of bits.  A collection of bits that can be read or written together is a "register".  A collection of registers is called a "register file".

Analog Circuit Limitations

There are a surprising number of underlying analog problems with real circuits.  For example, as a digitial circuit, this is an oscillator:
digital oscillator
But if you actually build it, this doesn't oscillate between true (3.3v) and false (0v), it get stuck around 1.1v!

The problem is that both underlying FET gates tend to get stuck halfway on, averaging out the supply voltage, and this input leaves the FET gates stuck halfway on.
FET inverter
So there is a stable state in the analog circuit not found in the digital circuit.

Similarly, analog problems are recurring in semiconductor fabrication.  For example, due to electron quantum tunneling, for 45nm chips Intel had to switch out the silicon FET gate material for a hafnium FET gate insulator.  We're now at 32nm chips.  One silicon atom is 0.1nm, so our transistors are already only a few hundred atoms across!

One of the biggest analog problems chip designers have faced for decades is time.  It takes about 0.1ns for a modern FET gate to switch.  So each logic gate that a signal passes through slows it down by 0.1ns, so complex circuits with dozens of gates in the critical path may take over a nanosecond to propagate through, cutting the circuit's clock speed to below a gigahertz (clock frequency==1.0/maximum propagation delay).  So, for example, typical CPU designs do not have thousands of registers--it would be easy to fit them all on a chip, but the ten-layer deep selection logic would have too big an impact on the CPU's clock speed!