We first start with the most basic sampling ideas based on various forms of
Fourier transforms
[1][2][3].
The Spectrum of a
Continuous-Time Signal and the Fourier Transform
Although in many cases digital signal processing views the signal as simple
sequence of numbers, here we are going to pose the problem as originating with
a function of continuous time. The fundamental tool is the classical Fourier
transform defined by
F
(
ω
)
=
∫
f
(
t
)
e
−
j
ω
t
ⅆ
t
F
(
ω
)
=
∫
f
(
t
)
e
−
j
ω
t
ⅆ
t
(1)
and its inverse
f
(
t
)
=
1
2
π
∫
F
(
ω
)
e
j
ω
t
ⅆ
ω
.
f
(
t
)
=
1
2
π
∫
F
(
ω
)
e
j
ω
t
ⅆ
ω
.
(2)
where
j
=
−
1
j
=
−
1
.
The Fourier transform of a signal is called its spectrum and it is complex
valued with a magnitude and phase.
If the signal is periodic with period
f
(
t
)
=
f
(
t
+
P
)
f
(
t
)
=
f
(
t
+
P
)
,
the Fourier transform does not exist as a function (it may as a distribution)
therefore the spectrum is defined as the set of Fourier series coefficients
C
(
k
)
=
1
P
∫
0
P
f
(
t
)
e
−
j
2
π
k
t
/
P
ⅆ
t
C
(
k
)
=
1
P
∫
0
P
f
(
t
)
e
−
j
2
π
k
t
/
P
ⅆ
t
(3)
with the expansion having the form
f
(
t
)
=
∑
k
C
(
k
)
e
j
2
π
k
t
/
P
.
f
(
t
)
=
∑
k
C
(
k
)
e
j
2
π
k
t
/
P
.
(4)
The functions
g
k
(
t
)
=
e
j
2
π
k
t
/
P
g
k
(
t
)
=
e
j
2
π
k
t
/
P
form an orthogonal basis for periodic functions and
(
Equation 3) is the inner
product
C
(
k
)
=
〈
f
(
t
)
,
g
k
(
t
)
〉
C
(
k
)
=
〈
f
(
t
)
,
g
k
(
t
)
〉
.
For the non-periodic case in
(Equation 1) the spectrum is
a function of continuous frequency and for the periodic case in
(Equation 3), the spectrum
is a number sequence (a function of discrete frequency).
The
Spectrum of a Sampled Signal and the DTFT
The discrete-time Fourier transform (DTFT) as defined in terms samples of a
continuous function is
F
d
(
ω
)
=
∑
n
f
(
T
n
)
e
−
j
ω
T
n
F
d
(
ω
)
=
∑
n
f
(
T
n
)
e
−
j
ω
T
n
(5)
and its inverse
f
(
T
n
)
=
T
2
π
∫
−
π
/
T
π
/
T
F
d
(
ω
)
e
j
ω
T
n
ⅆ
ω
f
(
T
n
)
=
T
2
π
∫
−
π
/
T
π
/
T
F
d
(
ω
)
e
j
ω
T
n
ⅆ
ω
(6)
can be derived by noting that
F
d
(
ω
)
F
d
(
ω
)
is periodic with period
P
=
2
π
/
T
P
=
2
π
/
T
and, therefore, it can be expanded in a Fourier series with
(
Equation 6) resulting from
calculating the series coefficients using
(
Equation 3).
The spectrum of a discrete-time signal is defined as the DTFT of the samples
of a continuous-time signal given in
(Equation 5). Samples of the
signal are given by the inverse DTFT in
(Equation 6) but they can
also be obtained by directly sampling
f
(
t
)
f
(
t
)
in (Equation 2) giving
f
(
T
n
)
=
1
2
π
∫
−
∞
∞
F
(
ω
)
e
j
ω
T
n
ⅆ
ω
f
(
T
n
)
=
1
2
π
∫
−
∞
∞
F
(
ω
)
e
j
ω
T
n
ⅆ
ω
(7)
which can be rewritten as an infinite sum of finite integrals in the form
f
(
T
n
)
=
1
2
π
∑
ℓ
∫
0
2
π
/
T
F
(
ω
+
2
π
ℓ
/
T
)
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
ⅆ
ω
f
(
T
n
)
=
1
2
π
∑
ℓ
∫
0
2
π
/
T
F
(
ω
+
2
π
ℓ
/
T
)
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
ⅆ
ω
=
1
2
π
∫
0
2
π
/
T
[
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
]
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
ⅆ
ω
=
1
2
π
∫
0
2
π
/
T
[
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
]
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
ⅆ
ω
(8)
where
F
p
(
ω
)
F
p
(
ω
)
is a periodic function made up of shifted versions of
F
(
ω
)
F
(
ω
)
(aliased) defined in
(
Equation 9) Because
(
Equation 8) and
(
Equation 6) are equal for
all
T
n
T
n
and because the limits can be shifted by
π
/
T
π
/
T
without changing the equality, the integrands are equal and we have
F
d
(
ω
)
=
1
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
1
T
F
p
(
ω
)
.
F
d
(
ω
)
=
1
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
1
T
F
p
(
ω
)
.
(9)
where
F
p
(
ω
)
F
p
(
ω
)
is a periodic function made up of shifted versions of
F
(
ω
)
F
(
ω
)
as in (
Equation 8). The
spectrum of the samples of
f
(
t
)
f
(
t
)
is an aliased version of the spectrum of
f
(
t
)
f
(
t
)
itself. The closer together the samples are taken, the further apart the
centers of the aliased spectra are.
This result is very important in determining the frequency domain effects of
sampling. It shows what the sampling rate should be and it is the basis for
deriving the sampling theorem.
Samples
of the Spectrum of a Sampled Signal and the DFT
Samples of the spectrum can be calculated from a finite number of samples of
the original continuous-time signal using the DFT. If we let the length of the
DFT be
N
N
and separation of the samples in the frequency domain be
Δ
Δ
and define the periodic functions
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
N
Δ
ℓ
)
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
N
Δ
ℓ
)
(10)
and
f
p
(
t
)
=
∑
m
f
(
t
+
N
T
m
)
f
p
(
t
)
=
∑
m
f
(
t
+
N
T
m
)
(11)
then from (
Equation 5) and
(
Equation 9) samples of the
DTFT of
f
(
T
n
)
f
(
T
n
)
are
F
p
(
Δ
k
)
=
T
∑
n
f
(
T
n
)
e
−
j
T
Δ
n
k
F
p
(
Δ
k
)
=
T
∑
n
f
(
T
n
)
e
−
j
T
Δ
n
k
=
T
∑
m
∑
n
=
0
N
−
1
f
(
T
n
+
T
N
m
)
e
−
j
Δ
(
T
n
+
T
N
m
)
k
=
T
∑
m
∑
n
=
0
N
−
1
f
(
T
n
+
T
N
m
)
e
−
j
Δ
(
T
n
+
T
N
m
)
k
=
T
∑
n
=
0
N
−
1
[
∑
m
f
(
T
n
+
T
N
m
)
]
e
−
j
Δ
(
T
n
+
T
N
m
)
k
,
=
T
∑
n
=
0
N
−
1
[
∑
m
f
(
T
n
+
T
N
m
)
]
e
−
j
Δ
(
T
n
+
T
N
m
)
k
,
(12)
therefore,
F
p
(
Δ
k
)
=
ℱ
{
f
p
(
T
n
)
}
F
p
(
Δ
k
)
=
ℱ
{
f
p
(
T
n
)
}
(13)
if
Δ
T
N
=
2
π
Δ
T
N
=
2
π
.
This formula gives a method for approximately calculating values of the
Fourier transform of a function by taking the DFT (usually with the FFT) of
samples of the function. This formula can easily be verified by forming the
Riemann sum to approximate the integrals in
(
Equation 1) or
(
Equation 2).
Samples of the DTFT of a
Sequence
It the signal is discrete in origin and is not a sampled function of a
continuous variable, the DTFT is defined with
T
=
1
T
=
1
as
H
(
ω
)
=
∑
n
h
(
n
)
e
−
j
ω
n
H
(
ω
)
=
∑
n
h
(
n
)
e
−
j
ω
n
(14)
with an inverse
h
(
n
)
=
1
2
π
∫
−
π
π
H
(
ω
)
e
j
ω
n
ⅆ
ω
.
h
(
n
)
=
1
2
π
∫
−
π
π
H
(
ω
)
e
j
ω
n
ⅆ
ω
.
(15)
If we want to calculate
H
(
ω
)
H
(
ω
)
,
we must sample it and that is written as
H
(
Δ
k
)
∑
n
h
(
n
)
e
−
j
Δ
k
n
H
(
Δ
k
)
∑
n
h
(
n
)
e
−
j
Δ
k
n
which after breaking the sum into an infinite sum of
length-
N
N
sums as was done in
(
Equation 12) becomes
H
(
Δ
k
)
∑
m
∑
n
=
0
N
−
1
h
(
n
+
N
m
)
e
−
j
Δ
k
n
H
(
Δ
k
)
∑
m
∑
n
=
0
N
−
1
h
(
n
+
N
m
)
e
−
j
Δ
k
n
if
Δ
=
2
π
/
N
Δ
=
2
π
/
N
.
This allows us to calculate samples of the DTFT by taking the DFT of samples
of a periodized
h
(
n
)
h
(
n
)
.
H
(
Δ
k
)
=
ℱ
{
h
p
(
n
)
}
.
H
(
Δ
k
)
=
ℱ
{
h
p
(
n
)
}
.
(16)
This a combination of the results in
(
Equation 9) and in
(
Equation 13).
Fourier Series
Coefficients from the DFT
If the signal to be analyzed is periodic, the Fourier integral in
(Equation 1) does not
converge to a function (it may to a distribution). This function is usually
expanded in a Fourier series to define its spectrum or a frequency
description. We will sample this function and show how to approximately
calculate the Fourier series coefficients using the DFT of the samples.
Consider a periodic signal
f
˜
(
t
)
=
f
˜
(
t
+
P
)
f
˜
(
t
)
=
f
˜
(
t
+
P
)
with
N
N
samples taken every
T
T
seconds to give
T
n
˜
(
t
)
T
n
˜
(
t
)
for integer
n
n
such that
N
T
=
P
N
T
=
P
.
The Fourier series expansion of
f
˜
(
t
)
f
˜
(
t
)
is
f
˜
(
t
)
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
t
/
P
f
˜
(
t
)
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
t
/
P
(17)
with the coefficients given in
(
Equation 3). Samples of
this are
f
˜
(
T
n
)
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
T
n
/
P
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
n
/
N
f
˜
(
T
n
)
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
T
n
/
P
=
∑
k
=
−
∞
∞
C
(
k
)
e
2
π
k
n
/
N
(18)
which is broken into a sum of sums as
f
˜
(
T
n
)
=
∑
ℓ
−
∞
∞
∑
k
=
0
N
−
1
C
(
k
+
N
ℓ
)
e
2
π
(
k
+
N
ℓ
)
n
/
N
=
∑
k
=
0
N
−
1
[
∑
ℓ
−
∞
∞
C
(
k
+
N
ℓ
)
]
e
2
π
k
n
/
N
.
f
˜
(
T
n
)
=
∑
ℓ
−
∞
∞
∑
k
=
0
N
−
1
C
(
k
+
N
ℓ
)
e
2
π
(
k
+
N
ℓ
)
n
/
N
=
∑
k
=
0
N
−
1
[
∑
ℓ
−
∞
∞
C
(
k
+
N
ℓ
)
]
e
2
π
k
n
/
N
.
(19)
But the inverse DFT is of the form
f
˜
(
T
n
)
=
1
N
∑
k
=
0
N
−
1
F
(
k
)
e
j
2
π
n
k
/
N
f
˜
(
T
n
)
=
1
N
∑
k
=
0
N
−
1
F
(
k
)
e
j
2
π
n
k
/
N
(20)
therefore,
ℱ
{
f
˜
(
T
n
)
}
=
N
∑
ℓ
C
(
k
+
N
ℓ
)
=
N
C
p
(
k
)
.
ℱ
{
f
˜
(
T
n
)
}
=
N
∑
ℓ
C
(
k
+
N
ℓ
)
=
N
C
p
(
k
)
.
(21)
and we have our result of the relation of the Fourier coefficients to the DFT
of a sampled periodic signal. Once again aliasing is a result of sampling.
Shannon's Sampling
Theorem
Given a signal modeled as a real (sometimes complex) valued function of a real
variable (usually time here), we define a bandlimited function as any function
whose Fourier transform or spectrum is zero outside of some finite domain
|
F
(
ω
)
|
=
0
for
|
ω
|
>
W
|
F
(
ω
)
|
=
0
for
|
ω
|
>
W
(22)
for some
W
<
∞
W
<
∞
.
The sampling theorem states that if
f
(
t
)
f
(
t
)
is sampled
f
s
(
n
)
=
f
(
T
n
)
f
s
(
n
)
=
f
(
T
n
)
(23)
such that
T
<
2
π
/
W
T
<
2
π
/
W
,
then
f
(
t
)
f
(
t
)
can be exactly reconstructed (interpolated) from its samples
f
s
(
n
)
f
s
(
n
)
using
f
(
t
)
=
∑
n
=
−
∞
∞
f
s
(
n
)
[
sin
(
π
t
/
T
−
π
n
)
π
t
/
T
−
π
n
]
.
f
(
t
)
=
∑
n
=
−
∞
∞
f
s
(
n
)
[
sin
(
π
t
/
T
−
π
n
)
π
t
/
T
−
π
n
]
.
(24)
This is more compactly written by defining the sinc
function as
sinc
(
x
)
=
sin
(
x
)
x
sinc
(
x
)
=
sin
(
x
)
x
(25)
which gives the sampling formula
(
(Reference)) the form
f
(
t
)
=
∑
n
f
s
(
n
)
sinc
(
π
t
/
T
−
π
n
)
.
f
(
t
)
=
∑
n
f
s
(
n
)
sinc
(
π
t
/
T
−
π
n
)
.
(26)
The derivation of
((Reference)) or
((Reference)) can be done a
number of ways. One of the quickest uses infinite sequences of delta functions
and will be developed later in these notes. We will use a more direct method
now to better see the assumptions and restrictions.
We first note that if
f
(
t
)
f
(
t
)
is bandlimited and if
T
<
2
π
/
W
T
<
2
π
/
W
then there is no overlap or aliasing in
F
p
(
ω
)
F
p
(
ω
)
.
In other words, we can write
(Equation 2) as
f
(
t
)
=
1
2
π
∫
−
∞
∞
F
(
ω
)
e
j
ω
t
ⅆ
ω
=
1
2
π
∫
−
π
/
T
π
/
T
F
p
(
ω
)
e
j
ω
t
ⅆ
ω
f
(
t
)
=
1
2
π
∫
−
∞
∞
F
(
ω
)
e
j
ω
t
ⅆ
ω
=
1
2
π
∫
−
π
/
T
π
/
T
F
p
(
ω
)
e
j
ω
t
ⅆ
ω
(27)
but
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
T
∑
n
f
(
T
n
)
d
−
j
ω
T
n
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
T
∑
n
f
(
T
n
)
d
−
j
ω
T
n
(28)
therefore,
f
(
t
)
=
1
2
π
∫
−
π
/
T
π
/
T
[
T
∑
n
f
(
T
n
)
e
−
j
ω
T
n
]
e
j
ω
t
ⅆ
ω
f
(
t
)
=
1
2
π
∫
−
π
/
T
π
/
T
[
T
∑
n
f
(
T
n
)
e
−
j
ω
T
n
]
e
j
ω
t
ⅆ
ω
(29)
=
T
2
π
∑
n
f
(
T
n
)
∫
−
π
/
T
π
/
T
e
j
(
t
−
T
n
)
ω
ⅆ
ω
=
T
2
π
∑
n
f
(
T
n
)
∫
−
π
/
T
π
/
T
e
j
(
t
−
T
n
)
ω
ⅆ
ω
=
∑
n
f
(
T
n
)
sin
(
π
T
t
−
π
n
)
π
T
t
−
π
n
=
∑
n
f
(
T
n
)
sin
(
π
T
t
−
π
n
)
π
T
t
−
π
n
(30)
which is the sampling theorem. An alternate derivation uses a rectangle
function and its Fourier transform, the sinc function, together with
convolution and multiplication. A still shorter derivation uses strings of
delta function with convolutions and multiplications. This is discussed later
in these notes.
There are several things to notice about this very important result. First,
note that although
f
(
t
)
f
(
t
)
is defined for all
t
t
from only its samples, it does require an infinite number of them to exactly
calculate
f
(
t
)
f
(
t
)
.
Also note that this sum can be thought of as an expansion of
f
(
t
)
f
(
t
)
in terms of an orthogonal set of basis function which are the sinc functions.
One can show that the coefficients in this expansion of
f
(
t
)
f
(
t
)
calculated by an inner product are simply samples of
f
(
t
)
f
(
t
)
.
In other words, the sinc functions span the space of bandlimited functions
with a very simple calculation of the expansion coefficients. One can ask the
question of what happens if a signal is ``under sampled". What happens if the
reconstruction formula in
((Reference)) is used when
there is aliasing and
((Reference)) is not true. We
will not pursue that just now. In any case, there are many variations and
generalizations of this result that are quite interesting and useful.