Hardware Reference
In-Depth Information
When merging is not possible, the conversion is trivial, consisting simply of a
change of notation (from Moore to Mealy style). To do so, just bring outside the output
values marked inside the state circles and associate them with the corresponding
pre-
ceding
(inward) transitions. An example is presented in i gure 1.9.
The merging of two states is possible when they fuli ll the following two requisites:
1) Their sets of
outward
transitions are exactly equal.
2) The pairs of equal outward transitions (one from each state) go to the same states.
An example is presented in i gures 1.10a-c. The original Moore FSM, with four
states, is presented in i gure 1.10a. Note that states A and B have the same set of
outward
transitions (
x
=
x
1
,
x
=
x
2
) and that the equal transitions go to the same states
(from both A and B, the transitions governed by
x
=
x
1
go to state C, while those
governed by
x
=
x
2
go to state D). Therefore, A and B can be merged. To do so, i rst
Figure 1.9
Moore-to-Mealy conversion when state merging is not possible (just a change of notation).
Figure 1.10
Moore-to-Mealy conversion principle. (a) Original Moore machine. (b) Moore-to-Mealy notation
change. (c) Merging of states A and B. (d-f) Another example, following the same procedure.