A fast partial Fourier transform (FPFT) for data compression and filtering

Mark W. Smith

doi:10.1117/12.858371

7 September 2010 A fast partial Fourier transform (FPFT) for data compression and filtering

Mark W. Smith

Proceedings Volume 7799, Mathematics of Data/Image Coding, Compression, and Encryption with Applications XII; 77990F (2010) https://doi.org/10.1117/12.858371
Event: SPIE Optical Engineering + Applications, 2010, San Diego, California, United States

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)log₂N multiplications independent of M, and the new FPFT algorithm requires on the order of (N/2)log₂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.

Citation Download Citation

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); https://doi.org/10.1117/12.858371

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
9 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Fourier transforms

Data compression

Parallel processing

Algorithm development

Linear filtering

Computer security

Computing systems

Show All Keywords

Keywords/Phrases

Search In:

Publication Years