CMU 15-110: Principles of Computing
Computer Systems 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
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
   
   • Q: How many different kinds of gates do we need so that we can compute every possible Boolean logical function?
   • A: We only need And, Or, and Not gates to compute any logical function!
     Aside: In the Optional/Advanced material, we will use Disjunctive Normal Form (DNF) to prove this.


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. We will explore more complicated arithmetic (Full Adders, etc) in the Optional/Advanced material.


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"} ] }
     
     
     • Volatile vs non-volatile
       Since this circuit requires electricity to maintain its memory, it is volatile -- turning off the computer loses the memory. There are other forms of non-volatile memory, such as hard drives, flash drives, SSD's, magnetic tapes, and so on.


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!