Lecture Notes on

Digital Signal
Processing

Enis Yazici
SRH University Heidelberg
[Link]@[Link]

Version 2.0 • 2026

 Preface

Digital Signal Processing (DSP) has transformed the way we analyze, interpret, and
manipulate information across virtually every branch of science and engineering. From
noise cancellation in consumer headphones to the detection of gravitational waves at LIGO,
from real-time speech recognition on smartphones to the reconstruction of particle tracks in
high-energy physics detectors, DSP provides the mathematical and algorithmic foundation
that makes these achievements possible.
These lecture notes guide students through the core principles of DSP in a way that
emphasizes understanding over memorization. We begin with the mathematical building
blocks (trigonometry, complex numbers, and exponentials) and show how these classical
ideas connect directly to the modern tools of sampling, filtering, Fourier analysis, and system
design. Every concept is developed from first principles, illustrated with worked
examples, and placed in historical context so that students can see not only how things
work but why they were invented.
The notes are designed to be self-contained. A student with a solid background in
calculus and basic linear algebra should be able to follow every derivation from start to
finish. At the same time, the connections to real-world applications, including
communications, audio processing, biomedical instrumentation, control systems, and
physics research, are woven throughout, so that the mathematics never feels
disconnected from practice.

Goal of These Notes

The primary goal is to build a deep, intuitive understanding of DSP that students can
carry into their research and professional careers. By the end of these notes, a reader
should be able to analyze discrete-time signals, design basic digital filters, understand
the DFT and FFT, and use the Z-transform to characterize system behaviour, and, just as
importantly, to explain why each of these tools works the way it does.

ii
Contents

1 Introduction 1
1.1 What Is a Signal?................................................................................................................1
1.2 From Continuous to Discrete: The Big Idea...................................................................2
1.3 What Can We Do with Digital Signals?...........................................................................2
1.4 The Role of Mathematics...................................................................................................2
1.5 Signals and Systems: A Classification.............................................................................3
1.6 Software Tools...................................................................................................................3
1.7 The Road Ahead.................................................................................................................4

2 Mathematical Background for DSP 5

2.1 The Unit Circle and Trigonometric Foundations...........................................................5
2.1.1 Geometric and Historical Motivation.................................................................5
2.1.2 Definition of the Unit Circle................................................................................6
2.1.3 Radian Measure....................................................................................................6
2.1.4 Basic Symmetry Properties..................................................................................7
2.1.5 Angle Addition Formulas....................................................................................8
2.1.6 Key Reference Angles...........................................................................................9
2.1.7 Example: Moving Around the Unit Circle.........................................................9
2.2 Sinusoids: Amplitude, Frequency, and Phase.............................................................10
2.2.1 Definition of a Sinusoid......................................................................................10
2.2.2 Periodicity............................................................................................................11
2.2.3 Amplitude, Frequency, and Phase: Separate Roles........................................11
2.2.4 Sinusoids with Arbitrary Frequency and Phase.............................................12
2.2.5 The Derivative of a Sinusoid.............................................................................12
2.2.6 Harmonic Sinusoids............................................................................................13
2.2.7 Sum of Sinusoids and Beats..............................................................................13
2.2.8 Discrete-Time Sinusoids.....................................................................................13
2.2.9 Aliasing.................................................................................................................13
2.2.10 Summary..............................................................................................................14
2.3 Complex Numbers: Geometry, Algebra, and Their Role in DSP...............................14
2.3.1 Algebraic Form...................................................................................................14
2.3.2 Geometric Interpretation: The Complex Plane...............................................15
2.3.3 Complex Conjugate.............................................................................................15
2.3.4 Polar Form and Multiplication as Rotation.....................................................15
2.3.5 Division and Inversion.......................................................................................16
2.3.6 Euler Representation..........................................................................................16
2.3.7 Complex Numbers in Signal Processing.........................................................16
2.3.8 Summary..............................................................................................................17
2.4 Euler’s Formula and Complex Exponentials...............................................................17

iii
CONTENTS

2.4.1 Historical Background........................................................................................17

2.4.2 Definition of the Complex Exponential............................................................18
2.4.3 Complex Exponential as Uniform Circular Motion.......................................18
2.4.4 The Fundamental Relations...............................................................................19
2.4.5 Derivatives and Integrals of ejωt................................................................................................19
2.4.6 Magnitude and Phase........................................................................................20
2.4.7 Frequency Shifting..............................................................................................20
2.4.8 Why Complex Exponentials Dominate DSP...................................................20
2.4.9 Summary..............................................................................................................21
2.5 Damped Exponentials and Derivatives of Sinusoids..................................................21
2.5.1 Exponential Growth and Decay........................................................................21
2.5.2 Damped Sinusoids..............................................................................................22
2.5.3 Complex Representation of Damped Sinusoids.............................................22
2.5.4 Envelope Behavior..............................................................................................22
2.5.5 Derivatives of Sinusoids.....................................................................................23
2.5.6 Derivative of a Damped Sinusoid.....................................................................23
2.5.7 Complex Exponential Derivative......................................................................24
2.5.8 Resonance: Underdamped, Critically Damped, Overdamped......................24
2.5.9 Connection to Discrete-Time Systems..............................................................24
2.5.10 Summary..............................................................................................................25
2.6 Linear Algebra Essentials for DSP.................................................................................25
2.6.1 Signals as Vectors...............................................................................................25
2.6.2 Inner Product.......................................................................................................25
2.6.3 Orthogonality.......................................................................................................26
2.6.4 Basis and Dimension...........................................................................................26
2.6.5 Orthogonal and Orthonormal Bases................................................................26
2.6.6 Projection.............................................................................................................26
2.6.7 The Fourier Basis................................................................................................27
2.7 Fundamental Discrete-Time Signals..............................................................................27
2.7.1 Unit Impulse........................................................................................................27
2.7.2 Unit Step..............................................................................................................27
2.7.3 Rectangular Pulse...............................................................................................27
2.7.4 Sinc Function.......................................................................................................28

3 Fundamental Concepts 30
3.1 Continuous-Time and Discrete-Time Signals...............................................................30
3.2 Sampling, Nyquist Rate, and Aliasing..........................................................................32
3.3 Quantization and Analog-to-Digital Conversion........................................................34
3.4 Basic Classes and Properties of Discrete-Time Signals...............................................35
3.5 Basic Operations on Discrete-Time Signals..................................................................36
3.6 Linear Time-Invariant (LTI) Systems............................................................................37
3.7 Difference Equations for Discrete-Time Systems........................................................39
3.8 Impulse Response, Convolution, and Step Response.................................................40
3.9 Stability and Causality of LTI Systems.........................................................................41

4 The Z-Transform 44

iv
 4.1 Definition and Properties...............................................................................................44
4.2 Key Applications..............................................................................................................45
4.3 Properties of Z-Transform..............................................................................................47
4.3.1 Linearity...............................................................................................................47
4.3.2 Time Shifting........................................................................................................48
CONTENTS

4.3.3 Scaling in the z-domain......................................................................................48

4.3.4 Convolution..........................................................................................................48
4.3.5 Initial Value Theorem.........................................................................................48
4.3.6 Final Value Theorem..........................................................................................48
4.4 Transfer Function and Frequency Response................................................................49
4.4.1 Poles, Zeros, and System Behaviour.................................................................50
4.4.2 Frequency Response: Evaluating H(z) on the Unit Circle...........................50
4.4.3 Geometric Interpretation...................................................................................51
4.5 Inverse Z-Transform.......................................................................................................54
4.5.1 Worked Example: Solving a Difference Equation with the Z-Transform 54

5 DFT and Fast Fourier Transform (FFT) 56

5.1 Frequency Analysis of Signals.......................................................................................56
5.1.1 Time and Frequency Domain Relationship......................................................57
5.1.2 The Discrete-Time Fourier Transform (DTFT)................................................57
5.1.3 From DTFT to DFT.............................................................................................58
5.1.4 Worked Example: Computing a 4-Point DFT by Hand..................................58
5.1.5 Examples of Frequency Transformations........................................................59
5.2 Properties of DFT.............................................................................................................60
5.3 FFT Algorithms and Computation.................................................................................62
5.3.1 Why the DFT Is Expensive.................................................................................62
5.3.2 Historical Background........................................................................................62
5.3.3 The Key Idea: Divide and Conquer..................................................................62
5.3.4 Radix-2 Decimation-in-Time (DIT)..................................................................63
5.3.5 Worked Example: 4-Point FFT..........................................................................63
5.3.6 Computational Complexity................................................................................64
5.3.7 Practical Considerations.....................................................................................64
5.3.8 FFT Variants........................................................................................................64

6 Design of Digital Filters 67

6.1 Introduction to Filters: FIR and IIR...............................................................................67
6.1.1 Finite Impulse Response (FIR) Filters..............................................................68
6.1.2 Infinite Impulse Response (IIR) Filters............................................................68
6.1.3 FIR vs. IIR: A Practical Comparison..................................................................68
6.2 FIR Filter Design Methods..............................................................................................69
6.2.1 The Window Method..........................................................................................69
6.2.2 Frequency Sampling Method............................................................................69
6.3 IIR Filter Design via the Bilinear Transform................................................................70
6.3.1 Worked Example: FIR Low-Pass Filter Using the Hamming Window . 70
6.3.2 Worked Example: IIR Filter Design via the Bilinear Transform...................71

v
CONTENTS

vi
 1 CHAPTER
1

Introduction

Think about the last time you made a phone call. Your voice travelled through a microphone,
was captured as a stream of electrical fluctuations, sliced into thousands of tiny snapshots
every second, and converted into a sequence of numbers. Those numbers were compressed,
encrypted, beamed across a cellular network, and reassembled at the other end into the
sound of your voice. The entire journey, from your lips to someone else’s ear on the other
side of the planet, took less than a fraction of a second. What made this possible was not a
single brilliant invention, but a whole discipline built on the marriage of mathematics and
engineering: Digital Signal Processing, or DSP.
The story of DSP is, at its heart, the story of how we learned to speak the language of
nature in numbers.

1.1 What Is a Signal?

Before we can process anything, we need to understand what we are processing. In the
broadest sense, a signal is anything that carries information. Sound is a signal: it is nothing
more than the oscillation of air pressure over time. An image is a signal too: it is a pattern
of electromagnetic waves, photons striking the sensors of a camera or the retina of an eye.
Temperature readings from a weather station, the voltage fluctuations in a power grid, the
electrocardiogram tracing the rhythm of a beating heart: all of these are signals.
What they have in common is that they are all physical phenomena, things that exist in
the real world and evolve over time or space. In communication engineering, we take these
physical things and do something remarkable: we convert them into pure mathematical
objects. A sound wave becomes a function of time. An image becomes a two-dimensional
array of numbers. The physical world, in all its richness and complexity, is translated into
the clean, precise language of mathematics.
Once this translation is complete, the power of the approach becomes apparent. We
can manipulate these mathematical objects with extraordinary precision. We can filter
out noise, compress data to a fraction of its original size, detect hidden patterns, and
extract information that would be invisible to the naked eye. Then, when we are done,
we convert everything back into physical form: sound comes out of a speaker, an image
appears on a screen, a robot arm moves in response to a control signal. This back-and-
forth journey between the physical world and the mathematical world is the essence of
signal processing.

1.2 From Continuous to Discrete: The Big Idea

1
Chapter 1. Introduction

Signals in nature are almost always continuous. When you listen to a violin, the sound
pressure varies smoothly and uninterruptedly. There are no gaps, no jumps, no pauses
in the physics. However, computers do not understand smooth, continuous curves. They
understand numbers, and more specifically, they understand finite collections of
numbers.
This is where discretization enters the picture. The idea is beautifully simple:
instead of trying to capture every single instant of a continuous signal, we take
measurements at regular intervals. Imagine watching a movie. What you perceive as fluid
motion is actually a rapid sequence of still photographs, typically 24 or 30 frames per
second. Each frame is a snapshot, a frozen moment in time. Your brain fills in the gaps and
creates the illusion of continuity. DSP does something remarkably similar with signals.
The process has two essential steps. First, sampling: we measure the amplitude
of the signal at evenly spaced points in time. A music recording, for example, is typically
sampled 44,100 times per second. Each of those measurements captures a single number
representing the air pressure at that instant. Second, quantization: since computers work
with finite precision, each sampled value must be rounded to one of a finite set of allowed
levels. This introduces a tiny amount of error, but if the quantization is fine enough, the error
is imperceptible.
The device that performs this conversion from the continuous world to the discrete
world is called an analog-to-digital converter, or ADC. At the output of an ADC,
what was once a continuously varying physical phenomenon has become a sequence of
numbers, ready for mathematical manipulation. It is worth pausing to appreciate how
profound this step really is. The entire richness of the natural world, the warmth of a
human voice, the shimmer of a sunset captured by a camera, the tremor of a seismic
wave, is reduced to an ordered list of integers. And yet, as we will see throughout these
notes, that list of integers contains, under appropriate conditions, enough information to
analyze, transform, and even reconstruct the original signal.

1.3 What Can We Do with Digital Signals?

Once a signal has been converted into digital form, an enormous toolkit becomes
available. We can filter the signal to remove unwanted components. Think of noise-
cancelling head-phones: they work by analyzing incoming sound in real time, identifying
the unwanted ambient noise, and generating a counter-signal that cancels it out. This is
DSP in action.
We can compress signals to make them smaller and easier to transmit. Every time you
stream a song on your phone or watch a video online, sophisticated compression algorithms
are at work, stripping away the parts of the signal that your ears or eyes would never notice,
and packing the rest into a compact digital package.
We can analyze signals to extract hidden information. In biomedical engineering, DSP
techniques are used to detect abnormal heart rhythms from electrocardiogram data. In
seismology, they help distinguish the signature of an earthquake from background vibrations.
In speech recognition, they enable your smartphone to understand your voice commands.
From cellular phones to satellites, from MRI scanners to self-driving cars, DSP provides
the mathematical and algorithmic foundation that makes these technologies work. It is no
exaggeration to say that the modern world runs on digital signal processing.

1.4 The Role of Mathematics

At this point, a natural question arises: if DSP is so powerful, what is the price of admission?
The answer, perhaps unsurprisingly, is mathematics.

2
 1.5 Signals and Systems: A Classification

The processing tools we use in DSP are called systems, and systems are described by
mathematical models. A filter, for instance, is really just a mathematical equation that takes
an input sequence and produces an output sequence. To understand how filters work, we
need algebra. To design them, we need calculus. To analyze their behaviour in different
conditions, we need complex numbers, exponentials, and the theory of linear systems.
The core operations of DSP can be summarized in a few sentences. We analyze signals
using frequency analysis, a technique that reveals the hidden oscillatory components inside
any signal. We transform signals from the time domain to the frequency domain using
the Fourier Transform, one of the most beautiful and powerful ideas in all of mathematics.
We design filters to select, reject, or reshape specific frequency components. We optimize
systems to perform as efficiently as possible. And we develop algorithms, step-by-step
computational procedures, that implement all of these operations on real hardware.
All of this requires a strong mathematical background. But here is the good news: the
mathematics of DSP is not arbitrary or abstract. Every equation has a clear physical meaning.
Every formula connects directly to something you can hear, see, or measure. The
challenge in engineering education has always been that students learn mathematical
tools, such as trigonometry, complex numbers, and differential equations, in isolation,
without seeing how these tools apply to real problems. These lecture notes are designed to
bridge that gap. Every mathematical concept introduced here will be immediately
connected to a concrete application in signal processing. You will never have to wonder
“why am I learning this?” because the answer will always be right in front of you.

1.5 Signals and Systems: A Classification

The world of DSP encompasses a rich variety of signals and systems, and it is useful to have
a vocabulary for describing them.
Signals can be deterministic, meaning their future values can be predicted exactly
from a mathematical formula, or stochastic, meaning they contain an element of
randomness and can only be described statistically. The pure tone of a tuning fork is
deterministic; the static
hiss of a radio tuned to an empty channel is stochastic.
Signals can also be periodic, repeating the same pattern over and over, or
aperiodic, exhibiting no such repetition. The steady hum of a power line is periodic; a
single spoken word is aperiodic.
Similarly, the systems that process these signals can be categorized along several dimen-
sions. A system is linear if it satisfies two properties: additivity (the response to a sum
of inputs equals the sum of individual responses) and homogeneity (scaling the input
scales the output by the same factor). A system that violates either property is nonlinear.
A system is time-invariant if its behaviour does not change over time, and time-
varying if it does. These classifications may sound like dry technicalities, but they have
profound practical consequences. Linear, time-invariant systems, the kind we will focus on
most heavily, are the ones we understand best and can analyze most completely. They are
the workhorses of DSP.

1.6 Software Tools

Modern DSP relies heavily on software tools that provide platforms for algorithm devel-
opment, simulation, and analysis. MATLAB, with its extensive Signal Processing Toolbox,
has been the industry standard for decades. Python, with libraries such as NumPy and
SciPy, has emerged as a powerful open-source alternative and is increasingly popular in both
academic and industrial settings. Throughout these notes, we will occasionally reference
both environments when discussing practical implementations.

3
Chapter 1. Introduction

1.7 The Road Ahead

The chapters that follow will build your understanding of DSP from the ground up. We
begin with the mathematical foundations: trigonometry, complex numbers, exponentials, and
difference equations. These are the raw materials from which everything else is constructed.
From there, we move to the core topics of the discipline: sampling theory, convolution, the
Discrete Fourier Transform, the Z-transform, and filter design.
Along the way, we will use visual aids, including graphs, flowcharts, and worked
examples, to make abstract concepts tangible. The goal is not to memorize formulas but
to develop a deep, intuitive understanding of what those formulas mean and why they
work. If we succeed, you will finish these notes not just knowing how to apply DSP
techniques, but understanding the elegant mathematical ideas that make them possible.

4
 2 CHAPTER
2

Mathematical Background for

DSP

Every great engineering discipline stands on a mathematical foundation. For digital signal
processing, that foundation is built from a surprisingly small number of ideas: trigonome-
try, complex numbers, exponentials, and difference equations. You have almost certainly
encountered each of these in earlier courses. But chances are you learned them in isolation,
as separate chapters in separate textbooks, without seeing how they connect to one another
or to anything in the physical world.
This chapter changes that. Here we rebuild these familiar concepts from scratch, but this
time with a clear purpose in mind. Trigonometry is not an abstract exercise in
memorizing identities; it is the language of oscillation, and oscillation is what signals do.
Complex numbers are not a mathematical curiosity invented to solve cubic equations;
they are the most natural way to describe rotation and phase. Exponentials are not just
another family of functions; they are the eigenfunctions of every linear time-invariant
system you will encounter in DSP.
The presentation is self-contained: every concept is explained before it is used. Examples,
geometric interpretations, and short historical notes are included throughout to give you a
strong foundation for the topics that follow, including sampling theory, convolution, Fourier
analysis, filtering, and discrete-time system design.

2.1 The Unit Circle and Trigonometric Foundations

2.1.1 Geometric and Historical Motivation
Trigonometric ideas did not emerge as abstract mathematical definitions. They grew out of
practical attempts to understand the world, especially the movement of celestial bodies. For
thousands of years, astronomers in ancient Babylon, Greece, India, China, and the Islamic
world attempted to predict the positions of the Sun, Moon, and planets. These motions were
observed to repeat in cycles, sometimes daily, sometimes yearly, sometimes over even longer
periods. A natural question arose:
How can we describe repeating motion using geometry?

The answer gradually led to the study of circles. A circle is the simplest geometric shape
that repeats perfectly as one moves along its boundary. If a point travels around a circle at
constant speed, its horizontal and vertical coordinates oscillate in a perfectly regular and
smooth manner. Today we call these oscillations the sine and cosine functions.
Historically, the earliest trigonometric tables were developed to help compute the lengths
of chords in a circle when the central angle was known. Hipparchus (2nd century BC) is
5
Chapter 2. Mathematical Background for DSP

often considered the first to formalize this approach. Later, Ptolemy’s Almagest (2nd
century AD) organized extensive chord tables, enabling astronomers to perform angular
calcula-tions for planetary predictions. Centuries after that, Indian mathematicians replaced
chord lengths with half-chords, giving functions essentially identical to modern sine. Muslim
mathematicians such as al-Battani and al-Tusi refined these concepts, and by the time Euro-
pean mathematics matured during the Renaissance, trigonometry had become a systematic
discipline.
Although ancient mathematicians developed trigonometry for astronomy, its geometric
heart remained unchanged:
A sinusoid is the projection of uniform circular motion onto a line.

This viewpoint is enormously important in signal processing. In DSP we treat signals as

sums of oscillatory components. These oscillations are most naturally represented as angles
on the unit circle. The circle becomes a map: moving forward corresponds to increasing
time; rotating corresponds to oscillating; completing a full round corresponds to repeating
the pattern.
Thus, the unit circle is not merely a geometric figure; it is the foundation of how we
understand and manipulate periodic processes. Modern Fourier analysis, which decomposes
signals into sums of sinusoids, depends entirely on this ancient geometric idea.

2.1.2 Definition of the Unit Circle

The unit circle is defined as the set of all points in the Euclidean plane whose distance from
the origin is one:
x2 + y2 = 1.
This simple equation encodes a deep geometric structure. Any point (x, y) on the
circle can be uniquely described by an angle θ, which measures the direction of the point
from the origin. We measure θ from the positive horizontal axis to the line connecting
the origin to the point.
The coordinates of the point are

(cos θ, sin θ).

Here cos θ is literally the horizontal projection of the point, and sin θ the vertical
projection. This perspective is geometrically intuitive: if a point travels around the circle, its
shadow on each coordinate axis oscillates back and forth. These shadows trace out the
familiar cosine and sine waves.
An important observation follows:
The trigonometric functions are not arbitrary formulas; they emerge directly from
geometry.

This geometric origin will guide everything we do later. When we encounter

sinusoids in signals, complex exponentials, or phasors, we are essentially looking at the
shadows of rotating vectors on the unit circle.

2.1.3 Radian Measure

Angles can be measured in degrees or radians, but radians are the natural choice for all
analytic work, including DSP. The reason becomes clear when we consider the arc length of
a circle.

6
 2.1 The Unit Circle and Trigonometric Foundations

(0,
1)

(cos θ, sin
sin θ θ)

θ
x
(−1, 0) cos θ (1, 0)

(0, −1)
Figure 2.1: The unit circle. A point at angle θ has coordinates (cos θ, sin θ). The horizontal
and vertical projections of the rotating radius vector produce cosine and sine waves,
respectively.

On a circle of radius 1, an angle θ (in radians) corresponds to an arc length ℓ = θ. In other

words:
arc length = radius × angle
and when radius = 1, the angle equals the arc length.
From this, one full revolution of the circle is simply the circumference:
2π radians = 360◦.
This definition is not arbitrary; it allows trigonometric functions to satisfy elegant differ-
ential equations. For instance:
d d
sin θ = cos θ, cos θ = − sin θ.
d d
These relationships holdθ only when angles θ are measured in radians. They break
down if degrees are used. Because DSP involves sinusoidal oscillations, frequency,
derivatives, integrals, and exponentials, the radian measure becomes the only consistent
and practical choice.
Another advantage appears when we connect angle and time. If a point moves
around the unit circle with constant angular velocity ω, then in time t it moves an angle
θ(t) = ωt.
This leads directly to sinusoidal signals like cos(ωt) and sin(ωt), which form the
building blocks of Fourier analysis.
Radians therefore provide a unified quantitative language: the same θ describes both
geometric angle and temporal evolution.

2.1.4 Basic Symmetry Properties

The symmetry properties of the trigonometric functions are not merely algebraic facts; they
follow directly from the geometry of the unit circle.

7
Chapter 2. Mathematical Background for DSP

Consider a point on the unit circle corresponding to angle θ. The point corresponding
to angle— θ is its reflection across the horizontal axis. This reflection leaves the
horizontal coordinate unchanged but reverses the sign of the vertical coordinate. Hence,

cos(−θ) = cos θ, sin(−θ) = − sin θ.

These identities express two fundamental symmetries:

• Cosine is an even function. Even functions remain unchanged when the

input is reflected. This symmetry corresponds to horizontal-axis reflection.

• Sine is an odd function. Odd functions change sign under reflection. This is
consistent with the vertical coordinate of a reflected point.

Symmetry is a core theme in DSP: when we analyze real-valued signals in the frequency
domain, we repeatedly encounter the even symmetry of magnitude and the odd symmetry
of phase.
A second fundamental property arises because moving around the circle by one full turn
returns the point to its starting location. Thus, sinusoidal functions are periodic:

sin(θ + 2π) = sin θ, cos(θ + 2π) = cos θ.

Periodicity implies that sinusoidal signals repeat indefinitely. In signal processing, this is
crucial: periodic waveforms form the basis of Fourier series, and periodicity is directly tied
to harmonic structure.

2.1.5 Angle Addition Formulas

One of the most powerful features of the unit circle is that rotations can be combined. If
a point first rotates by angle α and then by angle β, the combined rotation is equivalent to a
single rotation by α + β.
To express this idea algebraically, consider the coordinates of the point after each rotation.
Using basic geometry, one obtains:

sin(α ± β) = sin α cos β ± cos α sin β,

cos(α ± β) = cos α cos β ∓ sin α sin β.

These identities are central to signal processing for several reasons:

• They describe how phase shifts combine, which is essential when multiple
sinusoids interact.

• They allow us to rewrite products of sinusoids as sums, a key step in Fourier analysis.

• They show that the structure of trigonometric functions mirrors the structure of rota-
tions.

In DSP, a very common situation is adding two sinusoids of the same frequency but
different phases. The angle addition formulas allow us to calculate the resulting
amplitude and phase precisely.

8
 2.1 The Unit Circle and Trigonometric Foundations

2.1.6 Key Reference Angles

To work comfortably with sinusoids, it is helpful to know the trigonometric values at a few
key angles. These angles reflect the geometric structure of the circle and also occur
frequently in practical applications such as sampling, modulation, and spectral analysis.
For multiples of π/6 and π/4, the values are:

θ cos θ sin θ
0 1 0
π √ 1
6 √23 √2
π 2 2
4 2 √2
π 1 3
3 2 2
π
2
0 1
π −1 0
3π 0 −1
2
2π 1 0
These points divide the circle into regions of increasing and decreasing sine and cosine
values. They allow us to sketch sinusoidal signals quickly and understand how phase shifts
translate into horizontal movement.

Additional Examples.
2π
• At θ = 3
(120 degrees): √
2π 1 2π 3
cos =− , sin = .
3 2 3 2

The point lies in the second quadrant.

5π
• At θ = 4
(225 degrees):
√ √
5π 2 5π 2
cos 4 =−2 , sin 4 =−2 .

This corresponds to a diagonal point in the third quadrant.

• At θ = − π
:
3 √
π 1 3
π
cos − = , sin − =− .
3 2π 3 2
The point is the reflection of the θ = point across the horizontal axis.
3
Such reference angles appear constantly when analyzing signals with specific phase
offsets or studying the shape of modulated waveforms.

2.1.7 Example: Moving Around the Unit Circle

Consider a point moving around the unit circle with constant angular velocity ω. Its angle at
time t is
θ(t) = ωt.
The coordinates of the point are then

x(t) = cos(ωt), y(t) = sin(ωt).

9
Chapter 2. Mathematical Background for DSP

This simple geometric picture is fundamental in DSP. A sinusoid is nothing more than the
horizontal or vertical projection of uniform circular motion. The frequency of the sinusoid
corresponds to how fast the point rotates. A larger ω means the point completes more
revolutions per second, producing a higher-frequency oscillation.

Illustrative Cases.

• If ω = 2π, the point completes one full revolution per second. Thus x(t) =
cos(2πt) has period 1 second.
2π 1
• If ω = 4π, the motion is twice as fast, so the period becomes T = = seconds.
4π 2

• If θ(t) = ωt + φ0, the term φ0 simply indicates that the point starts from a
rotated initial position. This is the geometric origin of phase shift.

In later chapters, we will repeatedly return to this interpretation. Complex exponentials,

Fourier series, and phasors all rely on the idea that rotating objects in the plane naturally
encode oscillatory signals in time.

2.2 Sinusoids: Amplitude, Frequency, and Phase

Sinusoids are the central objects of study in signal processing. They arise naturally in physics,
engineering, mathematics, and communication systems. Historically, sinusoids appeared in
the study of vibrating strings, astronomical cycles, and solutions of differential equations
governing physical phenomena such as heat conduction and electromagnetic waves.
In DSP, sinusoids are even more fundamental:
Every linear and time-invariant (LTI) system responds to a sinusoid with a
sinusoid of the same frequency.

This remarkable property makes sinusoids the “eigenfunctions” of LTI systems and
explains why Fourier methods dominate signal analysis.

2.2.1 Definition of a Sinusoid

A continuous-time sinusoid has the mathematical form

x(t) = A cos(ωt + φ),

where:

• A > 0 is the amplitude (peak value),

• ω is the angular frequency measured in radians per second,

• φ is the phase shift,

• t is time.

The ordinary frequency in Hertz is

ω
f = .
2π

10
 2.2 Sinusoids: Amplitude, Frequency, and Phase

Geometric Interpretation. This formula is the horizontal projection of a point

rotating around the unit circle with angular velocity ω. If the rotating point has initial angle
φ, then its horizontal projection is:
x(t) = cos(ωt + φ).

Thus, a sinusoid is not merely an algebraic function but the “shadow” of circular motion.

2.2.2 Periodicity
A sinusoid repeats its values when the angle increases by 2π:

ω(t + T) + φ = ωt + φ + 2π.

Solving gives the period

2π 1
T= = .
ω f

Interpretation. A higher frequency corresponds to a faster oscillation, meaning the

signal completes more cycles per unit time.

2.2.3 Amplitude, Frequency, and Phase: Separate Roles

Each parameter controls a different aspect of the signal’s behavior.

Amplitude A. The amplitude sets the “height” of the waveform. Many physical
quantities such as sound pressure, voltage, and mechanical displacement are proportional to
amplitude.
Energy over one period is proportional to A2. Thus:

Higher amplitude ⇒ more energy.

Frequency ω or f . Frequency controls how many oscillations occur per

second. For example:

• A 440 Hz sinusoid is the musical note A4.

• Power systems use 50 or 60 Hz sinusoids.

• Human hearing ranges roughly from 20 Hz to 20 kHz.

Phase φ.Phase determines where in its cycle the sinusoid begins at t = 0. A positive phase
shifts the signal to the left; a negative phase shifts it to the right.
Because phase shifts correspond to rotations on the unit circle, they behave additively:

cos(ωt + φ1) + cos(ωt + φ2)

can be combined into a single sinusoid using the angle addition identities.

11
Chapter 2. Mathematical Background for DSP

Effect of amplitude, frequency, and phase on a sinusoid

2 cos(2πt)
2
cos(2πt)
cos(4πt)
cos(2πt + π/2)
x(t

0
)

−2
−0.2 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2
t (seconds)

Figure 2.2: Four sinusoids illustrating the effect of each parameter. Doubling the
amplitude (red) doubles the height. Doubling the frequency (green) doubles the number of
oscillations per second. Adding a phase of π/2 (orange, dashed) shifts the waveform to the
left.

2.2.4 Sinusoids with Arbitrary Frequency and Phase

Two sinusoids with the same frequency but different amplitudes and phases:

x1(t) = A1 cos(ωt + φ1), x2(t) = A2 cos(ωt +

φ2), can always be expressed as a single sinusoid:

x1(t) + x2(t) = Atot cos(ωt + φtot) .

The combined amplitude and phase are found using vector addition on the unit circle:

Atotejφtot = A1ejφ1 + A2ejφ2 .

This representation becomes essential later when we analyze oscillators, phasors,

and frequency-domain filtering.

2.2.5 The Derivative of a Sinusoid

Using radians yields clean and elegant formulas:
d
cos(ωt + φ) = −ω sin(ωt + φ),
dt
d
sin(ωt + φ) = ω cos(ωt + φ).
dt
Thus:

• Differentiation preserves frequency.

• Differentiation multiplies amplitude by ω.

• Differentiation shifts the phase by ±π/2.

This is why angular frequency ω is preferred over Hertz in calculus-based analysis.

12
 2.2 Sinusoids: Amplitude, Frequency, and Phase

2.2.6 Harmonic Sinusoids

A harmonic is a sinusoid whose frequency is an integer multiple of a fundamental frequency
f0:
f k = k f 0, k = 1, 2, 3, . . .
Many natural signals (musical tones, vibrating strings, human speech) have harmonic
structure. Fourier series decomposes periodic signals into sums of harmonics.

2.2.7 Sum of Sinusoids and Beats

Consider two close frequencies f1 and f2:

x(t) = cos(2π f1t) + cos(2π f2t).

Using the identity

a+b a−b
cos a + cos b = 2 cos cos ,
2 2

we obtain:
x(t) = 2 cos (π( f1 + f2)t) cos (π( f1 − f2)t) .
This is a high-frequency oscillation modulated by a slow envelope. The envelope fre-
quency |f1 − f2 is called the beat frequency.
|
In acoustics, beats are used for instrument tuning. In communication systems, they relate
to heterodyning and mixing.

2.2.8 Discrete-Time Sinusoids

Sampling x(t) with sampling frequency fs yields:

f
x[n] = A cos 2π f n + φ .
s

The quantity
Ω f
= 2π
fs
is called the digital (or normalized) frequency in radians/sample.
A remarkable fact in DSP:
Two discrete-time sinusoids with frequencies Ω and Ω + 2πk represent exactly the
same samples.
Thus the discrete-time frequency domain naturally “wraps around” every 2π.

2.2.9 Aliasing
If f > fs/2, the sampled sinusoid appears as a different sinusoid with lower frequency. This
effect is called aliasing:

Ωalias = Ω − 2πk for some integer k.

Aliasing explains why sampling frequency must exceed twice the highest signal fre-
quency (Nyquist-Shannon theorem).

13
Chapter 2. Mathematical Background for DSP

2.2.10 Summary
Sinusoids are the fundamental building blocks of DSP because:
• LTI systems preserve their frequency and shape,

• derivatives preserve sinusoidal structure,

• sums of sinusoids remain sinusoids of the same frequency,

• they naturally arise from circular motion,

• Fourier methods express signals as weighted sums of sinusoids.

Understanding sinusoids in depth opens the door to the entire subject of
DSP.

2.3 Complex Numbers: Geometry, Algebra, and Their Role

in DSP
If there is one mathematical tool that separates those who merely use DSP from those
who truly understand it, that tool is the complex number. This statement may seem
surprising. After all, the signals we record with microphones and cameras are perfectly
real: there is nothing “imaginary” about a voltage or a sound pressure. And yet, the
moment you try to describe what happens to those signals inside a filter, or how their
frequency content is distributed, you find yourself reaching for complex numbers almost
involuntarily. They are not an optional convenience; they are the natural language of
oscillation and phase.
The historical origins of complex numbers have nothing to do with signals. They arose
in the 16th century, when Italian mathematicians such as Cardano and Bombelli were trying
to solve cubic equations. They noticed that intermediate steps in their solutions sometimes
required square roots of negative numbers. Though initially viewed with deep suspicion,
these “imaginary” quantities eventually revealed themselves as describing something pro-
foundly physical: geometric rotation. Today, complex numbers are indispensable across all
of engineering, and nowhere more so than in DSP.
Much of modern signal analysis, including Fourier transforms, modulation, phasor
analysis, and filter design, becomes elegant and tractable only when the complex plane is
introduced.

2.3.1 Algebraic Form

A complex number is written as
z = x + jy,
where:
• x = ℜ{z} is the real part,
• y = ℑ{z} is the imaginary part,
• j is the imaginary unit, defined by j2 = −1.
Complex numbers add and multiply according
to:
(x1 + jy1) + (x2 + jy2) = (x1 + x2) + j(y1 + y2),
(x1 + jy1)(x2 + jy2) = (x1x2 − y1y2) + j(x1y2 + x2y1).
14
 Multiplication mixes the real and imaginary components and, as we will see, represents
a geometric rotation when numbers are described in polar form.

15
 2.3 Complex Numbers: Geometry, Algebra, and Their Role in DSP

2.3.2 Geometric Interpretation: The Complex Plane

The complex plane (also called the Argand plane) is a two-dimensional space in which each
complex number corresponds to a point with coordinates (x, y). Alternatively, z can be
interpreted as a vector from the origin.

Magnitude and Angle. The magnitude (or modulus) is

q
|z| = x2 + y2,

and the angle (or argument) is

arg(z) = θ = tan−1(y/x),
with appropriate quadrant handling (in practice, the two-argument function atan2(y, x) is
used to resolve the ambiguity).
Thus every complex number can be written in polar form:
z = |z|(cos θ + j sin θ).
This representation is especially important in DSP because sinusoidal oscillations, phasor
relationships, and frequency responses all depend on magnitudes and angles.

2.3.3 Complex Conjugate

The complex conjugate of z = x + jy is
z∗ = x − jy.
Geometrically, z∗ is the reflection of z across the real axis.
Conjugation plays a key role in DSP:
• Real-valued signals have Fourier transforms with conjugate symmetry:
X(−ω) = X∗(ω).

• Energy of a discrete signal is computed using:

∑ x[n]x∗[n].
n

• Inner products in complex vector spaces use conjugation to ensure positivity.

2.3.4 Polar Form and Multiplication as Rotation

The polar representation
z = r(cos θ + j sin θ)
leads to a remarkable property:
r1(cos θ1 + j sin θ1) r2(cos θ2 + j sin θ2) = (r1r2) cos(θ1 + θ2) + j sin(θ1 + θ2) .
Thus multiplication corresponds to:
• Scaling the magnitudes: r1r2,
• Adding the angles: θ1 + θ2.
This is deeply connected to how frequency shifts work in DSP.

16
Chapter 2. Mathematical Background for DSP

[Link] a complex phasor by ejα rotates it counterclockwise by α.

This property explains:
• phase addition in amplitude modulation,

• carrier mixing in communication systems,

• phase delays in filters,

• how the Fourier transform shifts signals.

2.3.5 Division and Inversion

From polar form: z r
1
z = r1 cos(θ1 − θ2) + j sin(θ1 − θ2) .
2 2
Thus dividing complex numbers corresponds to subtracting angles.
For inversion: 1 1 z∗
= (cos(−θ) + j sin(−θ)) = .
z r |z|2
This identity is critical when computing impedance in AC circuits and frequency re-
sponses in DSP.

2.3.6 Euler
Representation
By Euler’s identity, ejθ = cos θ + j sin θ,

we can rewrite z = rejθ.

This compact form makes multiplication and exponentiation extremely simple:

z1z2 = r1r2ej(θ1 +θ2 ).

2.3.7 Complex Numbers in Signal Processing

Complex numbers are indispensable in DSP for several reasons:

1. Efficient Representation of Sinusoids. A

sinusoid
A cos(ωt + φ)
is the real part of the complex exponential

Aej(ωt+φ).

2. Fourier Transform. Frequency-domain representations are

complex-valued because they encode both:
• magnitude (how strong a frequency component is),

• phase (how shifted it is).

3. Modulation and Demodulation. Mixing

signals corresponds algebraically to multiply-ing by complex exponentials.

17
 2.4 Euler’s Formula and Complex Exponentials

4. Filter Frequency Response. Evaluating a filter at

frequency ω requires computing

H(ejω),

which is inherently complex.

5. Quadrature Representations. Modern communication systems use in-phase (I)

and quadrature (Q) components:
s(t) = I(t) + jQ(t).

2.3.8 Summary
• Complex numbers provide a natural geometric description of oscillations.

• Multiplication adds angles and scales magnitudes, which is perfect for representing
phase and amplitude changes.

• Complex exponentials unify trigonometry with exponential models.

• Nearly every DSP algorithm eventually relies on complex arithmetic.

The introduction of the complex plane transforms sinusoidal analysis from a collection
of trigonometric identities into a coherent geometric framework.

2.4 Euler’s Formula and Complex Exponentials

If you had to choose a single equation to summarize the entire mathematical foundation of signal
processing, a strong case could be made for Euler’s formula:

ejθ = cos θ + j sin θ.

At first glance, this identity seems almost too simple to carry such weight. On the left
side, an exponential function with an imaginary argument. On the right side, the familiar
sine and cosine. Yet this short equation is the bridge that connects geometry, algebra,
and analysis into a single unified framework. It tells us that the exponential function,
when fed an imaginary number, does not grow or decay. Instead, it rotates. The complex
exponential ejθ traces out a circle in the complex plane, and its real and imaginary parts
are the cosine and sine waves that form the backbone of Fourier analysis.
This identity is not merely a convenient rewriting of trigonometric functions; it reveals
that complex exponentials are circular motions. Thus, complex exponentials and sinusoids
represent the same phenomenon in two different languages: the analytic language of expo-
nentials and the geometric language of rotations.

2.4.1 Historical Background

Leonhard Euler (1707–1783) was one of the most prolific mathematicians in history, and his
discovery that the exponential function extends naturally to imaginary arguments ranks
among his greatest achievements. At the time, the idea was startling. Exponential functions
were understood as describing growth and decay: populations multiplying, investments
compounding, radioactive substances diminishing. What could they possibly have to do with
circles and oscillation? Euler saw what others had missed. He recognized that the function
ejθ traces out a circle in the complex plane as θ varies, maintaining unit magnitude while

18
Chapter 2. Mathematical Background for DSP

its angle increases steadily. Growth and rotation, two phenomena that appear completely
unrelated in everyday experience, turned out to be two faces of the same mathematical coin.
Nearly a century later, Joseph Fourier (1768–1830) took this insight and pushed it further.
Fourier realized that complex exponentials form the natural basis for representing periodic
signals. In his view, every periodic function, no matter how complicated, is nothing more
than a superposition of rotating exponentials. This was a bold and controversial claim. Many
of his contemporaries, including the great Lagrange, were skeptical. But Fourier was right,
and his insight fundamentally transformed mathematics, physics, and engineering.
Today the entire field of DSP rests on the fact that:
Complex exponentials are the eigenfunctions of all linear time-invariant (LTI)
systems.

2.4.2 Definition of the Complex Exponential

Using Euler’s identity:
ejθ = cos θ + j sin
θ. Thus, for any real number θ, ejθ lies on the unit
circle:

|ejθ | = 1.

Interpreting ejθ as a point in the plane, we see that it represents a rotation by angle θ.

Geometric consequences.

• Increasing θ rotates the point counterclockwise.

• Adding angles corresponds to multiplying exponentials:

ej(θ1+θ2) = ejθ1 ejθ2 .

• Negative angles rotate clockwise.

2.4.3 Complex Exponential as Uniform Circular Motion

Let θ(t) = ωt. Then
z(t) = ejωt
traces the unit circle at a constant angular speed ω.
Breaking into components:

z(t) = cos(ωt) + j sin(ωt).

Thus,

• The real part is a cosine wave.

• The imaginary part is a sine wave.

• Both have the same amplitude and frequency.

This fact allows us to treat complex exponentials as “parent objects” and sinusoids as
their projections.

19
 2.4 Euler’s Formula and Complex Exponentials

Im

ejπ/2 = j

ej3π/4 ejπ/4

ejθ

ej0 =
Re
1

ej5π/4

Figure 2.3: Complex exponentials ejθ as points on the unit circle. Each phasor is a vector
from the origin to the circle. As θ increases, the phasor rotates counterclockwise; its real part
traces a cosine and its imaginary part traces a sine.

2.4.4 The Fundamental Relations

cos θ =
ejθ + e−jθ
jθ
θ e − e−jθ
2 , sin 2j .
=
These identities express sinusoids as combinations of two rotating exponentials: one
rotating forward (+ω) and one rotating backward (−ω).

DSP importance. This decomposition is the basis for:

• Fourier series and Fourier transforms,
• analytic signals and Hilbert transforms,
• spectral energy distribution,
• modulation and demodulation,
• filter frequency response H(ejω ).

2.4.5 Derivatives and Integrals of ejωt

A defining feature of exponentials is that they reproduce themselves under differentiation:
d jωt
e = jω ejωt.
dt
Thus, differentiation:
• preserves the exponential structure,
• scales the signal by jω,
• adds a phase shift of π/2 (because multiplication by j is a rotation).
Integrals behave similarly:
∫ 1 jωt
ejωtdt = e +
C. jω

20
Chapter 2. Mathematical Background for DSP

Consequences.

• The derivative of a sinusoid is another sinusoid of the same frequency.

• The amplitude depends linearly on ω.

• Higher-frequency components contribute disproportionately to signal slope.

2.4.6 Magnitude and Phase

Writing z = rejθ gives:
|z| = r, arg(z) = θ.
Thus, complex exponentials encode:

• magnitude (amplitude),
• angle (phase).

In frequency-domain DSP, these two components describe:

X(ejω) = |X(ω)|ejφ(ω),

where the magnitude tells how much of the frequency ω is present, and the phase describes
how this component is shifted in time.

2.4.7 Frequency Shifting

Multiplying a signal by ejω0 t shifts its spectrum:

x(t) ejω0 t ⇐⇒ X(ω − ω0).

This identity is the foundation of:

• amplitude modulation (AM radio),

• frequency-division multiplexing,

• demodulation and downconversion,

• bandpass filtering.

2.4.8 Why Complex Exponentials Dominate DSP

Complex exponentials are the eigenfunctions of every linear time-invariant system. That is, if

x(t) = ejωt,

then the system output is

y(t) = H(jω)ejωt,
where H(jω) is a complex number representing:
• amplitude scaling (through |H(jω)|),
• phase shift (through arg H(jω)).

21
 2.5 Damped Exponentials and Derivatives of Sinusoids

Thus:
To know a system completely, it suffices to know how it acts on complex
exponentials.

This principle is the backbone of:

• Fourier analysis,
• digital filter design,
• spectral representations,
• frequency response characterizations.

2.4.9 Summary
Complex exponentials unify geometry, trigonometry, and analysis:
• They describe uniform circular motion.
• They encode sinusoids compactly.
• Their derivatives and integrals are simple.
• They form a natural basis for representing signals.
• They diagonalize LTI systems.
Virtually every mathematical technique in DSP relies on Euler’s formula, making it one
of the most important identities in all of engineering mathematics.

2.5 Damped Exponentials and Derivatives of Sinusoids

Up to this point we have considered pure sinusoids of the form cos(ωt + φ), which oscillate forever
with the same amplitude. However, real physical systems rarely behave this way. Mechanical
vibrations decay due to friction, electrical circuits lose energy through resistance, and
acoustic waves attenuate as they propagate.
To model such phenomena mathematically, we combine sinusoidal oscillation with
exponential decay.

2.5.1 Exponential Growth and Decay

A real exponential function takes the form
e−αt,
where α ≥ 0 determines the rate of decay.

Interpretation.
• If α = 0, the function is constant.
• If α > 0, the function decreases smoothly to zero.
• The larger α is, the faster the decay.
In physics, α often represents:
• mechanical damping coefficient,
• electrical resistance-induced decay in RLC circuits,
• attenuation constant in acoustic and electromagnetic propagation.

22
 Chapter 2. Mathematical Background for DSP

2.5.2 Damped Sinusoids

A damped sinusoid is defined as

x(t) = Ae−αt cos(ωt + φ),

with α > 0.
This waveform oscillates at frequency ω, but its amplitude decreases exponentially with
time. Damped sinusoids appear in:

• vibrating mechanical structures,

• underdamped RLC circuits,

• impulse responses of stable continuous-time systems,

• room acoustics,

• resonance phenomena.

2.5.3 Complex Representation of Damped Sinusoids

Using Euler’s identity:

x(t) = Ae−αt ℜ{ej(ωt+φ)} = ℜ{Aejφe(−α+jω)t }.

Define the complex frequency
s = −α + jω.
Then
x(t) = ℜ{Aejφest}.
Interpretati
on.
• The real part of s controls decay.
• The imaginary part of s controls oscillation.

Later, in the Laplace transform and z-transform chapters, this split becomes vital for
discussing stability and pole locations.

2.5.4 Envelope Behavior

The amplitude envelope of the damped sinusoid is:

|x(t)| ≈ Ae−αt.

This is the “outer curve” encapsulating the oscillation. For underdamped systems, the
oscillation persists as long as the envelope remains non-negligible.
Two useful quantities:

Time
constant 1
τ=.
α
The amplitude decays to 1/e of its original value in time τ.

23
 2.5 Damped Exponentials and Derivatives of Sinusoids

Damped sinusoid x(t) = e−t cos(6πt) with exponential envelope

1 e−t
cos(6πt)
0.5 Envelope
x(t

0
)

−0.5

−1
−0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
t
Figure 2.4: A damped sinusoid and its exponential envelope. The oscillation frequency
remains constant while the amplitude decays exponentially. This waveform is characteristic
of under-damped mechanical and electrical systems.

Half-
life ln 2
t1/2 = α .
These measures directly quantify how quickly oscillations disappear in physical systems.

2.5.5 Derivatives of Sinusoids

Differentiating a sinusoid preserves its shape but alters amplitude and phase:

d
cos(ωt + φ) = −ω sin(ωt + φ),
dt
d
sin(ωt + φ) = ω cos(ωt + φ).
dt
Thus differentiation:

• multiplies amplitude by ω,

• shifts the phase by ±π/2,

• preserves frequency.

2.5.6 Derivative of a Damped Sinusoid

Applying the product rule:

d
e−αt cos(ωt + φ) = −αe−αt cos(ωt + φ) − ωe−αt sin(ωt + φ).
dt

Factor out e−αt:

= e−αt [−α cos(ωt + φ) − ω sin(ωt + φ)] .
This is again a damped sinusoid (but with a phase shift determined by α and ω).

24
Chapter 2. Mathematical Background for DSP

2.5.7 Complex Exponential Derivative

If

x(t) = e(−α+jω)t,
then
d
x(t) = (−α + jω)x(t).
d
Thus the exponential reproduces t itself under differentiation, up to a multiplicative
constant.
This single property is the reason why exponentials are the eigenfunctions of LTI systems
and why differential equations with constant coefficients have exponential solutions.

2.5.8 Resonance: Underdamped, Critically Damped, Overdamped

Many systems can be described by a second-order differential equation:
2
d x dx 2
+ 2ζω0 + ω 0 x = 0.
dt2 dt
Depending on the damping ratio ζ:

Underdamped (0 < ζ < 1): Solution is a damped sinusoid:

x(t) = Ae−ζω0 t cos(ωdt + φ),

√
with ωd = ω0 1 − ζ2.

Critically damped (ζ = 1): Fastest non-oscillatory decay.

Overdamped (ζ > 1): No oscillation, slow decay.

This taxonomy appears later in DSP when analyzing poles of digital filters and deciding
whether a system behaves oscillatory or purely exponential.

2.5.9 Connection to Discrete-Time Systems

The analog exponential est sampled at t = nT yields the discrete-time exponential
x[n] = esnT,
where the discrete-time complex frequency is

z = esT.

Thus:

• Continuous-time exponentials correspond to powers of z in discrete time.

• Stability in continuous time (Re(s) < 0) corresponds to |z| < 1 in discrete time.
• Damped sinusoids correspond to spirals in the z-plane.

This relationship becomes essential in the z-transform chapter.

25
 2.6 Linear Algebra Essentials for DSP

2.5.10 Summary
• Exponential decay models real-world damping mechanisms.
• Damped sinusoids arise in underdamped oscillatory systems.
• The complex exponential e(−α+jω)t captures both decay and oscillation.
• Derivatives of exponentials reproduce the same form, explaining why exponential
signals diagonalize LTI systems.
• Sampling exponentials naturally leads to z-plane analysis in discrete-time DSP.

2.6 Linear Algebra Essentials for DSP

The connection between linear algebra and signal processing is more than an analogy; it
is a precise mathematical correspondence. A discrete-time signal x[n] defined for n
= 0, 1, . .—. , N 1 is mathematically identical to a vector in RN (or N for complex
signals). Ad-dition of signals corresponds to vector addition, scaling corresponds to scalar
multiplication,
and all the geometric ideas of linear algebra (length, angle, projection, basis decomposition)
carry over directly.
This perspective transforms Fourier analysis from a mysterious integral formula into a
natural geometric operation: projecting a signal vector onto an orthogonal basis.

2.6.1 Signals as Vectors

Consider a discrete-time signal of length N:
x[n] = {x[0], x[1], . . . , x[N − 1]}.
We can identify this signal with the vector 

x[0]
x[1]  ∈ N .
x=  .

x[N − 
1]
In this view, every length-N signal is a point (or equivalently, an arrow from the origin)
in an N-dimensional space. Two signals can be added, subtracted, and scaled just like
ordinary vectors. This is not merely a notational convenience; it gives us access to the entire
machinery of linear algebra.

2.6.2 Inner Product

The inner product measures the “similarity” between two signals. For continuous signals
defined over an interval [a, b]:
∫ b
⟨x, y⟩ = x(t) y∗(t) dt.
a
For discrete signals of length N:
N
⟨x, y⟩ = 1—
x[n] [n].
∑ y∗
n=0
The inner product has several important properties: ⟨x, x ⟩ ≥ 0 (with equality only when
x = 0), and it is linear in the first argument and conjugate-linear in the second. The norm
(or “energy”) of a signal is defined as x √= ⟨x, x⟩.

26
Chapter 2. Mathematical Background for DSP

Example. Let x = (1, 2, −1) and y = (3, 0, 4). Then

⟨x, y⟩ = (1)(3) + (2)(0) + (−1)(4) = −1.
The nonzero inner product tells us these two vectors are not orthogonal: they share
some common “direction” in three-dimensional space.

2.6.3 Orthogonality
Two signals x and y are orthogonal ⟨ if x, y = 0. Geometrically, orthogonal signals
are “perpendicular”: they share no common ⟩ structure.
Orthogonality is the single most important concept connecting linear algebra to Fourier
analysis. When we decompose a signal into frequency components, we are projecting it onto
a set of orthogonal basis functions. The reason those projections do not interfere with each
other is precisely because the basis functions are orthogonal.

2.6.4 Basis and Dimension

A basis for N is a set of N linearly independent vectors { v0, v1, . . . , }
vN−1 such that
every vector in the space can be written uniquely as a linear combination:
x = c0v0 + c1v1 + · · · + cN−1vN−1.
The coefficients ck are the coordinates of x in this basis. Different bases give different
coordinate representations of the same signal. The standard basis uses unit vectors along
each axis, and the coordinates are simply the sample values x[0], x[1], The Fourier
basis
uses complex exponentials, and the coordinates are the DFT coefficients X[0], X[1], The
signal itself has not changed; only the language used to describe it is different.

2.6.5 Orthogonal and Orthonormal Bases

A basis is orthogonal if all its vectors are mutually orthogonal:
⟨vk, vm⟩ = 0 for k ̸= m.
It is orthonormal if, in addition, every basis vector has unit norm:
⟨
v 1, k = m,
k
, v m⟩= δ[k −m] =
( 0, k ̸= m.
The great advantage of an orthonormal basis is that the expansion coefficients can be
found by a simple inner product:
ck = ⟨x, vk⟩.
No matrix inversion, no system of equations. Just a dot product. This is why orthonormal
bases are so prized in signal processing.

2.6.6 Projection
Given a vector x and a unit vector v, the projection of x onto v is
projv x = ⟨x, v⟩ v.
The scalar ⟨x, v tells us “how much of x points in the direction of v.” This is exactly
what a DFT coefficient
⟩ does: X[k] =⟨ x, vk measures how much of the signal x oscillates
at the k-th frequency. ⟩

27
 2.7 Fundamental Discrete-Time Signals

[Link] x = (3, 4) and v = √1 (1, 1). Then

2

1 7
⟨x, v⟩ = √ (3 + 4) = √ ,
2 2
and the projection of x onto v is √27 · √21 (1, 1) =2 7 (1, 1) = (3.5, 3.5). This is the component of
(3, 4) that lies along the diagonal direction.

2.6.7 The Fourier Basis

The complex exponentials {ej2πkn/N} for k = 0, 1, . . . , N
− 1 form an orthogonal set over N
samples:
(
N−1 N−1
N, k = m,
ej2πkn/N
∑−j2πmn/N = =
e n=0 e∑
j2π(k−m)n/N 0, k ̸= m.
n=0
√
Dividing each basis vector by N produces an orthonormal set. This orthogonality is
the mathematical reason why Fourier decomposition works: each DFT coefficient X[k] is the
inner product of the signal with the k-th basis function, and orthogonality guarantees that
the contributions from different frequencies do not interfere with each other.

Example. Consider two discrete-time sinusoids of length N = 8: x[n] = cos(2πn/8) and

y[n] = cos(2π · 2n/8). Computing the inner product:
7
⟨x, y = ∑ 2πn cos 4πn = 0.
⟩cos
8 8
n=0

The two sinusoids are orthogonal: they occupy independent “directions” in the 8-
dimensional signal space. This is why the DFT can extract the amplitude of each frequency
component independently, without contamination from others.

2.7 Fundamental Discrete-Time Signals

2.7.1 Unit Impulse
(
1, n = 0,
δ[n] = 0, n =
̸ 0.

2.7.2 Un
it Step
(
1, n ≥ 0,
u[n] = 0, n < 0.

2.7.3 Rectangul
ar Pulse
1, 0 ≤ n < L,
rect [n] = 0, otherwise.
L

28
Chapter 2. Mathematical Background for DSP

2.7.4 Sinc
Function
sin(πx)
sinc(x) = .
πx
This is the impulse response of the ideal low-pass filter and the Fourier transform of a
rectangular pulse.

Problems
1. Draw the unit circle and mark the points corresponding to θ = 0, π/6, π/4, π/3, π/2, π.
Write the coordinates (cos θ, sin θ) for each.

2. Show, using the geometry of the unit circle, that cos θ is an even function and sin θ
is an odd function.

3. A sinusoid is given by x(t) = 3 cos(100πt + π/6). Determine the amplitude,

frequency (in Hz), angular frequency, period, and phase.

4. Two sinusoids x1(t) = cos(2π ·440 t) and x2(t) = cos(2π · 446 t) are added together.
Using the sum-to-product identity, find the beat frequency and describe what a listener
would hear.

5. Let z1 = 3 + 4j and z2 = —
1 2j. Compute: (a) z1 + z2, (b) z1z2, (c)| z|1 and arg(z1), (d)
z1/z2.

6. Express z = 2ejπ/3 in rectangular form x + jy, and verify that |z|2 = x2 + y2.

7. Using Euler’s formula, show that cos2 θ = 12 (1 + cos 2θ). This identity is used in AM
demodulation. Explain briefly why.

8. A damped sinusoid is given by x(t) = 5 e−2t cos(10πt). (a) Find the time constant τ.
(b) After how many seconds has the amplitude decayed to less than 1% of its initial
value?

9. Consider the first-order difference equation y[n] = 0.9 y[n− 1] + x[n] with −y[ 1] =
0. Compute y[0], y[1], y[2], y[3] when the input is the unit impulse x[n] = δ[n].

10. Show that the sinusoids cos(2π f1t) and cos(2π f2t) with ̸f1 = f2 are orthogonal
over the interval [0, T] where T is a common period. What role does this orthogonality
play in Fourier analysis?

11. Write cos(ωt + φ) as a linear combination of cos(ωt) and sin(ωt). A signal x(t) =
4 cos(2π · 50 t) − 3 sin(2π · 50 t) is given; find its amplitude and phase.

12. (Research) The Cooley–Tukey FFT paper of 1965 was not the first time the
algorithm was discovered. Investigate who else discovered similar algorithms before
them, and discuss why the earlier discoveries did not have the same impact.

29
 2.7 Fundamental Discrete-Time Signals

• Sinusoids are projections of uniform circular motion; the unit circle unifies
trigonometry with signal analysis.
• Complex exponentials ejθ encode both amplitude and phase, making them the
natural language of DSP.

• Euler’s formula bridges geometry and algebra: ejθ = cos θ + j sin θ.

• Damped sinusoids model real physical systems where energy dissipates over time.

• Orthogonality of sinusoids is the reason Fourier decomposition works.

30
 3 CHAPTER
3

Fundamental Concepts

The concepts in this chapter (signals, sampling, convolution, impulse response, stability)
may seem like they belong to the age of digital computers, but their intellectual roots reach
much further back.
The idea that physical phenomena can be represented as mathematical functions
emerged in the 17th century, when Newton and Leibniz developed calculus. The systematic
study of how systems respond to inputs began in the 18th century with Euler’s work on
vibrating strings and d’Alembert’s wave equation. By the 19th century, Fourier had
shown that any periodic function could be decomposed into sinusoids, and Heaviside had
introduced operational calculus, a precursor to the Laplace and Z-transforms, to analyze
electrical circuits.
The transition from continuous to discrete happened gradually. In 1928, Harry Nyquist,
working at Bell Telephone Laboratories, published a paper on telegraph transmission rates
that contained the kernel of the sampling theorem. In 1949, Claude Shannon gave the
theorem its modern form, proving that a band-limited signal can be perfectly reconstructed
from its samples if sampled fast enough. This single result justified the entire enterprise of
digital signal processing: it meant that nothing was lost by converting continuous signals
into sequences of numbers.
With the arrival of digital computers in the 1950s and 1960s, engineers realized that all
the elegant theory of linear systems (superposition, convolution, transfer functions) could be
applied to discrete-time sequences just as well as to continuous-time signals. The concepts
in this chapter are the result of that realization.

3.1 Continuous-Time and Discrete-Time Signals

Continuous-Time Signals
A continuous-time signal is a function of a real variable t:

x(t), t ∈ R.
The argument t is often physical time measured in seconds. The value x(t) might be a
voltage, a sound pressure level, a temperature, or some other physical quantity.
Examples:

• A microphone recording of speech, modeled as x(t) with t in seconds.

• The voltage at the output of an analog sensor.

31
 3.1 Continuous-Time and Discrete-Time Signals

• The displacement of a vibrating structure as a function of time.

In continuous time, we can, in principle, evaluate x(t) at any real time instant. This is an
idealization, but it is useful for modeling many physical phenomena.

Discrete-Time Signals
A discrete-time signal is defined only at integer time indices:

x[n], n ∈ Z.
Here n is an integer that usually corresponds to a sample index. We can think of x[n] as a sequence of
numbers:

. . . , x[−2], x[−1], x[0], x[1], x[2], . . .

Examples:

• A digital audio file stored as a list of samples.

• Temperature measurements recorded every hour.

• Any signal stored in a computer or processed by a digital filter.

In practice, most real applications use finite-length segments of discrete-time signals,
for example x[n] only for 0 ≤ n ≤ N − 1.

Relationship Between x(t) and x[n]

We often obtain x[n] by sampling a continuous-time signal x(t):
x[n] = x(nTs),

where Ts is the sampling period in seconds and fs = 1/Ts is the sampling frequency in Hz.
This means that x[0] = x(0), x[1] = x(Ts), x[2] = x(2Ts), and so on. The discrete-
time signal is therefore a snapshot of what happens at discrete times in the continuous
signal.
Understanding how much information about x(t) is preserved in x[n] is one of the main
questions of DSP and leads directly to the sampling theorem.

Continuous-time signal and its samples ( f = 50 Hz, fs = 200 Hz)

1 x(t) = cos(2π · 50 t)
Samples x[n]
Amplitude

−1

−1 · 10−2 0 1 · 10−22 · 10−23 · 10−24 · 10−25 · 10−26 · 10−27 · 10−28 · 10−29 · 10−2 0.1 0.11
t (seconds)

Figure 3.1: A continuous-time cosine at 50 Hz sampled at fs = 200 Hz. Four samples per
period are sufficient to capture the waveform; the Nyquist condition fs ≥ 2 f is satisfied.

32
Chapter 3. Fundamental Concepts

Summary
• Continuous-time signals x(t) are defined for all real t.
• Discrete-time signals x[n] are defined only for integer n.

• In DSP, we primarily work with discrete-time signals, often obtained by sampling a

continuous-time signal.

3.2 Sampling, Nyquist Rate, and Aliasing

The question of how often one must measure a changing quantity to capture it faithfully
is ancient in spirit. Astronomers faced it when recording planetary positions at discrete
observation times. But its precise mathematical answer is surprisingly modern.
In 1928, Harry Nyquist published a paper on the maximum signaling rate of a
telegraph channel, in which he implicitly identified the critical sampling rate. Around the
same time, the Soviet engineer Vladimir Kotelnikov independently derived the same
result. But it was Claude Shannon who, in his landmark 1949 paper “Communication in the
Presence of Noise,” gave the theorem its definitive form and rigorous proof, establishing
that a band-limited signal can be perfectly reconstructed from equally spaced samples,
provided the sampling rate is high enough.
This result is arguably the single most important theorem in DSP. Without it, there would
be no theoretical justification for digital audio, digital images, or any form of analog-to-digital
conversion.

Sampling Process
Sampling is the operation that creates a discrete-time signal from a continuous-time signal.
Mathematically:
x[n] = x(nTs).
The sampling frequency fs determines how many samples we take per second:

1
fs = Ts [Hz].

Intuitively, the faster we sample, the more detailed information we capture about the
original signal. However, sampling too fast can be wasteful, and sampling too slowly can
destroy important information.

The Nyquist–Shannon Sampling Theorem

The Nyquist–Shannon sampling theorem gives a precise condition for perfect reconstruction:
If a continuous-time signal x(t) has no frequency content above fmax (it is
band-limited), and we sample it at a rate
fs ≥ 2 fmax,
then x(t) can be perfectly reconstructed from its samples x[n].
The value fN = fs/2 is called the Nyquist frequency. To avoid aliasing, the highest
signal frequency fmax must be less than or equal to f N .

33
 3.2 Sampling, Nyquist Rate, and Aliasing

Aliasing and Frequency Folding

If we sample with fs < 2 fmax, then different continuous-time frequencies become
indistin-guishable after sampling. This phenomenon is called aliasing.
A continuous-time sinusoid with frequency f Hz, when sampled at fs Hz, appears as
a discrete-time sinusoid whose effective frequency is

falias = | f − k fs| ,

for some integer k chosen so that falias lies in the range [0, fs/2].
We can think of the frequency axis as being periodic and folding back into the
interval [0, fs/2]. High frequencies are folded down into this range, potentially causing
serious distortion.

Examples of Aliasing
Example 1. Suppose we have a sinusoid with frequency f = 900 Hz and we sample
at fs = 1000 Hz. The Nyquist frequency is fN = 500 Hz. It is clear that f > f N , so
aliasing will occur.
We can compute:
falias = |900 − 1 · 1000| = 100 Hz.

The resulting discrete-time samples look exactly like a 100 Hz signal. There is no way to
distinguish the original 900 Hz sinusoid from a 100 Hz sinusoid if we only see the samples.

Aliasing: a 900 Hz and a 100 Hz sinusoid produce identical samples at fs =

1000 Hz

1
Amplitude

cos(2π · 900
−1 t)
cos(2π · 100
Samples
t) at fs = 1000 Hz

−0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1
t (seconds)
·10−2
Figure 3.2: Aliasing demonstrated. The 900 Hz sinusoid (blue) and the 100 Hz sinusoid
(red) pass through exactly the same sample points (black dots) when sampled at fs = 1000
Hz. From the samples alone, the two signals are indistinguishable.

Example 2. Consider fs = 8000 Hz, which is a common sampling frequency for

telephony audio. The Nyquist frequency is 4000 Hz. Any frequency component above 4000
Hz will be aliased into the range [0, 4000] Hz. For this reason, analog anti-aliasing low-pass
filters are placed before the sampler in most audio systems to attenuate frequencies above
the desired band.

34
Chapter 3. Fundamental Concepts

Summary
• Sampling must satisfy fs ≥ 2 fmax to avoid aliasing.

• Aliasing makes different continuous-time frequencies appear as the same discrete-time

frequency.

• Anti-aliasing filters and proper choice of fs are essential in practical systems.

3.3 Quantization and Analog-to-Digital Conversion

Sampling converts a continuous-time signal into a discrete-time signal, but the sample values
are still continuous real numbers with infinite precision. A real digital system must represent
each sample with a finite number of bits. This process is called quantization, and it is the
second essential step in analog-to-digital conversion.

The Quantization Process

A B-bit quantizer maps the continuous amplitude range into 2 B discrete levels. If the signal
range is [−V, +V], the spacing between adjacent quantization levels is
2V
∆= .
2B

Each sample x[n] is replaced by the nearest quantization level xq[n]. The difference
between the original and quantized values is called the quantization error:

e[n] = x[n] − xq[n].

For a properly designed quantizer, the error satisfies |e[n]| ≤ ∆/2.

3-bit quantization of a cosine signal (23 = 8 levels)

1 Original x[n]
Quantized xq[n]
Amplitude

−1

0 2 4 6 8 10 12 14 16
n
Figure 3.3: A cosine signal quantized with 3 bits (8 levels). The horizontal gray lines show
the quantization levels. The staircase-like quantized signal (red, dashed) follows the original
(blue) but introduces a small error at each sample. Increasing the number of bits reduces this
error.

35
 3.4 Basic Classes and Properties of Discrete-Time Signals

Quantization Noise and Signal-to-Noise Ratio

When the signal is sufficiently complex relative to the step size ∆, the quantization error can
be modeled as a random variable uniformly distributed over [— ∆/2, +∆/2]. Under this
model, the average power of the quantization noise is

2 ∆2
σe = .
12
For a full-scale sinusoidal input, the signal power is V2/2. The Signal-to-Quantization-
Noise Ratio (SQNR) is then
V2/2 3 2B
SQNR
= 2 = ·2 ,
∆ /12 2
which in decibels gives the well-known rule of thumb:

SQNRdB ≈ 6.02 B + 1.76 dB.

This tells us that every additional bit of resolution improves the SNR by
approximately 6 dB. A 16-bit audio system (CD quality) achieves about 98 dB of dynamic
range, while a 24-bit professional recording system reaches roughly 146 dB.

Practical Considerations
• Clipping: If the input exceeds the range — [ V, +V], the quantizer saturates at the
extreme levels. Clipping produces severe distortion and must be avoided by proper
gain control.

• Dithering: Adding a small amount of random noise before quantization can

paradoxi-cally improve audio quality by breaking up the correlation between the signal
and the quantization error. This technique is standard in professional audio.

• Oversampling: Sampling at a rate much higher than the Nyquist rate, combined
with digital filtering and decimation, allows the effective resolution to exceed the
nominal bit depth of the ADC.

3.4 Basic Classes and Properties of Discrete-Time Signals

In this section we classify signals according to several basic properties. This helps build
intuition and prepares us for Fourier analysis and energy concepts later.

Real vs. Complex Signals

A discrete-time signal may be real-valued or complex-valued:

x[n] ∈ R or x[n] ∈ .

In many physical measurements, the raw signal is real-valued. However, complex-

valued signals are extremely convenient for mathematical analysis (for example, when using
complex exponentials ejΩn).

36
Chapter 3. Fundamental Concepts

Even and Odd

Signals
A signal x[n] is even
x[−n] = x[n] for all n.
if It is odd if
x[−n] = −x[n] for all

n.
Every signal can be decomposed into an even and an odd part:

x[n] = xe[n] + xo[n],

with 1 1
xe[n] = (x[n] + x[−n]), xo[n] = (x[n] − x[−n]).
2 2
This decomposition is useful in Fourier analysis and in understanding symmetry proper-
ties.

Energy and Power Signals

For a discrete-time signal x[n], the energy is defined as
∞
Ex = ∑ |x[n]|2 .
n=−∞

If this sum is finite, we call x[n] an energy signal. These are usually signals that exist
only for a finite time or decay to zero as n ∞.
A power signal has infinite energy → but
± finite average power:
P 1
x = lim N
∑ |x[n]|2 .
N
→∞ 2N + 1 n=−N

Periodic signals (such as pure sinusoids) are typical examples of power signals.
These concepts become important when we study Parseval’s theorem and spectral energy
distributions.

3.5 Basic Operations on Discrete-Time Signals

Several simple operations are applied to discrete-time signals in almost every DSP algorithm.
Understanding these operations helps us interpret the structure of systems and filters.

Time Shifting
Shifting a signal by n0 samples results in

y[n] = x[n − n0].

If n0 > 0, the signal moves to the right (delay). If n0 < 0, the signal moves to the left
(advance).
Example: (
1, 0 ≤ n ≤ 3,
x[n] = 0, otherwise,
then x[n − 2] is the same pulse starting at n = 2 and ending at n = 5.

37
 3.6 Linear Time-Invariant (LTI) Systems

Time Reversal
Time reversal (or reflection) is defined as
y[n] = x[−n].
This mirrors the signal with respect to n = 0.

Scaling
Multiplying a signal by a constant a:
y[n] = ax[n],
changes its amplitude but not its shape.

Addition and Superposition

The pointwise sum of two signals x1[n] and x2[n] is defined as
y[n] = x1[n] + x2[n].
This operation is closely tied to the principle of superposition in linear systems.

Modulation (Multiplying by a Sinusoid)

Multiplying a signal by a sinusoid
y[n] = x[n] cos(Ω0n)
is called modulation. In the frequency domain, this corresponds to shifting the spectrum of
x[n] by± Ω0 radians per sample. This operation is essential for communications, demodula-
tion, and frequency translation.

3.6 Linear Time-Invariant (LTI) Systems

The System Viewpoint
In DSP, we often think of a system as a transformation that takes an input signal x[n]
and produces an output signal y[n]:
y[n] = S{x[n]}.
The system could be a digital filter, an equalizer, a smoothing algorithm, a prediction
model, or something more complex.
Two properties are especially important:
• Linearity
• Time invariance

Linearity
A system is linear if for any signals x1[n], x2[n] and any scalars a, b:
S{ax1[n] + bx2[n]} = aS{x1[n]} + bS{x2[n]}.
Linearity means that scaling and addition commute with the system. If you double the
input, you double the output. If you add two inputs together, the response is the sum of the
responses to each input separately.

38
Chapter 3. Fundamental Concepts

Time Invariance
A system is time-invariant if a time shift in the input results in the same time shift in
the output:
If x[n] → y[n], then x[n − n0] → y[n − n0].
In other words, the system behaves the same way at all times. Its behavior does not
depend on the absolute time index, only on relative differences.

Examples of Linear and Non-Linear Systems

To test whether a system is linear, we check whether S{ax1[n] + bx2[n]} = a
S{x1[n]} + b S{x2[n]} holds for arbitrary inputs and scalars.

Example 1: A Linear System.S{ Let x[n] } = 2x[n] and choose x1[n]

{ = }1, 2, 3 , x2[n] =
{4, 5, 6} , a = 2, b = 3.
Applying the system to each input separately:

S{x1} = {2, 4, 6}, S{x2} = {8, 10, 12}.

Now combine first, then apply:

ax1 + bx2 = {14, 19, 24}, S{ax1 + bx2} = {28, 38, 48}.

Compare with the scaled sum of individual outputs:

a S{x1} + b S{x2} = {4, 8, 12} + {24, 30, 36} = {28, 38, 48}.

The results match, so S{x[n]} = 2x[n] is linear.

Example 2: A Non-Linear System. Let S{x[n]} = x[n]2. Using the same inputs and
scalars:
S{ax1 + bx2} = {14 2, 19 2, 24 } = {196, 361, 576}.
2

a S{x1} + b S{x2} = {2, 8, 18} + {48, 75, 108} = {50, 83, 126}.
The results differ, so squaring is not linear. This simple test is a powerful way to expose
nonlinearity.

Example 3: Moving Average Filter. Consider

1
y[n] = (x[n] + x[n − 1] + x[n − 2]).
3
This system is both linear and time-invariant. Applying the system to ax1[n] + bx2[n]
yields ay1[n] + by2[n] (linearity), and shifting the input by n0 simply shifts all indices by n0
(time invariance).

Examples of Time-Invariant and Time-Varying Systems

To test time invariance, we compare two paths: (a) shift the input first, then apply the system,
and (b) apply the system first, then shift the output. If the results always match, the system
is time-invariant.

39
 3.7 Difference Equations for Discrete-Time Systems

S{ } − −
Example 1: Time-Invariant
− x[(n− n ) 2] System. x[n] = x[n 2]. If we replace x[n]
− = x[n (n + 2)]. If instead we first compute by −
x[n
n0], the output becomes 0 0 y[n]
= x[n 2] and then shift,−we get y[n − n0] − = x[(n n0) 2]. Both paths give the same
result, so this system is time-invariant.

Example 2: Time-Varying System. S{x[n]} = n x[n].

Path (a): Replace input by x[n − 1], then apply the system:

S{x[n − 1]} = n x[n − 1].

Path (b): Apply the system first to get y[n] = n x[n], then shift:
y[n − 1] = (n − 1) x[n − 1].
Since n x[n—1] ̸ = (n− 1) x[n−1] in general, the system is not time-invariant. The explicit
dependence on the time index n is the telltale sign.

Example 3: First-Order Accumulator. S{x[n]} = x[n] + x[n − 1].

Path (a): Replace x[n] by x[n − n0]:

S{x[n − n0]} = x[n − n0] + x[(n − n0) − 1] = x[n − n0] + x[n − n0 − 1].
Path (b): Compute y[n] = x[n] + x[n − 1], then shift:
y[n − n0] = x[n − n0] + x[n − n0 − 1].

Both expressions are identical, so this system is time-invariant. The coefficients do not
depend on n, only on relative delays.

Non-example: Time-Varying Gain. S{ } x[n] = n x[n] is linear (scaling and

addition still work) but not time-invariant, as shown above. It is therefore not an LTI
system.

Why LTI Systems Are Special

LTI systems occupy a central place in DSP because:

• They are mathematically tractable.

• Their behavior is completely characterized by their impulse response h[n].

• Convolution and Fourier methods apply cleanly.

• Most practical filters, equalizers, and modulators are designed as LTI systems.

3.7 Difference Equations for Discrete-Time Systems

Linear Constant-Coefficient Difference Equations
Many discrete-time systems can be described by a linear constant-coefficient difference
equation (LCCDE):
N M

∑ ak y[n— k] ∑ bm x[n— m].

= m=0
k=0

40
Chapter 3. Fundamental Concepts

Equivalently, we can write

N M
y[n] = − ∑ ak y[n − k] + ∑ bm x[n − m],
k=1 m=0

assuming a0 = 1 for
simplicity.
Here,
• The ak coefficients describe the dependence on past outputs (feedback).
• The bm coefficients describe the dependence on current and past inputs (feedforward).

First-Order Example
Consider
y[n] = a y[n − 1] + b x[n].
This is a first-order system. If |a < 1, the effect of an impulse or any bounded input
decays over time, and the system| is stable. | If a > 1, the recursion will amplify past
outputs and eventually blow up. |
This simple equation can model exponential decay, leaky integration, and simple
feedback processes.

Solution Structure
For a first-order system y[n] = a y[n
— 1] + b x[n], the complete response can be
decomposed into two parts:
y[n] = any[0] n
` ˛¸ x + b ∑ an−kx[k] .
natu ral r esp onse
` k =0 ˛ ¸ x
forced re sponse

The natural response depends only on the initial condition and decays (or grows)
expo-nentially. The forced response is a weighted sum of present and past inputs. It is, in
fact, a convolution. This decomposition foreshadows the general result that every LTI
system response can be expressed as a convolution with the impulse response.

3.8 Impulse Response, Convolution, and Step Response

Impulse Response
The impulse response h[n] of an LTI system is defined as the output when the input is
the unit impulse:
x[n] = δ[n] ⇒ y[n] = h[n].
Because of linearity and time invariance, h[n] completely determines the system. Every
output for every input can be expressed using h[n].

Convolution Sum
For an LTI system with impulse response h[n], the output for an arbitrary input x[n] is given
by the convolution sum:
∞
y[n] = (x ∗ h)[n] ∑ x[k] h[n − k].
= k=−
∞
Intuitively:

41
 3.9 Stability and Causality of LTI Systems

• We take the impulse response h[n] and shift it to position k.

• We scale the shifted response by x[k].
• We sum these contributions over all k.

Example: Moving Average

Filter
Consider again the moving average: (1
3 , n = 0, 1,
2, 0, otherwise.
h[n] =

If x[n] is any input, then y[n] = (x ∗h)[n] is the local average of the last three samples.
This simple filter is widely used for smoothing noisy data.

Input x[k] Impulse response h[k]

1 1
3

0 0
0 1 2 3 4 0 1 2
Output y[n]k= (x ∗
k
h)[n]

0.5

0
0 1 2 3 4 5 6
n
Figure 3.4: Convolution of a rectangular pulse x[n] (length 5) with a moving-average impulse
response h[n] (length 3). The output y[n] is a trapezoidal shape of length— 5 + 3 1 = 7,
illustrating how convolution “spreads” and smooths the input signal.

Step Response
The step response of an LTI system is the output when the input is the unit step u[n]:

n
s[n] = (u ∗ h)
[n] =
∑ h[k].
k=−
∞

For stable systems, h[n] tends to zero and s[n] tends to a constant value. The step response
provides an intuitive picture of how the system reacts to a sudden change from 0 to 1.

3.9 Stability and Causality of LTI Systems

42
Chapter 3. Fundamental Concepts

BIBO Stability
A system is BIBO stable (bounded-input, bounded-output) if every bounded input
produces a bounded output. For LTI systems, there is a very important and simple
condition:
∞
The LTI system is BIBO stable ⇐⇒ ∑ |h[n]| < ∞.
n=−∞

If the absolute values of the impulse response samples sum to a finite number, the system
cannot amplify a bounded input into an unbounded output.

Causality
A system is causal if the output at time n depends only on current and past inputs:
y[n] depends only on x[k] for k ≤ n.
For an LTI system, this means h[n] = 0 for all n < 0. In other words, the impulse
response has no support in the negative time indices. This is necessary for real-time
implementation because we cannot react to future inputs.

Example: First-Order System Revisited

For
y[n] = a y[n − 1] + b x[n],
the impulse response is h[n] = banu[n].| If| a < 1, the sequence | h[n] decays
exponentially and| the sum ∑ h[n] converges. Thus the system| is BIBO stable.
If |a| ≥ 1, the
| response does not decay, and the system is not BIBO stable. This example
shows how the parameter a controls both the dynamics and the stability.

Problems
1. A continuous-time signal has frequency components at 1, 3, and 5 kHz. What is the
minimum sampling frequency that avoids aliasing? What is the corresponding Nyquist
frequency?
2. A 400 Hz sinusoid is sampled at fs = 600 Hz. Compute the alias frequency that will
appear in the discrete-time domain. Repeat for fs = 500 Hz.
3. Let (
1, 0 ≤ n ≤ 3,
x[n] = 0, otherwise.
Sketch x[n], x[n− 2], and x[−n]. Explain in words what time shifting and time reversal
do to this pulse.
4. Show that any signal x[n] can be decomposed into an even part xe[n] and an
odd part xo[n]. Write down explicit formulas and verify that xe[−n] = xe[n] and
xo[−n] =
−xo[n].
5. Compute the energy of the signal x[n] = (0.8)nu[n]. Is this an energy signal or a
power signal?
6. Determine whether the system y[n] = x[n]· x[n− 1] is (a) linear, (b) time-invariant,
(c) causal. Justify each answer.

43
 3.9 Stability and Causality of LTI Systems

7. For the impulse response h[n] = (0.5)nu[n], determine whether the system is
BIBO stable. Then compute the step response s[n] = (u ∗ h)[n] and find its steady-
state value as n → ∞.
8. Given x[n] = {1, 2, 1} and h[n] = {1, −1} (both starting at n = 0), compute y[n]
= (x ∗ h)[n] by hand. State the length of the output sequence.
9. Consider the system y[n] = 0.8 y[n 1] + x[n]. (a) Show that the impulse
response is h[n] = (0.8)nu[n]. (b) Compute| ∑n=0 h[n] and verify that the system is
− changes
stable. (c) What happens if the coefficient from 0.8 to 1.2?
∞ |

10. A moving average filter of length L has impulse response h[n] =L 1 for 0 ≤ n ≤ L −
1 and zero otherwise. For L = 4, compute the convolution of h[n] with x[n] =
δ[n] − δ[n − 3].
11. A system has the difference equation y[n] = x[n] − 2x[n −1] + x[n− 2]. (a) Find the
impulse response. (b) Is the system FIR or IIR? (c) Describe qualitatively what this
filter does to a slowly varying input signal.
12. A 12-bit ADC operates over the range [— 5V, +5V]. (a) How many quantization levels
does it have? (b) What is the step size ∆? (c) Compute the SQNR in dB using the
6.02B + 1.76 formula.
13. Explain in your own words why dithering (adding noise before quantization) can
improve the perceived quality of a quantized audio signal. Under what conditions
does this technique fail?
14. (Research) In 1928, Harry Nyquist published his famous theorem on sampling.
How-ever, the theorem is also attributed to Claude Shannon (1949) and sometimes to
Whit-taker (1915). Investigate the contributions of each and explain why the theorem
carries multiple names.

• Discrete-time signals are sequences x[n] obtained by sampling continuous-

time signals at rate fs.
• The Nyquist theorem requires fs ≥ 2 fmax to avoid aliasing.
• Quantization maps continuous sample values to a finite set of levels; each addi-
tional bit improves the SNR by approximately 6 dB.
• LTI systems are fully characterized by their impulse response h[n]; the output for
any input is given by convolution.

• A causal LTI system is BIBO stable if and only if ∑ |h[n]| < ∞.

44
 4 CHAPTER
4

The Z-Transform

The idea of associating a power series with a sequence of numbers has deep roots in math-
ematics. Generating functions, which encode sequences as coefficients of a formal power
series, were used by Euler and Laplace in the 18th century to solve combinatorial and proba-
bilistic problems. Abraham de Moivre, as early as 1730, employed generating functions to
analyze the Fibonacci sequence, an approach that is strikingly similar in spirit to modern
Z-transform techniques.
When engineers in the mid-20th century began building digital systems (radar
processors, early computers, sampled-data control loops), they needed a transform that
played the same role for discrete-time signals as the Laplace transform played for
continuous-time systems. The Laplace transform, developed by Pierre-Simon Laplace around
1785 and later systematized by Oliver Heaviside in the 1890s for circuit analysis, had proven
enormously powerful for continuous-time problems. But it could not be applied directly to
sequences of numbers produced by sampling.
The Z-transform emerged to fill that gap. It was formalized in the late 1940s and 1950s by
Lotfi Zadeh and John Ragazzini at Columbia University, who were working on sampled-data
control systems for military applications. Ragazzini is generally credited with
introducing the name “Z-transform” in a 1952 paper, reportedly choosing the letter z
because it was the last letter of the alphabet and suggested “the end of the line” for
transform methods.
The connection between the two transforms is elegant: sampling a continuous-time
signal at intervals T converts the Laplace variable s into the Z-transform variable z =
esT , mapping the left half of the s-plane into the interior of the unit circle. Stability, causality,
and frequency response, all the fundamental system properties, can be read directly from
the
geometry of the z-plane.
Today the Z-transform is indispensable in digital filter design, control system
analysis, and virtually every area of DSP.

4.1 Definition and Properties

The Z-transform of a discrete-time signal x[n] is defined as:
∞
X(z) = Z{x[n]} ∑ x[n]z−n
= n=−
∞

where z is a complex variable. This transformation converts the sequence x[n] into a
function X(z) of the complex variable z, encapsulating both magnitude and phase
information across different frequencies.
45
 4.2 Key Applications

By converting a discrete signal into its Z-transform, various characteristics of the system,
such as stability, causality, and frequency response, can be analyzed effectively. The inverse
Z-transform can be used to revert these frequency domain representations back into time
domain signals, facilitating the practical implementation of theoretical designs.

4.2 Key Applications

The practical applications of the Z-transform are vast and include:

• System Analysis: By examining the poles and zeros of the Z-transform, one
can determine the stability of the system.

• Filter Design: Digital filters are designed using the Z-transform to achieve
desired frequency responses.

• Signal Reconstruction: The Z-transform helps in reconstructing a signal

from its samples and is fundamental in the development of digital communication
systems.

The application of the Z-transform in these areas not only enhances the performance of
digital signal processing systems but also enriches our understanding of how signals behave
in different processing environments.

Basic Examples

Example 1: Z-Transform of a Unit Impulse Consider the discrete-time

signal δ[n], the unit impulse function:
(1 n = 0
δ[n] =
0 n ̸= 0
The Z-transform of δ[n] is:
∞
X(z) = Z{δ[n]} ∑ δ[n]z−n
= n=−
∞

Since δ[n] is 1 only at n = 0 and 0 otherwise, the sum simplifies to:

X(z) = δ[0]z0 = 1
Thus, the Z-transform of the unit impulse δ[n] is:
X(z) = 1

Example 2: Z-Transform of a Unit Step Sequence Consider the discrete-

time signal
u[n], the unit step function: (
1 n ≥0
u[n] =
0 n<0
The Z-transform of u[n]
is:
∞
X(z) = Z{u[n]} ∑ ∞
= n=−

46
u[n]z−n

47
Chapter 4. The Z-Transform

Since u[n] is 1 for n ≥ 0 and 0 otherwise, the sum becomes:

∞
X(z) = ∑ z−n
n=0

This is a geometric series with the first term a = 1 and common ratio r = z−1. For
the series to converge, |z| > 1. The sum of the geometric series is:
1 z
X(z) = = , |z| > 1
1−z −1 z−1
Thus, the Z-transform of the unit step function u[n] is:
z
X(z) = , |z > 1
z−1 |

Example 3: Z-Transform of an Exponential Sequence Consider the discrete-

time signal
x[n] = anu[n], where u[n] is the unit step function:

x[n] = ( n
a n ≥0
0 n<0

The Z-transform of x[n] = anu[n] is:

∞
X(z) = Z{anu[n]} ∑ anu[n]z−n
= n=−
∞

Since u[n] is 1 for n ≥ 0 and 0 otherwise, the sum becomes:

∞
X(z) = ∑(az−1)n
n=0

This is a geometric series with the first term a = 1 and common ratio r = az−1. For
the series to converge, |az−1| < 1, or equivalently |z| > |a|. The sum of the geometric
series is:
1 z
X(z) = = , |z| > |a|
1 − az −1 z−a
Thus, the Z-transform of the exponential sequence anu[n] is:
z
X(z) = , |z| > |a|
z−
a
Example 4: Z-Transform of a Cosine Sequence Consider the discrete-time
signal
x[n] = cos(ω0n)u[n], where u[n] is the unit step function:
x[n] = cos(ω0n)u[n]

To find the Z-transform, we use the Euler’s formula for cosine:

cos (ω0n) ejω0n + e−jω0n

= 2
Thus,

48
 1
x[n] = 2 ejω0 n + e−jω0 n u[n]

49
 4.3 Properties of Z-Transform

The Z-transform of x[n] is:

12
X(z) = Z{ejω0 nu[n]} + Z{e−jω0 nu[n]}

Using the property that the Z-transform of ejω0 nu[n] is z for |z| > |ejω0 |, we get:
z − 0
jω X e
1 z z
(z) = +
2 z− z − e−jω0
Combining the fractions: ejω0
X
z 1 1
(z) = +
2 z − ejω0 z − e−jω0
z z − e−jω0 + z − ejω0
X z
( )= (z − ejω0 )(z −
2
X z e−jω0 ) z(z − ejω0 +
z − e−jω0 )
( )=
2(z2 − (ejω0 +jω0
e−jω0−jω
)z + 1)
X(z z(2z — (e + e 0 ))
)=
2(z2 − 2 cos(ω0)z + 1)
z(2z − 2 cos(ω0))
X(z) = 2(z2 − 2 cos(ω0)z + 1)
z(z − cos(ω0))
X(z) = z2 − 2 cos(ω0)z + 1
Thus, the Z-transform of the cosine sequence cos(ω0n)u[n] is:
z(z − cos(ω0))
X z) =z2 − 2 cos(ω )z + 1, |z| 1
(> 0

The Z-transform converts a discrete-time signal into a complex function of z. It simplifies

the analysis and design of discrete-time systems by transforming convolution operations
into multiplication and providing tools to solve difference equations. Understanding the
basic examples of Z-transforms for common sequences helps in building a solid foundation
for more advanced topics in signal processing and system analysis.

4.3 Properties of Z-Transform

The Z-transform is an invaluable tool in digital signal processing, providing insights into
system behavior and simplifying the analysis and design of discrete-time systems. Below
are key properties of the Z-transform, each accompanied by enhanced explanations and
examples.

4.3.1 Linearity
The linearity property reflects the principle that the Z-transform of a linear combination of
signals is the same linear combination of their Z-transforms. This property is fundamental
in simplifying complex signal operations, making it easier to analyze systems composed of
multiple inputs or outputs.
Example: Let x1[n] = δ[n] and x2[n] = u[n]. Applying the linearity property:
z
z
Z{2δ[n] + 3u[n]} = 2Z{δ[n]} + 3Z{u[n]} = 2(1) + 3 −
1
50
Chapter 4. The Z-Transform

4.3.2 Time Shifting

The time shifting property describes how a shift in the time domain affects the Z-transform.
Specifically, it shows that delaying a signal x[n] by k samples results in the Z-transform
being multiplied by z−k. This property is particularly useful in analyzing systems where
delays are introduced, such as digital filters.
Example: Consider x[n] = δ[n]. The Z-transform of — x[n 2], which represents a
delay of 2 samples, is:
Z{δ[n − 2]} = z−2Z{δ[n]} = z−2

4.3.3 Scaling in the z-domain

Scaling in the z-domain property shows how scaling the argument n by a factor a inside the
signal x[n] translates into a scaling of the variable z in the Z-domain. This property is useful
for modifying the frequency characteristics of a signal.
Example: For x[n] = u[n] and a = 2, observe the scaling effect:
z
n z z
Z{2 u[n]} = Z{u[n]} = z
2
=
2 −1 z−2
2
4.3.4 Conv
olution
The convolution property links the convolution of two time-domain signals to the
multipli-cation of their Z-transforms. This is a critical property for systems where the
output is the convolution of the input with the system’s impulse response, as it simplifies
the analysis significantly.
Example: If x1[n] = x2[n] = u[n], the convolution y[n] = u[n] ∗ u[n] is represented by:
z z z2
Y( z) = =
z−1 z−1 (z − 1)2

4.3.5 Initial Value Theorem

The initial value theorem provides a quick way to determine the initial value x[0]
directly from the Z-transform, without needing to compute the inverse transform. It is
especially handy when the initial conditions of a system are required for analysis.
Example: For X(z) =−1 (corresponding to x[n] = u[n]):
z
z z
x[0] = lim =1
z→∞ z − 1

4.3.6 Final Value Theorem

The final value theorem predicts the long-term behavior of a signal from its Z-transform,
assuming the system reaches a steady state. It is crucial for determining the stability and
steady-state error of systems.
z
Example: For x[n] = 0.5nu[n], with its transform X(z) −0.5
= z :
z
x[∞] = lim(1 − z−1) =0
z→1 z − 0.5
These enhanced explanations and examples aim to provide a clearer and more com-
prehensive understanding of the properties of the Z-transform, illustrating their practical
significance in the field of digital signal processing.

51
 4.4 Transfer Function and Frequency Response

Problems
1. Compute the Z-transform of x[n] = 3 u[n] + 2 δ[n
— 1] using the linearity property.
State the ROC.
2. Find the Z-transform of x[n] = δ[n − 3] using the time-shifting property.
3. Determine the Z-transform and ROC of x[n] = 2nu[n]. Is the corresponding
system stable? Why or why not?
z
4. Using the convolution property, find Y(z) for the system with input X(z) = −1
z
and
transfer function H(z) = z
.
z−0.5

5. Given X(z) = z5—z , use the initial value theorem to find x[0] directly from X(z).
Verify your answer
2
by computing x[n] explicitly.
1 n
6. For the signal x[n] = 3
u[n], find X(z) and use the final value theorem to determine
limn→∞ x[n].
7. A system is described by y[n] −0.8 y[n −1] = x[n] + 0.5 x[n− 1]. Find the transfer
function H(z) = Y(z)/X(z). Locate the poles and zeros, and determine whether the
system is stable.
2 −1
8. Sketch the pole-zero diagram for H(z) = z
. Identify all poles and zeros, and
z2 −0.25
shade the ROC assuming a causal system.
9. Using partial fraction expansion, find the inverse Z-transform of
z
X(z) = , |z > 0.8.
(z − 0.5)(z − 0.8) |
10. Two causal LTI systems with impulse responses h1[n] = (0.5)nu[n] and h2[n] =
(0.3)nu[n] are connected in cascade. Find the overall transfer function H(z) = H1(z)
H2(z) and the poles of the combined system.
−2
1−z
11. A system has transfer function H(z) = 1−0.9
z−1
. Evaluate the frequency response
jω
H(e ) at ω = 0, ω = π/2, and ω = π. What type of filter does this system implement?
12. (Research) The connection between the Laplace transform variable s and the Z-
transform variable z is given by z = esT . Investigate how this mapping transforms
the stability boundary (the imaginary axis in the s-plane) and explain why the unit
circle plays the corresponding role in the z-plane.

4.4 Transfer Function and Frequency Response

One of the most powerful applications of the Z-transform is in characterizing LTI systems.
When we take the Z-transform of both sides of a general difference equation
N
M
∑ ak y[n— k]
= ∑ bm x[n— m],
m=0
k=0

the time-shifting property converts all delays into powers of z−1:

N ! !
∑ (z)
M
(z).
ak z−k ∑ z−m
= bm
k=0 Y X
m=0

52
Chapter 4. The Z-Transform

The transfer function is defined as the ratio of output to input in the z-domain:
Y(z) M
H(z) = ∑ m=0bm z−m
= N .
X(z) ∑k= ak z−k
0

This single rational function encodes everything about the system: its impulse response,
its stability, and its frequency-selective behaviour.

4.4.1 Poles, Zeros, and System Behaviour

By factoring the numerator and denominator polynomials:

b0 (z − z1)(z − z2) · · · (z − zM)

H(z) = · ,
a0 (z − p1)(z − p2) · · · (z − pN)

we identify the zeros z1, z2, . . . , zM (where the output vanishes) and the poles p1, p2, . . . , pN
(where the system response becomes infinite).
The pole and zero locations determine the system’s character:

• A pole near the unit circle at angle θ creates a resonance: the system amplifies
frequency components near ω = θ.
• A zero near the unit circle at angle θ creates a null: the system attenuates frequency
components near ω = θ.
• The further the poles are from the unit circle (toward the origin), the more damped and
less frequency-selective the system becomes.

Example. Consider the system y[n] = x[n] − 0.9 x[n− 1] (a simple FIR filter). Taking the
Z-transform:
z − 0.9
H(z) = 1—0.9 z−1 = .
z
This has a zero at z = 0.9 (near the unit circle at ω = 0) and a pole at z = 0 (the origin).
Since the zero is close to the point z = 1 on the unit circle, this filter attenuates low
frequencies. It is a high-pass filter.

4.4.2 Frequency Response: Evaluating H(z) on the Unit Circle

The frequency response of a discrete-time LTI system is obtained by evaluating the transfer
function at z = ejω :
H(ejω) = H(z)| ∑M
m= −jωm
0 bm e
z=ejω = ∑ N ak e−jωk .
k=
0
This complex-valued function of ω tells us how the system modifies each frequency
component of the input:

|
• The magnitude response H(ejω ) tells us by what factor the amplitude of frequency
ω is scaled. |

• The phase response ∠H(ejω ) tells us by how much the phase of frequency ω is
shifted. The magnitude response is often plotted in decibels:

|H(ejω)|dB = 20 log10 |H(ejω)|.

53
 4.4 Transfer Function and Frequency Response

Filter terminology. The frequency axis is divided into regions defined by the
magnitude response:
jω
• Passband: the range of frequencies where
| H(e| ≈)1 (the signal passes through
with little attenuation).

• Stopband: the range where |H(ejω )| ≈ 0 (the signal is heavily attenuated).

• Transition band: the intermediate region between passband and stopband.

• Cutoff frequency: t h e√b oundary of the passband, typically defined as the frequency
where |H| drops to 1/ 2 (i.e., −3 dB).

[Link] the first-order system H(z) = 1

, the frequency response is
1 −0.9 z−1

1
H(ejω) = .
1 − 0.9 e−jω
At ω = 0: H(ej0) =
1
−0.9 = 10, so the DC gain is 20 dB.
1
1
= 1.9 ≈ 0.526, which is −5.6 dB.
At ω = π: H(ejπ ) = +0.
91
1

The gain decreases with frequency, confirming that this is a low-pass filter. The pole
at z = 0.9 (close to the unit circle near ω = 0) creates the low-frequency resonance that is
responsible for the low-pass behaviour.

1
Magnitude response of H(z) =
−0.9 1 z−1
(first-order
low-pass)
20 20 log10 |H(ejω )|
−3 dB cutoff

10
|H(ejω )|
(dB)

−10
—0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1
Normalized frequency ω/π

Figure 4.1: Magnitude response (in dB) of a first-order IIR low-pass filter with pole at z =
0.9. The DC gain is 20 dB and the response rolls off smoothly toward higher frequencies. The
dashed line marks the −3 dB level used to define the cutoff frequency.

4.4.3 Geometric Interpretation

There is an elegant geometric way to evaluate | H(ejω ) without algebra. At any frequency ω,
the point ejω sits on the unit circle. The magnitude
| response is the product of distances from
ejω to all zeros, divided by the product of distances from ejω to all poles:

jω ∏m |ejω − zm |
|H(e )| = |b0/a0| · .
∏k |ejω − p
k |

54
Chapter 4. The Z-Transform

As ejω sweeps around the unit circle, its distance to a nearby pole becomes very
small, causing the magnitude to spike (a resonance). Similarly, passing near a zero
causes the magnitude to dip. This geometric picture gives an immediate, intuitive
understanding of why a given pole-zero configuration produces a particular frequency
response shape.

55
 4.4 Transfer Function and Frequency Response

The Region of Convergence (ROC) is the range of values of z for which the Z-transform
converges. The ROC is crucial for determining the behavior and stability of the system.

Im(z)

ROC: |z| > 0.8

pole
zero
Re(z)
|z| =
1

Stable causal system: all z-plane

Figure 4.2: A pole-zero diagram ininside
poles the z-plane. Poles× ( ) determine system dynamics; zeros◦ (
the unit circle
) shape the frequency response. For a causal system to be BIBO stable, all poles must lie strictly
inside the unit circle. The shaded region indicates the ROC.

DefinitionThe ROC of X(z) is the set of z values for which the Z-transform sum converges:
∞
ROC = {z ∈ ∑ x[n]z−n converges}
n=−
: ∞

Properties of ROC 1. The ROC does not contain any poles of X(z). 2. If x[n] is a
right-sided sequence, the ROC extends outward from the outermost pole. 3. If x[n] is a left-
sided sequence, the ROC extends inward from the innermost pole. 4. If x[n] is a two-sided
sequence, the ROC is a ring in the z-plane.

Examples 1. Right-sided Sequence: For x[n] = anu[n]:

∞ 1
X(z ) =
az−1) = 1 − az−1 |z| > |a|
∑( n
,
n=0

2. Left-sided Sequence: For x[n] = −anu[−n − 1]:

X(z) =
—1 −a−1z
1− |z| < |a|
∑ az ) −1
,
( n a−1z
n=−∞
=

3. Two-sided Sequence: For x[n]

= an:
∞

X(z) =
∑ (az−1)n
n=−∞

ROC: |z| > |a| or |z| < |a|

56
Chapter 4. The Z-Transform

4.5 Inverse Z-Transform

The inverse Z-transform is used to convert a function in the z-domain back to the time
domain. There are several methods to perform the inverse Z-transform:

Power Series Expansion Express X(z) as a power series in z−1:

∞
X(z) = ∑ x[n]z−n
n=−∞

The coefficients of z−n are the values of x[n].

Partial Fraction Expansion Decompose X(z) into simpler fractions, each of which
can be easily inverted:
X N(z)
(z) =
D(z)
Express X(z) as a sum of partial fractions and then use standard Z-transform pairs to find
x[n].

Contour Integration Use the inverse Z-transform integral formula:

x 1
[n] = I
2πj X(z)zn−1dz
C

where C is a counterclockwise contour enclosing the origin and within the ROC.

z
Examples1. Power Series Expansion: If X(z)
−2 = z :
z 2 4
X(z) = = 1+ + + ···
z− z z2
Thus, x[n] = 2
2nu[n].
z
2. Partial Fraction Expansion: If X(z)) = (z−1 z−2)
:
X A ( B
(z) = +
z−1 z−2
Solving for A and B, we
get:
X 1 1
(z) = −
z−1 z−2
Thus, x[n] = u[n] −
2nu[n].

4.5.1 Worked Example: Solving a Difference Equation with the Z-

Transform
One of the most powerful uses of the Z-transform is solving difference equations
algebraically, turning a recursive computation into a straightforward division of
polynomials.

Problem.A causal LTI system is described by the difference equation

y[n] − 0.5 y[n − 1] = x[n] + 2 x[n − 1].
57
Find the impulse response h[n], determine whether the system is stable, and describe
the frequency-selective behaviour.

58
 4.5 Inverse Z-Transform

Step 1: Take the Z-transform of both sides. Using the

time-shifting property (y[n 1] — ↔
−1
z Y(z)):
Y(z) − 0.5 z−1Y(z) = X(z) + 2 z−1X(z).

Step 2: Factor and form the transfer function.

Y(z) 1 − 0.5 z−1 = X(z) 1 + 2 z−1 ,

Y(z) 1 + 2 z−1 z+2
H(z) = = = .
X(z) 1 − 0.5 z−1 z − 0.5

Step 3: Identify poles and zeros. The system has one zero at z = −2 and one pole at
z = 0.5. Since the pole lies inside the unit circle (|0.5| < 1), the system is stable.

Step 4: Partial fraction expansion. To find h[n], write H(z)/z in partial fractions:
H(z) z+2 A B
= = + .
z z(z − 0.5) z z − 0.5
0+ 2 0.5+2
Solving: A = = −4 and B = = 5. Thus
0−0.5 0.5
5z
H(z) = —4 + ,
z − 0.5
and the impulse response is

h[n] = −4 δ[n] + 5 (0.5)n u[n].

Step
1−2
5: Frequency response. At ω = 0: H(ej0) = 1+2
= 6. At ω = π: H(ejπ ) =
=
1−0.5
— 2. 1+0.5
3 The magnitude at DC is H = 6 (15.6 dB), while at ω = π it drops to H = 0.67 ( 3.5
| | | | −
dB). This confirms a low-pass characteristic, consistent with the pole being located near z
= 1 on the real axis.

• The Z-transform converts a discrete-time sequence into a function of the complex

variable z: X(z) = ∑ x[n] z−n.
• The transfer function H(z) = Y(z)/X(z) completely characterizes an LTI
system in the z-domain.

• Poles determine system dynamics; zeros shape the frequency response. A causal
system is stable if all poles lie inside the unit circle.
• The frequency response H(ejω ) is obtained by evaluating H(z) on the unit
circle; its magnitude and phase describe how the system modifies each
frequency.

• The inverse Z-transform can be computed via power series expansion, partial
fractions, or contour integration.

59
 5 CHAPTER
5

DFT and Fast Fourier Transform

(FFT)

The idea that a complex signal can be decomposed into simple oscillatory components is one
of the deepest insights in all of science. Its origins trace back to 1807, when Jean-Baptiste
Joseph Fourier submitted a manuscript to the French Academy of Sciences claiming that
any function, no matter how irregular, could be represented as a sum of sines and cosines.
The claim was so bold that the review committee, which included Laplace, Lagrange, and
Legendre, refused to publish it. Lagrange in particular believed the result to be false.
Fourier was eventually vindicated: under mild conditions, his claim is correct, and the
decomposition now bears his name. The Fourier series for periodic signals and the Fourier
transform for non-periodic signals became cornerstones of 19th- and 20th-century physics
and engineering.
When signals are discrete and finite in length, the natural tool is the Discrete Fourier
Transform (DFT). The DFT takes N time-domain samples and produces N frequency-domain
coefficients, giving a complete and invertible representation of the signal’s spectral content.
Its efficient computation via the Fast Fourier Transform (FFT), discussed later in this chapter,
is what makes real-time spectral analysis practical on modern hardware.

5.1 Frequency Analysis of Signals

Imagine you are listening to a symphony orchestra. Your ear does not perceive the sound as a
single, complicated waveform wiggling up and down. Instead, you hear distinct instruments:
the warm low register of the cellos, the bright shimmer of the violins, the clear tone of a
flute. Without any conscious effort, your auditory system performs a feat of spectral analysis,
decomposing a complex sound wave into its constituent frequency components. Frequency
analysis in DSP does the same thing, but with mathematical precision.
The fundamental idea is simple but powerful: any signal, no matter how complicated it
looks in the time domain, can be represented as a sum of sinusoids at different frequencies.
Some of those sinusoids may be strong, others weak. Some may be shifted in phase relative
to others. But together, they reconstruct the original signal perfectly. This decomposition
reveals structure that is completely invisible when you look at the raw waveform.
The practical applications are enormous. In noise reduction, frequency analysis lets us
identify exactly which frequency components belong to the signal and which belong to the
noise, so we can surgically remove the noise while leaving the signal intact. In medical imag-
ing, MRI scanners collect data in the frequency domain and use inverse Fourier transforms
to reconstruct spatial images of the body’s interior. In mechanical engineering, frequency
analysis of vibration data reveals the resonant frequencies of a structure, information that is
critical for preventing catastrophic failures.
60
 5.1 Frequency Analysis of Signals

5.1.1 Time and Frequency Domain Relationship

The time domain and frequency domain are two complementary languages for
describing the same signal. In the time domain, we describe how a signal’s amplitude
changes from one instant to the next. In the frequency domain, we describe which
oscillatory components make up the signal and how strong each one is. Neither
description is more “correct” than the other; they are simply two different ways of
looking at the same mathematical object.
The bridge between these two perspectives is the Fourier Transform. It takes a time-
domain signal and decomposes it into a continuum of sinusoidal components, each charac-
terized by its frequency, amplitude, and phase.
Mathematically, the continuous Fourier Transform of a time-domain signal x(t) is defined
as:
X ∫∞
(f)= x(t)e−j2π f t dt
−∞
where:
• X( f ) is the frequency-domain representation of the signal.
• x(t) is the time-domain signal.
• f is the frequency variable.
• j is the imaginary unit.
This equation transforms the time-domain signal into a complex-valued function of
frequency, where the magnitude represents the amplitude of each frequency component,
and the phase represents the phase shift of that component.
The inverse Fourier Transform allows us to reconstruct the original time-domain signal
from its frequency components:
∫
∞
x(t) = X( f )ej2π f t
df
−∞
This bidirectional relationship means that we can switch between the time and frequency
domains as needed, depending on which representation is more useful for a particular
analysis.

5.1.2 The Discrete-Time Fourier Transform (DTFT)

The continuous Fourier Transform applies to continuous-time signals. When the signal is
already discrete, a sequence x[n], the appropriate tool is the Discrete-Time Fourier
Transform:
∞
X(ejω) = ∑ x[n] e−jωn.
n=−∞
The DTFT produces a continuous, periodic function of the frequency variable ω (with
period 2π). It tells us the spectral content of a discrete-time signal at every frequency,
not just at isolated points. The inverse DTFT
∫ π recovers the signal from its spectrum:
1
x[n] = X(ejω) ejωn d .
ω
2π −π
The DTFT is the natural frequency-domain representation of discrete-time signals, and
the frequency response H(ejω ) discussed in the Z-transform chapter is simply the DTFT of
the impulse response h[n].
However, the DTFT has a practical limitation: it produces a continuous function of ω,
which a computer cannot store or compute exactly. We need a way to evaluate the spectrum
at a finite number of frequencies.

61
Chapter 5. DFT and Fast Fourier Transform (FFT)

5.1.3 From DTFT to DFT

Suppose we have a finite-length signal x[n] defined for n = 0, 1, . . . , N— 1 (and zero
elsewhere). If we evaluate the DTFT at N equally spaced frequencies ωk = 2πk/N
for k = 0, 1, . . . , N − 1, we obtain

X k X N−1
(ej ) −j 2π
kn
[ ] x[ ] e N .
= ω

= n∑
ω=2πk/ n=
N 0
This is precisely the Discrete Fourier Transform (DFT). The DFT is not an
approximation of the DTFT. For a finite-length signal, the N DFT coefficients contain
exactly the same information as the continuous DTFT, and the original signal can be
perfectly recovered via the inverse DFT:
N−1
x[n 1
X [k] j N
2π
kn
.
]
= ∑ e
N k=0

The key insight is that sampling in one domain causes periodicity in the other:

• Sampling in time (which produces x[n] from x(t)) makes the spectrum periodic
with period 2π.

• Sampling in frequency (which produces X[k] from X(ejω )) makes the time-
domain signal periodic with period N.

This duality between sampling and periodicity is one of the most fundamental ideas
in DSP.

DTFT (continuous curve) and DFT samples (dots) of a rectangular pulse

DTFT |X(ejω
4 DFT
)| samples
X[k]
|X(ejω

2
)|

0
0 0.25 0.5 0.75 1
ω/π

Figure 5.1: The relationship between DTFT and DFT. The blue curve shows the continuous
DTFT magnitude of a short signal. The red dots show the DFT coefficients, which are equally
spaced samples of the DTFT. The DFT captures the same information in a form that computers
can store and process.

The DFT provides a way to analyze the frequency content of discrete signals and is
widely used in applications such as spectral analysis, filtering, and fast convolution.

5.1.4 Worked Example: Computing a 4-Point DFT by Hand

To demystify the DFT, let us compute it explicitly for a short signal.

62
[Link] the DFT of the signal x[n] = {1, 0, −1, 0} for n = 0, 1, 2, 3.

63
 5.1 Frequency Analysis of Signals

Setup. With N = 4, the DFT formula gives

X[k 3 3

]= ∑ x[n e−j 2π = ∑ x[n e−j

π
kn
.
n= ] kn n= ]
4 2
0 0

Define the twiddle factor W4 = e−jπ/2 = −j. Then W0 = 1, W1 = −j, W2 = −1, W3 = j.

4 4 4 4

k = 0:
X[0] = x[0] · 1 + x[1] · 1 + x[2] · 1 + x[3] · 1 = 1 + 0 + (−1) + 0 = 0.

The DC component is zero, meaning the signal has no constant offset.

k = 1:
0
X[1] = x[0] · W
4
+ x[1] 4· W1 + x[2]4 · W2 + x[3]
4
· W3 = 1 · 1 + 0 · (−j) + (−1) · (−1) + 0 · j = 1
+ 1 = 2.

k = 2:
0
X[2] = x[0] · W
4
+ x[1] ·4 W2 + x[2]4 · W4 + x[3]
4
· W6 = 1 · 1 + 0 · (−1) + (−1) · 1 + 0 · (−1) =
0.

k = 3:
0
X[3] = x[0] · W
4
+ x[1] ·4 W3 + x[2]4 · W6 + x[3]
4
· W9 = 1 · 1 + 0 · j + (−1) · (−1) + 0 · (−j) =
2.

Resul
t. X[k] = {0, 2, 0, 2}.

Interpretation. The signal has no energy at DC (k = 0) and no energy at the Nyquist

frequency (k = 2). All its spectral energy is concentrated at k = 1 and k = 3, which
correspond to ω = π/2 and ω = 3π/2. Since X[3] = X[N 1] is the conjugate-symmetric
— x[n] is a pure cosine at the
counterpart of X[1] for a real signal, this result confirms that
quarter-sampling-rate frequency.

Verification via inverse DFT.

1 3
x [n [ ] 2 1 2 ej2 π + 2 = π
] =4 ∑X ej
π
k 2 j 3π n
cos n ,
kn n e
k=
= 2
0
4
which evaluates to {1, 0, −1, 0}, confirming our result.

5.1.5 Examples of Frequency Transformations

Frequency transformations have practical applications across various fields, providing
insights into the characteristics of different signals. This subsection will present examples of
how Fourier analysis is applied to real-world problems, such as analyzing musical tones and
64
identifying mechanical vibrations for predictive maintenance.

65
Chapter 5. DFT and Fast Fourier Transform (FFT)

Analyzing Musical Tones

One common application of frequency analysis is in the realm of music, specifically in
analyzing musical tones to determine pitch. Musical instruments generate sound waves,
which are complex combinations of different frequencies. To identify the pitch of a note,
Fourier Transform is used to decompose the audio signal into its frequency components.
By examining the resulting spectrum, we can identify the fundamental frequency, which
corresponds to the perceived pitch, and its harmonics, which contribute to the timbre of the
sound.
For instance, when analyzing the sound produced by a guitar string, the signal in the time
domain appears as a waveform with varying amplitude. When this signal is transformed
into the frequency domain using the Discrete Fourier Transform (DFT), we observe distinct
peaks corresponding to the fundamental frequency and its harmonics. The fundamental
frequency determines the note being played, while the harmonics influence the quality
of the sound, giving each instrument its unique tonal character.
This type of analysis is useful in music production, where understanding and manipulat-
ing the frequency components can help enhance sound quality, tune instruments, and even
generate effects by emphasizing or suppressing certain harmonics. Frequency analysis is
also used in digital audio processing software for pitch detection and correction, enabling
accurate tuning of musical instruments and vocal recordings.

Identifying Dominant Frequencies in Mechanical Vibrations

Another significant application of frequency analysis is in the field of mechanical engineering,
particularly for predictive maintenance of machinery. Machines and mechanical components
often produce vibrations during operation. These vibrations can be analyzed in the frequency
domain to detect abnormalities and potential issues before they lead to failures.
By applying the Fast Fourier Transform (FFT) to vibration data collected from
sensors mounted on mechanical equipment, we can identify dominant frequencies that
indicate the normal operation or the presence of faults. For example, a rotating motor
may produce vibrations with a specific frequency corresponding to its rotation speed. If
additional fre-quencies are detected, such as harmonics or subharmonics, these may
indicate issues like misalignment, imbalance, or bearing faults.
Consider a scenario where vibration sensors are installed on an industrial fan. Under
normal operating conditions, the frequency spectrum of the vibration data will show a
dominant peak at the rotation frequency of the fan blades. However, if a misalignment
occurs, additional peaks may appear at harmonics of the rotation frequency. By monitoring
these frequency components, maintenance engineers can identify potential problems early
and take corrective actions, thereby preventing costly breakdowns and extending the
lifespan of machinery.

5.2 Properties of DFT

The Discrete Fourier Transform (DFT) is a powerful mathematical tool that allows us to
convert discrete time-domain signals into their frequency domain counterparts. This trans-
formation facilitates a deeper understanding of the frequency content of signals, which is
critical in many scientific and engineering applications.

• Linearity: The DFT of a sum of two signals equals the sum of the DFTs of each
individual signal. This property is particularly useful when dealing with multiple
signal components, such as in multi-carrier communication systems, where analyzing

66
 5.2 Properties of DFT

combined signals is essential. For example, consider two signals x1[n] and x2[n]; their DFTs
are X1[k] and X2[k], respectively. The DFT of the sum x1[n] + x2[n] is X1[k] + X2[k],
allowing for simplified analysis of complex signals.

• Symmetry: The symmetric properties of DFT, including even and odd symmetry,
simplify calculations, especially for real-valued signals. For real-valued signals, the
DFT exhibits conjugate symmetry, meaning that X[N — k] = X∗[k]. This property
helps reduce computational complexity, which is highly advantageous in
applications like image compression and audio signal processing. Symmetry
properties also play a cru-cial role in efficiently representing data, where only half of
the frequency components need to be calculated for real-valued signals.

• Periodicity: The DFT exhibits periodic behavior, meaning the frequency spectrum
repeats itself. Specifically, the DFT of a signal x[n] with length N is periodic with
a period of N. The implications of this periodicity are particularly evident in the
phenomenon of aliasing, which occurs when sampling signals at insufficient rates,
leading to overlapping frequency components. To avoid aliasing, signals must be
sampled at a rate greater than twice their highest frequency, as per the Nyquist
theorem. Periodicity also means that care must be taken when interpreting the DFT
output, as the frequency domain representation is inherently cyclic.

• Parseval’s Theorem: This theorem establishes a relationship between the

energy of a signal in the time domain and in the frequency domain. Parseval’s
theorem states that the total energy of a signal is the same in both domains,
n=
given
2
by ∑ |x[n]| =
N−1
0
1 N−1 |X[k]|2. Practical applications include calculating power spectral density and
∑ N k=
analyzing energy
0 efficiency in communication systems, which is critical for system design and
optimization. For example, in wireless communication, understanding the energy
distribution helps in designing power-efficient modulation schemes.

• Circular Convolution: Circular convolution is a key concept when working with

DFT, particularly in the context of linear time-invariant (LTI) systems. Circular
convolution arises due to the periodic nature of the DFT, and it can introduce artifacts if
not handled properly. Circular convolution can be converted to linear convolution by
zero-padding the input signals to avoid overlap. This is particularly important in digital
filtering, where the goal is to achieve a linear convolution result. For example, if
two signals x[n] and h[n] are zero-padded to length
— L + M 1, where L and M are
their original lengths, the circular convolution of their DFTs yields the same result as
their linear convolution.

These properties provide a comprehensive understanding of how DFT can be used to

analyze and process signals efficiently, with practical applications in fields like digital com-
munications, audio processing, and control systems. For instance, in digital communications,
DFT is used to implement Orthogonal Frequency Division Multiplexing (OFDM), which is a
widely adopted modulation technique in modern wireless systems like LTE and Wi-Fi. In
audio processing, DFT helps in spectral analysis, noise reduction, and sound synthesis.
The understanding of DFT properties also forms the basis for many advanced signal
processing techniques, such as spectral analysis, filter design, and the implementation of
Fast Fourier Transform (FFT) algorithms, which provide a computationally efficient way to
calculate the DFT of a signal. The FFT exploits the symmetry and periodicity properties
of DFT to reduce the computational complexity from O(N2) to O(N log N), making it
feasible to perform frequency analysis on large datasets in real-time applications.

67
Chapter 5. DFT and Fast Fourier Transform (FFT)

5.3 FFT Algorithms and Computation

5.3.1 Why the DFT Is Expensive
Computing the DFT directly from its definition requires, for each of the N output values
X[k], a sum of N complex multiplications and additions. The total cost is therefore
proportional to N2. For modest signal lengths this is manageable, but for the sizes
encountered in practice (audio buffers of 2 16 samples, radar sweeps, or image rows), an
O(N2) algorithm quickly becomes impractical.
To appreciate the scale: a direct DFT of N = 4096 samples requires roughly 16.7 million
complex multiplications. An FFT of the same length requires about 24,000. That is a factor of
nearly 700.

5.3.2 Historical Background

The idea of breaking a Fourier computation into smaller pieces is older than digital
computers. Carl Friedrich Gauss described an algorithm equivalent to the modern FFT
around 1805, decades before Fourier published his treatise on heat conduction. Gauss used
the technique to interpolate asteroid orbits from astronomical observations, but his
manuscript was written in Latin, remained unpublished during his lifetime, and was
largely forgotten.
The algorithm was independently rediscovered several times during the 20th
century. The decisive moment came in 1965, when James Cooley and John Tukey
published a short paper presenting what is now called the Cooley–Tukey FFT algorithm.
Their work ap-peared at a time when digital computers were becoming powerful enough
to handle large datasets, and the impact was immediate and enormous. Overnight,
problems that had been computationally infeasible became routine.
Within a few years, the FFT had transformed fields as diverse as medical imaging,
seismology, speech processing, and radio astronomy. It played a critical role in the
Apollo space program, where real-time spectral analysis of telemetry data was essential.
Today the FFT remains one of the most widely used numerical algorithms in existence.

5.3.3 The Key Idea: Divide and Conquer

The Cooley–Tukey algorithm exploits a simple observation about the DFT sum. If N is even,
N−1
the sum
Xk x n Wnk, W e−j2π/N ,
[ ]= ∑ [ ] N =
N
n=0
can be split into contributions from even-indexed and odd-indexed samples:
N/2−1
N/2−1
X[k] =
∑
m=
x[2m] mk + k
m=
∑ x[2m + 1] W
mk
N/2 .
0 WN/2 WN 0
` ˛¸ x ` ˛¸ x
G [ k] H [ k]

Here G[k] is the N/2-point DFT of the even-indexed samples and H[k] is the N/2-point
DFT of the odd-indexed samples. The crucial point is that both G[k] and H[k] are periodic
with period N/2, so for the second half of the output indices we have:
X[k] = G[k] +
H[k], X[k + N/2] = G[k] − H[k],
Wk N N
Wk
for k = 0, 1, . . . , N/2 − 1. k
Each pair of outputs requires only one complex multiplication (by the twiddle factor
WN ) and two additions. The same splitting can be applied recursively to G[k] and H[k]
until the sub-problems reduce to trivial one-point DFTs.

68
 5.3 FFT Algorithms and Computation

5.3.4 Radix-2 Decimation-in-Time (DIT)

When N is a power of two, the recursion has exactly log2 N stages, each involving N/2
butterfly operations. The total number of complex multiplications is therefore
N
log N,
2
2
which is O(N log N), a dramatic improvement over O(N2).
Each butterfly operation takes two inputs a and b and produces two outputs:
a′ = a + WNk b, b′ = a − WNk b.
The term “decimation in time” refers to the fact that the algorithm begins by reordering
the input samples according to the bit-reversal of their indices. For example, with N = 8,
the input order becomes {x[0], x[4], x[2], x[6], x[1], x[5], x[3], }x[7] . After this reordering,
the butterflies are applied in place, stage by stage, until the full DFT emerges at the
output.

x[0] G[0] + X[0]

+
+ +
x[2] G[1] W40 — X[2]
—

x[1] + H[0] X[1]

+
+
x[3] W41 +
— H[1] — X[3]
Bit-reversed input Stage 1 Stage DFT output
2

Figure 5.2: Signal flow graph for a 4-point Radix-2 decimation-in-time FFT. The input is
reordered by bit reversal. Stage 1 computes two independent 2-point DFTs. Stage 2 combines
them using twiddle factors Wk (shown in red) to produce the final output.
4

5.3.5 Worked Example: 4-Point FFT

Let x[n] = {1, 2, 3, 4} with N = 4. We compute X[k] step by step.

Stage 1: Two 2-point DFTs. Even samples: x[0] = 1, x[2] = 3.

G[0] = 1 + 3 = 4, G[1] = 1 − 3 = −2.
Odd samples: x[1] = 2, x[3] = 4.
H[0] = 2 + 4 = 6, H[1] = 2 − 4 = −2.

Stage 2: Combine with twiddle factors. The twiddle 4

factors are W0
= 1 and W1 =
4
e−jπ/2 = −j.
X[0] = G[0] + W40 H[0] = 4 + 6 = 10,
X[1] = G[1] + 4W1 H[1] = −2 + (−j)(−2) = −2 +
2j,
0
X[2] = G[0] − W4 H[0] = 4 − 6 = −2,
X[3] = G[1] − W41 H[1] = −2 − 2j.
Thus X[k] = { 10, −2 + 2j, −2, −2 − 2j .
} values by direct computation from the DFT definition and confirm
One can verify these
that they match exactly. The total cost was 1 complex multiplication and 8 additions,
compared to 16 multiplications for the direct DFT.

69
Chapter 5. DFT and Fast Fourier Transform (FFT)

5.3.6 Computational Complexity

The following table compares the number of complex multiplications for direct DFT and
Radix-2 FFT:

Direct DFT (N2) FFT ( log2

N
N Speedup
N) 2
8 64 12 5×
64 4,096 192 21×
1,024 1,048,576 5,120 205×
4,096 16,777,216 24,576 683×
65,536 4.3 × 109 524,288 8,192×
The speedup grows as 2N/ log2 N, which means the advantage becomes more dramatic
as N increases. For modern applications where N can reach millions of samples, the FFT is
not merely convenient; it is the only feasible approach.

5.3.7 Practical Considerations

Windowing and Spectral Leakage. The DFT assumes that the input signal is
periodic with period N. If the signal segment does not contain an integer number of cycles,
discontinuities appear at the boundaries, causing energy to spread across frequency bins, a
phenomenon called spectral leakage.
To mitigate leakage, a window function is applied to the signal before computing the
FFT. Common choices include the Hamming window, the Hanning window, and the Blackman
window. Each represents a different trade-off between the width of the main lobe (frequency
resolution) and the height of the side lobes (leakage suppression).

Zero Padding. Appending zeros to a signal before computing the FFT does not add new
frequency information, but it does interpolate the frequency spectrum onto a finer grid. This
can make spectral peaks easier to identify visually and is essential when using the FFT to
perform linear convolution via the overlap-add or overlap-save methods.

In-Place Computation. The Radix-2 FFT can be implemented in place, meaning that
the output values overwrite the input array. This is possible because the bit-reversal
permutation and the butterfly structure ensure that each value is consumed before it is
overwritten. In-place computation is important for embedded systems and real-time
applications where memory is limited.

5.3.8 FFT Variants

The Radix-2 algorithm requires N to be a power of two, but several generalizations exist:

• Radix-4 FFT: Groups four samples at each stage, reducing the number of
multiplica-tions by about 25% compared to Radix-2.

• Split-Radix FFT: Combines Radix-2 and Radix-4 butterflies for the lowest
known multiplication count among power-of-two algorithms.

• Mixed-Radix FFT: Handles arbitrary N by factoring it into primes and applying

smaller DFTs at each stage. This is the approach used by most modern FFT
libraries.

• Bluestein’s Algorithm: Computes the DFT for any N by reformulating it as a

convolu-tion, which can then be evaluated using a power-of-two FFT.

70
 5.3 FFT Algorithms and Computation

In practice, highly optimized libraries such as FFTW (“Fastest Fourier Transform in the
West”) automatically select the best algorithm and tune it to the specific hardware at runtime.

Problems
1. Compute the 4-point DFT of x[n] ={ 1, 0,−1, 0} directly from the definition. Identify
the frequency components present in the signal.

2. A real-valued signal x[n] has N = 8 samples. How many independent complex

DFT coefficients does X[k] have? Explain why, using the conjugate symmetry
property.

3. Verify Parseval’s theorem for the signal x[n] = { 1, 2, 3, 4} by computing the energy in
both the time domain and the frequency domain (using the 4-point DFT result from
the text).

4. The DFT of a length-N signal is periodic with period N. Explain why X[k] and X[k +
N] represent the same frequency, and discuss how this relates to aliasing in the
discrete-time domain.

5. How many complex multiplications are required to compute an N-point DFT directly
for N = 1024? How many are required using a Radix-2 FFT? Express the speedup
factor.

6. Consider the 4-point FFT worked example from the text: x[n] = {1, 2, 3, 4} with
X[k] ={ 10, −2 + 2j,− 2, −2 −2j . Verify by computing the inverse DFT that you
recover the original
} signal.

7. Two finite-length signals x[n] (length L = 4) and h[n] (length M = 3) are to be

convolved using the FFT. What is the minimum DFT length N required to avoid
circular convolution artifacts? Explain the zero-padding strategy.

8. A signal consists of two sinusoids at 100 Hz and 105 Hz, sampled at fs = 1000 Hz. You
take N = 100 samples. What is the frequency resolution ∆ f of the DFT? Can these two
frequencies be resolved? What happens if you increase N to 200?

9. Explain the difference between zero padding and increasing the signal length in terms
of frequency resolution. Which one actually provides new spectral information?

10. A rectangular window of length N is applied before computing the FFT. Describe
qualitatively what happens to the spectrum of a pure sinusoid that does not complete
an integer number of cycles within the window. How does a Hamming window
change this result?

11. The twiddle factor WNk = e−j2πk/N appears throughout the FFT algorithm. Show that
k
Wk+N/2 = N −W . Explain
N why this identity halves the number of required twiddle
factor computations.

12. (Research) The FFT is sometimes called “the most important numerical algorithm
of the 20th century.” Investigate three specific technologies or scientific discoveries
that were made possible (or dramatically accelerated) by the FFT, and explain the role
it played in each.

71
Chapter 5. DFT and Fast Fourier Transform (FFT)

• The DTFT converts a discrete-time signal into a continuous, periodic function

of frequency; the DFT samples this function at N equally spaced points.
• The DFT converts N time-domain samples into N frequency-domain coefficients:
X[k] = ∑ N−1 x[n]
n=0
e−j2πkn/N.
• Key DFT properties include linearity, conjugate symmetry for real signals, period-
icity, Parseval’s theorem, and the circular convolution theorem.

• The FFT reduces the computational cost from O(N2) to O(N log N) by recursively
splitting the DFT into smaller sub-problems.

• Windowing reduces spectral leakage at the cost of frequency resolution; the choice
of window is application-dependent.

72
 6 CHAPTER
6

Design of Digital Filters

Filtering is one of the oldest problems in electrical engineering. The need arose in the
early days of telephony: long-distance lines picked up interference from power cables
and neighbouring circuits, making speech unintelligible. George Campbell at AT&T
developed the first systematic electrical filter designs around 1910, using networks of
inductors and capacitors arranged to pass voice frequencies while blocking everything else.
His colleague Otto Zobel refined these designs in the 1920s into the “image parameter”
method, which remained the standard approach for decades.
A deeper theoretical framework arrived in the 1930s, when Stephen Butterworth
pub-lished his design for a filter with maximally flat magnitude response (1930), and
shortly afterward, Pafnuty Chebyshev’s earlier work on polynomial approximation was
applied to create filters with equiripple behaviour in the passband. Wilhelm Cauer
extended these ideas to produce elliptic filters, which achieve the sharpest possible
transition for a given filter order. These classical analog designs (Butterworth, Chebyshev,
and elliptic) remain the starting point for many digital filter designs today.
The transition to digital filters began in earnest in the 1960s, when Charles Rader
and Bernard Gold at MIT Lincoln Laboratory showed that difference equations
implemented on digital hardware could replicate, and in many cases surpass, the
performance of analog circuits. James Kaiser at Bell Labs developed the Kaiser window
for FIR filter design, and Thomas Parks and James McClellan introduced the optimal
equiripple FIR design algorithm that bears their names.
Digital filters offer advantages that analog filters cannot match: perfect
reproducibility, easy reconfigurability, and the ability to implement filter characteristics
that are difficult or impossible to achieve with analog components, such as perfectly
linear phase. On the other hand, they introduce quantization effects and require careful
attention to numerical precision.
In this chapter, we cover the two major families of digital filters and the key ideas behind
their design.

6.1 Introduction to Filters: FIR and IIR

Digital filters are used to modify the characteristics of a signal by enhancing desired frequency
components while attenuating unwanted ones. There are two primary types of digital filters:

73
Chapter 6. Design of Digital Filters

6.1.1 Finite Impulse Response (FIR) Filters

FIR filters are characterized by a finite-duration impulse response: if the input is a unit
impulse δ[n], the output settles to zero after a finite number of samples. The output of
an
FIR filter of order N − 1
is y[n] ∑ bk x[ n−k .
N−1

= k=0
]
FIR filters have several attractive properties:

• They are always BIBO stable, regardless of coefficient values.

• They can achieve exactly linear phase if the coefficients are symmetric, meaning all
frequency components experience the same delay.

• They have no feedback, which simplifies implementation and avoids limit-cycle oscil-
lations.

The price for these guarantees is that FIR filters typically require more coefficients (a
higher order) than IIR filters to achieve a comparable frequency selectivity.

6.1.2 Infinite Impulse Response (IIR) Filters

IIR filters use feedback: the current output depends not only on the input but also on
previous outputs. Their general form is
M N
y[n] = ∑ bk x[n − k] − ∑ ak y[n − k].
k=0 k=1

IIR filters can achieve sharp transitions between passband and stopband with far fewer
coefficients than FIR filters. However, they come with caveats:

• Stability must be verified explicitly (all poles must lie inside the unit circle).

• They generally do not have linear phase.

• Finite-precision arithmetic can cause limit cycles and coefficient sensitivity.

Classical analog filter designs (Butterworth, Chebyshev, and elliptic filters) can be con-
verted to IIR digital filters using techniques such as the bilinear transform or impulse
invariance. This connection to well-understood analog prototypes is one of the main reasons
IIR filters remain popular.

6.1.3 FIR vs. IIR: A Practical Comparison

Property FIR IIR
Stability always stable must be checked
Linear phase easily achieved generally not
Order for sharp cutoff high low
Design from analog prototype no yes
Sensitivity to quantization low higher
In practice, the choice between FIR and IIR depends on the application. Audio
equaliza-tion and biomedical signal processing, where phase distortion is unacceptable, tend
to favour FIR filters. Real-time control systems and communication receivers, where
computational efficiency matters most, often use IIR designs.

74
 6.2 FIR Filter Design Methods

Typical magnitude responses of low-pass FIR and IIR filters

FIR (order 30)

1 IIR (Butterworth, order 5)
Ideal low-pass
|H(ejω

0.5
)|

0
0 0.2 0.3 0.4 0.6 0.8 1
Normalized frequency ω/π

Figure 6.1: Magnitude responses of a 30th-order FIR filter and a 5th-order Butterworth IIR
filter, both targeting the same cutoff frequency. The IIR filter achieves a sharper transition with
far fewer coefficients, but the FIR filter can provide exact linear phase.

6.2 FIR Filter Design Methods

6.2.1 The Window Method
The simplest approach to FIR design starts from the ideal (but unrealizable) frequency
response and truncates its impulse response to a finite length. The ideal low-pass filter, for
example, has the impulse response

sin(ωc n)
hideal[n] =
π ,
n
which extends infinitely in both directions. Multiplying this infinite sequence by a finite
window w[n] of length N yields a realizable FIR filter:

h[n] = hideal[n] · w[n].

The choice of window controls the trade-off between the sharpness of the transition band
and the level of the side lobes (ripple). Common windows include:

• Rectangular window: sharpest main lobe but highest side lobes (−13 dB).

• Hamming window: good balance; side lobes at about −43 dB.

• Blackman window: very low side lobes (−58 dB) at the cost of a wider main lobe.

• Kaiser window: adjustable parameter β allows continuous control of the trade-off.

6.2.2 Frequency Sampling Method

An alternative approach specifies the desired frequency response at N equally spaced
fre-quencies and obtains the filter coefficients via the inverse DFT. The resulting filter
exactly matches the specification at the sampled frequencies; the behaviour between
samples de-pends on the transition samples chosen at the band edges.

75
Chapter 6. Design of Digital Filters

Common window functions (N = 51)

Rectangular
1
Hamming
Blackman
Hanning
w[n

0.5
]

0
−25 −20 −15 −10 −5 0 5 10 15 20 25
Sample index n

Figure 6.2: Comparison of common window functions. The rectangular window

preserves the sharpest frequency resolution but produces the highest side lobes. The
Blackman window suppresses side lobes most effectively but widens the main lobe. The
Hamming and Hanning windows offer practical compromises.

6.3 IIR Filter Design via the Bilinear Transform

The bilinear transform is the most widely used method for converting a continuous-time
filter Ha(s) into a discrete-time filter H(z). The substitution
2 1 − z−1
· s=
T 1 + z−1
maps the entire jω axis to the unit circle, guaranteeing that a stable analog prototype
produces a stable digital filter.
The mapping introduces a nonlinear compression of the frequency axis known as
fre-quency warping. To compensate, one pre-warps the critical frequencies before
applying the transform:
2 ωd T
Ωa = tan ,
T 2
where ωd is the desired digital frequency and Ω a is the analog frequency used in the proto-
type design.
Starting from a classical analog prototype (Butterworth for maximally flat response,
Chebyshev for equiripple behaviour, or elliptic for the sharpest possible transition), the
bilinear transform produces an IIR digital filter that inherits the analog design’s frequency-
domain characteristics.

6.3.1 Worked Example: FIR Low-Pass Filter Using the Hamming

Window
Problem. Design a length-7 FIR low-pass filter with normalized cutoff frequency ωc =
π/3 using the Hamming window.

Step 1: Compute the ideal impulse response. The ideal low-pass impulse response
is

sin(ωc n) sin(πn/3)
hideal[n] = πn = πn .

76
 6.3 IIR Filter Design via the Bilinear Transform

For a length-7 filter (N = 7), we center it at n = 3, so we compute hideal[n − 3] for n = 0, . . . , 6:

n hideal[n −
0 3] (−π)
sin π =
0 −3 √
3
1 sin(−2π
−2π/3)
= 4π ≈ 0.1378
√
sin(−π/3) 3
2 −π = 2π ≈ 0.2757
ωc 1
3 π = 3 ≈ 0.3333
4 0.2757
5 0.1378
6 0

Step 2: Apply the Hamming window. The Hamming window of length 7 is

2πn
w[n] = 0.54 − 0.46 cos 6 , n = 0, 1, . . . , 6.

Evaluating: w = {0.08, 0.31, 0.77, 1.00, 0.77, 0.31, 0.08}.

Step 3: Multiply.
h[n] = hideal[n − 3] · w[n] = {0, 0.043, 0.212, 0.333, 0.212, 0.043, 0}.

Observation. The coefficients are symmetric (h[n] = — h[6 n]), guaranteeing linear
phase. The Hamming window has reduced the side lobes compared to a rectangular window,
at the cost of a slightly wider transition band.

6.3.2 Worked Example: IIR Filter Design via the Bilinear

Transform
Problem. Convert the first-order Butterworth analog low-pass filter
H Ωc
a(s) =
s + Ωc
into a digital filter using the bilinear transform with T = 1, targeting a digital cutoff
frequency of ωd = π/4.

Step 1: Pre-warp the cutoff frequency.

2 ωd T π
Ωc = T
tan 2 = 2 tan 8 ≈ 2 × 0.4142 = 0.8284.

−1
1−z
Step 2: Apply the bilinear substitution. Substitute s−1= 2
1+z into Ha(s):
0.8284
H 0.8284 (1 + z−1)
(z) = = .
2 11−z
−1
+ 0.8284 2(1 − z−1) + 0.8284(1 + z−1)
+z−1

Step 3: Simplify. Expanding the denominator:

2 − 2z−1 + 0.8284 + 0.8284 z−1 = 2.8284 − 1.1716 z−1.
So 0.8284
+ 0.8284 z−1
H(z) = (1 + z−1)
2.8284 − 1.1716 z−1 0.2929
1 − 0.4142 z−1 .
=
77
78
Chapter 6. Design of Digital Filters

Step 4: Verify. The digital filter has a pole at z = 0.4142, which lies inside the unit
circle, so the filter isj0stable.
At ω = 0: H(e ) = 0.2929×2 = 1.0. The DC gain is unity.
1−0.4142 √
At ω = π/4: |H(e π/4)| ≈ j 2 = 0.707, confirming this is indeed the −3 dB cutoff
1/
frequency, exactly where we wanted it.
The pre-warping step was essential: without it, the bilinear transform’s frequency com-
pression would have shifted the cutoff to the wrong location.

Problems
1. An FIR filter has impulse response h[n] = { 1, 2, 3, 2,
} 1 for n = 0, . . . , 4. (a) Is this
filter guaranteed to be stable? Explain. (b) Show that h[n] — = h[4 n] and explain
why this symmetry implies linear phase.

2. Consider the IIR filter y[n] = 0.9 y[n— 1] + 0.1 x[n]. (a) Find the transfer function H(z).
(b) Locate the pole and determine whether the system is stable. (c) Evaluate |H(ejω )
at ω = 0 and ω = π. Is this a low-pass or high-pass filter? |

3. Design a length-5 FIR low-pass filter using the rectangular window method with
nor-malized cutoff frequency ωc = π/2. Compute the ideal impulse response
sin(ωc n)
hideal[n] =
π — for n = 2, . . . , 2 (use L’Hoˆ pital’s rule at n = 0), and apply the
rectangular window.
n
N—
for
4. Repeat the previous problem using a Hamming window: w[n] = 0.54 + 0.46 cos 2πn 1
n = − 2, . . . , 2. Compare the two sets of coefficients and discuss what changes.

5. A second-order IIR filter has the transfer function

H(z) = 1 − z−2
1 − 0.5 z−1 + 0.25 z−2 .
(a) Find the poles and zeros. (b) Is the system stable? (c) Evaluate H(ej0) and
H(ejπ ). What does this tell you about the filter type?

6. Explain in your own words why FIR filters are always stable, regardless of the coeffi-
cient values, while IIR filters require stability verification.

7. A Butterworth low-pass filter of order 2 has the analog transfer function

1
Ha(s) = √ .
s2 + 2 s + 1
Using the bilinear transform with T = 1, find H(z). Verify that both poles of H(z)
lie inside the unit circle.

8. An audio signal sampled at fs = 44100 Hz needs a low-pass filter with cutoff at 5000
Hz. To design this using the bilinear transform, compute the pre-warped analog cutoff
frequency Ωa.

9. A digital filter with impulse response h[n] = δ[n] − δ[n − 1] is applied to a slowly
varying signal. What is the output for the input x[n] = c (a constant)? What kind of
operation does this filter perform?

79
 6.3 IIR Filter Design via the Bilinear Transform

10. The FIR vs. IIR comparison table in this chapter lists five properties. For each of
the following applications, state whether FIR or IIR would be more appropriate
and explain your reasoning: (a) real-time echo cancellation in a telephone system,
(b) a biomedical monitor measuring EEG signals, (c) a bass-boost equalizer in a
portable music player.
11. (Research) The Parks–McClellan algorithm (also known as the Remez exchange
algo-rithm) is an alternative to the window method for FIR filter design. Investigate
how it works and explain its key advantage: equiripple behaviour in both the passband
and the stopband.

• FIR filters are always stable and can achieve exact linear phase, but require higher
orders for sharp transitions.

• IIR filters achieve sharp cutoffs with fewer coefficients, but stability must be
verified and linear phase is generally not possible.

• The window method designs FIR filters by truncating the ideal impulse response;
the window shape controls the resolution–leakage trade-off.

• The bilinear transform converts classical analog filter designs (Butterworth, Cheby-
shev, elliptic) into stable IIR digital filters, with frequency pre-warping to compen-
sate for axis compression.

80