summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--17.md4
-rw-r--r--18.1.md0
-rw-r--r--18.1.pngbin0 -> 10569 bytes
-rw-r--r--18.10.pngbin0 -> 12421 bytes
-rw-r--r--18.11.pngbin0 -> 13815 bytes
-rw-r--r--18.12.pngbin0 -> 5146 bytes
-rw-r--r--18.13.pngbin0 -> 15295 bytes
-rw-r--r--18.14.pngbin0 -> 10905 bytes
-rw-r--r--18.15.pngbin0 -> 17792 bytes
-rw-r--r--18.2.pngbin0 -> 14309 bytes
-rw-r--r--18.3.pngbin0 -> 7823 bytes
-rw-r--r--18.4.pngbin0 -> 3791 bytes
-rw-r--r--18.5.pngbin0 -> 6634 bytes
-rw-r--r--18.6.pngbin0 -> 10080 bytes
-rw-r--r--18.7.pngbin0 -> 12015 bytes
-rw-r--r--18.8.pngbin0 -> 34660 bytes
-rw-r--r--18.9.pngbin0 -> 11732 bytes
-rw-r--r--18.md175
18 files changed, 179 insertions, 0 deletions
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
--- /dev/null
+++ b/18.1.md
diff --git a/18.1.png b/18.1.png
new file mode 100644
index 0000000..668896d
--- /dev/null
+++ b/18.1.png
Binary files differ
diff --git a/18.10.png b/18.10.png
new file mode 100644
index 0000000..f0e4b0c
--- /dev/null
+++ b/18.10.png
Binary files differ
diff --git a/18.11.png b/18.11.png
new file mode 100644
index 0000000..1d32134
--- /dev/null
+++ b/18.11.png
Binary files differ
diff --git a/18.12.png b/18.12.png
new file mode 100644
index 0000000..f9a89b7
--- /dev/null
+++ b/18.12.png
Binary files differ
diff --git a/18.13.png b/18.13.png
new file mode 100644
index 0000000..24e7a23
--- /dev/null
+++ b/18.13.png
Binary files differ
diff --git a/18.14.png b/18.14.png
new file mode 100644
index 0000000..507ec06
--- /dev/null
+++ b/18.14.png
Binary files differ
diff --git a/18.15.png b/18.15.png
new file mode 100644
index 0000000..a1d8e9c
--- /dev/null
+++ b/18.15.png
Binary files differ
diff --git a/18.2.png b/18.2.png
new file mode 100644
index 0000000..6e49afb
--- /dev/null
+++ b/18.2.png
Binary files differ
diff --git a/18.3.png b/18.3.png
new file mode 100644
index 0000000..e6935d7
--- /dev/null
+++ b/18.3.png
Binary files differ
diff --git a/18.4.png b/18.4.png
new file mode 100644
index 0000000..bde0368
--- /dev/null
+++ b/18.4.png
Binary files differ
diff --git a/18.5.png b/18.5.png
new file mode 100644
index 0000000..d3789cf
--- /dev/null
+++ b/18.5.png
Binary files differ
diff --git a/18.6.png b/18.6.png
new file mode 100644
index 0000000..1a0ab2a
--- /dev/null
+++ b/18.6.png
Binary files differ
diff --git a/18.7.png b/18.7.png
new file mode 100644
index 0000000..4dc554c
--- /dev/null
+++ b/18.7.png
Binary files differ
diff --git a/18.8.png b/18.8.png
new file mode 100644
index 0000000..3fcb6fe
--- /dev/null
+++ b/18.8.png
Binary files differ
diff --git a/18.9.png b/18.9.png
new file mode 100644
index 0000000..7b236f2
--- /dev/null
+++ b/18.9.png
Binary files 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)