Hi. I'm using fftw in my code for my signal analysis. In fftw (1D), one of the parameters is 'n'. And the document says, "size n can be any positive integer, but sizes that are products of small factors are transformed most efficiently (although prime sizes still use an O(n log n) algorithm)" What would be the ideal n value? And does "product of small factors" mean multiples of the 'N' where is N is the sample size of x[N]? E.g. if my sample size is 30, so I supposed minimum value for n in fftw should be 30? or 60 or 90 etc. and not, say, 37, or 42, etc? And to get decent results, what are the values most people would use? is it 2xN? Many Thanks!

# fft 'n' size

Started by ●May 26, 2011

Reply by ●May 26, 20112011-05-26

On May 26, 11:40�am, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote:> Hi. > > I'm using fftw in my code for my signal analysis. > In fftw (1D), one of the parameters is 'n'. And the document says, > "size n can be any positive integer, but sizes that are products of small > factors are transformed most efficiently (although prime sizes still use an > O(n log n) algorithm)" > > What would be the ideal n value? And does "product of small factors" mean > multiples of the 'N' where is N is the sample size of x[N]? E.g. if my > sample size is 30, so I supposed minimum value for n in fftw should be 30? > or 60 or 90 etc. and not, say, 37, or 42, etc? And to get decent results, > what are the values most people would use? is it 2xN?Use the number of data points for n, unless you have very specific reasons to choose to do otherwise. Rune

Reply by ●May 26, 20112011-05-26

>On May 26, 11:40=A0am, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote: >> Hi. >> >> I'm using fftw in my code for my signal analysis. >> In fftw (1D), one of the parameters is 'n'. And the document says, >> "size n can be any positive integer, but sizes that are products ofsmall>> factors are transformed most efficiently (although prime sizes still use=>an >> O(n log n) algorithm)" >> >> What would be the ideal n value? And does "product of small factors"mean>> multiples of the 'N' where is N is the sample size of x[N]? E.g. if my >> sample size is 30, so I supposed minimum value for n in fftw should be30=>? >> or 60 or 90 etc. and not, say, 37, or 42, etc? And to get decentresults,>> what are the values most people would use? is it 2xN? > >Use the number of data points for n, unless you have very >specific reasons to choose to do otherwise. > >Rune >Am I right to understand that if we use value greater than the number of data points for n, fftw will fill the rest of the insufficient values with zeros and thus improving the impulse of the response. i.e. we can see a sharper and higher amplitude at the responding frequency. Would this help in doing frequency analysis where we need to pick up a targeted frequency among the noise? Thanks again.

Reply by ●May 26, 20112011-05-26

On May 26, 12:20�pm, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote:> >On May 26, 11:40=A0am, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote: > >> Hi. > > >> I'm using fftw in my code for my signal analysis. > >> In fftw (1D), one of the parameters is 'n'. And the document says, > >> "size n can be any positive integer, but sizes that are products of > small > >> factors are transformed most efficiently (although prime sizes still use > = > >an > >> O(n log n) algorithm)" > > >> What would be the ideal n value? And does "product of small factors" > mean > >> multiples of the 'N' where is N is the sample size of x[N]? E.g. if my > >> sample size is 30, so I supposed minimum value for n in fftw should be > 30= > >? > >> or 60 or 90 etc. and not, say, 37, or 42, etc? And to get decent > results, > >> what are the values most people would use? is it 2xN? > > >Use the number of data points for n, unless you have very > >specific reasons to choose to do otherwise. > > >Rune > > Am I right to understand that if we use value greater than the number of > data points for n, fftw will fill the rest of the insufficient values with > zerosMaybe, read the docs of whatever function you use. I'd be surprised if that's the case, though, since FFTW is a C library and C does not wrap size information with arrays.> and thus improving the impulse of the response. i.e. we can see a > sharper and higher amplitude at the responding frequency.No.> Would this help > in doing frequency analysis where we need to pick up a targeted frequency > among the noise?No. Rune

Reply by ●May 26, 20112011-05-26

On May 26, 6:20�am, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote:> >On May 26, 11:40=A0am, "Marc2050" <maarcc@n_o_s_p_a_m.gmail.com> wrote: > >> Hi. > > >> I'm using fftw in my code for my signal analysis. > >> In fftw (1D), one of the parameters is 'n'. And the document says, > >> "size n can be any positive integer, but sizes that are products of > small > >> factors are transformed most efficiently (although prime sizes still use > = > >an > >> O(n log n) algorithm)" > > >> What would be the ideal n value? And does "product of small factors" > mean > >> multiples of the 'N' where is N is the sample size of x[N]? E.g. if my > >> sample size is 30, so I supposed minimum value for n in fftw should be > 30= > >? > >> or 60 or 90 etc. and not, say, 37, or 42, etc? And to get decent > results, > >> what are the values most people would use? is it 2xN? > > >Use the number of data points for n, unless you have very > >specific reasons to choose to do otherwise. > > >Rune > > Am I right to understand that if we use value greater than the number of > data points for n, fftw will fill the rest of the insufficient values with > zeros and thus improving the impulse of the response. i.e. we can see a > sharper and higher amplitude at the responding frequency.yes, the zero padded FFT will yield finer bin resolution results (because it performs many more DFT's at finer frequencies) enabling you to more quickly pick out the responding frequency, Would this help> in doing frequency analysis where we need to pick up a targeted frequency > among the noise?No, zero padding doesn't help the resolving capability or noise reduction capabilities of the FFT. You need more points for that. Think of it this way, zero padding just provides a more detailed analysis of the original FFT result, it doesn't provide a more accurate result. http://flylib.com/books/2/729/1/html/2/images/0131089897/graphics/03fig18.gif> > Thanks again.- Hide quoted text - > > - Show quoted text -

Reply by ●May 26, 20112011-05-26

>Am I right to understand that if we use value greater than the number of >data points for n, fftw will fill the rest of the insufficient valueswith>zeros and thus improving the impulse of the response.Only if you place zeros in the additional locations. Otherwise, FFTW will simply pick up whatever data is in subsequent memory locations, which could create problems if your array does not have memory allocated to it. At least, that' what I remember about FFTW, i.e., there's no way to tell it to do a larger FFT than points you are providing. If you have 30 points and you want a 256-point FFT, then malloc 256 input locations and fill the remaining 226 with zeros, then run FFTW with a 256-point plan. Note that if you are doing an in-place FFT, your zeros will get wiped out and must be re-filled with each iteration. Steve Johnson posts in these threads occasionally and may have more information. Barring that, I'd do as suggested above, RTFM - freely available at FFTW's website. Mark