Post-class 11/04

1 files changed, 175 insertions, 0 deletions

diff --git a/18.md b/18.md
new file mode 100644
index 0000000..4a71007
--- /dev/null
+++ b/18.md
@@ -0,0 +1,175 @@
+[\<- Counters](17.md)
+
+---
+
+# State machine concepts
+
+### Extending Sequential Design
+
+- State maintained by flops
+- Next state a function of current state and inputs
+- Outputs are a function of current state, and possibly current inputs
+
+![diagram](18.1.png)
+
+### Tackling state machines
+
+- Like word problems in math
+- Clearly define inputs and outputs
+	- Make sure you understand what each signal means
+- How does time affect the behavior of the output?
+	- The present is a function of the past
+	- The past is what has happened in previous cycles
+	- What information from the past needs to be tracked?
+
+### State diagrams
+
+- How we capture/specify desired behavior
+- State "bubbles" represent "where are we?"
+	- Output value listed in state
+- Arcs/arrows indicate where to go next
+	- Need an arc for every possible input condition
+	- Can go to previous state, stay in current state, or go to new state
+
+![diagram](18.2.png)
+
+---
+
+## State diagram for simple sequence detector
+
+### Example 1
+
+- Assert output if input asserted for at least two cycles
+- Hold the output asserted until the input de-asserts
+- Since the output is a function of what has happened in previous cycles, need stateful tracking of the input sequence
+
+![diagram](18.3.png)
+
+### Step 1
+
+- Every cycle, evaluate input to determine what state to move to next
+- Initial State (A), to indicate sequence hasn't started
+	- Output (z) is 0, since we haven't seen the pattern
+	- Stay here until the first assertion is seen
+		- As long as w=0
+
+![diagram](18.4.png)
+
+### Step 2
+
+- If w is asserted, we need to add a state (B) to keep track of the fact that this has happened
+	- But Z is still 0 because we haven't seen the pattern yet
+- Need to evaluate input conditions relative to state B, since time has passed into a new cycle
+
+![diagram](18.5.png)
+
+### Step 3
+
+- State B represents "w was asserted the previous cycle"
+	- What is w doing this cycle?
+- If w is 0, sequence is broken, go back to A
+- If w is 1, we've now seen two 1's in a row
+	- That's our pattern, need a new state (C) so that we can assert z
+
+![diagram](18.6.png)
+
+### Step 4
+
+- We're not done yet, we still need to evaluate state C for the different input conditions
+	- If w stays 1, we can stay in state C
+	- If w deasserts, go back to state A
+- No new states means now we're done
+
+![diagram](18.7.png)
+
+---
+
+## Translating from state diagram to state table, with state assignments
+
+### Translate diagram into table
+
+![diagram](18.8.png)
+
+### Implementation Structure
+
+- Three states means we need 2 flops
+
+![diagram](18.9.png)
+
+### State Assignment
+
+- Define which flop encoding is associated with which state
+	- Encodings don't matter, as long as each state has a unique value
+
+![diagram](18.10.png)
+
+---
+
+## Next state and output equations
+
+### Interpreting the state table
+
+- State table is a different format of truth table
+	- Present/current state and control inputs are the "inputs"
+	- Next state values are the "outputs"
+
+|wy2y1|Y2Y1|
+|-----|----|
+|000  |00  |
+|001  |00  |
+|010  |00  |
+|011  |dd  |
+|100  |01  |
+|101  |10  |
+|110  |10  |
+|111  |dd  |
+
+### Next state equations
+
+- Every state flop needs its own logic equation for its D input
+	- Can take a minterm-like approach, or use K-maps, or take any other approach that works
+
+![diagram](18.11.png)
+
+### Output equation
+
+- Also need equation for z
+- Note that we don't typically take the extra step of creating a truth table, but it's an option if you can't derive the logic from the state table directly
+
+|y2y1|z|
+|----|-|
+|00  |0|
+|01  |0|
+|10  |1|
+|11  |d|
+
+![diagram](18.12.png)
+
+### Implementation
+
+![diagram](18.13.png)
+
+### Timing Diagram
+
+![diagram](18.14.png)
+
+### Summary of Steps
+
+1. Obtain the specification of the desired circuit
+2. Derive a state diagram
+3. Derive the corresponding state table
+4. Decide on the number of state variables
+5. Derive the logic expressions needed to implement the circuit
+
+---
+
+## Another sequence detector
+
+- Let's say we wanted to detect a slightly more complex pattern: 101
+- We need to detect all embedded sequences
+	- 10101 and 101101 both have two instances of 101 embedded in them
+- Need to think about how each input fits into a larger possible sequence
+
+### State diagram to detect 101
+
+![diagram](18.15.png)