Translator Disclaimer
7 September 2010 A fast partial Fourier transform (FPFT) for data compression and filtering
Author Affiliations +
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)log2N multiplications independent of M, and the new FPFT algorithm requires on the order of (N/2)log2M + 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.
© (2010) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Mark W. Smith "A fast partial Fourier transform (FPFT) for data compression and filtering", Proc. SPIE 7799, Mathematics of Data/Image Coding, Compression, and Encryption with Applications XII, 77990F (7 September 2010);

Back to Top