A fast partial Fourier transform (FPFT) for data compression and filtering
A discrete Fourier transform (DFT) or the closely related discrete cosine transform (DCT) is often employed as part of a
data compression scheme. This paper presents a fast partial Fourier transform (FPFT) algorithm that is useful for
calculating a subset of M Fourier transform coefficients for a data set comprised of N points (M < N). This algorithm
reduces to the standard DFT when M = 1 and it reduces to the radix-2, decimation-in-time FFT when M = N and N is a
power of 2. The DFT requires on the order of MN complex floating point multiplications to calculate M coefficients for
N data points, a complete FFT requires on the order of (N/2)log 2 N multiplications independent of M, and the new FPFT
algorithm requires on the order of (N/2)log 2 M + N multiplications. The FPFT algorithm introduced in this paper could
be readily adapted to parallel processing. In addition to data compression, the FPFT algorithm described in this paper
might be useful for very narrow band filter operations that pass only a small number of non-zero frequency coefficients
such that M << N.