DFT - Discrete Fourier Transform for Filtering and Frequency Analysis

Resources - 7.3.1, 7.3.2, 7.4

Linear filtering using DFT

Convolutions can be computationally demanding

• Increases every $2^N$ value Therefore it can we easier to solve the system $y[n]=h[n]\ast x[n]$ as

$$y[n]={\mathcal{F}}^{-1}(H(\omega )X(\omega ))$$

Filtering of long sequences

If the sequence is extremely long, it has implications regarding memory and processing delay. Aka we need to wait for the sampling to be completed.

How can we solve this? → The additive property of the convolution. $y[n]=h[n]\ast (x_1[n]+x_2[n]+\cdots +x_{L-1}[n])$ We divide $x[n]$ into $L-1$ chunks, and process each chunk individually before we add everything together. If $h[n]$ has a length of $M$, the resulting signal $y[n]$ becomes

Step by step:

1. Divide input sequence, $x[n]$, into non-overlapping blocks $x_m[n]$ each of length $L$
2. Pad $h$ with zeroes such that $N\ge M+L-1$
3. Filter each input block $x_m[n]$ to produce output block $y_m[n]$
4. Combine outputs: $y[n]={\sum }_m{y}_m[n]$

Frequency analysis