Re: FFT problems

[Bill Lash]

It looks as if FFTPACK, which is what Octave uses to do FFTs, uses a mixed
radix algorithm.  From the source distributed in octave it looks as if it
provides radix-2, radix-3, radix-4, and radix-5 FFTs (One of the references
on the Web that I saw suggests that FFTPACK also provides radix-6 and radix-7
FFTs, but I don't see a corresponding file in the source distribution). The
sequence length is factored and FFTs of the appropriate radix are stacked. Any 
factor other than these is handled by doing a DFT of that length.

So in your case of length 17, the 17 point DFT is calculated.  If sequence
were 18 points, it would be calculated as 2 radix-3 FFTs and a radix-2 FFT.


Hope this helps,

Bill




Roberto Hernandez wrote:
> 
> Here I am again with a question about FFT. I posted a couple of days ago and
> got a couple of answers but apparently my question wasn't clear. I suppose
> this example should make it so.
> 
> Say I run the following:
> 
> octave:1> a = 1:17;
> octave:2> fft(a)
> ans =
> 
>  Columns 1 through 3:
> 
>    153.0000 +   0.0000i    -8.5000 +  45.4710i    -8.5000 +  21.9410i
> 
>  Columns 4 through 6:
> 
>     -8.5000 +  13.7280i    -8.5000 +   9.3241i    -8.5000 +   6.4189i
> 
>  Columns 7 through 9:
> 
>     -8.5000 +   4.2325i    -8.5000 +   2.4185i    -8.5000 +   0.7876i
> 
>  Columns 10 through 12:
> 
>     -8.5000 -   0.7876i    -8.5000 -   2.4185i    -8.5000 -   4.2325i
> 
>  Columns 13 through 15:
> 
>     -8.5000 -   6.4189i    -8.5000 -   9.3241i    -8.5000 -  13.7280i
> 
>  Columns 16 and 17:
> 
>     -8.5000 -  21.9410i    -8.5000 -  45.4710i
> 
> The sequence a is non-radix 2. So what algorithm did the fft() function use?
> Is it the DFT: X(k) = sum(1, N) x(i) * exp(-j*(i-i)*(k - 1)*2*pi / N) ?
> Does anyone know?
> 
> Thanks,
> 
> - Roberto
> 
> -------------------------------------------------------------
> Octave is freely available under the terms of the GNU GPL.
> 
> Octave's home on the web:  http://www.octave.org
> How to fund new projects:  http://www.octave.org/funding.html
> Subscription information:  http://www.octave.org/archive.html
> -------------------------------------------------------------



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------