Note 20. Fast Convolution Using the FFT

Consider an FIR filter having a unit-sample response, h[n], that extends for NR samples. Such a filter’s output, y[k], at time k is given by the discrete convolution



where x[k] is the input sequence. In order to produce a block of NB output samples, y[0] through y[NB – 1], Eq. (20.1) must process a block of NB + NR – 1 input samples from x[–NR + 1] through x[NB – 1]. Assuming that x[k] is valid only for k ≥ 0, the first NR – 1 samples of the output will not be valid because computation of these values depends on samples of x[k] before k = 0. To produce a second block of NB output samples, y[NB] through ...

Get Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.