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