Logarithmic pruning of FFT frequencies

摘要

A standard fast Fourier transform (FFT) computes the transform at evenly spaced points on a linear scale. A simple modification of the FFT algorithm that results in an efficient method for calculating the transform only at evenly spaced frequencies on a logarithmic scale is proposed. The saving in the number of operations, compared with a standard FFT, is approximately 60% for typical values.