#
CMU 15-110: Principles of Computing

How a Computer Works, Part 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 (Disjunctive Normal Form)**Use Circuits (Logic) to Compute Arithmetic****Use Circuits to Store Values (Memory!)****Summary**

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

**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"} ] }

- Given a Truth Table (that represents a Boolean Logical Function)
**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:**

- Any logical function can be written in Disjunctive Normal Form (DNF).
- DNF only uses
`And`

,`Or`

, and`Not`

. - So, critically, given an arbitrary logical function,
we only need
`And`

,`Or`

, and`Not`

to build a machine that computes it. Awesome!

**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.

**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"} ] }

**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)