Bài giảng Digital Signal Processing - Chapter 8: DFT/FFT Algorithms - Võ Trung Dũng

re between f1 and f2. How close to f1 could f3 be in order for the 
spectrum of the collected samples to exhibit three distinct peaks? How close to f2 
could f3 be?
Solution: The total number of samples collected is L = fsTL = 10×10 = 100. The 
frequency resolution of the rectangular window is ∆f = fs/L = 10/100 = 0.1 kHz. 
Thus, the closest f3 to f1 and f2 will be:
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DTFT at a Single Frequency: this section’s attention is to the computational 
aspects of the DTFT.
This expression may be computed at any desired value of ω in the Nyquist interval
−π ≤ ω ≤ π
 Advantage of the periodicity: map the conventional symmetric Nyquist
interval −π ≤ ω ≤ π onto the right-sided one 0 ≤ ω ≤ 2π (DFT Nyquist interval)
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DTFT at a Single Frequency: can be thought of as the evaluation of the z-
transform of the sequence x(n) on the unit circle
X(ω) can be computed by evaluating the polynomial X(z) at z = ejω
 Horner’s rule of synthetic division: to evaluate the z-transform X(z)
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 Example with L = 4: Starting with X = 0 at n = L − 1 = 3,
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DTFT routine implementation:
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DTFT over Frequency Range: compute the DTFT over a frequency range, ωa≤ω<ωb, at N frequencies that are equally spaced over this interval
 Bin width:
 Routine: returns the N-dimensional complex-valued array X[k]= X(ωk)
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DTFT Function:
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 DFT: N-point DFT of a length-L signal is defined to be the DTFT evaluated at N 
equally spaced frequencies over the full Nyquist interval, 0 ≤ ω ≤ 2π
 DFT frequencies:
 in radians per sample:
 in Hz:
 N-point DFT: N-point DFT of length-L signal
for k = 0, 1, . . . , N − 1
 Bin width:
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 Routine: The N-dimensional complex DFT array X[k]= X(ωk), k = 0, 1, . . . , N −
1 can be computed by calling the routine dtft over the frequency range [ωa, ωb)= 
[0, 2π)
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 dft vs dtftr: 
 dft: has its N frequencies distributed evenly over the full Nyquist interval, [0, 
2π), 
 dtftr: has them distributed over any desired subinterval. N frequencies in the 
dtftr case are more closely spaced
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 dft with z transform: N computed values X(ωk) can also be thought of as the 
evaluation of the z transform X(z) at the following z-points on the unit circle
Where
 Nth roots of unity: are evenly spaced around the unit circle
DSP-Chapter 8-Dr. Dung Trung Vo
DTFT Computation
 Sample length: two lengths L and N can be specified independently of each 
other
 L is the number of time samples in the data record and can even be infinite; 
 N is the number of frequencies at which we choose to evaluate the DTFT
Most discussions of the DFT assume that L = N
 Zero Padding: If L < N, we can pad N−L zeros at the end of the data record to 
make it of length N. Padding any number of zeros at the end of a signal has no 
effect on its DTFT.
 Wrapping: If L > N, the data record may be reduced to length N by wrapping it 
modulo-N
DSP-Chapter 8-Dr. Dung Trung Vo
Physical versus Computational Resolution
 Physical versus Computational Resolution: if the length L of the signal is not 
large enough to provide sufficient physical resolution, then there is no point 
increasing the length N of the DFT
 Example: The following analog signal consisting of three equal-strength sinusoids 
of frequencies f1 = 2 kHz, f2 = 2.5 kHz, and f3 = 3 kHz
DSP-Chapter 8-Dr. Dung Trung Vo
Matrix Form of DFT
 Linear matrix transformation: transform the L dimensional vector of time data 
into an N-dimensional vector of frequency data
where Xk = X(ωk), k = 0, 1, . . . , N − 1.
 N×L matrix A:
 Component-wise:
DSP-Chapter 8-Dr. Dung Trung Vo
Matrix Form of DFT
 Matrix elements Akn
 Twiddle factor WN:
 Notes: 
 First row (k = 0) and first column (n = 0) of A are always unity
 The matrix A can be built from its second row (k = 1), consisting of the 
successive powers of WN
 Exponents in Wkn N can be reduced modulo-N
DSP-Chapter 8-Dr. Dung Trung Vo
Matrix Form of DFT
 Some examples of twiddle factors:
 2-point DFT matrices:
 4-point DFT matrices: 
DSP-Chapter 8-Dr. Dung Trung Vo
Matrix Form of DFT
 2-point DFTs of a length-2 signal:
 4-point DFTs of a length-4 signal:
DSP-Chapter 8-Dr. Dung Trung Vo
Modulo-N Reduction
 Modulo-N reduction or wrapping: is defined by dividing the signal x into 
contiguous non-overlapping blocks of length N, wrapping the blocks around to be
time-aligned with the first block, and adding them up
 Zero padding: If L is not an integral multiple of N, then the last sub-block will 
have length less than N; in this case, we may pad enough zeros at the end of the 
last block to increase its length to N
DSP-Chapter 8-Dr. Dung Trung Vo
Modulo-N Reduction
 Example: determine the mod-4 and mod-3 reductions of the length-8 signal 
vector:
 For the N = 4 case:
 For the N = 3 case:
where we padded a zero at the end of the third sub-block
DSP-Chapter 8-Dr. Dung Trung Vo
Modulo-N Reduction
 Periodic extension: of the signal x(n) with period N is defined:
DSP-Chapter 8-Dr. Dung Trung Vo
Modulo-N Reduction
 Periodic extension: of the signal x(n) with period N is defined:
 Connection of the mod-N reduction to the DFT: the length-N wrapped signal 
has the same N-point DFT as the original unwrapped signal x
DSP-Chapter 8-Dr. Dung Trung Vo
Modulo-N Reduction
 Example: Compute the 4-point DFT of the length-8 signal of Example 9.5.1 in 
two ways: (a) working with the full unwrapped vector x and (b) computing the DFT 
of its mod-4 reduction.
 Solution: The 4×8 DFT matrix was worked out above. The corresponding DFT is.
The same DFT can be computed by the DFT matrix acting on the wrapped signal,
DSP-Chapter 8-Dr. Dung Trung Vo
Inverse DFT
 Task: recovering the original length-L signal x from its N-point DFT X, that is, 
inverting the relationship
 Issue: When L > N, the matrix A is not invertible. As we saw, there are in this 
case several possible solutions x and having the same mod-N reduction . Among 
these solutions, the only one that is uniquely obtainable from the knowledge of the 
DFT vector X is .
 inverse DFT: corresponding DFT matrix is an N×N square invertible matrix
Or component-wise
DSP-Chapter 8-Dr. Dung Trung Vo
Inverse DFT
 Unitarity property of the DFT matrix:
 Matrix inverse:
 Inverse DFT:
 IDFT as a DFT:
DSP-Chapter 8-Dr. Dung Trung Vo
Discrete Fourier series (DFS)
 Discrete Fourier series (DFS): periodic signal x(n) may be represented by the 
discrete Fourier series (DFS)
 Fourier series coefficients:
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Complexity: if we compute the two (N/2)-DFTs directly, at a cost of (N/2)2 
multiplications each, the total cost of rebuilding the full N-DFT will be:
This amounts to 50 percent savings over computing the N-point DFT directly at a 
cost of N2
if the two (N/2)-DFTs were computed indirectly by rebuilding each of them from 
two (N/4)-DFTs, the total cost for rebuilding an N-DFT would be
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Complexity (cont.): if we start with (N/2m)-point DFTs and perform m 
successive merging steps, the total cost to rebuild the final N-DFT will be:
The first term, N2/2m, corresponds to performing the initial (N/2m)-point DFTs
directly. Because there are 2m of them, they will require a total cost of 
2m(N/2m)2=N2/2m.
If the subdivision process is continued for m = B stages, the final dimension will be 
N/2m = N/2B = 1, which requires no computation at all because the 1-point DFT of a 
1-point signal is itself. In this case, the first term will be absent
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Decimation-in-time radix-2 FFT algorithm: By grouping the even-indexed 
and odd-indexed terms N-point DFT
 Two length-(N/2) subsequences:
 Their (N/2)-point DFTs:
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Relation between twiddle factors WN and WN/2:
 Basic merging result:
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Two groups of N/2 equations:
 Twiddle factor property:
 Butterfly merging equations:
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Typical FFT algorithm:
1. Shuffling the N-dimensional input into N one-dimensional signals.
2. Performing N one-point DFTs.
3. Merging the N one-point DFTs into one N-point DFT.
 Shuffling process: generates the smaller and smaller signals
 Merging process: rebuilds the corresponding DFTs
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Shuffling process: 
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 DFT merging: 
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Bit-reversal process: shuffling process may also be understood as a bit-reversal 
process. If n is represented by three bits {b0, b1, b2}, 
its bit-reversed version is obtained by reversing the order of the bits
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Example: Using the FFT algorithm, compute the 8-point DFT of the following 8-
point signal:
Then, compute the inverse FFT of the result to recover the original time sequence
 Solution: the shuffling stages stop with 2-dimensional signals which are 
transformed into their 2-point DFTs by forming sums and differences
DSP-Chapter 8-Dr. Dung Trung Vo
Fast Fourier transform (FFT)
 Solution: