Dear All, I want to do zero padding of of the data and than do fft by FFTW(www.fftw.org). The dummiest way is to make an array which has more elements than the data set size. However, it takes more memory space and more computation time. I'm wondering if there is a way to tell FFTW do zero padding automatical and compute the fft. Best wishes, Peng

# Zero padding in FFTW

Started by ●March 4, 2005

Reply by ●March 5, 20052005-03-05

Reply by ●March 5, 20052005-03-05

Complex data. Say I have n complex numbers, I want to pad it with at least 10n complex numbers (this is for 1D array). For 2D array, that's 100n^2 padding for n^2 complex numbers. Thanks, Peng On 5 Mar 2005 07:51:11 -0800, dbell@niitek.com wrote:>Real data or complex data? >How many points of data, how many points of zeropadding? > >Dirk

Reply by ●March 5, 20052005-03-05

Peng Yu wrote:> I want to do zero padding of of the data and than do fft by > FFTW(www.fftw.org). > > The dummiest way is to make an array which has more elements than the > data set size. However, it takes more memory space and more > computation time. I'm wondering if there is a way to tell FFTW dozero> padding automatical and compute the fft.FFTW only computes the ordinary DFT; for anything beyond that you are on your own (although you can use FFTW as a part of your algorithm, of course). There are a couple of approaches to what you seem to want, if I understand you correctly. First, if you want *all* of the DFT outputs from zero-padded inputs, then you can't really save any memory--you still need storage for the outputs, after all. However, you can save some (but not too much) time compared to a full FFT, using what is known as a "pruned" FFT. There is some description of this at fftw.org/pruned.html, including code snippets for the inverse case (computing a few *outputs* from *all* of the inputs); in your case you reverse the steps. Second, if the reason you are zero-padding is to get a smoother spectrum (i.e. to interpolate the spectrum to a higher resolution, although resolution of spectral features is not really improved), then you might look instead at the "chirp-z" algorithm instead; see: http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm Cordially, Steven G. Johnson

Reply by ●March 5, 20052005-03-05

Hi, I think what I need is to get a smoother spectrum and only compute the low frequency amplitude. Is there any implementation of the following alogrithm? Or can I use FFTW to achieve my goal? Thanks! Best wishes, Peng>Second, if the reason you are zero-padding is to get a smoother >spectrum (i.e. to interpolate the spectrum to a higher resolution, >although resolution of spectral features is not really improved), then >you might look instead at the "chirp-z" algorithm instead; see: >http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm

Reply by ●March 5, 20052005-03-05

Hi, I think what I need is to get a smoother spectrum and only compute the low frequency amplitude. Is there any implementation of the following alogrithm? Or can I use FFTW to achieve my goal? Thanks! Best wishes, Peng>Second, if the reason you are zero-padding is to get a smoother >spectrum (i.e. to interpolate the spectrum to a higher resolution, >although resolution of spectral features is not really improved), then >you might look instead at the "chirp-z" algorithm instead; see: >http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm