1.6 The fft algorithm

FFT

(Fast Fourier Transform) An efficient computational algorithm for computing the DFT .

The fast fourier transform fft

DFT can be expensive to compute directly $$\forall k, 0\le k\le N-1\colon X(k)=\sum_{n=0}^{N-1} x(n)e^{-(i\times 2\pi \frac{k}{N}n)}$$

For each $k$ , we must execute:

• $N$ complex multiplies
• $N-1$ complex adds

• $N^2$ complex multiplies
• $N(N-1)$ complex adds

This " $O(N^2)$ " computation rapidly gets out of hand, as $N$ gets large:

The FFT provides us with a much more efficient way of computing the DFT. The FFT requires only " $O(N\lg N)$ " computations to compute the $N$ -point DFT.

How long is $10^{12}\sec$ ? More than 10 days! How long is $6E6\sec$ ?

The FFT and digital computers revolutionized DSP (1960 - 1980).

How does the fft work?

• The FFT exploits the symmetries of the complex exponentials $W_N^{(kn)}=e^{-(i\frac{2\pi }{N}kn)}$
• $W_N^{(kn)}$ are called " twiddle factors "

Complex conjugate symmetry

$$W_N^{(k(N-n))}=W_N^{-(kn)}=\overline{W_N^{(kn)}}$$ $$e^{-(i\times 2\pi \frac{k}{N}(N-n))}=e^{i\times 2\pi \frac{k}{N}n}=\overline{e^{-(i\times 2\pi \frac{k}{N}n)}}$$

Periodicity in n and k

$$W_N^{(kn)}=W_N^{(k(N+n))}=W_N^{((k+N)n)}$$ $$e^{-(i\frac{2\pi }{N}kn)}=e^{-(i\frac{2\pi }{N}k(N+n))}=e^{-(i\frac{2\pi }{N}(k+N)n)}$$ $$W_N=e^{-(i\frac{2\pi }{N})}$$

Decimation in time fft

• Just one of many different FFT algorithms
• The idea is to build a DFT out of smaller and smaller DFTs by decomposing $x(n)$ into smaller and smaller subsequences.
• Assume $N=2^m$ (a power of 2)

Derivation

$N$ is even , so we can complete $X(k)$ by separating $x(n)$ into two subsequences each of length $\frac{N}{2}$ . $$x(n)\to \begin{cases}\frac{N}{2} & \text{if $n=\mathrm{even}$}\\ \frac{N}{2} & \text{if $n=\mathrm{odd}$}\end{cases}$$ $$\forall k, 0\le k\le N-1\colon X(k)=\sum_{n=0}^{N-1} x(n)W_N^{(kn)}$$ $$X(k)=\sum_{n=2r} x(n)W_N^{(kn)}+\sum_{n=2r+1} x(n)W_N^{(kn)}$$ where $0\le r\le \frac{N}{2}-1$ . So

Why would we want to do this? Because it is more efficient!

So why stop here?! Keep decomposing. Break each of the $\frac{N}{2}$ -point DFTs into two $\frac{N}{4}$ -point DFTs, etc. , ....

We can keep decomposing: $$\frac{N}{2^1}=\{\frac{N}{2}, \frac{N}{4}, \frac{N}{8}, , \frac{N}{2^{(m-1)}}, \frac{N}{2^m}\}=1$$ where $$m=\log_{2}N=\text{times}$$

Computational cost: $N$ -pt DFTtwo $\frac{N}{2}$ -pt DFTs. The cost is $N^2\to 2\left(\frac{N}{2}\right)^2+N$ . So replacing each $\frac{N}{2}$ -pt DFT with two $\frac{N}{4}$ -pt DFTs will reduce cost to $$2(2\left(\frac{N}{4}\right)^2+\frac{N}{2})+N=4\left(\frac{N}{4}\right)^2+2N=\frac{N^2}{2^2}+2N=\frac{N^2}{2^p}+pN$$ As we keep going $p=\{3, 4, , m\}$ , where $m=\log_{2}N$ . We get the cost $$\frac{N^2}{2^{\log_{2}N}}+N\log_{2}N=\frac{N^2}{N}+N\log_{2}N=N+N\log_{2}N$$ $N+N\log_{2}N$ is the total number of complex adds and mults.

For large $N$ , $\mathrm{cost}\approx N\log_{2}N$ or " $O(N\log_{2}N)$ ", since $(N\log_{2}N, N)$ for large $N$ .