CS 240 Lab 1: Transistors to Gates
Peter Mawhorter
Outline
Land Acknowledgement
This campus where we’ll be working this semester was historically stewarded by the Nipmuc people, with Wapmanoag and Massachusett people also living in nearby areas. They are no longer the stewards of this land because it was stolen from them, and it’s important that we acknowledge that fact as we start to use this space. These people are still here, you can find their websites and some of them attend Wellesley.
Course Structure
Important Policies
- No food or drink
- You may step out for a snack/sip, and we’ll have a break.
- Masks are expected
- Asymptomatic infections mean that we will very likely have someone who is infectious in lab this semester, and even they won’t know it.
- COVID-19 comes with a significant risk¹ of long-term (presumably permanent) symptoms which interfere with activities of daily living.
- Some students & professors at Wellesley are immunocompromised and cannot receive full protection from vaccines.
1: This risk is hard to quantify, but many studies suggest it is somewhere between 1/1000 and 1/10 (i.e., between 0.1% and 10%). This planned study has a good discussion and citations, in particular, the 4th paragraph of the “expected key results” section. The risk is significantly higher than for the flu.
Course Parameters
- Pre-lab exercises in Gradescope
- Pre-lab exercises are individual
- Review slides & attempt exercises before lab
- Revise exercises after lab
- I will assign different partners each lab
- Let me know if you have preferences
- Grades are self-assigned for each unit based on pre-lab
feedback and per-lab reflections
- I may negotiate your grade if it seems wrong
Partner Work
- Be kind to each other (yes, even when you’re tired)
- Enhance each others’ learning
- You’ve had practice at this
Expectations
- You’re now full-fledged CS majors
- Capable of independent learning
- Will ask questions when you need to
- Will be responsible for meeting deadlines, doing prep work, etc.
- You will succeed and thrive in this class, and you’ll go on to do great things with this knowledge.
Growth Mindset
- When you’re having trouble, identify why and what you need to practice to improve.
- Don’t limit your own potential by buying into the belief that you are either “bad at” or “good at” a subject.
- This class is hard in order to make you grow strong (but hopefully in a gentle way).
Logging In
- Use your Wellesley username/password for Windows
- Use your CS Department username/password for Linux
- Use this form to request an account.
- Pressing F12 right after the numlock light comes on when it boots to get to the boot menu for some machines
Setup
- Find your partner.
- Log in to Windows on at least 1 machine.
- Open up a browser an navigate to the class website’s
lab page.
- Scroll down to find Lab 1
- Open up the learning goals, slides, and notebook
Basic Electronics
What is Electricity?
- Electricity = the movement of electrons in a material
- Movement happens because of extra electrons in one place, or extra “holes” in another place, or both.
- Electrons are so fast. Really, just so fast.
What is Electricity?
- We measure the surplus or deficit of electrons in relative terms
- This is voltage (V, measured in Volts), and is always a difference between two points.
- When unimpeded, the flow of electrons quickly reduces voltage to 0.
- Rate of flow is called current, (I, measured in Amps)
- All materials resist the flow of electrons
- This is called resistance (R, measured in Ohms = Ω)
What is Electricity?
- Materials that have low resistance are called “conductors”.
- The resistance of a copper wire is basically 0 (it’s around 1 Ω per 1000 feet of wire, depending a bit on thickness).
- We use resistors with specific Ohm ratings to create resistance in our circuits, often ~1.8 kΩ.
- Your body has a resistance value anywhere from 300-100,000 Ω
- Air has resistance of 1.3-3.3×10¹⁶ Ω (until about 21 kV/cm)
Ohm’s Law
V=I×R
Voltage (V) equals current (I) times resistance (R).
- More voltage → more current
- More resistance → less current, since I=VR
- Zero resistance = infinite current (!)
Ohm’s Law
- Conventions are hard to change, current is shown backwards from the flow of electrons (we don’t care).
- For our purposes, an open switch (meaning electricity has to jump across air) has infinite resistance: no current flows.
- We also don’t care about the resistance of our wires, they are effectively 0.
- A “short circuit” means a circuit with negligible resistance. Current becomes very high, until the circuit destroys itself.
Digital vs. Analog
Analog
Analog circuits like antennas or speakers have a complex balance of resistance, current, and voltage, which varies over time.Digital
We will study digital circuits, which have defined “high” and “low” voltage values; the exact numbers don’t matter so much.Digital vs. Analog
- A typical digital circuit uses just 5 volts, and might define “high” as anything above 3 volts, and “low” as anything below that (more detail).
- Only minimal current may be necessary for the circuit to function, as long as the correct voltage differences can be achieved.
- Using “high” and “low” we can represent True and False, or 1 and 0.
(Once you give a computer scientist a 1 and a 0, it’s game over.)
Prototyping Workbench
A prototyping workbench has places to hold wires and chips so you can put them together easily, with internal horizontal and vertical connections. It also has a power supply and things like switches and LEDs built-in.
This is one of our older model workbenches. The next few slides show which components we’ll be using in this class.
The central white area with lots of small sockets is where we’ll attach chips and wires to build our prototypes. Wire tips and the pins of chips should fit snugly into the sockets.
Smaller socket groups around the edges connect to pre-mounted components.
Internally, each row of 5 sockets is connected horizontally, so that components plugged into the same row are in contact. There are also 12 columns of sockets that aren’t part of the 5-socket rows. Each of these columns has internal vertical connections, so that the entire column is connected.
A few of the relevant connections are shown at left; the same pattern applies throughout.
We have set up small red and black jumper wires to distribute power and ground connections throughout the board from the top strips.
Each pair of vertically-connected columns has +5V on the left and ground on the right. This makes it easy to supply voltage or ground at any point on the board by connecting a horizontal row to one of the nearby vertical rails.
The logic indicators on the upper right can be used to display whether the connected wire has high or low voltage. If the LED is on that means the voltage is high, if it’s off that means low. (The newer models have two LEDS to indicate high/low separately.)
Connecting to either of the two horizontal sockets corresponding to a particular LED will supply voltage to that LED.
The logic switches near the lower left corner of the board can be toggled on or off. When on, they supply +5V power to the two corresponding sockets in the nearby strip. When off, those sockets are disconnected.
This picture doesn’t show it, but in our lab, these are pre-connected to ground through a high-resistance resistor. This means that when the switches are off, they will be low-voltage instead of disconnected.
The push-buttons in the lower left work like switches, except that they bounce back to off when released. When off, the top 4 sockets of the nearby strip are grounded, when on, the bottom 4 are grounded instead.
Not shown here, in our lab one of the top sockets for each button is connected to +5V via a resistor. This means that when the button is pressed, the top 4 sockets will be high-voltage, and when it’s released, they’ll be low.
Transistors
Transistors
To be able to build NOT, AND, and OR gates in a circuit, there has to be a way for voltage or current in one place to manipulate the flow of current or the difference in voltage somewhere else: a switching mechanism.
Early switches were big (vacuum tubes) but transistors represent the culmination of decades of research into making them smaller.
A modern transistor can be as small as 5 nanometers, with 10s of billions packaged on a singe chip.
Transistors
- When voltage is present at the trigger side of a transistor, current may flow through, but if no voltage is present, current may not flow.
- To create a NOT gate, connect input A to the trigger, and output F
to the wire leading into the transistor’s channel. (simulation
link)
- When A is high, the current flows across the transistor, draining away voltage above the transistor.
- When A is low, current cannot pass the transistor, and gets bottled up behind it, creating high voltage at the output.
- Resistors prevent a short circuit in either state.
Building a Gate
- A NOT gate can be built with 2 resistors and 1 transistor:
- Connect one resistor to the top/input leg of the transistor, and then to the +5V rail of the board.
- Connect the same horizontal row that has the resistor and transistor input plugged in to one of the “logic indicator” sockets using a wire. This is the gate output.
- Connect the middle/trigger leg of the transistor to one of the push-buttons (they already have resistors connected, so you get one resistor for free).
- Connect the bottom/output leg of the resistor to the ground rail on the board.
- Double-check your connections, then turn on power to the
board. The logic indicator should read “high.”
- Push the button to change the indicator to “low.”
Integrated Circuits
- Integrated Circuits (i.e., chips) contain transistors in a specific configuration.
- The pinout for a chip specifies the internal wiring. Find them online based on the chip number, or in the TTL Data Book.
- Must be connected to both a voltage source and ground to work.
Integrated Circuits
- Pins are numbered starting with 1 at the top-left and going around counter-clockwise.
- Notch determines the “top.”
- Watch out: the pins are often shown lined up in diagrams, rather than wrapped around the chip.
Thinking Logically
Gates and Truth Tables
- A truth table specifies the high/low or 1/0 combinations for different parts of a digital circuit. (You saw these in CS 111 for Booleans)
- True = 1 and False = 0
- Here, two inputs A and B (called
literals) are shown, along with a function F
of A and B.
What function is this?
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean Algebra
- Before, you might write “
A and B” or “A && B,” now we will write just “AB” for AND and “A+B” for OR.- Basically, AND is multiplication and OR is addition.
- 1×1 is 1, but anything ×0 is 0.
- 0+1=1+0=1+1 (if you can’t go above 1).
- Use ’ for NOT, or write a bar above: A’ or ˉA
Boolean Algebra
- A minterm is an AND of all of the inputs to a function, possibly with NOTs. The four minterms of two inputs A and B are: AB, A’B, AB’, and A’B’.
- A maxterm is an OR of all inputs, possibly
negated. The four maxterms of two inputs A and B are:
A + B, A’ + B, A + B’, and A’ + B’.
Basic Functions
Here are truth tables for NOT, AND, and OR, which you are already familiar with:
| NOT | |
|---|---|
| F = A’ | |
| A | F |
| 0 | 1 |
| 1 | 0 |
| AND | ||
|---|---|---|
| F = AB | ||
| A | B | F |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| OR | ||
|---|---|---|
| F = A + B | ||
| A | B | F |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Basic Functions
Here are truth tables for NAND, NOR, and XOR:
| NAND | ||
|---|---|---|
| F = (AB)’ | ||
| A | B | F |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| NOR | ||
|---|---|---|
| F = (A + B)’ | ||
| A | B | F |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| XOR | ||
|---|---|---|
| F = AB’ + A’B | ||
| A | B | F |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Basic Functions
- Why NAND, NOR, and XOR?
- NAND and NOR are easier to build in a circuit than AND and OR, as we’ll soon see.
- XOR is quite useful in a number of applications, including cryptography.
- As the formulas show, NAND, NOR, and XOR can be built out of AND, OR, and NOT.
- Alternatively, AND and OR can be built from NAND, NOR, and NOT.
Gate Symbols
Aside: Mental Juggling
Aside: truth tables present information clearly, but they’re hard to read, and it’s harder to keep them in your head as you then try to apply them to each other or think through a circuit.
This class will repeatedly strain (and also develop) your ability to mentally juggle multiple steps of translation between different representations and parts of a system.
Aside: Mental Juggling
Use tools to improve your juggling skills:
- Keep references handy, ideally visible without having to even click or turn a page.
- Practice to internalize key info, like the basic truth tables.
- Keep scratch paper or a scratch file handy to write things out when your mental stack is out of space.
Sum-of-Products
- Sum-of-products is a fancy way of saying: read the
truth table and make an AND out of each line where the output is 1, then
OR those together.
- Remember that AND = multiply (i.e., product), and OR = add (i.e., sum).
- Each product is a minterm.
- For this table, there are three 1s for F, with minterms A’B, AB’, and AB, so the sum-of-products form is F = A’B + AB’ + AB.
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Sum-of-Products
- Any boolean function can be expressed as a sum-of-products, which only needs NOT, AND, and OR.
- If we had circuits that could produce these functions, we could put them together to compute anything.
Equivalence
Two functions with the same truth table are equivalent.
| F = A’B’ + A’B | ||||
|---|---|---|---|---|
| A | B | A’B’ | A’B | A’B’ + A’B |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| Q = A’ + A’B + A’B’ | |||||
|---|---|---|---|---|---|
| A | B | A’ | A’B | A’B’ | A’ + A’B + A’B’ |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 |
Equivalence
- Use Boolean algebra to find/prove equivalence.
- Find ways to make the same circuit with fewer or cheaper gates.