FFT Length in Digital Filtering

When the FFT is employed for nonrecursive digital filtering, the time required to process one block of input data, N samples long, is often approximately of the form N(log, (N) + Q), where Q ≥0. Earlier results on determining optimum N have assumed Q = 0, because it has log been infomaly observed that typically little is to be gained by taking the value ofQ> 0into account, and because the assumption that Q = 0 permits determination of N without reference to machine dependent parameters. The present results generally support the long standing-observation and specific numerical bounds are determined for the factors of improvement possible if the value of Q> 0 taken into account. It is also argued that in some applications itmight be worthwhile to do that. A theory, applicable for general r and Q, is presented fordetermining N to minimize computation time, and calculating the resulting computation time. That theory is applied to determining for whatfilter lengths the FFT method of nonrecursive digital filtering is faster than the direct method; it is shown that even ordinary values of Q > 0 can play a strong role in determining the critical value of the filter length.