DSP First, 2/e
Lecture 17
DFT: Discrete Fourier Transform
LECTURE OBJECTIVES
§ Discrete Fourier Transform
§ DFT from DTFT by
frequency sampling
§ DFT computation (FFT)
§ DFT pairs and properties
§ Periodicity in DFT (time & frequency)
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 4
READING ASSIGNMENTS
§ This Lecture:
§ Chapter 8, Sections 8-1, 8-2 and 8-4
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 3
Sample the DTFT à DFT
§ Want computable Fourier transform § Finite signal length (L)
§ Finite number of frequencies
k is the frequency index
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 5
Want a Computable INVERSE Fourier Transform
§ Write the inverse DTFT as a finite Riemann sum:
§ Note that § Propose:
§ This is the inverse Discrete Fourier Transform (IDFT)
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 6
Orthogonality of Complex Exponentials
The sequence set:
because ,
and
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 8
Inverse DFT when L=N (proof)
§ Complex exponentials are ORTHOGONAL
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 7
4-pt DFT: Numerical Example
§ Take the 4-pt DFT of the following signal
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 9
N-pt DFT: Numerical Example
§ Take the N-pt DFT of the impulse
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 10
Matrix Form for N-pt DFT
§ In MATLAB, NxN DFT matrix is dftmtx(N)
• Obtain DFT by X = dftmtx(N)*x
• Or, more efficiently by X = fft(x,N) • Fast Fourier transform (FFT) algorithm later
DFT matrix
Signal vector
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 12
4-pt iDFT: Numerical Example
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 11
FFT: Fast Fourier Transform
§ FFT is an algorithm for computing the DFT
§ N log2N versus N2 operations
§ Count multiplications (and additions)
§ For example, when N = 1024 = 210
§ ≈10,000 ops vs. ≈1,000,000 operations § ≈1000 times faster
§ What about N=256, how much faster?
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 13
Zero-Padding gives denser FREQUENCY SAMPLING
§ Want many samples of DTFT § WHY? to make a smooth plot
§ Finite signal length (L)
§ Finite number of frequencies (N) § Thus, we need
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 14
DFT periodic in k (frequency domain)
§ Since DTFT is periodic in frequency, the DFT must also be periodic in k
§ What about Negative indices and Conjugate Symmetry?
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 16
Zero-Padding with the FFT
§ Get many samples of DTFT
§ Finite signal length (L)
§ Finite number of frequencies (N) § Thus, we need
In MATLAB
• Use X = fft(x,N)
• With L=length(x) less than N
• Define xpadtoN = [x,zeros(1,N-L)];
• Take the N-pt DFT of xpadtoN
Aug 2016
© 2003-2016, JH McClellan & RW Schafer 15
DFT Periodicity in Frequency Index
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 17
DFT pairs & properties
§ Recall DTFT pairs because DFT is sampled DTFT § See next two slides
§ DFT acts on a finite-length signal, so we can use DTFT pairs & properties for finite signals
§ Want DFT properties related to computation
§ And, we will concentrate on one more pair:
§ DTFT and DFT of finite sinusoid (or cexp) § Length-L signal
§ N-pt DFT
Aug 2016
© 2003-2016, JH McClellan & RW Schafer 18
Summary of DTFT Pairs
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 20
These 3 signals have infinite length
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 19
These 3 properties involve circular indexing
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 21
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 22
Delay Property of DFT
§ Recall DTFT property for time shifting:
§ Expected DFT property via frequency sampling
§ Indices such as must be evaluated modulo-N because
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 25
Convolution Property not the same
§ Almost true for DFT:
§ Convolution maps to multiplication of transforms
§ Need a different kind of convolution § CIRCULAR CONVOLUTION
§ Likewise, for Time-Shifting
§ Has to be circular
§ Because the “n” domain is also periodic
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 24
DTFT of a Length-L Pulse
§ Know DTFT of finite rectangular pulse § Dirichlet form and a linear phase term
§ Use frequency-sampling to get DFT
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 26
DTFT of a Finite Length Complex Exponential (1)
§ Know DTFT of finite rectangular pulse § Dirichlet form and a linear phase term
§ Use frequency-shift property
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 27
20-pt DFT of Complex Exponential
Aug 2016 29
© 2003-2016, JH McClellan & RW Schafer
DTFT of a Finite Length Complex Exponential (2)
§ Know DTFT, so we can sample in frequency
§ Thus, the N-point DFT is
Dirichlet Function
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 28
20-pt DFT of Complex Exp: “on the grid”
Aug 2016 30
© 2003-2016, JH McClellan & RW Schafer
50-pt DFT of Sinusoid: zero padding
?
Aug 2016 © 2003-2016, JH McClellan & RW Schafer
31
50-pt DFT of Sinusoid: zero padding
Zero-crossings of Dirichlet ? Width of Dirichlet ?
Density of frequency samples?
?
Thus we have a simple BPF
Aug 2016 © 2003-2016, JH McClellan & RW Schafer
33
Frequency shifting up and down is done by cosine multiplication in the time domain
BPF is frequency shifted version of LPF (below)
RECALL: BandPass Filter (BPF)
Aug 2016 © 2003-2016, JH McClellan & RW Schafer 32