CMU 15-110: Principles of Computing
How a Computer Works, Part 1:
Gates and Circuits

0. Circuit Simulator
1. Start with a Bucket of Sand!
2. Use Sand (Silicon) to Make Transistors to Make Logic Gates
3. Combine Gates to Make Circuits
4. Use Circuits to Compute Logic (Boolean Logical Functions)
5. Only Need And, Or, and Not Gates (Disjunctive Normal Form)
6. Use Circuits (Logic) to Compute Arithmetic
7. Use Circuits to Store Values (Memory!)
8. Summary

0. Circuit Simulator
   • Try out this circuit simulator.
   • Note: that circuit simulator, and all the circuit simulators on this page, are derived from SimcirJS.


1. Start with a Bucket of Sand!
   


2. Use Sand (Silicon) to Make Transistors to Make Logic Gates
   
   • Note: all the circuits here are interactive. Try them!
   
   
   • And Gate
     { "width":200, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":16,"label":"x","state":{"on":false}}, {"type":"Input","id":"dev1","x":16,"y":72,"label":"y","state":{"on":false}}, {"type":"AND","id":"dev2","x":80,"y":40,"label":"AND"}, {"type":"Output","id":"dev3","x":144,"y":40,"label":"Output"} ], "connectors":[ {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev2.in1","to":"dev1.out0"}, {"from":"dev3.in0","to":"dev2.out0"} ] } x y x and y - - ------- 0 0 0 0 1 0 1 0 0 1 1 1
   
   
   • Or Gate
     { "width":200, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":16,"label":"x","state":{"on":false}}, {"type":"Input","id":"dev1","x":16,"y":72,"label":"y","state":{"on":false}}, {"type":"OR","id":"dev2","x":80,"y":40,"label":"OR"}, {"type":"Output","id":"dev3","x":144,"y":40,"label":"Output"} ], "connectors":[ {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev2.in1","to":"dev1.out0"}, {"from":"dev3.in0","to":"dev2.out0"} ] } x y x or y - - ------- 0 0 0 0 1 1 1 0 1 1 1 1
   
   
   • Not Gate
     { "width":200, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"NOT","id":"dev0","x":80,"y":40,"label":"NOT"}, {"type":"Output","id":"dev1","x":144,"y":40,"label":"Output"}, {"type":"Input","id":"dev2","x":16,"y":40,"label":"x","state":{"on":false}} ], "connectors":[ {"from":"dev0.in0","to":"dev2.out0"}, {"from":"dev1.in0","to":"dev0.out0"} ] } x not x - ----- 0 1 1 0
   
   
   • Xor Gate
     { "width":200, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":16,"label":"x","state":{"on":false}}, {"type":"Input","id":"dev1","x":16,"y":72,"label":"y","state":{"on":false}}, {"type":"XOR","id":"dev2","x":80,"y":40,"label":"XOR"}, {"type":"Output","id":"dev3","x":144,"y":40,"label":"Output"} ], "connectors":[ {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev2.in1","to":"dev1.out0"}, {"from":"dev3.in0","to":"dev2.out0"} ] } x y x xor y - - -------- 0 0 0 0 1 1 1 0 1 1 1 0
   
   
   • Many Other Gates
     There are many other kinds of gates. You get the idea...


3. Combine Gates to Make Circuits
   For example, this circuit uses 2 gates (a Not gate and an Or gate):
   { "width":300, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":72,"label":"y","state":{"on":false}}, {"type":"NOT","id":"dev1","x":88,"y":72,"label":"NOT"}, {"type":"Output","id":"dev2","x":248,"y":24,"label":"Output"}, {"type":"Input","id":"dev3","x":16,"y":16,"label":"x","state":{"on":false}}, {"type":"OR","id":"dev4","x":168,"y":24,"label":"OR"} ], "connectors":[ {"from":"dev1.in0","to":"dev0.out0"}, {"from":"dev2.in0","to":"dev4.out0"}, {"from":"dev4.in0","to":"dev3.out0"}, {"from":"dev4.in1","to":"dev1.out0"} ] }


4. Use Circuits to Compute Logic (Boolean Logical Functions)
   
   • Given a Truth Table (that represents a Boolean Logical Function)
     x y f(x,y) - - ------ 0 0 1 0 1 1 1 0 0 1 1 1
   
   
   • We can build a circuit that computes that function:
     { "width":300, "height":125, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":72,"label":"y","state":{"on":false}}, {"type":"Input","id":"dev1","x":16,"y":16,"label":"x","state":{"on":false}}, {"type":"NOT","id":"dev2","x":88,"y":16,"label":"NOT"}, {"type":"OR","id":"dev3","x":168,"y":40,"label":"OR"}, {"type":"Output","id":"dev4","x":248,"y":40,"label":"Output"} ], "connectors":[ {"from":"dev2.in0","to":"dev1.out0"}, {"from":"dev3.in0","to":"dev2.out0"}, {"from":"dev3.in1","to":"dev0.out0"}, {"from":"dev4.in0","to":"dev3.out0"} ] }


5. Only Need And, Or, and Not Gates (Disjunctive Normal Form)
   
   • The issue
     Q: how do we know that we have enough different kinds of gates so that we can compute every possible Boolean logical function?
     A: We will use Disjunctive Normal Form (DNF) to show that we only need And, Or, and Not gates!
   
   
   • Start with any function
     We will use Xor as our example, but this works for any function:
     x y f(x,y) - - ------ 0 0 0 0 1 1 1 0 1 1 1 0
   
   
   • Add the row selector functions
     We add a few extra functions, each of which is only true for a single row. We are calling these row selectors:
     (not x) (not x) x x and and and and x y f(x,y) (not y) y (not y) y - - ------ ------- ------- ------- --- 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1
   
   
   • Note that row selectors only use And and Not
     This is important!
   
   
   • Highlight Row Selectors for rows where f(x,y) is 1
     (not x) (not x) x x and and and and x y f(x,y) (not y) y (not y) y - - ------ ------- ------- ------- --- 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1
   
   
   • We can make a function identical to f(xy) by Or'ing the highlighted row selector functions
     x y f(x,y) ((not x) and y) or (x and (not y)) - - ------ ---------------------------------- 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0
     
     Let's see this in action. Verify that the circuit below matches the function on the right in the table above. Then, try all the possible input combinations to verify that it works just like Xor.
     { "width":325, "height":150, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":8,"label":"x","state":{"on":false}}, {"type":"Input","id":"dev1","x":16,"y":96,"label":"y","state":{"on":false}}, {"type":"NOT","id":"dev2","x":96,"y":96,"label":"NOT"}, {"type":"NOT","id":"dev3","x":96,"y":8,"label":"NOT"}, {"type":"AND","id":"dev4","x":152,"y":24,"label":"AND"}, {"type":"AND","id":"dev5","x":152,"y":80,"label":"AND"}, {"type":"OR","id":"dev6","x":216,"y":48,"label":"OR"}, {"type":"Output","id":"dev7","x":272,"y":48,"label":"Output"} ], "connectors":[ {"from":"dev2.in0","to":"dev1.out0"}, {"from":"dev3.in0","to":"dev0.out0"}, {"from":"dev4.in0","to":"dev3.out0"}, {"from":"dev4.in1","to":"dev1.out0"}, {"from":"dev5.in0","to":"dev0.out0"}, {"from":"dev5.in1","to":"dev2.out0"}, {"from":"dev6.in0","to":"dev4.out0"}, {"from":"dev6.in1","to":"dev5.out0"}, {"from":"dev7.in0","to":"dev6.out0"} ] }
   
   
   • The last column of that truth table is in Disjunctive Normal Form (DNF)
     The last column we made, which combined row selectors, is in Disjunctive Normal Form (DNF)! Remember that row selectors only used And and Not. Here, we used Or to combine row selectors. So, DNF only uses And, Or, and Not.
   
   
   • In summary:
     
     1. Any logical function can be written in Disjunctive Normal Form (DNF).
     2. DNF only uses And, Or, and Not.
     3. So, critically, given an arbitrary logical function, we only need And, Or, and Not to build a machine that computes it. Awesome!


6. Use Circuits (Logic) to Compute Arithmetic
   Here we will just do 1-bit addition, to give you an idea of how we can use logic to compute arithmetic.
   • The issue:
     We want someting like a logic circuit, but instead of computing (x and y) or (x or y), we want to compute (x + y). That is, 1-bit addition. So we want something like this:
     x y x+y - - ---- 0 0 00 0 1 01 1 0 01 1 1 10
   
   
   • The solution:
     Treat each bit of the output as its own logical function. Look at this again:
     x y x+y - - ---- 0 0 00 0 1 01 1 0 01 1 1 10
     Look closely and verify that the red function is (x and y) and the blue function is (x xor y).
   
   
   • A working example:
     Verify that the following circuit uses And and Xor as just described, and that it adds x and y properly:
     { "width":325, "height":225, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":8,"label":"x","state":{"on":false}}, {"type":"NOT","id":"dev1","x":96,"y":96,"label":"NOT"}, {"type":"NOT","id":"dev2","x":96,"y":8,"label":"NOT"}, {"type":"AND","id":"dev3","x":152,"y":24,"label":"AND"}, {"type":"AND","id":"dev4","x":152,"y":80,"label":"AND"}, {"type":"OR","id":"dev5","x":216,"y":48,"label":"OR"}, {"type":"Output","id":"dev6","x":248,"y":160,"label":"Output"}, {"type":"Input","id":"dev7","x":16,"y":80,"label":"y","state":{"on":false}}, {"type":"Output","id":"dev8","x":208,"y":160,"label":"Output"}, {"type":"AND","id":"dev9","x":96,"y":160,"label":"AND"} ], "connectors":[ {"from":"dev1.in0","to":"dev7.out0"}, {"from":"dev2.in0","to":"dev0.out0"}, {"from":"dev3.in0","to":"dev2.out0"}, {"from":"dev3.in1","to":"dev7.out0"}, {"from":"dev4.in0","to":"dev0.out0"}, {"from":"dev4.in1","to":"dev1.out0"}, {"from":"dev5.in0","to":"dev3.out0"}, {"from":"dev5.in1","to":"dev4.out0"}, {"from":"dev6.in0","to":"dev5.out0"}, {"from":"dev8.in0","to":"dev9.out0"}, {"from":"dev9.in0","to":"dev0.out0"}, {"from":"dev9.in1","to":"dev7.out0"} ] }
   
   
   • Adding more than 1 bit
     The circuit we just made is called a Half Adder. It takes two single bits of input, and outputs their two-bit sum. If you are interested in learning how computers do arithmetic over larger numbers, read about Full Adders and how they can be combined to add larger numbers here.


7. Use Circuits to Store Values (Memory!)
   
   • The issue:
     We want to store values in memory. That is, we want a way to set a bit to 1, and reset it to 0, and for that bit to remain in that state until we change it.
   
   
   • The approach:
     We will create a circuit that includes a feedback loop. That is, the output of the circuit (the state of the memory) will also be an input into the circuit. That way, its next state will depend on its previous state.
   
   
   • The SR And-Or Latch (or Flip-Flop)
     There are many ways to solve this. We will use perhaps the easiest approach: an SR And-Or Latch (or Flip-Flop).
     • What's in the name?
       The "SR" is for "Set-Reset", which are the two inputs to the circuit. The "And-Or" is there because it uses an And and an Or gate (it also uses a Not gate). The term "Latch", or "Flip-Flop", basically means it is storing one bit of data, which is the output of the circuit.
     
     
     • How it works
       Press the S input twice to set the memory to 1. Press the R input twice to reset the memory to 0. Generally, neither input should be on unless you are actively setting or resetting the memory. And it should never happen that both inputs are on at the same time.
     
     
     • A Working Example
       { "width":275, "height":130, "showToolbox":false, "toolbox":[ {"type":"Input"}, {"type":"Output"}, {"type":"AND"}, {"type":"OR"}, {"type":"NOT"}, {"type":"NAND"}, {"type":"NOR"}, {"type":"XOR"} ], "devices":[ {"type":"Input","id":"dev0","x":16,"y":80,"label":"Reset (R)","state":{"on":false}}, {"type":"NOT","id":"dev1","x":72,"y":80,"label":"NOT"}, {"type":"Input","id":"dev2","x":16,"y":24,"label":"Set (S)","state":{"on":false}}, {"type":"OR","id":"dev3","x":104,"y":8,"label":"OR"}, {"type":"AND","id":"dev4","x":152,"y":72,"label":"AND"}, {"type":"Output","id":"dev5","x":224,"y":72,"label":"Output"} ], "connectors":[ {"from":"dev1.in0","to":"dev0.out0"}, {"from":"dev3.in0","to":"dev4.out0"}, {"from":"dev3.in1","to":"dev2.out0"}, {"from":"dev4.in0","to":"dev3.out0"}, {"from":"dev4.in1","to":"dev1.out0"}, {"from":"dev5.in0","to":"dev4.out0"} ] }


8. Summary
   We have not yet built a computer, but we have made great progress! Starting from a bucket of sand (silicon), we made logical gates, then we used those gates to build circuits, and then we used those circuits to:
   • Compute logic
   • Compute arithmetic, and
   • Store values (memory)
   We have more work to do, but this is a fine start!