State Assignment And Encoded State Table Ece
State Tables and State Diagrams
We have examined a general model for sequential circuits. In this model the effect of all previous inputs on the outputs is represented by a state of the circuit. Thus, the output of the circuit at any time depends upon its current state and the input. These also determine the next state of the circuit. The relationship that exists among the inputs, outputs, present states and next states can be specified by either the state table or the state diagram.
State Table
The state table representation of a sequential circuit consists of three sections labelled present state, next state and output. The present state designates the state of flipflops before the occurrence of a clock pulse. The next state shows the states of flipflops after the clock pulse, and the output section lists the value of the output variables during the present state.
State Diagram
In addition to graphical symbols, tables or equations, flipflops can also be represented graphically by a state diagram. In this diagram, a state is represented by a circle, and the transition between states is indicated by directed lines (or arcs) connecting the circles. An example of a state diagram is shown in Figure 3 below.
Figure 3. State Diagram 
The binary number inside each circle identifies the state the circle represents. The directed lines are labelled with two binary numbers separated by a slash (/). The input value that causes the state transition is labelled first. The number after the slash symbol / gives the value of the output. For example, the directed line from state 00 to 01 is labelled 1/0, meaning that, if the sequential circuit is in a present state and the input is 1, then the next state is 01 and the output is 0. If it is in a present state 00 and the input is 0, it will remain in that state. A directed line connecting a circle with itself indicates that no change of state occurs. The state diagram provides exactly the same information as the state table and is obtained directly from the state table.
Example: This example is taken from P. K. Lala, Practical Digital Logic Design and Testing, Prentice Hall, 1996, p.155.
Consider a sequential circuit shown in Figure 4. It has one input x, one output Z and two state variables Q1Q2 (thus having four possible present states 00, 01, 10, 11).
Figure 4. A Sequential Circuit 
The behaviour of the circuit is determined by the following Boolean expressions:
Z = x*Q1 
D1 = x' + Q1 
D2 = x*Q2' + x'*Q1' 
These equations can be used to form the state table. Suppose the present state (i.e. Q1Q2) = 00 and input x = 0. Under these conditions, we get Z = 0, D1 = 1, and D2 = 1. Thus the next state of the circuit D1D2 = 11, and this will be the present state after the clock pulse has been applied. The output of the circuit corresponding to the present state Q1Q2 = 00 and x = 1 is Z = 0. This data is entered into the state table as shown in Table 2.

Table 2. State table for the sequential circuit in Figure 4.
The state diagram for the sequential circuit in Figure 4 is shown in Figure 5.
Figure 5. State Diagram of circuit in Figure 4. 
State Diagrams of Various Flipflops
Table 3 shows the state diagrams of the four types of flipflops.

Table 3. State diagrams of the four types of flipflops.
You can see from the table that all four flipflops have the same number of states and transitions. Each flipflop is in the set state when Q=1 and in the reset state when Q=0. Also, each flipflop can move from one state to another, or it can reenter the same state. The only difference between the four types lies in the values of input signals that cause these transitions.
A state diagram is a very convenient way to visualise the operation of a flipflop or even of large sequential components.
Short Quiz
Presentation on theme: "ECE 331 – Digital System Design State Reduction and State Assignment (Lecture #22) The slides included herein were taken from the materials accompanying."— Presentation transcript:
1 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, 6 th Edition, by Roth and Kinney, and were used with permission from Cengage Learning.
2 Fall 2010ECE 331  Digital System Design2 Material to be covered … Chapter 15: Sections 1 – 9
3 ECE 331  Digital Systems Design3 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 stateassigned table Select type of FlipFlop to use Determine FlipFlop input equations and FSM output equation(s) Draw logic diagram
4 Fall 2010ECE 331  Digital System Design4 Elimination of Redundant States
5 Fall 2010ECE 331  Digital System Design5 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.
6 Fall 2010ECE 331  Digital System Design6 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:
7 Fall 2010ECE 331  Digital System Design7 Example: Sequence Detector State Table
8 Fall 2010ECE 331  Digital System Design8 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.
9 Fall 2010ECE 331  Digital System Design9 Example: Sequence Detector Reduced State Table
10 Fall 2010ECE 331  Digital System Design10 Example: Sequence Detector Reduced State Graph
11 Fall 2010ECE 331  Digital System Design11 Equivalent States Theorem 15.1: Two states p and q of a sequential circuit are equivalent iff for every single input X, the outputs are the same and the next states are equivalent, that is, where (p, X) is the output given the present state p and input X, and (p, X) is the next state given the present state p and input X. Note that the next states do not have to be equal, just equivalent.
12 Fall 2010ECE 331  Digital System Design12 Determination of Equivalent States a ≡ b iff d ≡ f andc ≡ h a ≡ d iff a ≡ d andc ≡ e
13 Fall 2010ECE 331  Digital System Design13 Implication Chart
14 Fall 2010ECE 331  Digital System Design14 Implication Chart After first pass.
15 Fall 2010ECE 331  Digital System Design15 Implication Chart After second pass.
16 Fall 2010ECE 331  Digital System Design16 Determination of Equivalent States d is replaced with a e is replaced with c d and e are removed
17 Fall 2010ECE 331  Digital System Design17 Implication Table Method The implication table method of determining state equivalence can be summarized as follows: 1. Construct a chart which contains a square for each pair of states. 2. Compare each pair of rows in the state table. If the outputs associated with states i and j are different, place an X in square ij to indicate that i j. If the outputs are the same, place the implied pairs in square ij. (If the next states of i and j are m and n for some input x, then mn is an implied pair.) If the outputs and next states are the same (or if ij only implies itself), place a check (√) in square ij to indicate that i ≡ j.
18 Fall 2010ECE 331  Digital System Design18 Implication Table Method 3.Go through the table squarebysquare. If square ij contains the implied pair mn, and square mn contains an X, then i j, and an X should be placed in square ij. 4.If any X’s were added in step 3, repeat step 3 until no more X’s are added. 5.For each square ij which does not contain an X, i ≡ j.
19 Fall 2010ECE 331  Digital System Design19 Future site of another example.
20 Fall 2010ECE 331  Digital System Design20 Derivation of FF Input Equations
21 Fall 2010ECE 331  Digital System Design21 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 flipflop input equations: 1.Assign flipflop state values to correspond to the states in the reduced table. 2.Construct a transition table which gives the next states of the flipflops as a function of the present states and inputs. 3.Derive the nextstate maps from the transition table. 4.Find flipflop input maps from the nextstate maps using the techniques developed in Unit 12 and find the flipflop input equations from the maps.
22 Fall 2010ECE 331  Digital System Design22 Example #1: FF Input Equations 1.Assign flipflop state values to correspond to the states in the reduced table. 2.Construct a transition table which gives the next states of the flipflops as a function of the present states and inputs.
23 Fall 2010ECE 331  Digital System Design23 Example #1: FF Input Equations 3.Derive the nextstate maps from the transition table. D FF Characteristic Equation: Q + = D
24 Fall 201024 Example #1: FF Input Equations 4.Derive the flipflop input maps from the nextstate maps; determine the flipflop input equations from the FF input maps. JK Excitation Table QQ+JK 000x 011x 10x1 11x0
25 Fall 2010ECE 331  Digital System Design25 Example #2: FF Input Equations 1.Assign flipflop state values to correspond to the states in the reduced table. 2.Construct a transition table which gives the next states of the flipflops as a function of the present states and inputs.
26 Fall 201026 Example #2: FF Input Equations 3.Derive the nextstate maps from the transition table. D FF Characteristic Equation: Q + = D
27 Fall 201027 Example #2: FF Input Equations 4.Derive the flipflop input maps from the nextstate maps; determine the flipflop input equations from the FF input maps. SR Excitation Table QQ+SR 000x 0110 1001 11x0
28 Fall 2010ECE 331  Digital System Design28 State Assignment
29 Fall 2010ECE 331  Digital System Design29 State Assignments After the number of states in a state table has been reduced, the next step in realizing the transition table (aka. state assigned table) is to assign flipflop 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.
30 Fall 2010ECE 331  Digital System Design30 State Assignments Given a sequential circuit with three states and two flipflops (A and B), there are 4 × 3 × 2 = 24 possible state assignments for the three states.
31 Fall 2010ECE 331  Digital System Design31 State Assignments When realizing a threestate sequential circuit with symmetrical flipflops (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.
32 Fall 2010ECE 331  Digital System Design32 State Assignments
33 Fall 2010ECE 331  Digital System Design33 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 nextstate 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.
34 Fall 2010ECE 331  Digital System Design34 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.
35 Fall 2010ECE 331  Digital System Design35 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)
36 Fall 2010ECE 331  Digital System Design36 Example: Selecting an Assignment Resulting Transition Table:
37 Fall 2010ECE 331  Digital System Design37 Example: Selecting an Assignment Derivation of FF input equations from nextstate maps:
38 Fall 2010ECE 331  Digital System Design38 OneHot State Assignment Sometimes reducing the number of flipflops used is not as important as reducing the logic feeding into the flipflops. Using a onehot state assignment may help accomplish this. The onehot assignment uses one flipflop for each state, so a state machine with N states requires N flipflops. Exactly one of the flipflops is set to one in each state.
39 Fall 2010ECE 331  Digital System Design39 Example: State Assignments For a fourstate FSM, three possible state assignments are: StateBinaryGraycodeOnehot S0S0 00 0001 S1S1 01 0010 S2S2 10110100 S3S3 11101000 # of FF224
40 Fall 2010ECE 331  Digital System Design40 Questions?
0 thoughts on “State Assignment And Encoded State Table Ece”