Nonuniform fast Fourier transform
Autor: | Michel Schonewille, A. J. W. Duijndam |
---|---|
Rok vydání: | 1999 |
Předmět: |
Discrete-time Fourier transform
Non-uniform discrete Fourier transform Low-pass filter Fast Fourier transform Gauss Short-time Fourier transform Filter (signal processing) Fractional Fourier transform Window function Discrete Fourier transform symbols.namesake Geophysics Fourier transform Dimension (vector space) Fourier analysis Geochemistry and Petrology symbols Harmonic wavelet transform Algorithm Mathematics |
Zdroj: | GEOPHYSICS. 64:539-551 |
ISSN: | 1942-2156 0016-8033 |
Popis: | The nonuniform discrete Fourier transform (NDFT) can be computed with a fast algorithm, referred to as the nonuniform fast Fourier transform (NFFT). In L dimensions, the NFFT requires O(N(-lne)L+(∏𝓁=1LM𝓁)∑𝓁=1LlogM𝓁) operations, where M𝓁 is the number of Fourier components along dimension 𝓁, N is the number of irregularly spaced samples, and e is the required accuracy. This is a dramatic improvement over the O(N∏𝓁=1LM𝓁) operations required for the direct evaluation (NDFT). The performance of the NFFT depends on the lowpass filter used in the algorithm. A truncated Gauss pulse, proposed in the literature, is optimized. A newly proposed filter, a Gauss pulse tapered with a Hanning window, performs better than the truncated Gauss pulse and the B-spline, also proposed in the literature. For small filter length, a numerically optimized filter shows the best results. Numerical experiments for 1-D and 2-D implementations confirm the theoretically predicted accuracy and efficiency properties of the algorithm. |
Databáze: | OpenAIRE |
Externí odkaz: |