Share Email Print
cover

Proceedings Paper

A fast partial Fourier transform (FPFT) for data compression and filtering
Author(s): Mark W. Smith
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 8 September 2010
PDF: 9 pages
Proc. SPIE 7799, Mathematics of Data/Image Coding, Compression, and Encryption with Applications XII, 77990F (8 September 2010); doi: 10.1117/12.858371
Show Author Affiliations
Mark W. Smith, Sandia National Labs. (United States)


Published in SPIE Proceedings Vol. 7799:
Mathematics of Data/Image Coding, Compression, and Encryption with Applications XII
Mark S. Schmalz; Gerhard X. Ritter; Junior Barrera; Jaakko T. Astola, Editor(s)

© SPIE. Terms of Use
Back to Top