diff options
| -rw-r--r-- | 1.1.png | bin | 0 -> 6345 bytes | |||
| -rw-r--r-- | 1.2.png | bin | 0 -> 6492 bytes | |||
| -rw-r--r-- | 1.md | 128 | ||||
| -rw-r--r-- | 2.1.png | bin | 0 -> 32176 bytes | |||
| -rw-r--r-- | 2.2.png | bin | 0 -> 21926 bytes | |||
| -rw-r--r-- | 2.3.png | bin | 0 -> 4482 bytes | |||
| -rw-r--r-- | 2.4.png | bin | 0 -> 15392 bytes | |||
| -rw-r--r-- | 2.md | 201 |
8 files changed, 329 insertions, 0 deletions
| Binary files differBinary files differ @@ -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 `~`) + + + +### 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 + + + +--- + +[Truth tables, minterms, and simple synthesis ->](2.md) Binary files differBinary files differBinary files differBinary files differ@@ -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 + + + +--- + +## 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 + + + +--- + +## 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`: + + + +--- + +## 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 + + |
