Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation

Note 20. Fast Convolution Using the FFT

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

20.1

where x[k] is the input sequence. In order to produce a block of N_B output samples, y[0] through y[N_B – 1], Eq. (20.1) must process a block of N_B + N_R – 1 input samples from x[–N_R + 1] through x[N_B – 1]. Assuming that x[k] is valid only for k ≥ 0, the first N_R – 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 N_B output samples, y[N_B] through ...