From 601c10ffec6072cb2e92f81c4bbe901ccd164047 Mon Sep 17 00:00:00 2001 From: lshprung Date: Wed, 4 Nov 2020 11:44:07 -0800 Subject: Post-class 11/04 --- 17.md | 4 ++ 18.1.md | 0 18.1.png | Bin 0 -> 10569 bytes 18.10.png | Bin 0 -> 12421 bytes 18.11.png | Bin 0 -> 13815 bytes 18.12.png | Bin 0 -> 5146 bytes 18.13.png | Bin 0 -> 15295 bytes 18.14.png | Bin 0 -> 10905 bytes 18.15.png | Bin 0 -> 17792 bytes 18.2.png | Bin 0 -> 14309 bytes 18.3.png | Bin 0 -> 7823 bytes 18.4.png | Bin 0 -> 3791 bytes 18.5.png | Bin 0 -> 6634 bytes 18.6.png | Bin 0 -> 10080 bytes 18.7.png | Bin 0 -> 12015 bytes 18.8.png | Bin 0 -> 34660 bytes 18.9.png | Bin 0 -> 11732 bytes 18.md | 175 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 18 files changed, 179 insertions(+) create mode 100644 18.1.md create mode 100644 18.1.png create mode 100644 18.10.png create mode 100644 18.11.png create mode 100644 18.12.png create mode 100644 18.13.png create mode 100644 18.14.png create mode 100644 18.15.png create mode 100644 18.2.png create mode 100644 18.3.png create mode 100644 18.4.png create mode 100644 18.5.png create mode 100644 18.6.png create mode 100644 18.7.png create mode 100644 18.8.png create mode 100644 18.9.png create mode 100644 18.md diff --git a/17.md b/17.md index 8ba3a2d..33196ed 100644 --- a/17.md +++ b/17.md @@ -146,3 +146,7 @@ - From scratch means creating the truth table and working out the logic yourself - Re-purposing means using a counter that has already been designed, and taking advantage of the provided control signals, like parallel load and count enable - Control signals (inputs) \*must\* be set to something, cannot be left hanging + +--- + +[State machine concepts ->](18.md) diff --git a/18.1.md b/18.1.md new file mode 100644 index 0000000..e69de29 diff --git a/18.1.png b/18.1.png new file mode 100644 index 0000000..668896d Binary files /dev/null and b/18.1.png differ diff --git a/18.10.png b/18.10.png new file mode 100644 index 0000000..f0e4b0c Binary files /dev/null and b/18.10.png differ diff --git a/18.11.png b/18.11.png new file mode 100644 index 0000000..1d32134 Binary files /dev/null and b/18.11.png differ diff --git a/18.12.png b/18.12.png new file mode 100644 index 0000000..f9a89b7 Binary files /dev/null and b/18.12.png differ diff --git a/18.13.png b/18.13.png new file mode 100644 index 0000000..24e7a23 Binary files /dev/null and b/18.13.png differ diff --git a/18.14.png b/18.14.png new file mode 100644 index 0000000..507ec06 Binary files /dev/null and b/18.14.png differ diff --git a/18.15.png b/18.15.png new file mode 100644 index 0000000..a1d8e9c Binary files /dev/null and b/18.15.png differ diff --git a/18.2.png b/18.2.png new file mode 100644 index 0000000..6e49afb Binary files /dev/null and b/18.2.png differ diff --git a/18.3.png b/18.3.png new file mode 100644 index 0000000..e6935d7 Binary files /dev/null and b/18.3.png differ diff --git a/18.4.png b/18.4.png new file mode 100644 index 0000000..bde0368 Binary files /dev/null and b/18.4.png differ diff --git a/18.5.png b/18.5.png new file mode 100644 index 0000000..d3789cf Binary files /dev/null and b/18.5.png differ diff --git a/18.6.png b/18.6.png new file mode 100644 index 0000000..1a0ab2a Binary files /dev/null and b/18.6.png differ diff --git a/18.7.png b/18.7.png new file mode 100644 index 0000000..4dc554c Binary files /dev/null and b/18.7.png differ diff --git a/18.8.png b/18.8.png new file mode 100644 index 0000000..3fcb6fe Binary files /dev/null and b/18.8.png differ diff --git a/18.9.png b/18.9.png new file mode 100644 index 0000000..7b236f2 Binary files /dev/null and b/18.9.png differ 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) -- cgit