A very important and fundamental operation in discrete-time signal
processing is that of sampling. Discrete-time signals are often obtained
from continuous-time signal by simple sampling. This is mathematically
modeled as the evaluation of a function of a real variable at discrete
values of time [16]. Physically, it is a more complicated and
varied process which might be modeled as convolution of the sampled signal
by a narrow pulse or an inner product with a basis function or, perhaps,
by some nonlinear process.
The sampling of continuous-time signals is reviewed in the recent books by
Marks [10] which is a bit casual with mathematical details, but
gives a good overview and list of references. He gives a more advanced
treatment in [11]. Some of these references are
[13], [17], [9], [8], [7], [16], [15]. These will discuss
the usual sampling theorem but also interpretations and extensions such as
sampling the value and one derivative at each point, or of non uniform
sampling.
Multirate discrete-time systems use sampling and sub sampling for a
variety of reasons [4], [18]. A very general definition of sampling
might be any mapping of a signal into a sequence of numbers. It might be
the process of calculating coefficients of an expansion using inner
products. A powerful tool is the use of periodically time varying theory,
particularly the bifrequency map, block formulation, commutators, filter
banks, and multidimensional formulations. One current interest follows
from the study of wavelet basis functions. What kind of sampling theory
can be developed for signals described in terms of wavelets? Some of the
literature can be found in [1], [6], [12], [5], [2].
Another relatively new framework is the idea of tight frames [5], [19], [2].
Here signals are expanded in terms of an over determined set of expansion
functions or vectors. If these expansions are what is called a tight
frame, the mathematics of calculating the expansion coefficients with
inner products works just as if the expansion functions were an
orthonormal basis set. The redundancy of tight frames offers interesting
possibilities. One example of a tight frame is an over sampled band
limited function expansion.
We first start with the most basic sampling ideas based on various forms
of Fourier transforms [14], [3], [19].
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
d
t
F
(
ω
)
=
∫
f
(
t
)
e
-
j
ω
t
d
t
(1)
and its inverse
f
(
t
)
=
1
2
π
∫
F
(
ω
)
e
j
ω
t
d
ω
.
f
(
t
)
=
1
2
π
∫
F
(
ω
)
e
j
ω
t
d
ω
.
(2)
where j=-1j=-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
d
t
C
(
k
)
=
1
P
∫
0
P
f
(
t
)
e
-
j
2
π
k
t
/
P
d
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 gk(t)=ej2πkt/Pgk(t)=ej2πkt/P form an orthogonal basis for
periodic functions and (Equation 3) is the inner product C(k)=〈f(t),gk(t)〉C(k)=〈f(t),gk(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
d
ω
f
(
T
n
)
=
T
2
π
∫
-
π
/
T
π
/
T
F
d
(
ω
)
e
j
ω
T
n
d
ω
(6)
can be derived by noting that Fd(ω)Fd(ω) is periodic with period
P=2π/TP=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
d
ω
f
(
T
n
)
=
1
2
π
∫
-
∞
∞
F
(
ω
)
e
j
ω
T
n
d
ω
(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
d
ω
f
(
T
n
)
=
1
2
π
∑
ℓ
∫
0
2
π
/
T
F
(
ω
+
2
π
ℓ
/
T
)
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
d
ω
(8)
=
1
2
π
∫
0
2
π
/
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
d
ω
=
1
2
π
∫
0
2
π
/
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
e
j
(
ω
+
2
π
ℓ
/
T
)
T
n
d
ω
(9)
where Fp(ω)Fp(ω) is a periodic function made up of shifted versions of
F(ω)F(ω) (aliased) defined in (Equation 10) Because (Equation 9) and
(Equation 6) are equal for all TnTn 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
(
ω
)
.
(10)
where Fp(ω)Fp(ω) is a periodic function made up of shifted versions of
F(ω)F(ω) as in (Equation 9). 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 NN and separation of the samples in the
frequency domain be ΔΔ and define the periodic functions
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
N
Δ
ℓ
)
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
N
Δ
ℓ
)
(11)
and
f
p
(
t
)
=
∑
m
f
(
t
+
N
T
m
)
f
p
(
t
)
=
∑
m
f
(
t
+
N
T
m
)
(12)
then from (Equation 62) and (Equation 10) samples of the DTFT of f(Tn)f(Tn) 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
(13)
=
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
(14)
=
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
,
(15)
therefore,
F
p
(
Δ
k
)
=
DFT
{
f
p
(
T
n
)
}
F
p
(
Δ
k
)
=
DFT
{
f
p
(
T
n
)
}
(16)
if ΔTN=2πΔTN=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
If the signal is discrete in origin and is not a sampled function of a
continuous variable, the DTFT is defined with T=1T=1 as
H
(
ω
)
=
∑
n
h
(
n
)
e
-
j
ω
n
H
(
ω
)
=
∑
n
h
(
n
)
e
-
j
ω
n
(17)
with an inverse
h
(
n
)
=
1
2
π
∫
-
π
π
H
(
ω
)
e
j
ω
n
d
ω
.
h
(
n
)
=
1
2
π
∫
-
π
π
H
(
ω
)
e
j
ω
n
d
ω
.
(18)
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
(19)
which after breaking the sum into an infinite sum of length-NN sums as
was done in (Equation 15) 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
(20)
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
)
=
DFT
{
h
p
(
n
)
}
.
H
(
Δ
k
)
=
DFT
{
h
p
(
n
)
}
.
(21)
This a combination of the results in (Equation 10) and in (Equation 16).
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 NN
samples taken every TT seconds to give Tn˜(t)Tn˜(t) for integer nn
such that NT=PNT=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
(22)
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
(23)
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
.
(24)
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
(25)
therefore,
DFT
{
f
˜
(
T
n
)
}
=
N
∑
ℓ
C
(
k
+
N
ℓ
)
=
N
C
p
(
k
)
.
DFT
{
f
˜
(
T
n
)
}
=
N
∑
ℓ
C
(
k
+
N
ℓ
)
=
N
C
p
(
k
)
.
(26)
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
(27)
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
)
(28)
such that T<2π/WT<2π/W, then f(t)f(t) can be exactly reconstructed
(interpolated) from its samples fs(n)fs(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
.
(29)
This is more compactly written by defining the sinc function as
sinc
(
x
)
=
sin
(
x
)
x
sinc
(
x
)
=
sin
(
x
)
x
(30)
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
)
.
(31)
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π/WT<2π/W then there
is no overlap or aliasing in Fp(ω)Fp(ω). In other words, we can write
(Equation 2) as
f
(
t
)
=
1
2
π
∫
-
∞
∞
F
(
ω
)
e
j
ω
t
d
ω
=
1
2
π
∫
-
π
/
T
π
/
T
F
p
(
ω
)
e
j
ω
t
d
ω
f
(
t
)
=
1
2
π
∫
-
∞
∞
F
(
ω
)
e
j
ω
t
d
ω
=
1
2
π
∫
-
π
/
T
π
/
T
F
p
(
ω
)
e
j
ω
t
d
ω
(32)
but
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
T
∑
n
f
(
T
n
)
e
-
j
ω
T
n
F
p
(
ω
)
=
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
=
T
∑
n
f
(
T
n
)
e
-
j
ω
T
n
(33)
therefore,
f
(
t
)
=
1
2
π
∫
-
π
/
T
π
/
T
T
∑
n
f
(
T
n
)
e
-
j
ω
T
n
e
j
ω
t
d
ω
f
(
t
)
=
1
2
π
∫
-
π
/
T
π
/
T
T
∑
n
f
(
T
n
)
e
-
j
ω
T
n
e
j
ω
t
d
ω
(34)
=
T
2
π
∑
n
f
(
T
n
)
∫
-
π
/
T
π
/
T
e
j
(
t
-
T
n
)
ω
d
ω
=
T
2
π
∑
n
f
(
T
n
)
∫
-
π
/
T
π
/
T
e
j
(
t
-
T
n
)
ω
d
ω
(35)
=
∑
n
f
(
T
n
)
sin
(
π
T
t
-
π
n
)
π
T
t
-
π
n
=
∑
n
f
(
T
n
)
sin
(
π
T
t
-
π
n
)
π
T
t
-
π
n
(36)
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 tt 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.
Most theoretical and mathematical analysis of signals and systems use the
Fourier series, Fourier transform, Laplace transform, discrete-time
Fourier transform (DTFT), or the z-transform, however, when we want to
actually evaluate transforms, we calculate values at sample frequencies.
In other words, we use the discrete Fourier transform (DFT) and, for
efficiency, usually evaluate it with the FFT algorithm. An important
question is how can we calculate or approximately calculate these symbolic
formula-based transforms with our practical finite numerical tool. It
would certainly seem that if we wanted the Fourier transform of a signal
or function, we could sample the function, take its DFT with the FFT, and
have some approximation to samples of the desired Fourier transform. We
saw in the previous section that it is, in fact, possible provided some
care is taken.
Summary
For the signal that is a function of a continuous variable we have
Table 1
| FT: |
f
(
t
)
f
(
t
)
|
→
→
|
F
(
ω
)
F
(
ω
)
|
| DTFT: |
f
(
T
n
)
f
(
T
n
)
|
→
→
|
1
T
F
p
(
ω
)
=
1
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
1
T
F
p
(
ω
)
=
1
T
∑
ℓ
F
(
ω
+
2
π
ℓ
/
T
)
|
| DFT: |
f
p
(
T
n
)
f
p
(
T
n
)
|
→
→
|
1TFp(Δk)1TFp(Δk) for ΔTN=2πΔTN=2π |
For the signal that is a function of a discrete variable we have
Table 2
| DTFT: |
h
(
n
)
h
(
n
)
|
→
→
|
H
(
ω
)
H
(
ω
)
|
| DFT: |
h
p
(
n
)
h
p
(
n
)
|
→
→
|
H(Δk)H(Δk) for ΔN=2πΔN=2π |
For the periodic signal of a continuous variable we have
Table 3
| FS: |
g
˜
(
t
)
g
˜
(
t
)
|
→
→
|
C
(
k
)
C
(
k
)
|
| DFT: |
g
˜
(
T
n
)
g
˜
(
T
n
)
|
→
→
|
NCp(k)NCp(k) for TN=PTN=P |
For the sampled bandlimited signal we have
Table 4
| Sinc: |
f
(
t
)
f
(
t
)
|
→
→
|
f
(
T
n
)
f
(
T
n
)
|
| |
|
|
f
(
t
)
=
∑
n
f
(
T
n
)
sinc
(
2
π
t
/
T
-
π
n
)
f
(
t
)
=
∑
n
f
(
T
n
)
sinc
(
2
π
t
/
T
-
π
n
)
|
| |
|
|
if F(ω)=0F(ω)=0 for |ω|>2π/T|ω|>2π/T |
These formulas summarize much of the relations of the Fourier transforms
of sampled signals and how they might be approximately calculate with the
FFT. We next turn to the use of distributions and strings of delta
functions as tool to study sampling.
Th preceding discussions used traditional Fourier techniques to develop
sampling tools. If distributions or delta functions are allowed, the
Fourier transform will exist for a much larger class of signals. One
should take care when using distributions as if they were functions but it
is a very powerful extension.
There are several functions which have equally spaced sequences of
impulses that can be used as tools in deriving a sampling formula. These
are called “pitch fork" functions, picket fence functions, comb functions
and shah functions. We start first with a finite length sequence to be
used with the DFT. We define
⨿
M
(
n
)
=
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
⨿
M
(
n
)
=
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
(37)
where N=LMN=LM.
D
F
T
{
⨿
M
(
n
)
}
=
∑
n
=
0
N
-
1
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
e
-
j
2
π
n
k
/
N
D
F
T
{
⨿
M
(
n
)
}
=
∑
n
=
0
N
-
1
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
e
-
j
2
π
n
k
/
N
(38)
=
∑
m
=
0
L
-
1
∑
n
=
0
N
-
1
δ
(
n
-
M
m
)
e
-
j
2
π
n
k
/
N
=
∑
m
=
0
L
-
1
∑
n
=
0
N
-
1
δ
(
n
-
M
m
)
e
-
j
2
π
n
k
/
N
(39)
=
∑
m
=
0
L
-
1
e
-
j
2
π
M
m
k
/
N
=
∑
m
=
0
L
-
1
e
-
j
2
π
m
k
/
L
=
∑
m
=
0
L
-
1
e
-
j
2
π
M
m
k
/
N
=
∑
m
=
0
L
-
1
e
-
j
2
π
m
k
/
L
(40)
=
{
0 otherwise
L<k>L
=
0
=
{
0 otherwise
L
k
L
=
0
(41)
=
L
∑
l
=
0
M
-
1
δ
(
k
-
L
l
)
=
L
?
L
(
k
)
=L
∑
l
=
0
M
-
1
δ
(
k
-
L
l
)
=L
?
L
(k)
(42)
For the DTFT we have a similar derivation:
D
T
F
T
{
⨿
M
(
n
)
}
=
∑
n
=
-
∞
∞
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
e
-
j
ω
n
D
T
F
T
{
⨿
M
(
n
)
}
=
∑
n
=
-
∞
∞
∑
m
=
0
L
-
1
δ
(
n
-
M
m
)
e
-
j
ω
n
(43)
=
∑
m
=
0
L
-
1
∑
n
=
-
∞
∞
δ
(
n
-
M
m
)
e
-
j
ω
n
=
∑
m
=
0
L
-
1
∑
n
=
-
∞
∞
δ
(
n
-
M
m
)
e
-
j
ω
n
(44)
=
∑
m
=
0
L
-
1
e
-
j
ω
M
m
=
∑
m
=
0
L
-
1
e
-
j
ω
M
m
(45)
=
{
L
ω
=
k
2
π
/
M
0 otherwise
=
{
L
ω
=
k
2
π
/
M
0 otherwise
(46)
=
∑
l
=
0
M
-
1
δ
(
ω
-
2
π
l
/
M
l
)
=
K
?
2π/M
(
ω
)
=
∑
l
=
0
M
-
1
δ(ω-2πl/Ml)=K
?
2π/M
(ω)(47)
where KK
is constant.
An alternate derivation for the DTFT uses the inverse DTFT.
I
D
T
F
T
{
⨿
2
π
/
M
(
ω
)
}
=
1
2
π
∫
-
π
π
⨿
2
π
/
M
(
ω
)
e
j
ω
n
d
ω
I
D
T
F
T
{
⨿
2
π
/
M
(
ω
)
}
=
1
2
π
∫
-
π
π
⨿
2
π
/
M
(
ω
)
e
j
ω
n
d
ω
(48)
=
1
2
π
∫
-
π
π
∑
l
δ
(
ω
-
2
π
l
/
M
)
e
j
ω
n
d
ω
=
1
2
π
∫
-
π
π
∑
l
δ
(
ω
-
2
π
l
/
M
)
e
j
ω
n
d
ω
(49)
=
1
2
π
∑
l
∫
-
π
π
δ
(
ω
-
2
π
l
/
M
)
e
j
ω
n
d
ω
=
1
2
π
∑
l
∫
-
π
π
δ
(
ω
-
2
π
l
/
M
)
e
j
ω
n
d
ω
(50)
=
1
2
π
∑
l
=
0
M
-
1
e
2
π
l
n
/
M
=
{
0 otherwise
M
/
2
π
n
=
M
=
1
2
π
∑
l
=
0
M
-
1
e
2
π
l
n
/
M
=
{
0 otherwise
M
/
2
π
n
=
M
(51)
=
(
M
2π
)
?
2π/M
(
ω
)
=(
M
2π
)
?
2π/M
(ω)(52)
Therefore,
?
M
(
n
)
→
(
2π
M
)
?
2π/T
(
ω
)
?
M
(n)→(
2π
M
)
?
2π/T
(ω)
(53)
For regular Fourier transform, we have a string of impulse functions in
both the time and frequency. This we see from:
F
T
{
⨿
T
(
t
)
}
=
∫
-
∞
∞
∑
n
δ
(
t
-
n
T
)
e
-
j
ω
t
d
t
=
∑
n
∫
δ
(
t
-
n
T
)
e
-
j
ω
t
d
t
F
T
{
⨿
T
(
t
)
}
=
∫
-
∞
∞
∑
n
δ
(
t
-
n
T
)
e
-
j
ω
t
d
t
=
∑
n
∫
δ
(
t
-
n
T
)
e
-
j
ω
t
d
t
(54)
=
∑
n
e
-
j
ω
n
T
=
{
0 otherwise
∞
ω
=
2
π
/
T
=
∑
n
e
-
j
ω
n
T
=
{
0 otherwise
∞
ω
=
2
π
/
T
(55)
=
2π
T
?
2π/T
(
ω
)
=
2π
T
?
2π/T
(ω)(56)
The multiplicative constant is found from knowing the result for a single delta function.
These “shah functions" will be useful in sampling signals in both the
continuous time and discrete time cases.
In several situations we would like to increase the data rate of a signal
or, to increase its length if it has finite length. This may be part of a
multi rate system or part of an interpolation process. Consider the
process of inserting M-1M-1 zeros between each sample of a discrete time
signal.
y
(
n
)
=
{
0 otherwise
x
(
n
/
M
)
<
n
>
M
=
0
(
or
n
=
kM
)
y(n)=
{
0 otherwise
x
(
n
/
M
)
n
M
=
0
(
or
n
=
kM
)
(57)
For the finite length sequence case we calculate the DFT of the stretched
or up–sampled sequence by
C
s
(
k
)
=
∑
n
=
0
M
N
-
1
y
(
n
)
W
M
N
n
k
C
s
(
k
)
=
∑
n
=
0
M
N
-
1
y
(
n
)
W
M
N
n
k
(58)
C
s
(
k
)
=
∑
n
=
0
M
N
-
1
x
(
n
/
M
)
⨿
M
(
n
)
W
M
N
n
k
C
s
(
k
)
=
∑
n
=
0
M
N
-
1
x
(
n
/
M
)
⨿
M
(
n
)
W
M
N
n
k
(59)
where the length is now NMNM and k=0,1,⋯,NM-1k=0,1,⋯,NM-1. Changing the
index variable n=Mmn=Mm gives:
C
s
(
k
)
=
∑
m
=
0
N
-
1
x
(
m
)
W
N
m
k
=
C
(
k
)
.
C
s
(
k
)
=
∑
m
=
0
N
-
1
x
(
m
)
W
N
m
k
=
C
(
k
)
.
(60)
which says the DFT of the stretched sequence is exactly the same as the
DFT of the original sequence but over MM periods, each of length NN.
For up–sampling an infinitely long sequence, we calculate the DTFT of the
modified sequence in ((Reference)) as
C
s
(
ω
)
=
∑
n
=
-
∞
∞
x
(
n
/
M
)
⨿
M
(
n
)
e
-
j
ω
n
=
∑
m
x
(
m
)
e
-
j
ω
M
m
C
s
(
ω
)
=
∑
n
=
-
∞
∞
x
(
n
/
M
)
⨿
M
(
n
)
e
-
j
ω
n
=
∑
m
x
(
m
)
e
-
j
ω
M
m
(61)
=
C
(
M
ω
)
=
C
(
M
ω
)
(62)
where C(ω)C(ω) is the DTFT of x(n)x(n). Here again the transforms of the
up–sampled signal is the same as the original signal except over MM
periods. This shows up here as Cs(ω)Cs(ω) being a compressed version
of MM periods of C(ω)C(ω).
The z-transform of an up–sampled sequence is simply derived by:
Y
(
z
)
=
∑
n
=
-
∞
∞
y
(
n
)
z
-
n
=
∑
n
x
(
n
/
M
)
⨿
M
(
n
)
z
-
n
=
∑
m
x
(
m
)
z
-
M
m
Y
(
z
)
=
∑
n
=
-
∞
∞
y
(
n
)
z
-
n
=
∑
n
x
(
n
/
M
)
⨿
M
(
n
)
z
-
n
=
∑
m
x
(
m
)
z
-
M
m
(63)
=
X
(
z
M
)
=
X
(
z
M
)
(64)
which is consistent with a complex version of the DTFT in (Equation 62).
Notice that in all of these cases, there is no loss of information or
invertibility. In other words, there is no aliasing.
In this section we consider the sampling problem where, unless there is
sufficient redundancy, there will be a loss of information caused by
removing data in the time domain and aliasing in the frequency domain.
The sampling process or the down sampling process creates a new shorter or
compressed signal by keeping every MthMth sample of the original
sequence. This process is best seen as done in two steps. The first is
to mask off the terms to be removed by setting M-1M-1 terms to zero in each
length-MM block (multiply x(n)x(n) by ⨿M(n)⨿M(n)), then that sequence is
compressed or shortened by removing the M-1M-1 zeroed terms.
We will now calculate the length L=N/ML=N/M DFT of a sequence that was
obtained by sampling every MM terms of an original length-NN sequence
x(n)x(n). We will use the orthogonal properties of the basis vectors of the
DFT which says:
∑
n
=
0
M
-
1
e
-
j
2
π
n
l
/
M
=
{
0 otherwise.
M if n is an integer multiple of
M
∑
n
=
0
M
-
1
e
-
j
2
π
n
l
/
M
=
{
0 otherwise.
M if n is an integer multiple of
M
(65)
We now calculate the DFT of the down-sampled signal.
C
d
(
k
)
=
∑
m
=
0
L
-
1
x
(
M
m
)
W
L
m
k
C
d
(k)=
∑
m
=
0
L
-
1
x(Mm)
W
L
m
k
(66)
where N
=
L
M
N=LM
and
k
=
0,1,...,L-1
k=0,1,...,L-1.
This is done by masking
x
(
n
)
x(n)
.
C
d
(
k
)
=
∑
n
=
0
N
-
1
x
(
n
)
x
M
(
n
)
W
L
n
k
C
d
(k)=
∑
n
=
0
N
-
1
x(n)
x
M
(n)
W
L
n
k
(67)
=
∑
n
=
0
N
-
1
x
(
n
)
[
1
M
∑
l
=
0
M
-
1
e
-
j
2
π
n
l
/
M
]
e
-
j
2
π
n
k
/
N
=
∑
n
=
0
N
-
1
x(n)[
1
M
∑
l
=
0
M
-
1
e
-
j
2
π
n
l
/
M
]
e
-
j
2
π
n
k
/
N
(68)
=
1
M
∑
l
=
0
M
-
1
∑
n
=
0
N
-
1
x
(
n
)
e
j
2
π
(
k
+
L
l
)
n
/
N
=
1
M
∑
l
=
0
M
-
1
∑
n
=
0
N
-
1
x(n)
e
j
2
π
(
k
+
L
l
)
n
/
N
(69)
=
1
M
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
=
1
M
∑
l
=
0
M
-
1
C(k+Ll)(70)
The compression or removal of the masked terms is achieved in the frequency domain by using
k
=
0,1,...,L-1
k=0,1,...,L-1
This is a length-L DFT of the samples of
x
(
n
)
x(n).
Unless
C(k)C(k) is sufficiently bandlimited, this causes aliasing and
x(n)x(n) is not unrecoverable.
It is instructive to consider an alternative derivation of the above
result. In this case we use the IDFT given by
x
(
n
)
=
1
N
∑
k
=
0
N
-
1
C
(
k
)
W
N
-
n
k
.
x
(
n
)
=
1
N
∑
k
=
0
N
-
1
C
(
k
)
W
N
-
n
k
.
(71)
The sampled signal gives
y
(
n
)
=
x
(
M
n
)
=
1
N
∑
k
=
0
N
-
1
C
(
k
)
W
N
-
M
n
k
.
y
(
n
)
=
x
(
M
n
)
=
1
N
∑
k
=
0
N
-
1
C
(
k
)
W
N
-
M
n
k
.
(72)
for n=0,1,⋯,L-1n=0,1,⋯,L-1. This sum can be broken down by
y
(
n
)
=
1
N
∑
k
=
0
L
-
1
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
W
N
-
M
n
(
k
+
L
l
)
.
y
(
n
)
=
1
N
∑
k
=
0
L
-
1
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
W
N
-
M
n
(
k
+
L
l
)
.
(73)
=
1
N
∑
k
=
0
L
-
1
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
W
N
-
M
n
k
.
=
1
N
∑
k
=
0
L
-
1
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
W
N
-
M
n
k
.
(74)
From the term in the brackets, we have
C
s
(
k
)
=
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
C
s
(
k
)
=
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
(75)
as was obtained in (Equation 70).
Now consider still another derivation using shah functions. Let
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
(76)
From the convolution property of the DFT we have
C
s
(
k
)
=
L
⨿
L
(
k
)
*
C
(
k
)
C
s
(
k
)
=
L
⨿
L
(
k
)
*
C
(
k
)
(77)
therefore
C
s
(
k
)
=
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
C
s
(
k
)
=
∑
l
=
0
M
-
1
C
(
k
+
L
l
)
(78)
which again is the same as in (Equation 70).
We now turn to the down sampling of an infinitely long signal which will
require use of the DTFT of the signals.
C
s
(
ω
)
=
∑
m
=
-
∞
∞
x
(
M
m
)
e
-
j
ω
M
m
C
s
(
ω
)
=
∑
m
=
-
∞
∞
x
(
M
m
)
e
-
j
ω
M
m
(79)
=
∑
n
x
(
n
)
⨿
M
(
n
)
e
-
j
ω
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
e
-
j
ω
n
(80)
=
∑
n
x
(
n
)
1
M
∑
l
=
0
M
-
1
e
-
j
2
π
n
l
/
M
e
-
j
ω
n
=
∑
n
x
(
n
)
1
M
∑
l
=
0
M
-
1
e
-
j
2
π
n
l
/
M
e
-
j
ω
n
(81)
=
1
M
∑
l
=
0
M
-
1
∑
n
x
(
n
)
e
-
j
(
ω
-
2
π
l
/
M
)
n
=
1
M
∑
l
=
0
M
-
1
∑
n
x
(
n
)
e
-
j
(
ω
-
2
π
l
/
M
)
n
(82)
=
1
M
∑
l
=
0
M
-
1
C
(
ω
-
2
π
l
/
M
)
=
1
M
∑
l
=
0
M
-
1
C
(
ω
-
2
π
l
/
M
)
(83)
which shows the aliasing caused by the masking (sampling without
compression). We now give the effects of compressing xs(n)xs(n) which is a
simple scaling of ωω. This is the inverse of the stretching results
in (Equation 62).
C
s
(
ω
)
=
1
M
∑
l
=
0
M
-
1
C
(
ω
/
M
-
2
π
l
/
M
)
.
C
s
(
ω
)
=
1
M
∑
l
=
0
M
-
1
C
(
ω
/
M
-
2
π
l
/
M
)
.
(84)
In order to see how the various properties of the DFT can be used,
consider an alternate derivation which uses the IDTFT.
x
(
n
)
=
1
2
π
∫
-
π
π
C
(
ω
)
e
j
ω
n
d
ω
x
(
n
)
=
1
2
π
∫
-
π
π
C
(
ω
)
e
j
ω
n
d
ω
(85)
which for the down–sampled signal becomes
x
(
M
n
)
=
1
2
π
∫
-
π
π
C
(
ω
)
e
j
ω
M
n
d
ω
x
(
M
n
)
=
1
2
π
∫
-
π
π
C
(
ω
)
e
j
ω
M
n
d
ω
(86)
The integral broken into the sum of MM sections using a change of
variables of ω=(ω1+2πl)/Mω=(ω1+2πl)/M giving
x
(
M
n
)
=
1
2
π
∑
l
=
0
M
-
1
∫
-
π
π
C
(
ω
1
/
M
+
2
π
l
/
M
)
e
j
(
ω
1
/
M
+
2
π
l
/
M
)
M
n
d
ω
1
x
(
M
n
)
=
1
2
π
∑
l
=
0
M
-
1
∫
-
π
π
C
(
ω
1
/
M
+
2
π
l
/
M
)
e
j
(
ω
1
/
M
+
2
π
l
/
M
)
M
n
d
ω
1
(87)
which shows the transform to be the same as given in ((Reference)).
Still another approach which uses the shah function can be given by
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
x
s
(
n
)
=
⨿
M
(
n
)
x
(
n
)
(88)
which has as a DTFT
C
s
(
ω
)
=
(
2
π
M
)
⨿
2
π
/
M
(
ω
)
*
C
(
ω
)
C
s
(
ω
)
=
(
2
π
M
)
⨿
2
π
/
M
(
ω
)
*
C
(
ω
)
(89)
=
2
π
M
∑
l
=
0
M
-
1
C
(
ω
+
2
π
l
/
M
)
=
2
π
M
∑
l
=
0
M
-
1
C
(
ω
+
2
π
l
/
M
)
(90)
which after compressing becomes
C
s
=
2
π
M
∑
l
=
0
M
-
1
C
(
ω
/
M
+
2
π
l
/
M
)
C
s
=
2
π
M
∑
l
=
0
M
-
1
C
(
ω
/
M
+
2
π
l
/
M
)
(91)
which is same as ((Reference)).
Now we consider the effects of down–sampling on the z-transform of a
signal.
X
(
z
)
=
∑
n
=
-
∞
∞
x
(
n
)
z
-
n
X
(
z
)
=
∑
n
=
-
∞
∞
x
(
n
)
z
-
n
(92)
Applying this to the sampled signal gives
X
s
(
z
)
=
∑
n
x
(
M
n
)
z
-
M
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
z
-
n
X
s
(
z
)
=
∑
n
x
(
M
n
)
z
-
M
n
=
∑
n
x
(
n
)
⨿
M
(
n
)
z
-
n
(93)
=
∑
n
x
(
n
)
∑
l
=
0
M
-
1
e
j
2
π
n
l
/
M
z
-
n
=
∑
n
x
(
n
)
∑
l
=
0
M
-
1
e
j
2
π
n
l
/
M
z
-
n
(94)
=
∑
l
=
0
M
-
1
∑
n
x
(
n
)
e
j
2
π
l
/
M
z
-
n
=
∑
l
=
0
M
-
1
∑
n
x
(
n
)
e
j
2
π
l
/
M
z
-
n
(95)
=
∑
l
=
0
M
-
1
X
(
e
-
j
2
π
l
/
M
z
)
=
∑
l
=
0
M
-
1
X
(
e
-
j
2
π
l
/
M
z
)
(96)
which becomes after compressing
=
∑
l
=
0
M
-
1
X
(
e
-
j
2
π
l
/
M
z
1
/
M
)
.
=
∑
l
=
0
M
-
1
X
(
e
-
j
2
π
l
/
M
z
1
/
M
)
.
(97)
This concludes our investigations of the effects of down–sampling a
discrete–time signal and we discover much the same aliasing properties as
in sampling a continuous–time signal. We also saw some of the
mathematical steps used in the development.
We will later develop relations of sampling to multirate systems,
periodically time varying systems, and block processing. This should be a
very effective formulation for teaching as well as research on these
topics.
-
Burrus, C. S. and Gopinath, R. A. (1993). Introduction to Wavelets and the Wavelet Transform. [Notes for the IEEE Signal Processing Society's tutorial program held in conjunction with the ICASSP-93 on April 26, 1993]. Minneapolis, MN: ICASSP-93 Tutorial.
-
Burrus, C. Sidney and Gopinath, Ramesh A. and Guo, Haitao. (1998). Introduction to Wavelets and the Wavelet Transform. Upper Saddle River, NJ: Prentice Hall.
-
Bracewell, R. N. (1985). The Fourier Transform and Its Applications. (Third). New York: McGraw-Hill.
-
Crochiere, R. E. and Rabiner, L. R. (1983). Multirate Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
-
Daubechies, Ingrid. (1992). Ten Lectures on Wavelets. [Notes from the 1990 CBMS-NSF Conference on Wavelets and Applications at Lowell, MA]. Philadelphia, PA: SIAM.
-
Gopinath, R. A. and Burrus, C. S. (1992, May). On the Moments of the Scaling Function. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, p. 963–966). ISCAS-92, San Diego, CA
-
Jerri, Abdul J. (1977, November). The Shannon Sampling Theroem — Its Various Extensions and Applications: A Tutorial Review. Proceedings of the IEEE, 65(11), 1565–1596.
-
Kramer, H. P. (1959). A Gereralized Sampling Theorem. J. Math. Phys., 38, 68–72.
-
Linden, D. A. (1959, July). A Discussion of Sampling Theorems. Proceedings of the IRE, 47(7), 1219–1226.
-
Marks II, R. J. (1991). Introduction to Shannon Sampling and Interpolation Theory. New York: Springer-Verlag.
-
Marks II, Robert J. (Ed.). (1993). Advanced Topics in Shannon Sampling and Interpolation Theory. New York: Springer–Verlag.
-
Meyer, Yves. (1993). Wavelets, Algorithms and Applications. [Translated by R. D. Ryan based on lectures given for the Spanish Institute in Madrid in Feb. 1991]. Philadelphia: SIAM.
-
Nyquist, H. (1928). Certain Topics in Telegraph Transmission Theory. AIEE Transactions, 47, 617–644.
-
Papoulis, A. (1962). The Fourier Integral and Its Applications. McGraw-Hill.
-
Papoulis, A. (1977). Generalized Sampling Expansion. IEEE Trans. on Circuits and Systems, 24, 652–654.
-
Papoulis, Athanasios. (1977). Signal Analysis. New York: McGraw-Hill.
-
Shannon, C. E. (1949, January). Communication in the Presence of Noise. Proceedings of the IRE, 37, 10–21.
-
Vaidyanathan, P. P. (1992). Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall.
-
Young, R. M. (1980). An Introduction to Nonharmonic Fourier Series. New York: Academic Press.
