Copyright c 2011
Edward Ashford Lee & Pravin Varaiya
All rights reserved
Second Edition, Version 2.02
ISBN 978-0-578-07719-2
Please cite this book as:
E. A. Lee and P. Varaiya,
Structure and Interpretation of Signals and Systems,
Second Edition, LeeVaraiya.org, 2011.
First Edition was printed by:
Addison-Wesley, ISBN 0-201-74551-8, 2003, Pearson Education, Inc.
Contents
Preface
1
Signals and Systems
1.1
Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Defining Signals and Systems
2.1
Defining functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
Defining signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3
Defining systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
State Machines
3.1
Structure of state machines . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Finite state machines . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3
Nondeterministic state machines . . . . . . . . . . . . . . . . . . . . . . 107
iii
3.4
Simulation relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4
Composing State Machines
4.1
Synchrony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.2
Side-by-side composition . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.3
Cascade composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.4
Product-form inputs and outputs . . . . . . . . . . . . . . . . . . . . . . 148
4.5
General feedforward composition
. . . . . . . . . . . . . . . . . . . . . 152
4.6
Hierarchical composition . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.7
Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.8
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5
Linear Systems
5.1
Operation of an infinite state machine . . . . . . . . . . . . . . . . . . . 189
5.2
Linear functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.3
The [A, B,C, D] representation of a system . . . . . . . . . . . . . . . . . 195
5.4
Continuous-time state-space models . . . . . . . . . . . . . . . . . . . . 218
5.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
6
Hybrid Systems
6.1
Mixed models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.2
Modal models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.3
Timed automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.4
More interesting dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 250
6.5
Supervisory control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
6.6
Formal model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
iv
Lee & Varaiya, Signals and Systems
6.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
7
Frequency Domain
7.1
Frequency decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 277
7.2
Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
7.3
Spatial frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
7.4
Periodic and finite signals . . . . . . . . . . . . . . . . . . . . . . . . . . 285
7.5
Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
7.6
Discrete-time signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
7.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
8
Frequency Response
8.1
LTI systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
8.2
Finding and using the frequency response . . . . . . . . . . . . . . . . . 325
8.3
Determining the Fourier series coefficients . . . . . . . . . . . . . . . . . 339
8.4
Frequency response and the Fourier series . . . . . . . . . . . . . . . . . 340
8.5
Frequency response of composite systems . . . . . . . . . . . . . . . . . 341
8.6
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
9
Filtering
9.1
Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
9.2
Frequency response and impulse response . . . . . . . . . . . . . . . . . 378
9.3
Causality
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
9.4
Finite impulse response (FIR) filters . . . . . . . . . . . . . . . . . . . . 382
9.5
Infinite impulse response (IIR) filters . . . . . . . . . . . . . . . . . . . . 395
9.6
Implementation of filters . . . . . . . . . . . . . . . . . . . . . . . . . . 398
9.7
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Lee & Varaiya, Signals and Systems
v
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
10 The Four Fourier Transforms
10.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
10.2 The Fourier series (FS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
10.3 The discrete Fourier transform (DFT)
. . . . . . . . . . . . . . . . . . . 419
10.4 The discrete-Time Fourier transform (DTFT) . . . . . . . . . . . . . . . 424
10.5 The continuous-time Fourier transform . . . . . . . . . . . . . . . . . . . 429
10.6 Fourier transforms vs. Fourier series . . . . . . . . . . . . . . . . . . . . 433
10.7 Properties of Fourier transforms . . . . . . . . . . . . . . . . . . . . . . 442
10.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
11 Sampling and Reconstruction
11.1 Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
11.2 Reconstruction
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
11.3 The Nyquist-Shannon sampling theorem . . . . . . . . . . . . . . . . . . 486
11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
12 Stability
12.1 Boundedness and stability
. . . . . . . . . . . . . . . . . . . . . . . . . 501
12.2 The Z transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
12.3 The Laplace transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
13 Laplace and Z Transforms
13.1 Properties of the Z tranform
. . . . . . . . . . . . . . . . . . . . . . . . 536
13.2 Frequency response and pole-zero plots . . . . . . . . . . . . . . . . . . 548
13.3 Properties of the Laplace transform . . . . . . . . . . . . . . . . . . . . . 550
vi
Lee & Varaiya, Signals and Systems
13.4 Frequency response and pole-zero plots . . . . . . . . . . . . . . . . . . 555
13.5 The inverse transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
13.6 Steady state response . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
13.7 Linear difference and differential equations . . . . . . . . . . . . . . . . 571
13.8 State-space models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
13.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
14 Composition and Feedback Control
14.1 Cascade composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
14.2 Parallel composition
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
14.3 Feedback composition
. . . . . . . . . . . . . . . . . . . . . . . . . . . 624
14.4 PID controllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
14.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
A Sets and Functions
A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654
A.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
B Complex Numbers
B.1 Imaginary numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688
B.2 Arithmetic of imaginary numbers . . . . . . . . . . . . . . . . . . . . . . 689
B.3 Complex numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
B.4 Arithmetic of complex numbers
. . . . . . . . . . . . . . . . . . . . . . 691
B.5 Exponentials
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692
B.6 Polar coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
Lee & Varaiya, Signals and Systems
vii
Bibliography
Notation Index
Index
viii
Lee & Varaiya, Signals and Systems
Preface
Signals convey information. Systems transform signals. This book introduces the mathe-
matical models used to design and understand both. It is intended for students interested
in developing a deep understanding of how to digitally create and manipulate signals to
measure and control the physical world and to enhance human experience and communi-
cation.
The discipline known as “signals and systems” is rooted in the intellectual tradition of
electrical engineering (EE). This tradition, however, has evolved in unexpected ways.
EE has lost its tight coupling with the “electrical.” So although many of the techniques
introduced in this book were first developed to analyze circuits, today they are widely
applied in information processing, system biology, mechanical engineering, finance, and
many other disciplines.
This book approaches signals and systems from a computational point of view. A more
traditional introduction to signals and systems would be biased towards the historic ap-
plication, analysis and design of circuits. It would focus almost exclusively on linear
time-invariant systems, and would develop continuous-time models first, with discrete-
time models then treated as an advanced topic.
The approach in this book benefits students by showing from the start that the methods of
signals and systems are applicable to software systems, and most interestingly, to systems
ix
Preface
that mix computers with physical devices and processes, including mechanical control
systems, biological systems, chemical processes, transportation systems, and financial
systems. Such systems have become pervasive, and profoundly affect our daily lives.
The shift away from circuits implies some changes in the way the methodology of signals
and systems is presented. While it is still true that a voltage that varies over time is
a signal, so is a packet sequence on a network. This text defines signals to cover both.
While it is still true that an RLC circuit is a system, so is a computer program for decoding
Internet audio. This text defines systems to cover both. While for some systems the state
is still captured adequately by variables in a differential equation, for many it is now the
values in registers and memory of a computer. This text defines state to cover both.
The fundamental limits also change. Although we still face thermal noise and the speed
of light, we are likely to encounter other limits–such as complexity, computability, chaos,
and, most commonly, limits imposed by other human constructions–before we get to
these. The limitations imposed, for example, when transporting voice signals over the In-
ternet, are not primarily physical limitations. They are instead limitations arising from the
design and implementation of the Internet, and from the fact that transporting voice was
never one of the original intentions of the design. Similarly, computer-based audio sys-
tems face latency and jitter imposed by an operating system designed to time share scarce
computing resources among data processing tasks. This text focuses on composition of
systems so that the limits imposed by one system on another can be understood.
The mathematical basis for the discipline also changes with this new emphasis. The
mathematical foundations of circuit analysis are calculus and differential equations. Al-
though we still use calculus and differential equations, we frequently need discrete math,
set theory, and mathematical logic. Whereas the mathematics of calculus and differential
equations evolved to describe the physical world, the world we face as system designers
often has nonphysical properties that are not such a good match for this mathematics.
This text bases the entire study on a highly adaptable formalism rooted in elementary set
theory.
Despite these fundamental changes in the medium with which we operate, the methodol-
ogy of signals and systems remains robust and powerful. It is the methodology, not the
medium, that defines the field.
The book is based on a course at Berkeley required of all majors in Electrical Engineer-
ing and Computer Sciences (EECS). The experience developing the course is reflected in
certain distinguished features of this book. First, no background in electrical engineer-
x
Lee & Varaiya, Signals and Systems
Preface
ing or computer science is assumed. Readers should have some exposure to calculus,
elementary set theory, series, first order linear differential equations, trigonometry, and
elementary complex numbers. The appendices review set theory and complex numbers,
so this background can be made up students.
Approach
This book is about mathematical modeling and analysis of signals and systems, appli-
cations of these methods, and the connection between mathematical models and compu-
tational realizations. We develop three themes. The first theme is the use of sets and
functions as a universal language to describe diverse signals and systems. Signals—
voice, images, bit sequences—are represented as functions with an appropriate domain
and range. Systems are represented as functions whose domain and range are themselves
sets of signals. Thus, for example, an Internet voice signal is represented as a function
that maps voice-like signals into sequences of packets.
The second theme is that complex systems are constructed by connecting simpler sub-
systems in standard ways—cascade, parallel, feedback. The connections determine the
behavior of the interconnected system from the behaviors of component subsystems. The
connections place consistency requirements on the input and output signals of the systems
being connected.
Our third theme is to relate the declarative view (mathematical, “what is”) with the imper-
ative view (procedural, “how to”). That is, we associate mathematical analysis of systems
with realizations of these systems. This is the heart of engineering. When electrical en-
gineering was entirely about circuits, this was relatively easy, because it was the physics
of the circuits that was being described by the mathematics. Today we have to some-
how associate the mathematical analysis with very different realizations of the systems,
most especially software. We do this association through the study of state machines, and
through the consideration of many real-world signals, which, unlike their mathematical
abstractions, have little discernable declarative structure. Speech signals, for instance, are
far more interesting than sinusoids, and yet many signals and systems textbooks talk only
about sinusoids.
Lee & Varaiya, Signals and Systems
xi
Preface
Content
We begin in Chapter 1 by describing signals as functions, focusing on characterizing the
domain and the range for familiar signals that humans perceive, such as sound, images,
video, trajectories of vehicles, as well as signals typically used by machines to store or
manipulate information, such as sequences of words or bits.
Systems, also introduced in Chapter 1, are described as functions, but now the domain and
the range are themselves sets of signals. Systems can be connected to form a more com-
plex system, and the function describing these more complex systems is a composition of
functions describing the component systems.
Chapter 2 focuses on how to define the functions that we use to model both signals and
systems. It distinguishes declarative definitions (assertions of what a signal or system is)
from imperative ones (descriptions of how a signal is produced or processed by a system).
The imperative approach is further developed in Chapter 3 using the notion of state, the
state transition function, and the output function, all in the context of finite state machines.
In Chapter 4, state machines are composed in various ways (cascade, parallel, and feed-
back) to make more interesting systems. Applications to feedback control illustrate the
power of the state machine model.
In Chapter 5, time-based systems are studied, first with discrete-time syst