short
long
{ buy, sell, absent}
over
over
long
short
y
longTerm
{( x( n) , y( n)) | x( n) < y( n) } / sell 35
xy
30
price
25
20
15
closing price 10
5
0
2
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
x10
day
buy
absent
sell
2
x10
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
day
Figure 6.1: An implementation of the classical moving average cross-over method
for trading stocks.
234
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
Example 6.1: Moving averages are popular on Wall Street for detecting trends in
stock prices. But in using them, a key question arises: how long should the moving
average be? A short-term moving average might detect short-term trends, while a
long-term moving average might detect long term trends. A classical method com-
bines the two and compares them to generate buy and sell signals. If the short-term
trend is more sharply upward than the long term trend, a buy signal is generated.
If the short term trend is more sharply downward than the long term trend, a sell
signal is generated.
A system implementing this moving average cross-over method is shown in
Figure 6.1. The input is the discrete-time signal price : Z → R representing the
closing price of a stock each day. The LTI systems shortTerm and longTerm are
both moving average systems, but shortTerm averages fewer successive inputs than
longTerm. The outputs of these systems are the discrete-time signals x and y. The
finite state machine reacts on each sample from these signals. It begins in the state
short over long. The transition out of this state has the guard
{(x(n),y(n)) | x(n) > y(n)}.
When this transition is taken, a buy signal is generated. The sell signal is generated
similarly. The plots below show the buy and sell signals generated by a (synthetic)
sequence of stock prices.
This example illustrates a simple form of technical stock trading. In this extreme
form, it has the controversial feature that it ignores the fundamentals of the com-
pany whose stock is being traded. It is using the stock price alone as the indicator
of worth. In fact, much more sophisticated signal processing methods are used by
technical stock traders, and they often do take as inputs other quantifiers of com-
pany worth, such as reported revenues and profits.
6.2
Modal models
In the previous section, time-based systems are combined with state machines as peers. A
richer interaction is possible with a hierarchical combination. The general structure of a
Lee & Varaiya, Signals and Systems
235
6.2. MODAL MODELS
HybridSystem
guard/output
action
events
...
{
...
} events
state
state
name
name
...
{
time-based
signals
...
action
} time-based
guard/output
signals
action
time-based system
time-based system
Figure 6.2: Notation for hybrid systems.
hierarchical hybrid system model is shown in figure 6.2. In that figure, there is a two-state
finite state machine. There are some changes to the notation, however, from what was
First, notice that the inputs and outputs include both event signals and time-based signals.
Second, notice that each state of the state machine is associated with a time-based system,
called the refinement of the state. The refinement of a state gives the time-based behavior
of HybridSystem while the machine is in that state. Thus, the states of the state machine
define modes of operation of the system, where the behavior in a given mode is given
by the refinement. A hybrid system is sometimes called a modal model for this reason.
The refinement has access to all the inputs of HybridSystem, and produces the time-based
output signals of HybridSystem while the machine is in its mode.
Note that the term “state” for such a hybrid system can become confusing. The state
machine has states, but so do the refinement systems (unless they are memoryless). When
there is any possibility of confusion we explicitly refer to the states of the machine as
modes, and we refer to the states of the refinement as refinement states. The (complete)
state of the hybrid system is a pair (m, s) where m is the mode and s is the state of the
time-based refinement system associated with mode m.
236
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
Another difference from the notation used in chapters 3 and 4 is that state transitions in the machine have, in addition to the usual guard and output notations, an action. The action
will typically set the initial refinement state of the time-based system in the destination
mode.
The guards are, as usual, sets. However, we need for the guards to be rich enough that
a transition can be triggered by a particular value of a refinement state or by a value of a
time-based input. Thus, the elements of the guards are tuples containing values of input
events, time-based signals, and the refinement states. In the state machines in chapters
3 and 4, the elements of the guards only contained values of input events. For hybrid systems, we add time-based signals and refinement states.
Example 6.2: Overload of an electronic system might be modeled by a state tran-
sition that is triggered by the magnitude of the current refinement state exceeding
some threshold.
On the other hand, when the system is in some mode, the refinement state is only affected
by the time-based inputs. It is not affected by the event inputs. This keeps the time-based
models simple, so that they don’t have to deal with stuttering inputs.
Correspondingly, the time-based outputs are generated by the refinement, and hence need
not be mentioned after the slash on the transitions.
The state machine may react at any time in the time base T . The mode in which it is
before this reaction is called the current mode. It will take a discrete state transition
and switch to the destination mode if the input values and the refinement state at that
time match a guard. If it does not take a discrete state transition, then the state machine
stutters. In either case, the refinement of the current mode also reacts to the time-based
inputs, changes its state and produces outputs.
Example 6.3:
Many high-end audio systems offer “digital signal processing.”
Such a system typically has an embedded computer (a digital signal processor or
DSP, see box on page 402). This computer is used to process the audio signal
in various ways, for example to add reverberation or to perform frequency selec-
tive filtering. A particularly simple function that might be performed is loudness
compensation, something offered by all but the cheapest audio systems.
Lee & Varaiya, Signals and Systems
237
6.2. MODAL MODELS
LoudnessCompensation
{ on, off, absent}
{( u( n) , x( n) , s( n), y( n)) | u( n) = on}
y
flat
boost
x
{( u( n) , x( n) , s( n), y( n)) | u( n) = off}
s( n+1) = As( n) + bx( n)
s( n+1) = As( n) + bx( n)
y( n) = x( n)
y( n) = c T s( n) + dx( n)
Figure 6.3: This system implements loundness compensation, described in ex-
ample 6.3
238
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
At low volumes, the human ear is less sensitive to low frequencies (base notes)
than to high frequencies. Loudness compensation boosts the low frequencies. This
is done simply by implementing a filter, which is a linear time-invariant system that
can be described by a state-space model, as in the previous chapter. Thus, there are
two modes, one where the low frequencies are boosted (using the filter), and one
where they are not.
A simple realization of loudness compensation offers a switch on a control panel to
turn on and off the compensation. Figure 6.3 shows a hybrid system that reacts to
input events from this switch to select from among two modes. The upper input is
simply an event indicating the position of the control switch when it is thrown. The
lower input x is a discrete-time signal, probably sampled at 44,100 samples/second,
the CD rate. The LoudnessCompensation hybrid system has two modes. In the flat
mode, the output y is simply set equal to the input x. That is, if Tf lat ⊂ Z is the time
indexes during which the machine is in the flat mode, then
∀ n ∈ Tflat, y(n) = x(n).
This (obviously) does not boost low frequencies, since the output is equal to the
input.
When the on event occurs, the machine transitions to the boost mode, where the
filter is applied to the input x. This is done using the state update and output equa-
tions
∀ n ∈ Tboost, s(n + 1) = As(n) + bx(n)
y(n)
=
cT s(n) + dx(n),
where A, b, c, d are chosen to boost the low frequencies (how to do that is explained
in Chapter 9).
Note that in the flat mode, even though the output equation does not depend on the
state, the state update equation is still applied. This ensures that when switching
between states, no glitches are heard in the audio signal. The state of the boost
refinement is maintained even when the mode is flat.
This loudness compensator is not very sophisticated. A more sophisticated version
would have a set of compensation filters and would select among them depending
on the volume level. This is explored in Exercise 1.
Lee & Varaiya, Signals and Systems
239
6.3. TIMED AUTOMATA
We consider a sequence of special cases of hybrid systems. Although the next few exam-
ples are all continuous-time models, it is easy to construct similar discrete-time models.
6.3
Timed automata
Timed automata are the simplest continuous-time hybrid systems. They are modal models
where the time-based refinements have very simple dynamics; all they do is measure the
passage of time. Such refinements are called clocks. The resulting models are finite state
machines (automata) with time. Note that although all the examples in this section use
continuous time, discrete-time versions are very similar.
A clock is modeled by a first-order differential equation,
∀ t ∈ Tm, ˙s(t) = a,
where s : R → R is a function, s(t) is the value of the clock at time t, and Tm ⊂ T is the
subset of time during which the hybrid system is in mode m. The rate of the clock, a, is a
constant while the system is in this mode.
Example 6.4: Suppose we want to produce a sequence of output events called tick
with the time between two consecutive ticks alternating between 1 and 2 seconds.
That is, we want to produce a tick at times 1, 3, 4, 6, 7, 9, · · · .
A hybrid system tickGenerator that does this is illustrated in Figure 6.4. There
are two modes labeled mode 1 and mode 2. The refinement state in each mode
is the value of a clock at time t, denoted by s ∈ R. So at any time t the state of
tickGenerator is the pair (mode(t), s(t)). The output is the event signal v and the
time-based signal s. There is no input.
In both modes, s evolves according to the differential equation ˙
s(t) = 1, where ˙
s(t)
is the derivative of s with respect to time evaluated at some time t. Thus, s simply
measures the passage of time, with its value rising 1 second for every second of
elapsed time.
The behavior of the system is shown in Figure 6.5. At time 0, as indicated by the
bold arrow in Figure 6.4, the system initially enters mode 1. The bold arrow has an
action, “s(0) := 0,” which sets s(0) to 0. The notation “:=” is used instead of “=”
to emphasize that this is an assignment, not an assertion (see Section A.1.1).
240
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
tickGenerator { s( t) | s( t) = 1} / tick
s( t) := 0
v( t) ∈{ tick, absent}
mode 1
mode 2
s( t) ∈ Reals
s(0) := 0 { s( t) | s( t) = 2} / tick
s( t) := 0
. s( t) = 1
. s( t) = 1
Figure 6.4: This hybrid system generates tick at time intervals alternating be-
tween 1 and 2 seconds. It is a timed automaton.
Lee & Varaiya, Signals and Systems
241
6.3. TIMED AUTOMATA
mode( t)
... t
(a)
0
1
3
4
s( t)
... t
(b)
v( t)
tick
...
absent
t
(c)
Figure 6.5: (a) The modes of the hybrid system of Figure 6.4, (b) the refinement
state s, and (c) the discrete event output v.
In this example, there is no input, so a guard is a subset of the possible values (R)
of the refinement states. The guard on the transition from mode 1 to mode 2 is
{s(t) | s(t) = 1},
which is satisfied one time unit after beginning. For all t ∈ [0, 1], s(t) = t. At time
t = 1, this guard is satisfied, the transition is taken, and the output event v(1) = tick
is produced. For all t ∈ [0, 1), v(t) has value absent.
This transition also has an action, “s(t) := 0,” which resets s to zero. This gives the
initial condition for the refinement system of the destination mode. In our defini-
tion, at time t = 1, s(t) = 1, even though the action seems to contradict this. This
is emphasized in Figure 6.5 by showing with a bold dot the value of s at each dis-
continuity. The action s(t) := 0 is merely providing the initial conditions for the
refinement of the destination mode. But the destination mode is not active until
t > 1, so the action is setting s(1+) to 0, where 1+ denotes a time infinitesimally
larger than 1.
242
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
For t ∈ (1, 3], the system remains in mode 2, evolving according to the differential
equation
˙
s(t)
=
1,
s(1)
=
0.
So for 1 < t ≤ 3,
Z t
s(t) = s(1) +
1dt = t − 1.
1
At time t = 3, the guard on the arc from mode 2 to mode 1 is satisfied, so the
transition is taken. The output event tick is again produced, and s is reset to 0 again.
Notice in Figure 6.5 that the output v is absent for all but a few discrete values of t ∈ R.
This signal is called a discrete event signal for this reason. Of course, this signal can also
be reinterpreted as a sequence of tick events with an arbitrary number of stuttering events
in between. That signal could therefore be supplied as input to an ordinary state machine,
enabling compositions of ordinary state machines with hybrid systems.
Also notice in Figure 6.5 that the hybrid system evolves in alternating phases: there is a
time-passage phase in which the system stays in the same mode and its refinement state
changes with the passage of time; this is followed by an instantaneous discrete-event
phase in which a mode transition occurs, an output event is produced, and the refinement
state in the destination mode is initialized. In the figure, the time-passage phases are
(0, 1], (1, 3], (3, 4], · · · and the discrete-event phases occur at 1, 3, 4, · · · .
Transitions between modes have actions associated with them. Sometimes, it is useful to
have transitions from one mode back to itself, just so that the action can be realized. This
is illustrated in the next example.
Example 6.5: Figure 6.6 shows a hybrid system representation of the 60-minute
parking meter considered in Chapter 3. In the version in Figure 3.6, the states of a state machine are used to measure the passage of time by counting ticks provided
by the environment. In the hybrid version of figure 6.6, the passage of time is
explicitly modeled by first-order differential equations.
There are two modes, expired and safe, and the refinement state at time t is s(t) ∈ R.
At time t = 0, the initial mode is expired, and s(0) = 0. In the expired mode, s
Lee & Varaiya, Signals and Systems
243
6.3. TIMED AUTOMATA
quarter = {( u( t), s( t)) | u( t) = coin25}
nickel = {( u( t), s( t)) | u( t) = coin5}
timeout = {( u( t), s( t)) | u( t) = absent and s( t) = 0}
parkingMeter
quarter / absent
s( t) := 25
quarter / absent
u( t) ∈{ coin5,
s( t) := min( s( t) + 25, 60)
v( t) ∈{ expired,
nickel / absent
coin25, absent}
absent}
s( t) := 5
expired
safe
nickel / absent
s(0) := 0
s( t) := min( s( t) + 5, 60)
timeout / expired
. s( t) = 0
. s( t) = −1
Figure 6.6: A hybrid system representation of a 60-minute parking meter.
244
Lee & Varaiya, Signals and Systems
6. HYBRID SYSTEMS
remains at 0. The input events coin5 and coin25 cause one of two transitions from
expired to safe to be taken. These transitions have guards that are named nickel and
quarter and are defined by
nickel = {(u(t), s(t)) | u(t) = coin5}
quarter = {(u(t), s(t)) | u(t) = coin25}.
Using names for these guards in the figure makes it more readable. It would be
cluttered if the guards were directly noted on the transitions.
The transitions from expired to safe produce absent. The actions on the transitions
change the value of s to 5 and 25, depending on whether coin5 or coin25 is received.
In the safe mode, the refinement state decreases according to the differential equa-
tion of the clock,
∀ t ∈ Tsafe, ˙s(t) = −1.
There are three possible outgoing transitions from this mode. If the input event
coin5 or coin25 occurs, then one of two self-loop transitions is taken, no output is
produced, and the associated action increments s by setting as s(t) := min(s(t) +
5, 60) or s(t) := min(s(t) + 25, 60). But if the guard timeo