DISCRETE FOURIER TRANSFORM
AND SIGNAL SPECTRUM
BAU
Discrete Fourier Transform
2
In time domain,
representation of
digital signals
describes the signal
amplitude versus the
sampling time
instant or the sample
number
The representation
of the digital signal
in terms of its
frequency
component in a
frequency domain is 1,000-Hz sinusoid with 32 samples
very useful at a sampling rate of 8,000 Hz
Fourier Series Coefficients of Periodic
Digital Signals
3
we want to estimate the spectrum of a periodic digital
signal x(n)
sampled at a rate of fs Hz
fundamental period T0 = N.T where T=1/ fs
we assume that the periodic digital signal is band limited
such that all harmonic frequencies are less than the folding
frequency fs/2 so that aliasing does not occur
Fourier Series Coefficients of Periodic
Digital Signals
4
The coefficients of the Fourier series expansion of the
periodic signal x(n) in a complex form are:
The Fourier series coefficient ck is periodic of N:
Fourier Series Coefficients of Periodic
Digital Signals
5
Only the line spectral portion between the frequency -fs/2 and
frequency fs/2 (folding frequency) represents frequency information
of the periodic signal
Fourier Series Coefficients of Periodic
Digital Signals
6
The spectral portion from fs/2 to fs is a copy of the
spectrum in the negative frequency range from -fs/2 to
0 Hz
For convenience, we compute the spectrum over the
range from 0 to fs Hz with nonnegative indices
For the kth harmonic, the frequency is
f0 = 1/T0 is the fundamental frequency in Hz
EXAMPLE
7
Solution
8
Solution
9
Solution
10
Discrete Fourier Transform Formulas
11
We assume that a periodic signal x(n) is obtained by
copying the acquired N data samples with the duration
of T to itself repetitively.
x(n) ----- DFT -----> X(k)
X(k) constitutes the DFT coefficients
Notice that the factor of N is a constant and does not
affect the relative magnitudes of the DFT coefficients
X(k)
Development of DFT formula
12
DFT definition
13
Given a sequence x(n), 0 ≤ n ≤ N-1
Where WN is defined as (twiddle factor)
Inverse DFT
14
The inverse DFT is given by
the expansion is:
Matlab FFT functions
15
Example
16
Solution
17
18
19
DFT definition
20
Given a sequence x(n), 0 ≤ n ≤ N-1
The inverse DFT is given by
Frequency components
21
The calculated N DFT coefficients X(k) represent the frequency
components ranging from 0 Hz (or radians/second) to fs Hz (or ωs
radians/second)
Frequency resolution: the frequency step between two consecutive
DFT coefficients to measure how fine the frequency domain
presentation is
Example
22
Solution
23
Amplitude Spectrum and Power
Spectrum
24
One of the DFT applications is transformation of a finite-length
digital signal x(n) into the spectrum in frequency domain
Amplitude Spectrum and Power
Spectrum
25
we achieve the digital sequence x(n) by sampling the analog signal
x(t)
Truncating the sampled signal with a data window with a length T0
= NT
we get
we apply the DFT to the obtained sequence
each calculated DFT coefficient is a complex number, We define the
amplitude spectrum as:
Amplitude Spectrum and Power
Spectrum
26
We can modify the amplitude spectrum to a one-sided amplitude
spectrum by doubling the amplitudes, keeping the original DC term
at k = 0.
the phase spectrum is given by
Amplitude Spectrum and Power
Spectrum
27
The DFT power spectrum is defined as:
Similarly, for a one-sided power spectrum, we get:
Example
28
Consider the sequence
Solution
29
Solution
30
Solution
31
The one-sided amplitude spectrum and one-sided power spectrum
Example
32
Zero padding effect by using FFT
33
Spectral Estimation Using Window
Functions
34
When we apply DFT to the sampled data, we
theoretically imply the following assumptions:
the sampled data are periodic to themselves (repeat
themselves)
the sampled data are continuous to themselves and band
limited to the folding frequency
Spectral Estimation Using Window
Functions
35
Consider the pure 1-Hz sine wave with 32 samples
Spectral Estimation Using Window
Functions
36
if we use a window size of N = 16 samples, which is a
multiple of the two waveform cycles, the second window
repeats with continuity.
when the window size is chosen to be 18 samples, which
is not a multiple of the waveform cycles (2.25 cycles), the
second window repeats the first window with
discontinuity
Spectral Estimation Using Window
Functions
37
The first spectral plot contains a single frequency, while the second
spectrum has the expected frequency component plus many
harmonics: spectral leakage
Spectral Estimation Using Window
Functions
38
The amount of spectral leakage shown in the second
plot is due to amplitude discontinuity in time domain
The bigger the discontinuity, the more the leakage.
To reduce the effect of spectral leakage, a window
function can be used whose amplitude tapers smoothly
and gradually toward zero at both ends
Applying the window function w(n) to a data sequence
x(n) to obtain a windowed sequence xw(n)
Spectral Estimation Using Window
Functions
39
Common window functions
40
The common window functions are listed as follows:
Plots of window sequences.
41
Spectral Estimation Using Window
Functions
42
Fast Fourier Transform
43
The DFT coefficients may be computed via a fast Fourier
transform (FFT) algorithm
The FFT is a very efficient algorithm for computing
DFT coefficients
The FFT algorithm requires the time domain sequence
x(n) to have a length of data points equal to a power of
2;
For example, the number of samples in x(n) can be N =
2, 4, 8, 16, etc.
Fast Fourier Transform
44
In the case of using the FFT algorithm to compute DFT
coefficients, where the length of the available data is not
equal to a power of 2 we can pad the data sequence
with zeros to create a new sequence
The modified data sequence for applying FFT, therefore,
is:
Fast Fourier Transform
45
we consider the digital sequence x(n) consisting of 2m
samples
If x(n) does not contain 2m samples, then we simply
append it with zeros
radix-2 FFT algorithms:
Decimation in-frequency algorithm
decimation-in-time algorithm
Method of Decimation-in-Frequency
46
Using the definition of DFT:
The equation can be expanded as:
Method of Decimation-in-Frequency
47
we can rewrite as a sum of the following two parts:
Modifying the second term:
Method of Decimation-in-Frequency
48
Now letting k = 2m as an even number achieves
while substituting k = 2m + 1 as an odd number yields
Method of Decimation-in-Frequency
49
where a(n) and b(n) are introduced and expressed as
We can summarize by:
Method of Decimation-in-Frequency
50
First
Iteration
Method of Decimation-in-Frequency
51
Second
Iteration
Block
Diagram
of 8-point
FFT
Method of Decimation-in-Frequency
52
the number of complex multiplications for DFT and FFT,
respectively, are determined by
In the 8-point FFT, there are 12 complex multiplications
compared with the eight-point DFT with 64 complex
multiplications
a sequence with 1,024 data points. Applying DFT will
require 1,024 x 1,024=1,048,576 complex multiplications
applying FFT will need only (1,024/2) x log2 (1,024) = 5,120
complex multiplications
Method of Decimation-in-Frequency
53
Next, the index (bin number) of the eight-point DFT
coefficient X(k) becomes 0, 4, 2, 6, 1, 5, 3, and 7,
respectively, which are not in the natural order.
Method of Decimation-in-Frequency
54
Example 4.12
55
Solution
56
Example 4.13
57
Method of Decimation-in-Time
58
In this method, we split the input sequence x(n) into the
even indexed x(2m) and x(2m+1), each with N data
points
Method of Decimation-in-Time
59
Define new functions as
Note that
Method of Decimation-in-Time
60
We can write:
Considering that:
the second half of frequency bins can be computed as
follows:
Method of Decimation-in-Time
61
Method of Decimation-in-Time
62
Method of Decimation-in-Time
63
Example 4.14
64
Example 4.15.
65
