The purpose of this week is to understand how to compute convolution using the discrete fourier transform (DFT).

1. DFT-Based Processing

The advantage of DFT-based processing over simple convolution between filters is that the FFT makes DFT computation much more efficient than convolution. However, you must be careful about time-domain aliasing.

1.1. Time-Domain Aliasing

Let’s assume you have a signal $x$ of length $L$ and you want to pass it through a digital filter $h$ of length $M$. The result will be a signal $y$ of length $L+M-1$.

Let $M < L < N < L+M-1$.

You may think $Y_N(k)=X_N(k)H_N(k)$ will return the same signal $y[n]=x[n]*h[n]$ when you compute the IFFT, but this is not what happens, since $N < L + M - 1$, the signal is acutally an aliased. Instead, some signal $y_p$ is returned.

This signal obeys the following formula:

$$y_p[n]=\sum_{l=-\infty}^{\infty}y[n-lN]\{u[n]-u[n-N]\}$$

Or, alternatively $y_p$ is the result of circular convolution, not linear convolution, between $x$ and $h$.