State Reduction And State Ass 1y5t59
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3b7i
Overview 3e4r5l
& View State Reduction And State Ass as PDF for free.
More details w3441
- Words: 1,463
- Pages: 37
ECE 331 – Digital System Design
State Reduction and State Assignment (Lecture #22)
The slides included herein were taken from the materials accompanying Fundamentals of Logic Design, 6th Edition, by Roth and Kinney, and were used with permission from Cengage Learning.
Material to be covered …
Chapter 15: Sections 1 – 9
Fall 2010
ECE 331 - Digital System Design
2
Sequential Circuit Design • Understand specifications • Draw state graph (to describe state machine behavior) • Construct state table (from state graph)
• Perform state minimization (if necessary) • Encode states (aka. state assignment) • Create state-assigned table
• Select type of Flip-Flop to use • Determine Flip-Flop input equations and FSM output equation(s)
• Draw logic diagram ECE 331 - Digital Systems Design
3
Elimination of Redundant States
Fall 2010
ECE 331 - Digital System Design
4
Elimination of Redundant States In Unit 14, we were careful to avoid introducing unnecessary states when setting up a state graph or table. We will now approach the problem of deriving the state graph somewhat differently. When first setting up the state table, we will not be overly concerned with inclusion of extra states, and when the table is complete, we will eliminate any redundant states. We will rework Example 1 in Section 14.3 using excess states, and then eliminate the excess states.
Fall 2010
ECE 331 - Digital System Design
5
Example: Sequence Detector A sequential circuit has one input (X) and one output (Z). The circuit examines groups of four consecutive inputs and produces an output Z = 1 if the input sequence 0101 or 1001 occurs. The circuit resets after every four inputs. Find a Mealy state graph. A typical input and output sequence is:
Fall 2010
ECE 331 - Digital System Design
6
Example: Sequence Detector
State Table Fall 2010
ECE 331 - Digital System Design
7
Example: Sequence Detector Since states H and I have the same next states and the same outputs, there is no way of telling states H and I apart. We can replace I with H.
Fall 2010
ECE 331 - Digital System Design
8
Example: Sequence Detector
Reduced State Table Fall 2010
ECE 331 - Digital System Design
9
Example: Sequence Detector
Reduced State Graph Fall 2010
ECE 331 - Digital System Design
10
Determination of Equivalent States
a ≡ b iff d ≡ f and c≡h
a ≡ d iff a ≡ d and c ≡ e
Fall 2010
ECE 331 - Digital System Design
12
Implication Chart
Fall 2010
ECE 331 - Digital System Design
13
Implication Chart
After first .
Fall 2010
ECE 331 - Digital System Design
14
Implication Chart
After second .
Fall 2010
ECE 331 - Digital System Design
15
Implication Table Method 3. Go through the table square-by-square. If square i-j contains the implied pair m-n, and square m-n contains an X, then i j, and an X should be placed in square i-j. 4. If any X’s were added in step 3, repeat step 3 until no more X’s are added. 5. For each square i-j which does not contain an X, i ≡ j.
Fall 2010
ECE 331 - Digital System Design
16
Future site of another example.
Fall 2010
ECE 331 - Digital System Design
17
Derivation of FF Input Equations
Fall 2010
ECE 331 - Digital System Design
18
Derivation of FF Input Equations After the number of states in a state table has been reduced, the following procedure can be used to derive the flip-flop input equations: 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs. 3. Derive the next-state maps from the transition table. 4. Find flip-flop input maps from the next-state maps using the techniques developed in Unit 12 and find the flip-flop input equations from the maps. Fall 2010
ECE 331 - Digital System Design
19
Example #1: FF Input Equations 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs.
Fall 2010
ECE 331 - Digital System Design
20
Example #1: FF Input Equations 3. Derive the next-state maps from the transition table.
D FF Characteristic Equation:
Q+ = D
Fall 2010
ECE 331 - Digital System Design
21
Example #1: FF Input Equations 4. Derive the flip-flop input maps from the next-state maps; determine the flip-flop input equations from the FF input maps.
JK Excitation Table
Fall 2010
Q
Q+
J
K
0
0
0
x
0
1
1
x
1
0
x
1
1
1
x
0
22
Example #2: FF Input Equations 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs.
Fall 2010
ECE 331 - Digital System Design
23
Example #2: FF Input Equations 3. Derive the next-state maps from the transition table.
D FF Characteristic Equation:
Q+ = D
Fall 2010
24
Example #2: FF Input Equations 4. Derive the flip-flop input maps from the next-state maps; determine the flip-flop input equations from the FF input maps.
SR Excitation Table
Fall 2010
Q
Q+
S
R
0
0
0
x
0
1
1
0
1
0
0
1
1
1
x
0
25
State Assignment
Fall 2010
ECE 331 - Digital System Design
26
State Assignments After the number of states in a state table has been reduced, the next step in realizing the transition table (aka. stateassigned table) is to assign flip-flop states (i.e. binary values) to correspond to the states in the state table. The cost of the logic required to realize a sequential circuit is strongly dependent on the way this state assignment is made.
Fall 2010
ECE 331 - Digital System Design
27
State Assignments Given a sequential circuit with three states and two flip-flops (A and B), there are 4 × 3 × 2 = 24 possible state assignments for the three states.
Fall 2010
ECE 331 - Digital System Design
28
State Assignments When realizing a three-state sequential circuit with symmetrical flip-flops (i.e. JK or SR), it is only necessary to try three different states to be assured of a minimum cost realization. Similarly, only three different assignments must be tried for four states.
Fall 2010
ECE 331 - Digital System Design
29
State Assignments
Fall 2010
ECE 331 - Digital System Design
30
Guidelines for State Assignment Trying all nonequivalent state assignments is not practical in most cases. The following guidelines are useful in making assignments which will place 1’s (or 0's) together in the next-state maps: 1. States which have the same next state for a given input should be given adjacent assignments. 2. States which are the next states of the same state should be given adjacent assignments. 3. States which have the same output for a given input should be given adjacent assignments. Fall 2010
ECE 331 - Digital System Design
31
Example: Selecting an Assignment
1. States which have the same next state for a given input should be given adjacent assignments. 2. States which are the next states of the same state should be given adjacent assignments. 3. States which have the same output for a given input should be given adjacent assignments. Fall 2010
ECE 331 - Digital System Design
32
Example: Selecting an Assignment Based on the State Assignment Guidelines: 1. (b, d) (c, f) (b, e) 2. (a, c) (d, f) (b, d) (b, f) (c, e) 3. (a, c) (b, d) (e, f)
Fall 2010
ECE 331 - Digital System Design
33
Example: Selecting an Assignment Resulting Transition Table:
Fall 2010
ECE 331 - Digital System Design
34
Example: Selecting an Assignment Derivation of FF input equations from next-state maps:
Fall 2010
ECE 331 - Digital System Design
35
One-Hot State Assignment Sometimes reducing the number of flip-flops used is not as important as reducing the logic feeding into the flip-flops. Using a one-hot state assignment may help accomplish this. The one-hot assignment uses one flip-flop for each state, so a state machine with N states requires N flip-flops. Exactly one of the flip-flops is set to one in each state.
Fall 2010
ECE 331 - Digital System Design
36
Example: State Assignments For a four-state FSM, three possible state assignments are:
Fall 2010
State
Binary
Gray-code
One-hot
S0
00
00
0001
S1
01
01
0010
S2
10
11
0100
S3
11
10
1000
# of FF
2
2
4
ECE 331 - Digital System Design
37
State Reduction and State Assignment (Lecture #22)
The slides included herein were taken from the materials accompanying Fundamentals of Logic Design, 6th Edition, by Roth and Kinney, and were used with permission from Cengage Learning.
Material to be covered …
Chapter 15: Sections 1 – 9
Fall 2010
ECE 331 - Digital System Design
2
Sequential Circuit Design • Understand specifications • Draw state graph (to describe state machine behavior) • Construct state table (from state graph)
• Perform state minimization (if necessary) • Encode states (aka. state assignment) • Create state-assigned table
• Select type of Flip-Flop to use • Determine Flip-Flop input equations and FSM output equation(s)
• Draw logic diagram ECE 331 - Digital Systems Design
3
Elimination of Redundant States
Fall 2010
ECE 331 - Digital System Design
4
Elimination of Redundant States In Unit 14, we were careful to avoid introducing unnecessary states when setting up a state graph or table. We will now approach the problem of deriving the state graph somewhat differently. When first setting up the state table, we will not be overly concerned with inclusion of extra states, and when the table is complete, we will eliminate any redundant states. We will rework Example 1 in Section 14.3 using excess states, and then eliminate the excess states.
Fall 2010
ECE 331 - Digital System Design
5
Example: Sequence Detector A sequential circuit has one input (X) and one output (Z). The circuit examines groups of four consecutive inputs and produces an output Z = 1 if the input sequence 0101 or 1001 occurs. The circuit resets after every four inputs. Find a Mealy state graph. A typical input and output sequence is:
Fall 2010
ECE 331 - Digital System Design
6
Example: Sequence Detector
State Table Fall 2010
ECE 331 - Digital System Design
7
Example: Sequence Detector Since states H and I have the same next states and the same outputs, there is no way of telling states H and I apart. We can replace I with H.
Fall 2010
ECE 331 - Digital System Design
8
Example: Sequence Detector
Reduced State Table Fall 2010
ECE 331 - Digital System Design
9
Example: Sequence Detector
Reduced State Graph Fall 2010
ECE 331 - Digital System Design
10
Determination of Equivalent States
a ≡ b iff d ≡ f and c≡h
a ≡ d iff a ≡ d and c ≡ e
Fall 2010
ECE 331 - Digital System Design
12
Implication Chart
Fall 2010
ECE 331 - Digital System Design
13
Implication Chart
After first .
Fall 2010
ECE 331 - Digital System Design
14
Implication Chart
After second .
Fall 2010
ECE 331 - Digital System Design
15
Implication Table Method 3. Go through the table square-by-square. If square i-j contains the implied pair m-n, and square m-n contains an X, then i j, and an X should be placed in square i-j. 4. If any X’s were added in step 3, repeat step 3 until no more X’s are added. 5. For each square i-j which does not contain an X, i ≡ j.
Fall 2010
ECE 331 - Digital System Design
16
Future site of another example.
Fall 2010
ECE 331 - Digital System Design
17
Derivation of FF Input Equations
Fall 2010
ECE 331 - Digital System Design
18
Derivation of FF Input Equations After the number of states in a state table has been reduced, the following procedure can be used to derive the flip-flop input equations: 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs. 3. Derive the next-state maps from the transition table. 4. Find flip-flop input maps from the next-state maps using the techniques developed in Unit 12 and find the flip-flop input equations from the maps. Fall 2010
ECE 331 - Digital System Design
19
Example #1: FF Input Equations 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs.
Fall 2010
ECE 331 - Digital System Design
20
Example #1: FF Input Equations 3. Derive the next-state maps from the transition table.
D FF Characteristic Equation:
Q+ = D
Fall 2010
ECE 331 - Digital System Design
21
Example #1: FF Input Equations 4. Derive the flip-flop input maps from the next-state maps; determine the flip-flop input equations from the FF input maps.
JK Excitation Table
Fall 2010
Q
Q+
J
K
0
0
0
x
0
1
1
x
1
0
x
1
1
1
x
0
22
Example #2: FF Input Equations 1. Assign flip-flop state values to correspond to the states in the reduced table. 2. Construct a transition table which gives the next states of the flip-flops as a function of the present states and inputs.
Fall 2010
ECE 331 - Digital System Design
23
Example #2: FF Input Equations 3. Derive the next-state maps from the transition table.
D FF Characteristic Equation:
Q+ = D
Fall 2010
24
Example #2: FF Input Equations 4. Derive the flip-flop input maps from the next-state maps; determine the flip-flop input equations from the FF input maps.
SR Excitation Table
Fall 2010
Q
Q+
S
R
0
0
0
x
0
1
1
0
1
0
0
1
1
1
x
0
25
State Assignment
Fall 2010
ECE 331 - Digital System Design
26
State Assignments After the number of states in a state table has been reduced, the next step in realizing the transition table (aka. stateassigned table) is to assign flip-flop states (i.e. binary values) to correspond to the states in the state table. The cost of the logic required to realize a sequential circuit is strongly dependent on the way this state assignment is made.
Fall 2010
ECE 331 - Digital System Design
27
State Assignments Given a sequential circuit with three states and two flip-flops (A and B), there are 4 × 3 × 2 = 24 possible state assignments for the three states.
Fall 2010
ECE 331 - Digital System Design
28
State Assignments When realizing a three-state sequential circuit with symmetrical flip-flops (i.e. JK or SR), it is only necessary to try three different states to be assured of a minimum cost realization. Similarly, only three different assignments must be tried for four states.
Fall 2010
ECE 331 - Digital System Design
29
State Assignments
Fall 2010
ECE 331 - Digital System Design
30
Guidelines for State Assignment Trying all nonequivalent state assignments is not practical in most cases. The following guidelines are useful in making assignments which will place 1’s (or 0's) together in the next-state maps: 1. States which have the same next state for a given input should be given adjacent assignments. 2. States which are the next states of the same state should be given adjacent assignments. 3. States which have the same output for a given input should be given adjacent assignments. Fall 2010
ECE 331 - Digital System Design
31
Example: Selecting an Assignment
1. States which have the same next state for a given input should be given adjacent assignments. 2. States which are the next states of the same state should be given adjacent assignments. 3. States which have the same output for a given input should be given adjacent assignments. Fall 2010
ECE 331 - Digital System Design
32
Example: Selecting an Assignment Based on the State Assignment Guidelines: 1. (b, d) (c, f) (b, e) 2. (a, c) (d, f) (b, d) (b, f) (c, e) 3. (a, c) (b, d) (e, f)
Fall 2010
ECE 331 - Digital System Design
33
Example: Selecting an Assignment Resulting Transition Table:
Fall 2010
ECE 331 - Digital System Design
34
Example: Selecting an Assignment Derivation of FF input equations from next-state maps:
Fall 2010
ECE 331 - Digital System Design
35
One-Hot State Assignment Sometimes reducing the number of flip-flops used is not as important as reducing the logic feeding into the flip-flops. Using a one-hot state assignment may help accomplish this. The one-hot assignment uses one flip-flop for each state, so a state machine with N states requires N flip-flops. Exactly one of the flip-flops is set to one in each state.
Fall 2010
ECE 331 - Digital System Design
36
Example: State Assignments For a four-state FSM, three possible state assignments are:
Fall 2010
State
Binary
Gray-code
One-hot
S0
00
00
0001
S1
01
01
0010
S2
10
11
0100
S3
11
10
1000
# of FF
2
2
4
ECE 331 - Digital System Design
37
Related Documents 3m3m1z
State Reduction And State Ass 1y5t59
April 2022 0
State Reduction And Assignment 5mmz
November 2019 20
State Diagram, State Table, State Reduction, State Assignment 3d5t1w
October 2021 0
State Emergency 3p7132
December 2019 36
State Table 6o3v58
October 2022 0
State Equations.pdf q6l1s
December 2019 32More Documents from "anjugadu" 4615f
Recursion.ppt 6g3520
March 2021 0