O'Reilly logo

Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation by C. Britton Rorabaugh

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

20.1

image

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required