1
{0}/0
{0}/1
B
Outputs={0,1, absent}
Outputs={0,1, absent}
Figure 4.4: Example of a cascade composition. The composed state machine is
on the right.
146
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
and alphabets
Inputs = Outputs = {0, 1, absent}.
The initial state is
initialState = (0, 0).
The update function is given by the table:
current
(next state, output) for input
state
0
1
absent
(0,0)
((0,0),0)
((1,1),1)
((0,0), absent)
(0,1)
((0,0),1)
((1,1),0)
((0,1), absent)
(1,0)
((1,1),1)
((0,0),0)
((1,0), absent)
(1,1)
((1,1),0)
((0,0),1)
((1,1), absent)
The update function is also presented in the state transition diagram of Figure 4.4.
The self-loops corresponding to the stuttering input symbol absent are not shown
in the diagram.
Observe from the table or the diagram that states (0, 1) and (1, 0) are not reachable
from the initial state. A state s is said to be reachable if some sequence of input
symbols can take the state machine from the initial state to s. This suggests that a
simpler machine with fewer states would exhibit the same input/output behaviors.
In fact, notice from the table that the input is always equal to the output! A trivial
one-state machine can exhibit the same input/output behaviors. (Exercise 8 gives a
procedure for calculating the reachable states of an arbitrary state machine.)
The simple behavior of the composite machine is not immediately apparent from
Figure 4.4. We have to systematically construct the composite machine to derive
this simple behavior. In fact, this composite machine can be viewed as an encoder
and decoder, because the input bit sequence is encoded by a distinctly different
bit sequence (the intermediate signal in Figure 4.4), and then the second machine,
given the intermediate signal, reconstructs the original.
This particular encoder is known as a differential precoder. It is “differential” in
that when the input symbol is 0, the intermediate signal sample is unchanged from
the previous sample (whether it was 0 or 1), and when the input symbol is 1, the
sample is changed. Thus, the input symbol indicates change in the input with a 1,
and no change with a 0. Differential precoders are used when it is important that
Lee & Varaiya, Signals and Systems
147
4.4. PRODUCT-FORM INPUTS AND OUTPUTS
the average number of 1’s and 0’s is the same, regardless of the input sequence that
is encoded.
4.4
Product-form inputs and outputs
In the state machine model of (3.1), at each step the environment selects one input symbol
to which the machine reacts and produces one output symbol. Sometimes we wish to
model the fact that some input values are selected by one part of the environment, while
other input values are simultaneously selected by another part. Also, some output values
are sent to one part of the environment, while other output values are simultaneously sent
to another part. The product-form composition permits these models.
The machine in Figure 4.5 is shown as a block with two distinct input and output arrows.
The figure suggests that the machine receives inputs from two sources and sends outputs
to two destinations. In the answering machine example of Chapter 3, for instance, the
end greeting input value might originate in a physically different piece of hardware in the
machine than the offhook value.
The distinct arrows into and out of a block are called ports. Each port has a set of values
called the port alphabet associated with it, as shown in figure 4.5. Each port alphabet
must include a stuttering element. The set Inputs of input values to the state machine
is the product of the input sets associated with the ports. Of course, the product can be
constructed in any order; each ordering results in a distinct (but bisimilar) state machine
model.
InputsA
OutputsA
( States, Inputs, Outputs, update, initialState )
InputsB
Inputs = InputsA × InputsB
OutputsB
Outputs = OutputsA × OutputsB
Figure 4.5: State machine with product-form inputs and outputs.
148
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
In Figure 4.5 there are two input ports and two output ports. The upper input port can
present to the state machine any value in the alphabet InputsA, which includes absent, its
stuttering element. The lower port can present any value in the set InputsB, which also
includes absent. The input value actually presented to the state machine in a reaction is
taken from the set
Inputs = Inputs ×
.
A
InputsB
The stuttering element for this alphabet is the pair (absent, absent). The output value
produced by a reaction is taken from the set
Outputs = Outputs ×
.
A
OutputsB
If the output of the n-th reaction is (yA(n), yB(n)), then the upper port shows yA(n) and the
lower port shows yB(n). These can now be separately presented as inputs to downstream
state machines. Again, the stuttering element is (absent, absent).
Example 4.3: The answering machine of Figure 3.1 has input alphabet
Inputs = {ring, offhook, end greeting, end message}.
In a typical realization of an answering machine, ring and offhook come from a sub-
system (often an ASIC, or application-specific integrated circuit) that interfaces
to the telephone line. The value end greeting comes from another subsystem, such
as a magnetic tape machine or digital audio storage device, that plays the answer
message. The value end message comes from a similar, but distinct, subsystem that
records incoming messages. So a more convenient model will show three separate
factors for the inputs, as in figure 4.6. That figure also shows the outputs in prod-
uct form, anticipating that the distinct output values will need to be sent to distinct
subsystems.
Several features distinguish the diagram in Figure 4.6 from that of Figure 3.1. Each state except the idle state has acquired a self-loop labeled stutter, which is a name
for the guard
stutter = {(absent, absent, absent)}.
This self loop prevents the state machine from returning to the idle state (via the
else transition) when nothing interesting is happening on the inputs. Usually, there
will not be a reaction if nothing interesting is happening on the inputs, but because
Lee & Varaiya, Signals and Systems
149
4.4. PRODUCT-FORM INPUTS AND OUTPUTS
of synchrony, this machine may be composed with others, and all machines have
to react at the same time. So if anything interesting is happening elsewhere in the
system, then this machine has to react even though nothing interesting is happening
here. Recall that such a reaction is called a stutter. The state does not change, and
the output symbol produced is the stuttering element of the output alphabet.
Each guard now consists of a set of triples, since the product-form input has three
components. The shorthand “(*, offhook, *)” on the arc from the record message
stutter
s e n t } b
{( absent , ring , absent )}
s e n t } b
{( absent , ring , absent )}
else
e r , a
count1
sw
stutter
n
{ a
{ e n d g r e e t i n g , a
{( absent , ring , absent )}/
( answer , absent , absent )
idle
count2
s e n t } b
else
ff h o o k , a
g , o
else
play greeting
s e n t }
{ rin
b
{ r e c o r d e d ,
a
stutter
else
stutter
s e n t } b
{(*, offhook ,*)}
s e n t }
record
b
e s s a g e , a
message
{( end greeting , absent , absent )}/
( absent , absent , record )
{ e n d m
else /( absent , recorded , absent )
{ re c o r d , a
NOTE : stutter = {( absent , absent , absent )}
Figure 4.6: Answering machine with product-form inputs and outputs has three
input ports and three output ports.
150
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
state to the idle state represents a set,
(∗, offhook, ∗) = {
(absent, offhook, absent),
(end greeting, offhook, absent),
(absent, offhook, end message),
(end greeting, offhook, end message)}.
The “*” is a don’t care or wildcard notation. Anything in its position will trigger
the guard.
Because there are three output ports, the output symbols are also triples, but most
of them are implicitly (absent, absent, absent).
( States, Inputs, Outputs, update, initialState )
OutputsA1
InputsA
( StatesA, InputsA, OutputsA, updateA, initialStateA )
OutputsA2
OutputsA2 ! InputsB1
OutputsB
InputsB2
( StatesB, InputsB, OutputsB, updateB, initialStateB )
Figure 4.7: More complex composition.
Lee & Varaiya, Signals and Systems
151
4.5. GENERAL FEEDFORWARD COMPOSITION
4.5
General feedforward composition
Given that state machines can have product-form inputs and outputs, it is easy to construct
a composition of state machines that combines features of both the cascade composition
of Figure 4.3 and the side-by-side composition of Figure 4.1. An example is shown in Figure 4.7. In that figure,
Outputs
=
×
A
OutputsA1
OutputsA2
Inputs
=
×
.
B
InputsB1
InputsB2
Notice that the bottom port of machine A goes both to the output of the composite machine
and to the top port of machine B. Sending a value to multiple destinations like this is called
forking. In Exercise 1 at the end of this chapter you are asked to define the composite
machine for this example.
Example 4.4: We compose the answering machine of figure 4.6 with a playback
system, shown in Figure 4.8, which plays messages that have been recorded by
the answering machine. The playback system receives the recorded input symbol
{ recorded , absent}
else
{ light on, light off, absent}
{(*, play,*)}/
{( recorded ,*,*)}/
( absent, play messages)
( light on, absent)
message
pending
{ play, absent}
else
no
playing
messages
else
{ done playing, absent}
{(*, *, done playing)}/
( light off, absent)
{ play messages, absent}
Figure 4.8: Playback system for composing with the answering machine.
152
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
from the answering machine whenever the answering machine is done recording
a message. Its task is to light an indicator that a message is pending, and to wait
for a user to press a play button on the answering machine to request that pending
messages be played back. When that button is pressed, all pending messages are
played back. When they are done being played back, then the indicator light is
turned off.
The composition is shown in Figure 4.9. The figure shows a number of other com-
ponents, not modeled as state machines, to help understand how everything works
in practice. These other components are shown as three-dimensional objects, to
greeting
playback device
{ answer}
{ end greeting}
{ light on, light off}
{ recorded message}
AnsweringMachine
light
{ ring, offhook}
Playback
{ record}
{ end message}
{ play}
{ done playing}
{ play messages}
recording device
telephone
message playback
play
line
device
button
interface
Figure 4.9: Composition of an answering machine with a message playback ma-
chine. The three-dimensional boxes are physical components that are not mod-
eled as state machines. They are the sources of some inputs and the destinations
of some outputs.
Lee & Varaiya, Signals and Systems
153
4.6. HIERARCHICAL COMPOSITION
emphasize their physicality. We have simplified the figure by omitting the absent
elements of all the sets. They are implicit.
A telephone line interface provides ring and offhook when these are detected. De-
tection of one of these can trigger a reaction of the composite machine. In fact, any
output symbol from any of the physical components can trigger a reaction of the
composite machine. When AnsweringMachine generates the answer output sym-
bol, then the “greeting playback device” plays back the greeting. From the perspec-
tive of the state machine model, all that happens is that time passes (during which
some reactions may occur), and then an end greeting input symbol is received. The
recording device works similarly. When AnsweringMachine generates a recorded
output symbol, then the Playback machine will respond by lighting the indicator
light. When a user presses the play button the input symbol play is generated, the
composite machine reacts, and the Playback machine issues a play messages out-
put symbol to the “message playback device.” This device also allows time to pass,
then generates a done playing input symbol to the composite state machine.
If we wish to model the playback or recording subsystem in more detail using finite
state machines, then we need to be able to handle feedback compositions. These
are considered below.
4.6
Hierarchical composition
By using the compositions discussed above, we can now handle any interconnection of
state machines that does not have feedback. Consider for example the cascade of three
state machines shown in Figure 4.10. The composition techniques we have discussed so
far involved only two state machines. It is easy to generalize the composition in Figure
4.3 to handle three state machines (see Exercise 2), but a more systematic method might be to apply the composition of Figure 4.3 to compose two of the state machines, and then
apply it again to compose the third state machine with the result of the first composition.
This is called hierarchical composition.
In general, given a collection of interconnected state machines, there are several ways
to hierarchically compose them. For example, in Figure 4.10, we could first compose
machines A and B to get, say, machine D, and then compose D with C. Alternatively, we
could first compose B and C to get, say, machine E, and then compose E and A. These
154
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
two procedures result in different but bisimilar state machine models (each simulates the
other).
4.7
Feedback
In simple feedback systems, an output from a state machine is fed back as an input to the
same state machine. In more complicated feedback systems, several state machines might
be connected in a loop; the output of one eventually affects its own input through some
intervening state machines.
Feedback is a subtle form of composition in the synchronous model. In synchronous
composition, in a reaction, the output symbol of a state machine is simultaneous with the
input symbol. So the output symbol of a machine in feedback composition depends on an
input symbol that depends on its own output symbol!
( States, Inputs, Outputs, update, initialState )
( StatesA, InputsA, OutputsA, updateA, initialStateA )
( StatesB, InputsB, OutputsB, updateB, initialStateB )
( StatesC, InputsC, OutputsC, updateC, initialStateC )
Figure 4.10: Cascade composition of three state machines. They can be com-
posed in different ways into different, but bisimilar, state machines.
Lee & Varaiya, Signals and Systems
155
4.7. FEEDBACK
x
y
f
g
Figure 4.11: Illustration of a fixed point problem.
We frequently encounter such situations in mathematics. A common problem is to find x
such that
x = f (x)
(4.6)
for a given function f . A solution to this equation, if it exists, is called a fixed point in
mathematics. It is analogous to feedback because the ‘output’ f (x) of f is equal to its
‘input’ x, and vice versa. The top diagram in Figure 4.12 illustrates a similar relationship:
the state machine’s output symbol is the same as its (simultaneous) input symbol.
A more complicated problem, involving two equations, is to find x and y so that
x = f (y), and y = g(x).
The analogous feedback composition has two state machines in feedback, with the struc-
ture of Figure 4.11.2
A fixed-point equation like (4.6) may have no fixed point, a unique fixed point, or multiple
fixed points. Take for example the function f : R → R where ∀x ∈ R, f (x) = 1 + x2. In
this case, (4.6) becomes x = 1 + x2, which has no fixed point in the reals. If f (x) = 1 − x,
(4.6) becomes x = 1 − x, which has a unique fixed point, x = 0.5. Lastly, if f (x) = x2,
(4.6) becomes x = x2, which has two fixed points, x = 0 and x = 1.
In the context of state machines, a feedback composition with no fixed point in some
reachable state is a defective design; we call such a composition ill-formed. We can not
evaluate an ill-formed composition. Usually, we also wish to exclude feedback composi-
tions that have more than one non-stuttering fixed point in some reachable state. So these
too are ill-formed. A feedback composition with a unique non-stuttering fixed point in all
reachable states is well-formed. Fortunately, it is easy to construct well-formed feedback
2Figure 4.9 would be a feedback composition if any of the three recording or playback devices were
modeled as state machines. In the figure, however, these devices are part of the environment.
156
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
compositions, and they prove surprisingly useful. We explore this further, beginning with
a somewhat artificial case of feedback composition with no inputs.
4.7.1