From 61d08ae07f49161aafaf690e6ba8684ce1e49258 Mon Sep 17 00:00:00 2001 From: lshprung Date: Thu, 24 Sep 2020 17:18:40 -0700 Subject: First commit --- 1.1.png | Bin 0 -> 6345 bytes 1.2.png | Bin 0 -> 6492 bytes 1.md | 128 +++++++++++++++++++++++++++++++++++++++++ 2.1.png | Bin 0 -> 32176 bytes 2.2.png | Bin 0 -> 21926 bytes 2.3.png | Bin 0 -> 4482 bytes 2.4.png | Bin 0 -> 15392 bytes 2.md | 201 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 329 insertions(+) create mode 100644 1.1.png create mode 100644 1.2.png create mode 100644 1.md create mode 100644 2.1.png create mode 100644 2.2.png create mode 100644 2.3.png create mode 100644 2.4.png create mode 100644 2.md diff --git a/1.1.png b/1.1.png new file mode 100644 index 0000000..7e4308a Binary files /dev/null and b/1.1.png differ diff --git a/1.2.png b/1.2.png new file mode 100644 index 0000000..0c4a5ea Binary files /dev/null and b/1.2.png differ 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 Binary files /dev/null and b/2.1.png differ diff --git a/2.2.png b/2.2.png new file mode 100644 index 0000000..469ea43 Binary files /dev/null and b/2.2.png differ diff --git a/2.3.png b/2.3.png new file mode 100644 index 0000000..c37e951 Binary files /dev/null and b/2.3.png differ diff --git a/2.4.png b/2.4.png new file mode 100644 index 0000000..4d46ef9 Binary files /dev/null and b/2.4.png differ 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) -- cgit