First commit

8 files changed, 329 insertions, 0 deletions

diff --git a/1.1.png b/1.1.png
new file mode 100644
index 0000000..7e4308a
--- /dev/null
+++ b/1.1.png
diff --git a/1.2.png b/1.2.png
new file mode 100644
index 0000000..0c4a5ea
--- /dev/null
+++ b/1.2.png
diff --git a/1.md b/1.md
new file mode 100644
index 0000000..2432c0c
--- /dev/null
+++ b/1.md
@@ -0,0 +1,128 @@
+# Digital Hardware and Logic Gates
+
+## Digital Hardware Concepts
+
+### Digital Hardware
+
+- Hardware (HW) means electronic circuits
+- Digital means every wire (or signal) can be in one of two (binary) states
+	- Electrically, the states are two different voltage levels (e.g. 5V and 0V)
+	- We abstractly define two logic values (1 and 0) to be associated with these two voltage levels
+	- We also use the terms "true" and "false"
+- Abstraction is key to much of this course!
+
+### Representing Information
+
+- Every signal means something (abstractly)
+- A single signal can represent some state, or be used as a means of control
+- Multiple signals can be grouped together to create a binary value
+	- Each signal is a bit (binary digit)
+- The same multi-bit value can mean different things in different contexts...
+
+### Putting values in context
+
+- The 6-bit value 101000 might mean
+	- 40, as an unsigned number, or address
+	- -24, if viewed as a 6-bit signed number
+	- "store byte", as an opcode (instruction)
+- Sometimes, leading 0's are implied
+	- 101000 as an 8-bit unsigned number is still 40
+		- But it's not still -24 as an 8-bit signed number (it's also 40)
+- With no context, the default is to interpret as an unsigned (i.e. no negatives) number
+
+---
+
+## Counting in Binary
+
+- Insight into unsigned numbers
+- When we count, we start from 0, add 1 at each step:
+	- 0+1 = 1
+	- 1+1 = 2, but we can't express 2
+- In decimal, 9+1 = 10
+	- Carry into next position and go back to 0
+	- Same with binary, but that happens at 1+1
+- 1+1 = 10, 10+1 = 11, 11+1 = 100, etc.
+- What is 111?
+
+### Counting from 0 to 15
+
+- You will need to know this range of binary numbers
+- Leading 0's: 3 as a 4-bit number is 0011
+
+|Decimal|Binary|
+|--|----|
+|0 |0   |
+|1 |1   |
+|2 |10  |
+|3 |11  |
+|4 |100 |
+|5 |101 |
+|6 |110 |
+|7 |111 |
+|8 |1000|
+|9 |1001|
+|9 |1001|
+|10|1010|
+|11|1011|
+|12|1100|
+|13|1101|
+|14|1110|
+|15|1111|
+
+---
+
+## ASCII codes
+
+- Another context for representing letters
+	- A table can be found [here](https://www.asciitable.com/)
+- ASCII codes are 7-bit values (between 0 and 127)
+
+---
+
+## Logic building blocks
+
+### Logic Circuit Building Blocks
+
+- Logic circuits are functions that generate an output based on a set of inputs
+	- Inputs and output are binary/logical values
+- Three fundamental operations
+	- AND (output is true only if all inputs are true)
+	- OR (output is true if any of the inputs are true)
+	- NOT (output is the inverse of the input)
+		- Also called INV (for inverter)
+- **All** logic functions are made by a combination of these three operations
+
+### Logic in algebraic form
+
+- Note: variable names are generic; they have no inherent meaning
+- AND
+	- Expressed as a product (multiplication)
+	- `Y = X1 * X2` (or just `X1X2`)
+- OR
+	- Expressed as a sum (addition)
+	- `Y = X1 + X2`
+- NOT
+	- `Y = !X1`
+
+### Logic Gates
+
+- Because these are HW circuits, it's useful to have a schematic abstraction
+	- We call these logic "gates"
+	- The symbols for AND, OR, and INV are below
+	- AND and OR can have more than 2 inputs
+		- Same symbol
+- Note the overbar used at the output of the inverter
+	- Just another way of expressing `!` (or `~`)
+
+![schematic](1.1.png)
+
+### Logic Circuits
+
+- If we want a function that is different than just AND or OR, or we have more than two signals to work with, we can combine gates into a larger circuit
+- Much of what we'll be covering is how to define the circuit needed to implement a given logic function
+
+![schematic](1.2.png)
+
+---
+
+[Truth tables, minterms, and simple synthesis ->](2.md)
diff --git a/2.1.png b/2.1.png
new file mode 100644
index 0000000..f0d5c5a
--- /dev/null
+++ b/2.1.png
diff --git a/2.2.png b/2.2.png
new file mode 100644
index 0000000..469ea43
--- /dev/null
+++ b/2.2.png
diff --git a/2.3.png b/2.3.png
new file mode 100644
index 0000000..c37e951
--- /dev/null
+++ b/2.3.png
diff --git a/2.4.png b/2.4.png
new file mode 100644
index 0000000..4d46ef9
--- /dev/null
+++ b/2.4.png
diff --git a/2.md b/2.md
new file mode 100644
index 0000000..f39bfcb
--- /dev/null
+++ b/2.md
@@ -0,0 +1,201 @@
+[\<- Digital Hardware and Logic Gates](1.md)
+
+---
+
+# Truth Tables, minterms, and simple synthesis
+
+## Truth Tables
+
+- The fundamental way to capture desired behavior of a logic function
+- Inputs on the left, output(s) on the right
+	- Variable names are an abstraction
+- Each row is a unique combination of inputs
+	- A 2-input table has four (2^2) rows
+	- A 3-input table has eight (2^3) rows
+- The output in a given row is the desired behavior for the input values specified in that row
+
+### Truth Table structure
+
+- Rows are listed in counting order, covering all possible input combinations
+- Every input needs a value
+	- Leading zero's
+
+|X1X2X3|F (Output)|
+|------|-|
+|000   | |
+|001   | |
+|010   | |
+|011   | |
+|100   | |
+|101   | |
+|110   | |
+|111   | |
+
+### Truth Table for AND and OR
+
+- Note: we list input combinations in "counting" order
+
+|x1|x2| |x1 * x2 (AND)|x1 + x2 (OR)|
+|--|--|-|-------------|------------|
+|0 |0 | |0            |0           |
+|0 |1 | |0            |1           |
+|1 |0 | |0            |1           |
+|1 |1 | |1            |1           |
+
+---
+
+## The XOR Gate
+
+### The Exclusive-OR (XOR) Gate
+
+- Not as fundamental as AND/OR/NOT, but extremely common
+
+![XOR info](2.1.png)
+
+---
+
+## Analysis vs. Synthesis
+
+- "What does this circuit do?" vs "I want a circuit that does this"
+- Analysis is the process of generating **the** truth table for a given circuit
+- Synthesis is the process of generating **a** circuit based on a truth table (or just knowing what you want the circuit to do)
+	- Two different circuits can yield the same result
+	- We will learn different synthesis techniques
+
+### Synthesis by recognition
+
+- These functions (s1 and s0) happen to match a single gate implementations
+	- Not typical; we'll learn more synthesis tools
+
+![S demo](2.2.png)
+
+---
+
+## Product Terms
+
+- An application of the AND function
+	- Since we model AND as multiplication
+- Evaluates tot true only if **all** inputs are true
+	- Allows for "detection" of a specific set of conditions (i.e., input values)
+- Inputs can be inverted to detect 0's
+- Examples:
+	- `X*Y` is true only if `X=1` AND `Y=1`
+	- `X*!Y` is true only if `X=1` AND `Y=0`
+
+### Product terms in schematics
+
+- We will be using product terms a lot
+- Don't always need to draw inverters
+	- A bubble implies the presence of an inverter
+- Two different ways to draw `!X*Y`:
+
+![!X\*Y demo](2.3.png)
+
+---
+
+## Minterms and the canonical SOP
+
+### Minterms (and maxterms)
+
+- A product term that uses all inputs
+	- A row in the truth table
+- Enumerated by input values
+
+|Row number|x1|x2|x3| |Minterm             |Maxterm             |
+|----------|--|--|--|-|--------------------|--------------------|
+|0         |0 |0 |0 | |m0 = !x1 * !x2 * !x3|M0 =  x1 +  x2 +  x3|
+|1         |0 |0 |1 | |m1 = !x1 * !x2 *  x3|M1 =  x1 +  x2 + !x3|
+|2         |0 |1 |0 | |m2 = !x1 *  x2 * !x3|M2 =  x1 + !x2 +  x3|
+|3         |0 |1 |1 | |m3 = !x1 *  x2 *  x3|M3 =  x1 + !x2 + !x3|
+|4         |1 |0 |0 | |m4 =  x1 * !x2 * !x3|M4 = !x1 +  x2 +  x3|
+|5         |1 |0 |1 | |m5 =  x1 * !x2 *  x3|M5 = !x1 +  x2 + !x3|
+|6         |1 |1 |0 | |m6 =  x1 *  x2 * !x3|M6 = !x1 + !x2 +  x3|
+|7         |1 |1 |1 | |m7 =  x1 *  x2 *  x3|M7 = !x1 + !x2 + !x3|
+
+### Synthesis with Minterms
+
+- Identify all minterms where the output is 1
+	- In table below; m1, m4, m5, m6
+- "Add" them together to create a sum of products (SOP) equation
+	- F = m1 + m4 + m5 + m6
+
+|Row number|x1|x2|x3| |f(x1, x2, x3)|
+|----------|--|--|--|-|-------------|
+|0         |0 |0 |0 | |0            |
+|1         |0 |0 |1 | |1            |
+|2         |0 |1 |0 | |0            |
+|3         |0 |1 |1 | |0            |
+|4         |1 |0 |0 | |1            |
+|5         |1 |0 |1 | |1            |
+|6         |1 |1 |0 | |1            |
+|7         |1 |1 |1 | |0            |
+
+### Canonical SOP equation
+
+- Continuing from previous section, we had
+	- F = m1 + m4 + m5 + m6
+- But m1, m4, m5, and m6 are really product terms of the acutal inputs
+- The full equation, using actual inputs
+	- `F = (!x1 * !x2 * !x3) + (x1 * !x2 * !x3) + (x1 * !x2 * x3) + (x1 * x2 * !x3)`
+- The canonical SOP equation is explicitly the sum of the minterms
+
+### Shorthand for canonical SOP
+
+- Sigma notation -> sum of minterms
+- E.g., `F(x1, x2, x3) =	Σm(2,4,6,7)`
+	- Note this is different function than previous ex.
+	- Order of input variables matters!
+
+|Row #|Minterm        |F(x1, x2, x3)|
+|-----|---------------|-------------|
+|0    |!x1 * !x2 * !x3|0            |
+|1    |!x1 * !x2 *  x3|0            |
+|2    |!x1 *  x2 * !x3|1            |
+|3    |!x1 *  x2 *  x3|0            |
+|4    | x1 * !x2 * !x3|1            |
+|5    | x1 * !x2 *  x3|0            |
+|6    | x1 *  x2 * !x3|1            |
+|7    | x1 *  x2 *  x3|1            |
+
+---
+
+## 3-way Light Switch Design example
+
+- Three inputs, corresponding to three light switches
+	- A 0 means that switch is down, a 1 means up
+- Toggling any switch will toggle whether the light is on or off
+	- All down -> light off
+	- Any one up -> light on
+	- Any two up -> light off
+	- All three up -> light on
+
+### Express as truth table
+
+- A 3-input function has 8 rows, and the rows enumerate the input combinations
+
+|x1|x2|x3| |f|
+|--|--|--|-|-|
+|0 |0 |0 | |0|
+|0 |0 |1 | |1|
+|0 |1 |0 | |1|
+|0 |1 |1 | |0|
+|1 |0 |0 | |1|
+|1 |0 |1 | |0|
+|1 |1 |0 | |0|
+|1 |1 |1 | |1|
+
+### Synthesize
+
+- Need to "add" minterms 1,2,3, and 7
+	- `F = 	Σm(1,2,4,7)`
+	- `F = (!x1 * !x2 * x3) + (!x1 * x2 * !x3) + (x1 * !x2 * !x3) + (x1 * x2 * x3)`
+- A valid synthesis, but there are multiple ways to synthesize the same truth table
+- Before we look at others, we need to understand more about Boolean algebra
+	- Boolean means variables can only be 1 or 0
+
+### Schematic
+
+- Wires can get "busy", i.e., hard to follow
+- Connections by label is typical
+
+![diagram](2.4.png)