CHAPTER 14
Derivation of State Graphs and Tables
Contents
14.1 Design of a Sequence Detector
14.2 More Complex Design Problems
14.3 Guidelines for Construction of State Graphs
14.4 Serial Data Code Conversion
14.5 Alphanumeric State Graph Notation
Objectives
1. Given a problem statement for the design of a Mealy or Moore
sequential circuit, find the corresponding state graph and table.
2. Explain the significance of each state in your graph or table
in terms of the input sequences required to reach that state.
3. Check your state graph using appropriate input sequences.
14.1 Design of a Sequence Detector
Fig 14.1 Sequence Detector to be Designed
Z =
(time:
10
11
12
13 14 15)
14.1 Design of a Sequence Detector
Fig 14.2 and 14.3 : Formation of State Graph
14.1 Design of a Sequence Detector
Fig 14.4 Mealy State Graph for Sequence Detector
14.1 Design of a Sequence Detector
Table 14-1, State Table
Present
Output
Next State
Present
state
X=0
X=1
X=0
X =1
S0
S1
S2
S0
S2
S0
S1
S1
S1
0
0
0
0
0
1
Table 14-2, Transition Table with State Assignment
A+ B+
AB
X=0
X=1
X=0
X =1
00
01
10
00
10
00
01
01
01
0
0
0
0
0
1
14.1 Design of a Sequence Detector
Map for the output function Z (from table 1,2)
14.1 Design of a Sequence Detector
Fig 14.5: Final Circuit
14.1 Design of a Sequence Detector
Moore Machine Design Process
14.1 Design of a Sequence Detector
Fig 14.6 Moore State Graph for Sequence Detector
14.1 Design of a Sequence Detector
Table 14-3 State Table
Next State
Present
state
X=0
S0
S1
S2
S3
S0
S2
S0
S2
Table 14-4 Transition Table
with State assignment
A+ B+
X=1
Present
Output (Z)
AB
X=0
X=1
S1
S1
S3
S1
0
0
0
1
00
01
11
10
00
11
00
11
01
01
10
01
0
0
0
1
14.2 More Complex Design Problems
The circuit to be designed (Mealy)
Output Z=1 if input sequence ends in either 010 or 1001
X=
Z=
14.2 More Complex Design Problems
Fig 14.7
formation of state graph ( step1 )
state
sequence received
S0
S1
S2
S3
reset
0
01
010
14.2 More Complex Design Problems
Fig 14.8
formation of state graph ( step2 )
state
sequence ends in
S0
S1
S2
S3
S4
S5
reset
0 (but not 10)
01
10
1 (but not 01)
100
14.2 More Complex Design Problems
Fig 14.9 Completed State Graph for a Sequence Detector to be Designed
state
sequence ends in
S0
S1
S2
S3
S4
S5
reset
0 (but not 10)
01
10
1 (but not 01)
100
14.2 More Complex Design Problems
The circuit to be designed (Moore)
Output Z=1 if the total number of 1s received is odd and at least
two consecutive 0s have been received
X=
Z=
(0)
14.2 More Complex Design Problems
Fig 14.10 formation of state graph ( step1)
14.2 More Complex Design Problems
Fig 14.11 formation of state graph ( step2 )
state
sequence received
S0
S1
S2
S3
S4
reset or even 1s
odd 1s
even 1s and ends in 0
even 1s and 00 has occurred
00 has occurred and odd 1s
14.2 More Complex Design Problems
Fig 14.12 Completed State Graph for a Sequence Detector to be Designed
state
Input sequences
S0
S1
S2
S3
S4
S5
reset or even 1s
odd 1s
even 1s and ends in 0
even 1s and 00 has occurred
odd 1s and 00 has occurred
odd 1s and ends in 0
14.3 Guidelines for Construction of State Graphs
1. Construct some sample input and output sequences to make sure that you understand
the problem statement.
2. Determine under what conditions ,if any, the circuit should reset to its initial state.
3. If only one or two sequences lead to a non-zero output, a good way to start is to construct
a partial state graph for those sequences.
4. Determine what sequences or groups of sequences must be remembered by the circuit and
set up states accordingly.
5. Each time you add an arrow to the state graph, determine it can go to one of the previously
defined states or whether a new state must be added
6. Check your state graph to make sure there is one and only one path leaving each state
for each combination of values of the input variables
7. When your state graph is complete, test it by applying the input sequences formulated in part1
and making sure the output sequences are correct
14.3 Guidelines for Construction of State Graphs
Example 1 : Z=1 when input sequence 0101 or 1001 occurs.
The circuit resets after every four inputs. Mealy Circuit
A typical sequence of input and output
X =
0101
0010
1001
0100
Z =
0001
0000
0001
0000
14.3 Guidelines for Construction of State Graphs
Fig 14.13 Partial State Graph for Example 1
state
sequence received
S0
S1
S2
S3
S4
Reset
0
1
01 or 10
010 or 100
14.3 Guidelines for Construction of State Graphs
Fig 14.14 Complete State Graph for Example 1
state
sequence received
S0
S1
S2
S3
S4
S5
Reset
0
1
01 or 10
010 or 100
two inputs received, no 1
output is possible
three inputs received, no 1
output is possible
S6
14.3 Guidelines for Construction of State Graphs
Example 2 : Z1=1 every time the input sequence 100 is completed
Z2=1 every time the input sequence 010 is completed
Once Z2=1 occurred, Z1=1 can never occur but not vice versa
Mealy circuit
A typical sequence of input and output
X = 1 0 0 1
0 1 0
0 1
1 0
Z1 = 0 0 1 0
1 0 0
0 0
0 0
Z2 = 0 0 0 0
0 0 1
1 0
0 1
14.3 Guidelines for Construction of State Graphs
Fig 14.15 Partial Graphs for Example 2
14.3 Guidelines for Construction of State Graphs
Table 14-5 State Descriptions for Example 2
stats
S0
S1
S2
S3
S4
S5
S6
S7
Description
No progress on 100
Progress of 1 on 100
Progress of 10 on 100
No progress on 100
Progress of 10 on 100
No progress on 010
No progress on 010
Progress of 0 on 010
Progress of 0 on 010
Progress of 01 on 010
010 has never occurred
Progress of 0 on 010
Progress of 01 on 010
No progress on 010
010 has occurred
14.3 Guidelines for Construction of State Graphs
Fig 14.16 State Graphs for Example 2
14.3 Guidelines for Construction of State Graphs
Table 14-6
Present
state
Next
X=0
State
X=1
Output
X= 0
(Z1 Z2)
X=1
S0
S1
S2
S3
S4
S5
S6
S7
S3
S2
S3
S3
S5
S5
S5
S5
S1
S1
S4
S4
S1
S6
S7
S7
00
00
10
00
01
00
01
00
00
00
00
00
00
00
00
00
14.3 Guidelines for Construction of State Graphs
Example 3: Two inputs X1, X2, One output Z
(a) The input sequence X1X2=01, 11 cause the output 0
(b) The input sequence X1X2=10, 11 cause the output 1
(c) The input sequence X1X2=10, 01 cause the output to change
Previous
Input (X1X2)
Output
(Z)
State
Designation
00 or 11
00 or 11
01
01
10
10
0
1
0
1
0
1
S0
S1
S2
S3
S4
S5
14.3 Guidelines for Construction of State Graphs
Table 14-7
Present
Next state
State
S0
S1
S2
S3
S4
S5
0
1
0
1
0
1
X1X2
00
01
11
10
S0
S1
S0
S1
S0
S1
S2
S3
S2
S3
S3
S2
S0
S1
S0
S0
S1
S1
S4
S5
S4
S5
S4
S5
14.3 Guidelines for Construction of State Graphs
Fig 14-17 State Graph for Example 3
14.4 Serial Data Code Conversion
Fig 14.18 Serial Data Transmission
14.4 Serial Data Code Conversion
Fig 14.19 Coding Schemes for Serial Data Transmission
14.4 Serial Data Code Conversion
Fig 14.20 Mealy circuit for NRZ to Manchester Conversion
14.4 Serial Data Code Conversion
Fig 14.20 Sequence Detector to be Designed
Present
Next State
Output (Z)
State
X=0
X=1
X=0
X=1
S0
S1
S2
S1
S0
-
S2
S0
0
1
-
1
0
(d) State table
14.4 Serial Data Code Conversion
Fig 14.21 Moore Circuit for NRZ-to-Manchester Conversion
14.4 Serial Data Code Conversion
Fig 14.21 Moore Circuit for NRZ-to-Manchester Conversion
Present
Next State
Present
State
X=0
X=1
Output (Z)
S0
S1
S2
S3
S1
S2
S1
-
S3
S3
S0
0
0
1
1
(c) State table
14.5 Alphanumeric State Graph Notation
Fig 14.22 State Graphs with Variable Names on Arc Labels
14.5 Alphanumeric State Graph Notation
Table 14-8 State Table for Fig 14-22
PS
NS
FR =
S0
S1
S2
The result :
Output
00
01
10
11
Z1
Z2
Z3
S0
S1
S2
S2
S0
S1
S1
S2
S0
S1
S2
S0
1
0
0
0
1
0
0
0
1
F + F ' R + F ' R' = F + F ' = 1
If we AND together every possible pair of arc labels emanating from S0, we get
F F ' R = 0,
F F ' R ' = 0,
F ' R F ' R' = 0,
