Fast Fourier Transform

Review all the signal processing topics from part IB.

The key idea of the Fast Fourier Transform (FFT) is divide and conquer

• The Discrete Fourier Transform (DFT) can be represented as a matrix multiplication

• Sum the odd and even terms separately, i.e. the problem of size $N$ is divided into $$ \begin{aligned} x(k) &= \sum_0^{N-1} x_n e^{2\pi i k n/N}\\ x(k) &= \sum_0^{N/2-1} x_{2n} e^{2\pi i k 2n/N}+ \sum_0^{N/2-1} x_{2n+1} e^{2\pi i k (2n+1)/N}\\ x(k) &= \sum_0^{N/2-1} x_{2n} e^{2\pi i k n/(N /2)}+ e^{2\pi i k /N}\sum_0^{N/2-1} x_{2n+1} e^{2\pi i k n/(N/2)}\\ x(k) &= x_\text{even} (k)+ e^{2\pi i k /N}x_\text{odd}(k)\end{aligned} $$

  Notice that the discrete $x_\text{even}$ and $x_\text{odd}$ are respectively periodic over $\frac{N}{2}$. The problem of size $N$ has been reduced to $$ S(N) = 2 \times S\left(\frac N 2\right) +1$$ where $S$ is the cost function. Explicitly, $$ S(N) \propto O\left(N \log(N)\right) $$

Using $2^N$ for array size is important.

import numpy as np
import matplotlib.pyplot as plt

dt = 0.01
fftsize = 256
t=np.arange(fftsize)*dt

y = np.cos(2*np.pi*12*t) + 0.5* np.sin(2*np.pi*34*t)

plt.plot(t,y)

Y = np.fft.fft(y)

plt.subplot(2,1,1); plt.plot(np.abs(Y))

f = np.fft.fftfreq(fftsize,dt) # get the array of frequencies that correspond to elements of Y
plt.subplot(2,1,2); plt.plot(f, np.abs(Y)) # this creates flop-back lines

Y2 = np.fft.fftshift(Y) # rolls the array from + -> - to increasingly positive
f2 = np.fft.fftshift(f)

plt.subplot(f2, Y2) # no flop-back