fft 'n' size

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!

On May 26, 11:40&#4294967295;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

>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. Would this help
in doing frequency analysis where we need to pick up a targeted frequency
among the noise?

Thanks again.

On May 26, 12:20&#4294967295;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
> zeros

Maybe, 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

On May 26, 6:20&#4294967295;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 -

>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.

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