Hopefully all the readers here are aware that electrons are the carriers of electricity. Electrons are elementary particles possessing electric charge, and because of this are directed into movement by electric fields (which they themselves also emit).
In uninteresting situations, electrons are attached to nuclei (by mutual attraction due to opposite electric charges) in atoms. Interesting situations are either when the electrons are energetic enough, or when there are so many electrons that the atoms are essentially "full", that they are not held tightly.
In such situations, the electrons will move towards places with fewer electrons. Sources and sinks of electrons can be produced chemically (known as cathodes and anodes), and conductive materials permit easy movement of electrons.
Other materials can interact with the flow of electrons: resistors offer constant impediment to electrical flow; capacitors gather electrons, resisting flow when they are full; inductors resist changes in flow (in either direction).
Background: Circuits chapter from the MIT OpenCourseWare introductory course on electrical engineering and computer science. Read sections 6.1-6.5.
Background: Circuits lesson from Khan Academy course on physics. Activities 1-7 ("Introduction" - "Resistivity").
Background: Basic electronics overview on Makerspace.com.
Semiconductors are the crucial material for development of electronics devices. A semiconductor is a material which resists electrical flow initially, but with a small amount of electrical pressure yields and permits free electrical flow. The amount of electrical pressure required (expressed usually in terms of electrical potential energy, Voltage), is called the band gap.
Semiconductors can be joined to create a transistor; the transistor is a small device with three electrical pins: source, gate, and drain. When the gate has electrical pressure applied, the flow is permitted between the source and the drain; otherwise, it is not.
A brief reminder of the operations of Boolean logic: logical operators NOT, AND, OR. XOR. NAND, NOR.
Boolean logic is a kind of very simple arithmetic in which there are only two values: True (written here 1) and False (written here 0). The most familiar logical operators feature in most languages: NOT, AND, OR.
NOT is a unary operator (single-input), and simply flips it's input: NOT(True) = False and NOT(False) = True. AND is a binary operator (two-input) which evaluates to True if both operands are True, and otherwise evaluates to False. OR is a binary operator which evaluates to True if at least one operand is True, and False if both are False.
Because there are only two values, it is easy to write out all possible values for an expression with multiple variables; these are called truth tables.
Example: expression "X OR Y"
X | Y | X OR Y
--|---|--------
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 1
Exercise: Compute the truth table for NOT:
X | NOT X
--|-------
0 | ?
1 | ?
Exercise: Compute the truth table table for AND.
Exercise: Compute the truth table for exclusive-or, defined by the formula:
XOR(X, Y) = (X OR Y) AND NOT (X AND Y)
Background: Wikipedia article on truth tables.
Since truth tables are relatively easy to write out (for small numbers of variables in an expression), we can prove many formulas just by checking each possible value! This makes Boolean equations much simpler to check than equations of real numbers or integers, where each variable can take infinitely many values, and thus require symbolic manipulations.
Exercise: Prove De Morgan's theorem, NOT(X OR Y) = NOT(X) AND NOT(Y), by completing the table and checking the last two columns are the same.
X | Y | NOT(X OR Y) | NOT(X) AND NOT(Y)
--|---|-------------|-------------------
0 | 0 | ? | ?
1 | 0 | ? | ?
0 | 1 | ? | ?
1 | 1 | ? | ?
NOT(AND(-, -)) and NOT(OR(-, -)) are very common operations (we will see why in a moment), so they are assigned shorthands NAND and NOR:
NAND(X, Y) = NOT(X AND Y)
NOR(X, Y) = NOT(X OR Y)
A very important result is that NAND and NOR are somehow extremely fundamental building blocks: with either of these alone you can generate all other logical operations:
NOT(X) = NAND(1, X)
AND(X, Y) = NOT(NAND(X, Y))
OR(X, Y) = NAND(NOT(X), NOT(Y)))
Notice that to define AND and OR we use NAND and NOT; this is OK, because we already defined NOT in terms of NAND! You can replace NOT with NAND(1, -) if you prefer.
Exercise: using truth tables, check these three equations
Exercise: write similar formulas expressing NOT, AND, and OR in terms of NOR
Exercise: why NOT and OR can't be expressed in terms of AND? Explain.
A n-bit binary number is a list of n boolean values; usually we assign the number a letter name, e.g. X, and each boolean value (called a bit) we label with an integer starting with 0.
Example: a two-bit binary number X is two boolean values X1 X0; the possible two-bit binary numbers are:
X1 | X0 | X
---|----|----
0 | 0 | 00
0 | 1 | 01
1 | 0 | 10
1 | 1 | 11
Example: an eight-bit binary number X is eight bits, X7 X6 X5 X4 X3 X2 X1 X0.
Exercise: Without listing explicitly, how many possible 8-bit binary numbers are there?
Just as each digit in a decimal (usual) integer represents a different power of 10, each bit in a binary number represents a different power of 2. To convert from binary to decimal, simply add up the powers of 2!
Example: Converting the three-bit binary number X = 101 to decimal:
X2 | X1 | X0
---|----|----
1 | 0 | 1
^ ^ ^--------- times 2^0 = 1
| |--------------- times 2^1 = 2
|-------------------- times 2^2 = 4
1 * 2^2 + 0 * 2^1 + 1 * 2^0
= 1 * 4 + 0 * 2 + 1 * 1
= 4 + 0 + 1
= 5
Exercise: Convert X = 110 to decimal.
To reverse the process and convert a decimal number x (lower-case) into a binary number, first find the largest power of 2 which is smaller than (or equal to) x; this power is the highest bit in your binary number. Subtract, and repeat to find the next True bit. (Intemediate bits will be False.)
Example: Converting 9 into binary. We find the largest power of 2 that is less than 9:
2^0 = 1 <= 9
2^1 = 2 <= 9
2^2 = 4 <= 9
2^3 = 8 <= 9
2^4 = 16 > 9 => high bit is 3
Thus X = X3 X2 X1 X0, and X3 = 1. 9 - 8 = 1, so now we find the highest bit of 1:
2^0 = 1 => high bit is 0
Thus the next high bit is 0, so X0 = 1, and intermediate bits X2 and X1 are both zero: X = 1001.
Exercise: Convert 11 to binary.
Exercise: Convert these powers of 2 into binary: 2, 4, 8, 16, 32. What do you notice?
Exercise: Convert these numbers into binary: 1, 3, 7, 15, 31 (they are all 2^n - 1 for some n). What do you notice?
Machines don't have infinite memory; binary numbers are thus usually of fixed width. Common sizes on modern computers are 64bit and 128bit; for exercises, we will work with much smaller fixed bit sizes.
For fixed-width binary numbers, we will simply throw away bits which are too high: the decimal 9 has binary representation 1001; if we only use 3-bit numbers, this becomes 001, the same as the binary representation of the decimal number 1!
Exercise: check that these numbers all have the same 3-bit representation: 3 = 11 = 17, 0 = 8 = 16, 2 = 10 = 18.
Since we can convert decimal numbers to binary and back, a natural question is, "how does arithmetic look on binary representations?"
Example: 5 + 7 = 12, and on binary representations (4-bit): 0101 + 0111 = 1100
If X and Y are single-bit numbers, and Z is the single-bit representation of their sum, we can write a table to describe how Z depends on X and Y:
X0 | Y0 | Z0
---|----|----
0 | 0 | ?
1 | 0 | ?
0 | 1 | ?
1 | 1 | ?
To compute each ?, convert X0 and Y0 to decimal, add, and convert back to binary; since we work only with single-bit, this is very simple: 0 (binary) is 0 (decimal) and 1 (binary) is 1 (decimal). The addition is also very simple: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 2.
Exercise: complete the table by converting 2 into single-bit binary:
X0 | Y0 | Z0
---|----|----
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | ?
This is exactly the same as the table for XOR(X0, Y0); thus we say that XOR implements single-bit addition.
Exercise: do the same for single-bit multiplication: write down the table of binary numbers for X0, Y0, and the binary representation of their product Z0, and find the logical operation which matches. We say this operation implements single-bit multiplication.
Example: We now implement describe the implementation of two-bit addition in logical operations. We have to use some properties about the addition algorithm.
First is carrying: when adding a column of decimal digits, if the result is greater than 9 there is overflow into the next digit:
(1) <-- carried from first column, 2+8 = 10
12
+ 18
----
0 <-- single-digit addition in first column result
3 <-- single-digit addition in second column result
----
30
The same principle works with binary addition:
(1) <-- carried from second column, 1+1 = 10 (binary)
(1) <-- carried from first column, 1+1 = 10 (binary)
001
+ 011
------
0 <-- single-bit addition in first column result
0 <-- single-bit addition in second column result
1 <-- single-bit addition in third column result
------
100
We already know the result of single-bit addition is implemented by XOR; let's look at the carry bit:
X | Y | CARRY(X,Y)
--|---|------------
0 | 0 | 0 no need to carry, sum is 0 (still single-bit)
0 | 1 | 0 no need to carry, sum is 1 (still single-bit)
1 | 0 | 0 no need to carry, sum is 1 (still single-bit)
1 | 1 | 1 carry required, sum is 10 (carry the 1)
Comparing truth tables, we see CARRY is implemented by AND.
To implement two-bit addition, we need to compute formulas for Z1 and Z0, where X + Y = Z. The formula for Z0 is the same as before; there's no carrying for the first column. For Z1, we need a formula that computes single bit addition of X1, Y1, and AND(X0,Y0); we can write this as XOR(X1,XOR(Y1, AND(X0,Y0)).
Following the same strategy, all arithmetic operations can be expressed in terms of the logical operations we've seen before. And all logical operations can be expressed in terms of NAND.
Two transistors can be used to construct an elementary logic circuit: NAND. Electrons start from POWER with high energy, and spend this energy as they travel to GROUND. A and B are gates on the two transistors; when a gate is powered, electrons travel across the transistor without losing energy. If a gate is unpowered, then electrons spend all their energy crossing the gates. OUT is a tap measuring how much energy the electrons have lost crossing R.
POWER
|
-----
| R |
-----
|---- OUT
-----
A --| T |
-----
|
-----
B --| T |
-----
|
GROUND
Exercise: Using A and B as the inputs, and OUT as the output, explain how this circuit acts as NAND(A,B); for each entry in the truth table, follow the explanation above. True is "high energy" and False is "low energy".
This means we can build a digital (= binary electric) calculator! A few additional operations (load, store, jump) and some memory cells, and we have a simple computer.