CMU 15110: Principles of Computing
Computer Systems 1: Gates and Circuits
 Circuit Simulator
 Start with a Bucket of Sand!
 Use Sand (Silicon) to Make Transistors to Make Logic Gates
 Combine Gates to Make Circuits
 Use Circuits to Compute Logic (Boolean Logical Functions)
 Only Need
And
, Or
, and Not
Gates
 Use Circuits (Logic) to Compute Arithmetic
 Use Circuits to Store Values (Memory!)
 Summary
 Circuit Simulator
 Start with a Bucket of Sand!
 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...
 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"}
]
}
 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"}
]
}
 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.
 Use Circuits (Logic) to Compute Arithmetic
Here we will just do 1bit 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, 1bit 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 twobit sum.
We will explore more complicated arithmetic (Full Adders, etc)
in the Optional/Advanced material.
 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 AndOr Latch (or FlipFlop)
There are many ways to solve this. We will use perhaps
the easiest approach: an SR AndOr Latch (or FlipFlop).
 What's in the name?
The "SR" is for "SetReset", which are the two
inputs to the circuit. The "AndOr" is there because
it uses an And
and an Or
gate
(it also uses a Not
gate).
The term "Latch", or "FlipFlop", 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 nonvolatile
Since this circuit requires electricity to maintain its memory,
it is volatile  turning off the computer loses the memory.
There are other forms of nonvolatile memory, such as hard
drives, flash drives, SSD's, magnetic tapes, and so on.
 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!