##ThinkDSP
This notebook contains solutions to exercises in Chapter 7: Discrete Fourier Transform
Copyright 2015 Allen Downey
Exercise: In this chapter, I showed how we can express the DFT and inverse DFT as matrix multiplications. These operations take time proportional to , where is the length of the wave array. That is fast enough for many applications, but there is a faster algorithm, the Fast Fourier Transform (FFT), which takes time proportional to .
The key to the FFT is the Danielson-Lanczos lemma:
Where is the th element of the DFT of ; is a wave array containing the even elements of , and contains the odd elements of .
This lemma suggests a recursive algorithm for the DFT:
Given a wave array, , split it into its even elements, , and its odd elements, .
Compute the DFT of and by making recursive calls.
Compute for each value of using the Danielson-Lanczos lemma.
For the base case of this recursion, you could wait until the length of is 1. In that case, . Or if the length of is sufficiently small, you could compute its DFT by matrix multiplication, possibly using a precomputed matrix.
Hint: I suggest you implement this algorithm incrementally by starting with a version that is not truly recursive. In Step 2, instead of making a recursive call, use dft
or np.fft.fft
. Get Step 3 working, and confirm that the results are consistent with the other implementations. Then add a base case and confirm that it works. Finally, replace Step 2 with recursive calls.
One more hint: Remember that the DFT is periodic; you might find np.tile
useful.
You can read more about the FFT at https://en.wikipedia.org/wiki/Fast_Fourier_transform.
As the test case, I'll start with a small real signal and compute its FFT:
Here's my implementation of DFT from the book:
We can confirm that this implementation gets the same result.
As a step toward making a recursive FFT, I'll start with a version that splits the input array and uses np.fft.fft to compute the FFT of the halves.
And we get the same results:
Finally, we can replace np.fft.fft
with recursive calls, and add a base case:
And we get the same results:
This implementation of FFT takes time proportional to . It also takes space proportional to , and it wastes some time making and copying arrays. It can be improved to run "in place"; in that case, it requires no additional space, and spends less time on overhead.