Digital Signal Processing
Moslem Amiri, Václav Přenosil
Masaryk University
Understanding Digital Signal Processing, Third Edition, Richard Lyons
(0-13-261480-4) © Pearson Education, 2011.
The Discrete Fourier Transform (2)
2
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Zero padding
 A method to improve DFT spectral estimation
 Involves addition of zero-valued data samples to
an original DFT input sequence to increase total
number of input data samples
 Investigating zero-padding technique illustrates
DFT’s property of frequency-domain sampling
 When we sample a continuous time-domain function,
having a CFT, and take DFT of those samples, the
DFT results in a frequency-domain sampled
approximation of the CFT
 The more points in DFT, the better DFT output
approximates CFT
3
DFT Resolution, Zero Padding, Frequency-Domain Sampling
4
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Fig. 3-20
 Because CFT is taken over an infinitely wide time
interval, CFT has continuous resolution
 Suppose we want to use a 16-point DFT to
approximate CFT of f(t) in Fig. 3-20(a)
 16 discrete samples of f(t) are shown on left side of
Fig. 3-21(a)
 Applying those time samples to a 16-point DFT results
in discrete frequency-domain samples, the positive
frequencies of which are represented on right side of
Fig. 3-21(a)
 DFT output comprises samples of Fig. 3-20(b)’s CFT
5
DFT Resolution, Zero Padding, Frequency-Domain Sampling
6
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Fig. 3-21
 If we append 16 zeros to input sequence and
take a 32-point DFT, we get output shown on
right side of (b)
 DFT frequency sampling is increased by a factor of two
 Adding 32 more zeros and taking a 64-point DFT,
we get output shown on right side of (c)
 64-point DFT output shows true shape of CFT
 Adding 64 more zeros and taking a 128-point
DFT, we get output shown on right side of (d)
 DFT frequency-domain sampling characteristic is
obvious now
7
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Fig. 3-21
 Although zero-padded DFT output bin index of
main lobe changes as N increases, zero-padded
DFT output frequency associated with main lobe
remains the same
 If we perform zero padding on L nonzero input
samples to get a total of N time samples for an Npoint
DFT, zero-padded DFT output bin center
frequencies are related to original fs by
N
fm
m s
=binththeoffrequencycenter
8
DFT Resolution, Zero Padding, Frequency-Domain Sampling
Fig. no.
Main lobe peak
located at m = L = N =
Frequency of main
lobe peak relative to fs
3-21(a) 3 16 16 3fs / 16
3-21(b) 6 16 32 6fs / 32 = 3fs / 16
3-21(c) 12 16 64 12fs / 64 = 3fs / 16
3-21(d) 24 16 128 24fs / 128 = 3fs / 16
9
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Zero padding
 DFT magnitude expressions
don’t apply if zero padding is used
 To perform zero padding on L nonzero samples of a
sinusoid whose frequency is located at a bin center to get
a total of N input samples, replace N with L above
 To perform both zero padding and windowing on
input, do not apply window to entire input
including appended zero-valued samples
 Window function must be applied only to original nonzero
time samples; otherwise padded zeros will zero out and
distort part of window function, leading to erroneous
results
NAMNAM ocomplexoreal == and2/
10
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Discrete-time Fourier transform (DTFT)
 DTFT is continuous Fourier transform of an Lpoint
discrete time-domain sequence
 On a computer we can’t perform DTFT because it
has an infinitely fine frequency resolution
 But we can approximate DTFT by performing an Npoint
DFT on an L-point discrete time sequence where
N > L
 Done by zero-padding original time sequence and
taking DFT
11
DFT Resolution, Zero Padding, Frequency-Domain Sampling
 Zero padding
 Zero padding does not improve our ability to
resolve, to distinguish between, two closely
spaced signals in frequency domain
 E.g., main lobes of various spectra in Fig. 3-21 do not
change in width, if measured in Hz, with increased
zero padding
 To improve our true spectral resolution of two
signals, we need more nonzero time samples
 To realize Fres Hz spectral resolution, we must
collect 1/Fres seconds, worth of nonzero time
samples for our DFT processing
12
DFT Processing Gain
 Two types of processing gain associated with
DFTs
 1) DFT’s processing gain
 Using DFT to detect signal energy embedded in noise
 DFT can pull signals out of background noise
 This is due to inherent correlation gain that takes place
in any N-point DFT
 2) integration gain
 Possible when multiple DFT outputs are averaged
13
DFT Processing Gain
 Processing gain of a single DFT
 A DFT output bin can be treated as a bandpass filter
(band center = mfs/N) whose gain can be increased and
whose bandwidth can be reduced by increasing the
value of N
 Maximum possible DFT output magnitude increases as
number of points (N) increases
 Also, as N increases, DFT output bin main lobes
become narrower
 Decreasing a bandpass filter’s bandwidth is useful in
energy detection because frequency resolution
improves in addition to filter’s ability to minimize amount
of background noise that resides within its passband
NAMNAM ocomplexoreal == and2/
14
DFT Processing Gain
15
DFT Processing Gain
 Fig. 3-22
 DFT of a spectral tone (a constant-frequency
sinewave) added to random noise
 Output power levels are normalized so that the
highest bin output power is set to 0 dB
 (a) shows first 32 outputs of a 64-point DFT when
input tone is at center of DFT’s m = 20th bin
 Because tone’s original signal power is below average
noise power level, it is difficult to detect when N = 64
 If we quadruple the number of input samples (N =
256), the tone power is raised above average
background noise power as shown for m = 80 in
(b)
16
DFT Processing Gain
 Signal-to-noise ratio (SNR)
 DFT’s output signal-power level over the average
output noise-power level
 DFT’s output SNR increases as N gets larger
because a DFT bin’s output noise standard
deviation (rms) value is proportional to , and
DFT’s output magnitude for the bin containing
signal tone is proportional to N
 For real inputs, if N > N′, an N-point DFT’s output
SNRN increases over N′-point DFT SNRN′ by:
 If we increase a DFT’s size from N′ to N = 2N′, DFT’s
output SNR increases by 3 dB
N
)'(log10 10' NNSNRSNR NN +=
17
DFT Processing Gain
18
DFT Processing Gain
 Integration gain due to averaging multiple
DFTs
 Theoretically, we could get very large DFT
processing gains by increasing DFT size
 Problem is that the number of necessary DFT
multiplications increases proportionally to N2
 Larger DFTs become very computationally intensive
 Because addition is easier and faster to perform
than multiplication, we can average outputs of
multiple DFTs to obtain further processing gain
and signal detection sensitivity
19
The DFT of Rectangular Functions
 DFT of a rectangular function
 One of the most prevalent and important
computations encountered in DSP
 Seen in sampling theory, window functions,
discussions of convolution, spectral analysis, and
in design of digital filters
)2/sin(
)2/sin(
or,
)sin(
or,
)/sin(
)sin(
DFT functionrect.
x
Nx
x
x
Nx
x
=
20
The DFT of Rectangular Functions
 DFT of a general rectangular function
 A general rectangular function x(n) is defined as
N samples containing K unity-valued samples
21
The DFT of Rectangular Functions
∑
∑
∑
∑
−
=
−
−−−−−
−−−−−−−−−−−−−
−+−−+−−+−−−−
−+−
−=
−
=
−+−
−=
−
+−=
−
=
++++⋅=
++++=
++++=
=
 →
⋅=
=
1
0
)(
)1(210)(
)1()(2)(1)(0)(
))1(()2()1()(
)1(
/2
)1(
/2
2/
1)2/(
/2
)(
]...[
...
...
)(
1
)()(
K
p
qpjnjq
Kjqqjqjqjnjq
Kjqnjqqjnjqqjnjqqjnjq
Knjqnjqnjqnjq
Kn
nn
nqj
Nmq
Kn
nn
Nmnj
N
Nn
Nmnj
eeqX
eeeee
eeeeeeee
eeee
eqX
e
enxmX
o
o
oooo
oooo
o
o
o
o
π
π
π
22
The DFT of Rectangular Functions
)2/sin(
)2/sin(
)2/sin(2
)2/sin(2
)(
)(
)(
)(
1
1
)(
2/)1(
1
0
2/)1(2/)()sin(
:equationsEuler'
2/2/
2/2/
2/)1(
2/2/2/
2/2/2/
1
0
seriesgeometric
1
0
)(
q
qK
ee
qj
qKj
e
ee
ee
e
eee
eee
e
e
e
eeqX
Kjq
K
p
jpq
Kjqjee
jqjq
jqKjqK
Kjq
jqjqjq
jqKjqKjqK
jq
jqKK
p
jpq
K
p
jpqnjq
jj
o
⋅=
⋅= →
−
−
⋅=
−
−
=
−
−
=
=
−−
−
=
−
−−−=
−
−
−−
−−
−−
−
−−
=
−
−
=
−
∑
∑
∑
− φφ
φ

23
The DFT of Rectangular Functions
)/sin(
)/sin(
)(
)2/2sin(
)2/2sin(
)(
)2/sin(
)2/sin(
)2/sin(
)2/sin(
)(
)2/)1()(/2(kernelDirichlet
theofformGeneral
)2/)1()(/2(/2
)2/)1((
2/)1()()2/sin(
)2/sin(
1
0
)(
2/)1(
1
0
Nm
NmK
emX
Nm
NmK
emX
q
qK
e
q
qK
ee
eeqX
KnNmj
KnNmjNmq
Knjq
Kjqnjqq
qK
ee
K
p
jpqnjq
o
o
o
o
Kjq
K
p
jpq
o
π
π
π
π
π
ππ
⋅= →
⋅= →
⋅=
⋅⋅= →
=
−−
−−=
−−
−−
⋅=∑
−
=
−
−−
−
=
−
∑
24
The DFT of Rectangular Functions
25
The DFT of Rectangular Functions
 Dirichlet kernel (DFT of rectangular function)
 Has a main lobe, centered about m = 0 point
 Peak amplitude of main lobe is K
 X(0) = sum of K unity-valued samples = K
 Main lobe’s width = 2N/K
 Thus main lobe width is inversely proportional to K
 A fundamental characteristic of Fourier transforms: the
narrower the function in one domain, the wider its
transform will be in the other domain
K
N
K
N
m
Nm
NmK
emX KnNmj o
==
⋅=
=
−−
π
π
π
π
π
π
crossingzerofirst
)2/)1()(/2(
)/sin(
)/sin(
)(

26
The DFT of Rectangular Functions
27
The DFT of Rectangular Functions
 Fig. 3-26
 64-point DFT of 64-sample rectangular function,
with 11 unity values (N = 64 and K = 11)
 It’s easier to comprehend the true spectral nature
of X(m) by viewing its absolute magnitude
 Provided in Fig. 3-27(a)
 Fig. 3-27(a)
 The main and sidelobes are clearly evident now
 K = 11  peak value of main lobe = 11
 Width of main lobe = N/K = 64/11 = 5.82
28
The DFT of Rectangular Functions
29
The DFT of Rectangular Functions
 DFT of a symmetrical rectangular function
)/sin(
)/sin(
)(
)/sin(
)/sin(
)/sin(
)/sin(
)(
)/sin(
)/sin(
)(
kernelDirichlet
theofformlSymmetrica
)0)(/2(
)2/)1(2/)1)((/2(2/)1(
)2/)1()(/2(
Nm
NmK
mX
Nm
NmK
e
Nm
NmK
emX
Nm
NmK
emX
Nmj
KKNmjKn
KnNmj
o
o
π
π
π
π
π
π
π
π
π
π
π
= →
⋅=
⋅= →
⋅=
−−−−=
−−
30
The DFT of Rectangular Functions
 DFT of a symmetrical rectangular function
 This DFT is itself a real function
 So it contains no imaginary part or phase term
 If x(n) is real and even, x(n) = x(−n), then Xreal(m) is
nonzero and Ximag(m) is always zero
)/sin(
)/sin(
)(
Nm
NmK
mX
π
π
=
31
The DFT of Rectangular Functions
32
The DFT of Rectangular Functions
 Fig. 3-29 (64-point DFT)
 Xreal(m) is nonzero and Ximag(m) is zero
 Identical magnitudes in Figs. 3-27(a) and 3-29(d)
 Shifting K unity-valued samples to center merely
affects phase angle of X(m), not its magnitude (shifting
theorem of DFT)
 Even though Ximag(m) is zero in (c), phase angle
of X(m) is not always zero
 X(m)’s phase angles in (e) are either +π, zero, or −π
 ejπ = ej(−π) = −1 we could easily reconstruct Xreal(m)
from |X(m)| and phase angle Xø(m) if we must
 Xreal(m) is equal to |X(m)| with the signs of |X(m)|’s
alternate sidelobes reversed
33
The DFT of Rectangular Functions
34
The DFT of Rectangular Functions
 Fig. 3-30
 Another example of how DFT of a rectangular
function is a sampled version of Dirichlet kernel
 A 64-point x(n) where 31 unity-valued samples
are centered about n = 0 index location
 By broadening x(n), i.e., increasing K, we’ve
narrowed Dirichlet kernel of X(m)
 Peak value of |X(m)| = K = 31
31
64
crossingzerofirst ==
K
N
m
35
The DFT of Rectangular Functions
 DFT of an all-ones rectangular function
)/sin(
)sin(
)(
)/sin(
)sin(
)/sin(
)/sin(
)(
)/sin(
)/sin(
)(
1)(TypekernelDirichlet
theofformones-All
)0)(/2(
)2/)1(2/)1)((/2(2/)1(
and
)2/)1()(/2(
Nm
m
mX
Nm
m
e
Nm
NmN
emX
Nm
NmK
emX
Nmj
NNNmjNn
NK
KnNmj
o
o
π
π
π
π
π
π
π
π
π
π
π
= →
⋅=
⋅= →
⋅=
−−−−=
=
−−
36
The DFT of Rectangular Functions
37
The DFT of Rectangular Functions
 Fig. 3-32
 Dirichlet kernel of X(m) in (b) is as narrow as it
can get
 Main lobe’s first positive zero crossing occurs at
m = 64/64 = 1 sample in (b)
 Peak value of |X(m)| = N = 64
 x(n) is all ones  |X(m)| is zero for all m ≠ 0
 The sinc function
 Defines overall DFT frequency response to an input
sinusoidal sequence
 Is also amplitude response of a single DFT bin
)/sin(
)sin(
)(1)(TypekernelDirichlet
theofformones-All
Nm
m
mX
π
π
= →
38
The DFT of Rectangular Functions
 DFT of an all-ones rectangular function
m
m
mX
m
m
N
Nm
m
mX
Nm
m
mX
π
π
π
π
π
π
π
π
ααα
)sin(
)(
)sin(
/
)sin(
)(
)/sin(
)sin(
)(
d)(normalize
3)(TypekernelDirichlet
theofformones-All
large)isN(when
2)(TypekernelDirichlet
theofformones-All
)sin(smallis
1)(TypekernelDirichlet
theofformones-All
≈ →
⋅=≈ →
= →
≈→

39
The DFT of Rectangular Functions
40
The DFT of Rectangular Functions
DFT frequency
axis
representation
Frequency
variable
Resolution of
X(m)
Repetition
interval of
X(m)
Frequency
axis range
Frequency in Hz f fs/N fs -fs/2 to fs/2
Frequency in
cycles/sample
f/fs 1/N 1 -1/2 to 1/2
Frequency in
radians/sample
ω 2π/N 2π -π to π
41
The DFT of Rectangular Functions
 Alternate form of DFT of an all-ones
rectangular function
 Using radians/sample frequency notation for DFT
axis leads to another prevalent form of DFT of allones
rectangular function
 Letting normalized discrete frequency axis
variable be ω = 2πm/N, then πm = Nω/2
)2/sin(
)2/sin(
)(
)/sin(
)sin(
)(
4)(TypekernelDirichlet
theofformones-All
1)(TypekernelDirichlet
theofformones-All
ω
ω
ω
π
π
N
X
Nm
m
mX
= →
= →
42
Interpreting DFT Using DTFT
43
Interpreting DFT Using DTFT
 Fig. 3-35
 (a) shows an infinite-length continuous-time
signal containing a single finite-width pulse
 Magnitude of its continuous Fourier transform (CFT) is
continuous frequency-domain function X1(ω)
 continuous frequency variable ω is radians per second
 If CFT is performed on infinite-length signal of
periodic pulses in (b), result is line spectra known
as Fourier series X2(ω)
 X2(ω) Fourier series is a sampled version of
continuous spectrum in (a)
44
Interpreting DFT Using DTFT
 Fig. 3-35
 (c) shows infinite-length discrete time sequence
x(n), containing several nonzero samples
 We can perform a CFT of x(n) describing its spectrum
as a continuous frequency-domain function X3(ω)
 This continuous spectrum is called a discrete-time
Fourier transform (DTFT) defined by
 ω frequency variable is measured in radians/sample
∑
∞
−∞=
−
=
n
nj
enxX ω
ω )()(
45
Interpreting DFT Using DTFT
 DTFT example
 Time sequence: xo(n) = (0.75)n for n ≥ 0
 Its DTFT is
 Xo(ω) is continuous and periodic with a period of
2π, whose magnitude is shown in Fig. 3-36
75.075.01
1
)(
)75.0(75.0)(
)()(
seriesgeometric
00
−
=
−
= →
==
=
−
∞
=
−
∞
=
−
∞
−∞=
−
∑∑
∑
ω
ω
ω
ωω
ω
ω
ω
ω
j
j
jo
n
nj
n
njn
o
n
nj
e
e
e
X
eeX
enxX
46
Interpreting DFT Using DTFT
 Verification of 2π periodicity of DTFT
)()(
)()()2(
1
2)2(
ω
πω
ω
πωπω
Xenx
eenxenxkX
n
nj
nkj
n
nj
n
nkj
==
==+
∑
∑∑
∞
−∞=
−
=
−
∞
−∞=
−
∞
−∞=
+−

47
Interpreting DFT Using DTFT
48
Interpreting DFT Using DTFT
 Fig. 3-35 (cont.)
 Transforms indicated in Figs. (a) through (c) are
pencil-and-paper mathematics of calculus
 In a computer, using only finite-length discrete
sequences, we can only approximate CFT (the
DTFT) of infinite-length x(n) time sequence in (c)
 That approximation is DFT, and it’s the only Fourier
transform tool available
 Taking DFT of x1(n), where x1(n) is a finite-length
portion of x(n), we obtain discrete periodic X1(m) in (d)
 X1(m) is a sampled version of X3(ω)
∑
−
=
−
= ==
1
0
/2
1/231 )(|)()(
N
n
Nmnj
Nm enxXmX π
πωω
49
Interpreting DFT Using DTFT
 Fig. 3-35
 X1(m) is also exactly equal to CFT of periodic
time sequence x2(n) in (d)
 The DFT is equal to the continuous Fourier
transform (the DTFT) of a periodic time-domain
discrete sequence
 If a function is periodic, its forward/inverse DTFT
will be discrete; if a function is discrete, its
forward/inverse DTFT will be periodic