1.5 Fast convolution using the fft

Important application of the fft

• Zero-pad these two sequences to length $2N-1$ , take DFTs using the FFT algorithm $$x(n)\to X(k)$$ $$h(n)\to H(k)$$ The cost is $$O((2N-1)\lg (2N-1))=O(N\lg N)$$
• Multiply DFTs $$X(k)H(k)$$ The cost is $$O(2N-1)=O(N)$$
• Inverse DFT using FFT $$X(k)H(k)\to y(n)$$ The cost is $$O((2N-1)\lg (2N-1))=O(N\lg N)$$

So the total cost for direct convolution of two $N$ -point sequences is $O(N^2)$ . Total cost for convolution using FFT algorithm is $O(N\lg N)$ . That is a huge savings ( ).

Summary of dft

• $x(n)$ is an $N$ -point signal ( ).

• $$X(k)=\sum_{n=0}^{N-1} x(n)e^{-(i\frac{2\pi }{N}kn)}=\sum_{n=0}^{N-1} x(n)W_N^{(kn)}$$ where $W_N=e^{-(i\frac{2\pi }{N})}$ is a "twiddle factor" and the first part is the basic DFT.

What is the dft

$$X(k)=X(F=\frac{k}{N})=\sum_{n=0}^{N-1} x(n)e^{-(i\times 2\pi Fn)}$$ where $X(F=\frac{k}{N})$ is the DTFT of $x(n)$ and $\sum_{n=0}^{N-1} x(n)e^{-(i\times 2\pi Fn)}$ is the DTFT of $x(n)$ at digital frequency $F$ . This is a sample of the DTFT. We can do frequency domain analysis on a computer!

Inverse dft (idft)

$$x(n)=\frac{1}{N}\sum_{n=0}^{N-1} X(k)e^{i\frac{2\pi }{N}kn}$$

• Build $x(n)$ using Simple complex sinusoidal building block signals
• Amplitude of each complex sinusoidal building block in $x(n)$ is $\frac{1}{N}X(k)$

Circular convolution

Regular convolution from circular convolution

• Zero pad $x(n)$ and $h(n)$ to $\mathrm{length}=\mathrm{length}(x)+\mathrm{length}(h)-1$
• Zero padding increases frequency resolution in DFT domain ( )

The fast fourier transform (fft)

• Efficient computational algorithm for calculating the DFT
• "Divide and conquer"
• Break signal into even and odd samples keep taking shorter and shorter DFTs, then build $N$ -pt DFT by cleverly combining shorter DFTs
• $N$ -pt DFT: $O(N^2)\searrow O(N\log_{2}N)$

Fast convolution

• Use FFT's to compute circular convolution of zero-padded signals
• Much faster than regular convolution if signal lengths are long
• $O(N^2)\searrow O(N\log_{2}N)$

See .