Digital Signal Processing Reference
In-Depth Information
symbol triggering the corresponding state transition and
action
specifies the
output symbol to be produced by the
FSM
reaction. The edge without source state
points to the initial state.
One reaction of the
FSM
is given by triggering a single enabled state transition.
An enabled state transition is an outgoing transition from the current state where
the guard matches the current input symbol. Thereby, the
FSM
changes to the
destination state of the transition and produces the output symbol specified by
the action. To simplify the notation, each state is assumed to have implicit self
transitions for input symbols not used as guards for any explicit transition. The
action in such cases is empty or the output symbol
∈
Δ
ε
∈
Δ
indicating the absence of
an output value.
FSMs
as presented in Definition
1
can be easily extended to multiple input signals
and multiple output signals. In such a scenario, input and output symbols are defined
by subdomains, i.e.,
Δ
=
Δ
1
×···×
Δ
m
.
The *charts approach allows nesting of dataflow graphs and
FSMs
by allowing
the refinement of a dataflow actor via
FSMs
and allowing an
FSM
state to be refined
via a dataflow graph. We first discuss how
FSMs
are used to refine dataflow actors.
Σ
=
Σ
1
×···×
Σ
n
and
2.2.1
Refining Dataflow Actors via
FSMs
To u se an
FSM
as a refinement for a dataflow actor, the consumption and production
rates have to be determined from the
FSM
for the refined actor. However, the
derivation of the consumption and production rates depends on the Model of
Computation (
MoC
) of the dataflow graph containing the actor. The tokens on the
channels connected to the refined dataflow actor are mapped to the input alphabet
Σ
to refer to the
n
th
token on the channel connected to the input port
i
. In the action of the
FSM
, we will
use
o
of the refining
FSM
. In the guard of the
FSM
, we will use
i
[
n
]
to refer to the
n
th token to produce on the channel connected to the output
port
o
. Each unique
i
[
n
]
Σ
m
associated with it and the cross
product of these subdomains form the input alphabet to the
FSM
. The same is true
for
o
[
n
]
has a symbol subdomain
, thus perfectly matching the
FSM
model (see
from the output alphabet of the
FSM
, which is used to derive a token value to be
produced on each outgoing edge of the actor.
FSM in Dynamic Dataflow:
If an
FSM
refines a
DDF
actor, then each state of
the
FSM
is associated with a number of tokens that will be consumed by the next
firing of the actor. The semantics is as follows: For a given state
q
of the
FSM
,the
number of consumed tokens is determined by examining each outgoing transition
of the state. For each input port
i
of the actor, the maximum index
n
is determined
with which the input port
i
occurs in any of the transitions leaving the state
q
.Ifthe
input port
i
does not occur in any transition, an index of
[
n
]
and the output alphabet
Δ
1 is assumed. Then, for
the given state
q
the consumption rate for each input port
i
is the maximum index
n
incremented by one. Note that this derivation of the consumption rates implicitly
−